• 📢博客主页：https://blog.csdn.net/dxt19980308

  

  创新互联公司-专业网站定制、快速模板网站建设、高性价比唐山网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式唐山网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖唐山地区。费用合理售后完善，10年实体公司更值得信赖。

• 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！

• 📢本文由肩匣与橘编写，首发于🙉

• 📢生活依旧是美好而又温柔的，你也是✨

---

目录

🔴线性表

1.1 顺序表

1.1.1 顺序表定义

1.1.2 顺序表基本操作

1.2 单链表

1.2.1 单链表节点定义

1.2.2 单链表基本操作

1.3 双链表

1.3.1 双链表节点定义

1.3.2 双链表基本操作

1.4 静态链表

🟠栈和队列

2.1 栈

2.1.1 顺序栈

2.1.2 链式栈

2.2 队列

2.2.1 顺序队列

2.2.2 链式队列

2.3 应用

🟡串

3.1 串的定义与实现

3.2 串的模式匹配

🟢树与二叉树

4.1 二叉树

4.1.1二叉树的概念

4.1.2二叉树的操作 

4.2 线索二叉树 

4.2.1 线索二叉树的概念 

4.2.2线索二叉树的操作

4.3 树和森林

4.3.1 树的存储结构

4.4 树的应用

4.4.1 并查集

4.4.2 二叉查找树

🔵图

5.1 图的存储结构

5.1.1 邻接矩阵法

5.1.2 邻接表法

5.1.3 十字链表法

5.1.4 临界多重表法

5.2 图的遍历

5.2.1 广度优先遍历BFS

5.2.2 深度优先遍历DFS

5.3 图的应用

5.3.1最小生成树

5.3.2 拓扑排序

🟣查找

6.1 顺序查找和折半查找

6.1.1 顺序查找

6.1.2 折半查找 

🟤排序

7.1 插入排序

7.1.1 直接插入排序

7.1.2 折半插入排序

7.1.3 希尔排序 

7.2 交换排序

7.2.1 冒泡排序

7.2.2 快速排序

7.3 选择排序

7.3.1 简单选择排序

7.3.2 堆排序

7.4 归并排序

---

🔴线性表 1.1 顺序表 1.1.1 顺序表定义

静态定义

#define Maxsize 50 
typedef struct{
    ElemType data[MaxSize]; 
    int length;
}SqList;

动态定义

#define InitSize 100 
typedef struct {
ElemType *data; //指示动态分配数组的指针
int MaxSize, length; //数组的大容量和当前个数
} SeqList;

1.1.2 顺序表基本操作

插入

bool ListInsert(SqList &L,int i,ElemType e){
//本算法实现将元素e插入到顺序表L中第i个位置
if(i<1||i>L.length+1) //判断i的范围是否有效
    return false;
if(L.length>=MaxSize) //当前存储空间已满，不能插入
    return false;
for(int j=L.length;j>=i;j--)//将第i个元素及之后的元素后移
L.data[j]=L.data[j-1];
L.data[i-1]=e; //在位置i处放入e 
L.length++; //线性表长度加1 
return true;
}

删除

bool ListDelete(SqList &L,int i,ElemType &e){
//本算法实现删除顺序表L中第i个位置的元素
    if(i<1||i>L.length) //判断i的范围是否有效
        return false;
    e=L.data[i-1]; //将被删除的元素赋值给e
    for(int j=i;j< L.length;j++)//将第i个位置之后的元素前移
        L.data[j-1]=L.data[j];
    L.length--; //线性表长度减1 
    return true;
}

按值查找

int LocateElem(SqList L,ElemType e){
//实现查找顺序表中值为e的元素
    int i;
    for(i=0;i< L.length;i++) 
        if(L.data[i]==e)
            return i+1; //返回其位序i+1
    return 0; //退出循环，说明查找失败
}

1.2 单链表 1.2.1 单链表节点定义

typedef struct LNode{ //定义单链表结点类型
    ElemType data; //数据域
    struct LNode *next; //指针域
}LNode,*LinkList;

1.2.2 单链表基本操作

头插法

LinkList CreateList1(LinkList &L){
//从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素
    LNode *s;int x;
    L=(LinkList)malloc(sizeof(LNode)); //创建头结点
    L->next=NULL; //初始化为空链表
    while(scanf(" d",&x) != EOF){ //循环输入
        s=(LNode*)malloc(sizeof(LNode));//创建新结点
        s->data=x;
        s->next=L->next;
        L->next=s; //将新结点插入表中，L为头指针
        scanf(" d",&x);
    }//while结束
    return L;
}

尾插法

LinkList CreatList2(LinkList &L) {
//从表头到表尾正向建立单链表L，每次均在表尾插入元素
    int x; //设元素类型为整型
    L = (LinkList)malloc(sizeof(LNode)); 
    LNode *s, *r = L; //r为表尾指针
    while(scanf(" d",&x) != EOF) { //循环输入
        s = (LNode*)malloc(sizeof(LNode)); 
        s->data = x;
        r->next = s;
        r = s; //r指向新的表尾结点
        scanf(" d",&x);
    }
    r->next = NULL; //尾结点指针置空
    return L  
}

按序号索值

LNode *GetElem(LinkList L,int i){
//本算法取出单链表L(带头结点)中第i个位置的结点指针
    int j=1; //计数，初始化为1
    LNode *p=L->next; //头结点指针赋给P 
    if(i==0)
        return L; //若i等于0.则返回头结点
    if(i<1)
        return NULL; //若i无效，则返回NULL 
    while(p&&jnext; 
        j++;
    }
    return p; //返回第i个结点的指针，如果i大于表长，p= NULL,直接返回p即可
}

按值查找结点

LNode *LocateElem(LinkList L,ElemType e){
//本算法查找单链表L(带头结点)中数据域值等于e的结点指针，否 则返回NULL
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e)//从第1个结点开始查找data域为e的结点
        p=p->next;
    return p; //找到后返回该结点指针，否则返回NULL
}

插入节点操作 (两种)

前插

p=GetElem(L,i-1); //查找插入位置的前驱结点
s->next=p->next; 
p->next=s;

后插

//将*s结点插入到*p之前的主要代码片段
s->next=p->next; //修改指针域，不能颠倒
p->next=s;
temp=p->data; //交换数据域部分
p->data=s->data; 
s->data=temp;

删除节点操作

//删除所给节点后一节点
p=GetElem(L,i-1); //查找删除位置的前驱结点
q=p->next; //令q指向被删除结点
p->next=q->next; //将*q结点从链中“断开”
free(q); //释放结点的存储空间
//删除所给节点
q=p->next; //令q指向*p的后继结点
p->data=p->next->data; //和后继结点交换数据域
p->next=q->next; //将*q结点从链中“断开” 
free(q); //释放后继结点的存储空间

1.3 双链表 1.3.1 双链表节点定义

typedef struct DNode{ //定义双链表结点类型
    ElemType data; //数据域
    struct DNode *prior,*next; //前驱和后继指针
}DNode,*DLinkList;

1.3.2 双链表基本操作

插入

s->next=p->next; //将结点*s插入到结点*p之后
p->next->prior=s;
s->prior=p; p->next=s;

删除

p->next=q->next; 
q->next->prior=p; 
free(q);

1.4 静态链表

#define MaxSize 50 //静态链表的大长度
typedef struct{ //静态链表结构类型的定义
    ElemType data; //存储数据元素
    int next; //下一个元素的数组下标
}SLinkList[MaxSize];

🟠栈和队列 2.1 栈 2.1.1 顺序栈

顺序栈的存储类型定义:

#define MaxSize 50 //定义栈中元素的大个数
typedef struct{
    ElemType data[MaxSize]; //存放栈中元素
    int top; //栈顶指针
}SqStack;

顺序栈的基本运算

(1)初始化
void InitStack(&S){
    //初始化栈
    s.top=-1; //初始化栈顶指针
}
(2)判断空
bool StackEmpty(S){
    //判断栈是否为空
    if (S.top == -1) //栈空
        return true;
    else //不空
        return false;
}
(3)进栈
bool Push(SqStack &S, ElemType x) {
    //进栈操作
    if (S.top == MaxSize - 1) //栈满，报错
        return false;
    S.data[++S.top] = x; //指针先加1，再入栈
    return true;
}

bool Pop(SqStack &S, ElemType &x) {
    //出栈操作
    if (S.top == -1) //栈空，报错
        return false;
    x = S.data[S.top--]; //先出栈，指针再减1
    return true;
}

bool GetTop(SqStack S, ElemType &x) {
    //获取栈顶元素
    if (S.top == -1) //栈空，报错
        return false;
    x = S.data[S.top]; //x记录栈顶元素
    return true;
}

2.1.2 链式栈

链式栈的存储定义：

typedef struct Linknode{
ElemType data; //数据域
struct Linknode *next; //指针域
}*LiStack;

2.2 队列 2.2.1 顺序队列

顺序队列的定义

#define MaxSize 50 //定义队列中元素的大个数
typedef struct {
        ElemType data[MaxSize]; //存放队列元素
        int front, rear; //队头指针和队尾指针
} SqQueue;

循环队列的操作

(1)初始化
void InitQueue(SqQueue &Q) {
    //初始化循环队列
    Q.rear = Q.front = 0; //初始化队首、队尾指针
}
(2)判空
bool isEmpty(SqQueue Q) {
    //判断循环队列是否为空
    if(Q.rear==Q.front) return true; //队空条件
    else return false;
}
(3)入队
bool EnQueue(SqQueue &Q, ElemType x) {
    //循环队列的入队操作
    if ((Q.rear + 1)%MaxSize == Q.front) return false;
    //队满报错
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1)	MaxSize; //队尾指针加1取模
    return true;
}
(4)出队
bool DeQueue(SqQueue &Q, ElemType &x) {
    //循环队列的出队操作
    if (Q.rear == Q.front) return false; //队空报错
    x = Q.data[Q.front];
    Q.front = (Q.front + 1)	MaxSize; //队头指针加1取模
    return true;
}

2.2.2 链式队列

链式队列的存储

typedef struct{ //链式队列结点
    ElemType data;
    struct LinkNode *next;
    }LinkNode;
typedef struct { //链式队列
    LinkNode *front, *rear; //队列的对头和队尾指针
} LinkQueue;

链式队列的基本操作

(1)初始化
void InitQueue(LinkQueue &Q) {
    //初始化链式队列
    Q.front = Q.rear = (LinkNode *)malloc(sizeof( LinkNode));//建立头结点
    Q.front->next = NULL; //初始为空
}
(2)判断空
bool IsEmpty(LinkQueue Q) { 
    if(Q.front==Q.rear) 
        return true; 
    else 
        return false;
}
(3)入队
void EnQueue(LinkQueue &Q, ElemType x) {
//链式队列入队操作
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = x; s->next = NULL; //创建新结点，插入到链尾
    Q.rear->next = s;
    Q.rear = s;
}
(4)出队
bool DeQueue(LinkQueue &Q, ElemType &x) {
    //链式队列出队操作
    if (Q.front == Q.rear)
        return false;//空队
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next; 
    if (Q.rear == p)
        Q.rear = Q.front; //若原队列中只有一个结点，删除后变空
    free(p); 
    return true;
}

2.3 应用

栈在递归中的作用 (斐波那契)

int Fib(n){//斐波那契数列实现
    if(n==0)
        return 0;//边界条件
    else if(n==1)
        return 1;//边界条件
    else
        return Fib(n-1)+Fib(n-2);//递归表达式
}

🟡串 3.1 串的定义与实现

定长顺序存储表示

#define MAXLEN 255 typedef struct{
    char ch[MAXLEN];//每个分量分配一个字符
    int length;//串的实际长度
}SString;

堆分配存储表示

typedef struct{
    char *ch//按串长度分配存储区 ch指向串的基地址
    int length;//串的长度
}HString;

3.2 串的模式匹配

简单的模式匹配

int Index(SString S,SString T){ 
int i=1;j=1; while(i<=S[0]&&j<=T[0]){
    if	(S[i]==T[j]){
	    ++i;++j; //继续比较后继字符
    }	
    else{
   	    i=i-j+2;j=1; //指针后退重新开始匹配
    }
    }if(j>T[0])
        return i-T[0]; 
    else
        return 0;
}

KMP

void get_next(char T[],int next[]){ 
    i=1;
    next[1]=0; j=0;
    while(i<=T[0]){ //T[0]用于保存字符串的长度
        if(j==0||T[i]==T[j]){
            ++i;++j;next[i]=j;
        }
        else
            j=next[j];
     }
}
int KMP(char S[],char T[],int next[],int pos){ 
    i=pos;
    j=1;
    while(i<=S[0]&&j<=T[0]){ if(j==0||S[i]==T[j]){
        ++i;
        ++j;
    }
    else
        j=next[j];
    } if(j>T[0])
        return i-T[0]; else
    return 0;
}

🟢树与二叉树 4.1 二叉树 4.1.1二叉树的概念

typedef struct BiTNode { //链式二叉树定义
ElemType data; //数据域
struct BiTNode *lchild, *rchild; //左、右孩子指针
} BiTNode, *BiTree;

4.1.2二叉树的操作 

二叉树的遍历 (递归) 

1.先序遍历
void PreOrder(BiTree T) { 
    if (T != NULL) {
        visit(T); //访问根结点
        PreOrder(T->lchild); //递归遍历左子树PreOrder(T->rchild); //递归遍历右子树
    }
}
2.中序遍历
void InOrder(BiTree T) { 
    if (T != NULL) {
        InOrder(T->lchild); //递归遍历左子树
        visit(T); //访问根结点
        InOrder(T->rchild); //递归遍历右子树
    }
}
3.后序遍历
void PostOrder(BiTree T) { 
    if (T != NULL) {
        PostOrder(T->lchild); //递归遍历左子树
        PostOrder(T->rchild); //递归遍历右子树visit(T); //访问根结点
    }
}

二叉树的遍历 (非递归)

void InOrder2(BiTree T) {
    //二叉树中序遍历的非递归算法，需要借助一个栈
    InitStack(S); BiTree p = T; //初始化栈；p是遍历指针
        while (p||!IsEmpty(S)) { //栈不空或p不空时循环
            if (p) { //一路向西~不对一路向左(
                Push(S,p); //当前节点入栈
                p = p->lchild;//左子树不空便继续往左走
            }
            else { //退栈，访问根结点，遍历右子树
                Pop(S,p); visit(p); //退栈，访问根结点
                p = p->rchild; //再向右子树走
            }
        }
}

二叉树的层次遍历

void LevelOrder(BiTree T) {
    //层次遍历
    InitQueue(Q); //初始化辅助队列
    BiTree p;
    EnQueue(Q,T); //将根结点入队
    while (!IsEmpty(Q)) { //队列不空循环
    DeQueue(Q,p); //队头元素出队
    visit(p); //访问当前p所指向结点
    if (p->lchild!=NULL)
        EnQueue(Q,p->lchild);//左子树不空，则入队列
    if (p->rchild!=NULL)
        EnQueue(Q,p->rchild);//右子树不空，则入队列
    }
}

4.2 线索二叉树  4.2.1 线索二叉树的概念 

线索二叉树节点定义

typedef struct ThreadNode {
    // 线 索 二 叉 树 定 义 ElemType data; //数据元素
    struct ThreadNode *lchild, *rchild; //左、右孩子指针
    int ltag, rtag; //左、右线索标志
} ThreadNode, *ThreadTree;

4.2.2线索二叉树的操作

线索二叉树的构造

void InTread(ThreadTree &p,ThreadTree &pre) {
    //中序遍历对二叉树线索化的递归算法
    if (p!=NULL) {
        InTread(p->lchild, pre); //递归，线索化左子树
    if (p->lchild == NULL) { //左子树为空建立前驱线索
        p->lchild = pre;
        p->ltag = 1;
    }
    if (pre!=NULL && pre->rchild == NULL) {
        pre->rchild = p; //建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = p; //标记当前结点成为刚刚访问过的结点
    InTread(p->rchild, pre); //递归，线索化右子树
    }//if{p!=NULL}
}

通过中序遍历建立中序线索二叉树线的主过程算法
void CreateInThread(ThreadTree T) {
    //中序遍历建立中序线索二叉树
    ThreadTree pre = NULL;
    if (T!=NULL) { //非空二叉树，线索化
        InTread(T, pre); //线索化二叉树
        pre->rchild = NULL; //处理遍历的最后一个结点
        pre->rtag = 1;
    }
}

线索二叉树的遍历 

(1)求中序线索二叉树中序序列下的第一个结点
ThreadNode *Firstnode(ThreadTree p) {
    //求中序线索二叉树中序序列下的第一个结点
    while (p->ltag == 0)
        p = p->lchild; //最左下结点(不一定是叶结点)
    return p;
}
(2)求中序线索二叉树中结点p在中序序列下的后继结点
ThreadNode *Nextnode(ThreadNode *p) {
    //求中序线索二叉树中结点p在中序序列下的后继结点
    if (p->rtag == 0)
        return Firstnode(p->rchild); 
    else
        return p->rchild; //rtag==1直接返回后继线索
}
(1-1)求中序线索二叉树中序序列下的最后一个结点
ThreadNode *Lastnode(ThreadTree p) {
    //求中序线索二叉树中序序列下的最后一个结点
    while (p->rtag == 0) 
        p = p->rchild;
    return p;
}
(2-1)求中序线索二叉树中结点p在中序序列下的前驱结点
ThreadNode *Prenode(ThreadNode *p) {
    //求中序线索二叉树中结点p在中序序列下的前驱结点
    if (p->ltag == 0)
        return Lastnode(p->lchild); 
    else
        return p->lchild;
}
(3)不带头结点的中序线索二叉树的中序遍历
void InOrder(ThreadTree T) {
    //不带头结点的中序线索二叉树的中序遍历
    for (ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p))
    visit(p);
}

4.3 树和森林 4.3.1 树的存储结构

双亲表示法 

#define MAX_TREE_SIZE 100 //树中最多结点数、
typedef struct { //树的结点定义
    ElemType data; //数据元素
    int parent; //双亲位置域
} PTNode;
typedef struct{ //树的类型定义
    PTNode nodes[MAX_TREE_SIZE];//双亲表示
    int n; //结点数
}PTree;

孩子兄弟表示法

typedef struct CSNode{
    ElemType data; //数据域
    struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针
}CSNode,*CSTree;

4.4 树的应用 4.4.1 并查集

并查集结构定义

#define SIZE 100
int UFSets[SIZE]； //集合元素数组(双亲指针数组)

并查集初始化

void Initial(int S[]) {
    for (int i = 0; i< MaxSize; i++) //每个自成单元素集合
        S[i] = -1;
}

Find 操作

int Find(int S[], int x) {
    while (S[x] >= 0) //循环寻找x的根
        x = S[x];
    return x; //根的S[]小于0
}

Union 操作

void Union(int S[], int Root1, int Root2) {
    //Root1与Root2不同并且表示子集合的名字
    S[Root2] = Root1; //将根Root2连接到另一根Root1下面
}

4.4.2 二叉查找树

二叉查找树非递归查找 

BSTNode *BST_Search(BiTree T, ElemType key, BiTNode *&p) {
    //查找函数返回指向关键字值为key的结点指针，若不存在，返回NULL
    p = NULL;//p指向被查找结点的双亲结点，用于插入删除操作
    while (T != NULL && key != T->data) { p = T;
        if (key< T->data) 
            T = T->lchild;
        else
            T = T->rchild;
    }
    return T;
}

二叉查找树插入

int BST_Insert(BiTree &T, KeyType k) {
    //在二叉排序树T中插入一个关键字为k的结点
    if (T == NULL) { //原树为空，新插入的记录为根结点
        T = (BiTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL; 
        return 1; //返回1，表示成功
    }
    else if (k == T->key) //树中存在相同关键字的结点
        return 0;
    else if (k< T->key) //插入到T的左子树中
        return BST_Insert(T->lchild, k); else //插入到T的右子树中
    return BST_Insert(T->rchild, k);
}

二叉排序树构造

void Creat_BST(BiTree &T, KeyType str[], int n) {
    //用关键字数组str[]建立一个二叉排序树 
    T = NULL; //初始时bt为空树
    int i = 0;
    while (i< n){ //依次将每个元素插入
        BST_Insert(T, str[i]);
        i++;
    }
}

🔵图 5.1 图的存储结构 5.1.1 邻接矩阵法

#define MaxVertexNum 100 //顶点数目的大值
    typedef char VertexType; //顶点的数据类型
    typedef int EdgeType; //带权图中边上权值的数据类型
    typedef struct {
        VertexType Vex[MaxVertexNum]; //顶点表
        EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表
        int vexnum, arcnum; //图的当前顶点数和弧数
} MGraph;

5.1.2 邻接表法

#define MaxVertexNum 100 //图中顶点数目的大值
    typedef struct ArcNode { //边表结点
        int adjvex; //该弧所指向的顶点的位置
        struct ArcNode *next; //指向下一条弧的指针
        //InfoType info; //网的边权值
    } ArcNode;
typedef struct VNode { //顶点表结点
    VertexType data; //顶点信息
    ArcNode *first; //指向第一条依附该结点的弧的指针
    } VNode, AdjList[MaxVertexNum];
typedef struct { //图的邻接表存储结构定义
    AdjList vertices; //邻接表
    int vexnum, arcnum; //图的顶点数和弧数
} ALGraph;

5.1.3 十字链表法

#define MaxVertexNum 100 //图中顶点数目的大值
typedef struct ArcNode{ //边表结点
    int tailvex, headvex; //该弧的头尾结点
    struct ArcNode2 *hlink, *tlink; //分别指向弧头相同和弧尾相同的结点
    //InfoType info; //相关信息指针
} ArcNode;
typedef struct VNode{ //顶点表结点
    VertexType data; //顶点信息
    ArcNode *firstin, *firstout; //指向第一条入弧和出弧
} VNode; typedef struct {
    VNode xlist[MaxVertexNum]; //邻接表
    int vexnum, arcnum; //图的顶点数和弧数
} GLGraph;

5.1.4 临界多重表法

#define MaxVertexNum 100 //图中顶点数目的大值
typedef struct ArcNode { //边表结点
    bool mark; //访问标记
    int ivex, jvex; //分别指向该弧的两个结点
    struct ArcNode3 *ilink, *jlink; //分别指向两个顶点的下一条边
    //InfoType info; //相关信息指针
} ArcNode;
typedef struct VNode { //顶点表结点
    VertexType data; //顶点信息
    ArcNode *firstedge; //指向第一条依附该顶点的边
}VNode;
typedef struct {
    VNode adjmulist[MaxVertexNum]; //邻接表
    int vexnum, arcnum; //图的顶点数和弧数
} AMLGraph;

5.2 图的遍历 5.2.1 广度优先遍历BFS

bool visited[MAX_VERTEX_NUM]; //访问标记数组
void BFSTraverse(Graph G){
//对图G进行广度优先遍历，设访问函数为visit()
    for(i=0;i=0;w=NextNeighbor(G,v,w))
        { //检测v所有邻接点
            if(!visited[w]){ //w为v的尚未访问的邻接顶点
                visit(w); //访问顶点w
                visited[w]=true; //对w做已访问标记
                EnQueue(Q,w); //顶点w入队列
            }//if
        }
    }//while
}

BFS 算法求解单源最短路径问题

void BFS_MIN_Distance(Graph G,int u){
//d[i]表示从u到i结点的最短路径
    for (int i = 0; i< G.vexnum; ++i) 
        d[i]=∞； //初始化路径长度
    visited[u]=true;d[u]=0; 
    EnQueue(Q,u);
    while(!IsEmpty(Q)){ //BFS算法主过程
        DeQueue(Q,u); //队头元素u出队
        for (w=FirstNeighbor(G,u); w>=0;w=NextNeighbor(G,u,w))
        {
            if(!visited[w]){ //w为u的尚未访问的邻接顶点
                visited[w]=true; //设已访问标记
                d[w]=d[u]+1; // 路 径 长 度 加 1 
                EnQueue(Q,w); //顶点w入队
            }//if
        }
    }//while
}

5.2.2 深度优先遍历DFS

bool visited[MAX_VERTEX_NUM]; //访问标记数组
void DFSTraverse(Graph G){
//对图G进行深度优先遍历
    for(v=0;v=0;w=NextNeighbor(G,v,w))
    {
    if(!visited[w]){ //w为u的尚未访问的邻接顶点
        DFS(G,w);
        }//if
    }
}

5.3 图的应用 5.3.1最小生成树

GENERIC_MST(G){ T=NULL;
    while T 未形成一颗生成树；
        do 找到一条最小代价边(u,v)并且加入T后不会产生回路；
            T=T (u,v);
}

Prim 算法

void Prim(G,T){
    T= ; //初始化空树
    U={w}; //添加任一顶点w
    while((V-U)!= ){ //若树中不含全部顶点
        设(u,v)是使u U与v (V-U)，且权值最小的边； 
        T=T {(u,v)}; //边归入树
        U=U {v}; //顶点归入树
    }
}

Krustal 算法

void Kruskal(V,T){
    T=V; //初始化树T，仅含顶点
    numS=n; //连通分量数
    while(numS>1){ //如果连通分量数大于1
        从E中取出权值最小的边(v,u); 
        if(v和u属于T中不同的连通分量){
            T=T {(v,u)}; //将此边加入生成数中
            numS--; //连通分量数减1
        }
    }
}

5.3.2 拓扑排序

bool TopologicalSort(Graph G){
//如果G存在拓扑序列，返回true；否则返回false，这时G中存在环
    InitStack(S); //初始化栈，存储入度为0的顶点
    for (int i = 0; i< G.vexnum; ++i)
    {
        if(indegree[i]==0)
            Push(S,i); //将所有入度为0的顶点进栈
    }
    int count=0; //计数，记录当前已经输出的顶点数
    while(!IsEmpty(S)){ //栈不空，则存在入度为0的顶点
        Pop(S,i); //栈顶元素出栈
        print[count++]=i; // 输 出 顶 点 i 
        for(p=G.vertices[i].firstarc;p=p->nextarc){
        //将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S 
            v=p->adjvex;
            if(!(--indegree[v])) Push(S,v); //入度为0，则入栈
        }//for
    }//while
    if(count< G.vexnum)
        return false; //排序失败，有向图中有回路
    else
        return true; //拓扑排序成功
}

邻接矩阵存储结构的 NextNeighbor 函数

int NextNeighbor(MGraph& G,int x,int y){ 
    if(x!=-1&&y!=-1){
        for (int col=y+1;col< G.vexnum;col++)
        {
            if(G.Edge[x][col] >0&&G.Edge[x][col]< maxWeight)
            return col; //maxWeight代表∞
        }
    }
    return -1;
}

邻接表做存储结构

int NextNeighbor(ALGraph& G,int x,int y){ if(x!=-1){ //顶点x存在
    ArcNode *p=G.vertices[x].first; //对应边链表第一个边结点
    while(p!=NULL&&p->data!=y) //寻找邻接顶点Y p=p->next;
        if(p!=NULL&&p->next!=NULL)
            return p->next->data; //返回下一个邻接顶点
    }
    return -1;
}

🟣查找 6.1 顺序查找和折半查找 6.1.1 顺序查找

typedef struct{ //查找表的数据结构
    ElemType *elem; //元素存储空间基址，建表时按实际长度分配，0号单元留空
    int TableLen; //表的长度
}SSTable;
int Search_Seq(SSTable ST,ElemType key){
//在顺序表ST中顺序查找关键字为key的元素。若找到则返回该元 素在表中的位置
    ST.elem[0]=key; //“哨兵”
    for (i=ST.TableLen;ST.elem[i]!=key; --i){ //从后往前找

    }
    return i; //若表中不存在关键字为key的元素，将查找到i为0时退出for循环
}

6.1.2 折半查找 

int Binary_Search(SeqList L, ElemType key) {
    //在有序表L中查找关键字为key的元素，若存在则分会其位置，不 存在返回-1
    int low = 0, high = L.length - 1, mid; while (low<= high) {
    mid = (low + high) / 2; //取中间位置
    if (L.elem[mid] == key)
        return mid; //查找成功则返回所在位置else if(L.elem[mid] >key)
        high = mid - 1; //从前半部分继续查找
    else
        low = mid + 1; //从后半部分继续查找
    }
    return -1;
}

🟤排序 7.1 插入排序 7.1.1 直接插入排序

void InsertSort(ElemType A[], int n) {
    //直接插入排序int i, j;
    for (i = 2; i<= n; i++) //依次将A[2]～A[n]插入到前面已排好的序列
    if (A[i].key< A[i - 1].key) { //若A[i]的关键码小于其前驱，需将A[i]插入有序表
        A[0] = A[i]; //复制为哨兵，A[0]不存放元素
        for (j = i - 1; A[0].key< A[j].key; --j) //从后往前查找待插入位置
            A[j+1] = A[j]; //向后挪位
        A[j + 1] = A[0]; //复制到插入位置
    }
}

7.1.2 折半插入排序

void InsertSort(ElemType A[], int n) {
//折半插入排序
    int i, j, low, high, mid;
    for (i = 2; i<= n; i++) { //依次将A[2]～A[n]插入到前面已排序序列
        A[0] = A[i]; //将A[i]暂存到A[0]
        low = 1; high = i - 1; //设置折半查找的范围
        while (low<= high) { //折半查找（默认递增有序）
            mid = (low + high) / 2; //取中间点
            if (A[mid].key >A[0].key) high = mid - 1; //查找左子表
            else low = mid + 1; //查找右子表
        }
        for (j = i - 1; j >= high + 1; --j)
            A[j + 1] = A[j]; //统一后移元素，空出插入位置
        A[high + 1] = A[0]; //插入操作
    }
}

7.1.3 希尔排序 

void ShellSort(ElemType A[], int n) {
//希尔排序，对顺序表做希尔插入排序，比直接插入排序有如下修  改
//1.前后记录的增量是dk，不是1
//2.A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    int i, j, dk; //dk:步长
    for (dk = n / 2; dk >= 1; dk = dk / 2) //步长变化
        for (i = dk + 1; i<= n; ++i)
            if (A[i].key< A[i - dk].key) { //需将A[i]插入有序增量子表
            A[0] = A[i]; //暂存在A[0]
            for (j = i - dk; j >0 && A[0].key< A[j
                ].key; j -= dk)
                A[j + dk] = A[j]; //记录后移，查找插入的位置
            A[j + dk] = A[j]; //插入
        }//if
}

7.2 交换排序 7.2.1 冒泡排序

void BubbleSort(ElemType A[], int n) {
//用冒泡排序法将序列A中的元素按从小到大排列
    bool flag;
    for (int i = 0; i< n - 1; i++) {
        flag = false; //表示本趟冒泡是否发生交换的标志
        for (int j = n - 1; j >i; j--) //一趟冒泡过程
            if (A[j - 1].key >A[j].key) { //若为逆序
                swap(A[j - 1], A[j]); //交换
                flag = true;
            }
            if (flag == true)
                return; //本趟遍历后没有发生交换说明表已经有序
    }
}

7.2.2 快速排序

void QuickSort(ElemType A[], int low, int high) {
//快速排序
    if (low< high) { //递归跳出的条件
    //Partition()就是划分操作，将表A[low...high]划分为满 足上述条件的两个子表
    int pivotpos = Partition(A, low, high); //划分
    QuickSort(A, low, pivotpos - 1); //依次对两个子表进行递归排序
    QuickSort(A, pivotpos + 1, high);
    }
}
int Partition(ElemType A[], int low, int high) {
//严版教材中的划分算法（一趟排序过程）
    ElemType pivot = A[low]; //将当前表中第一个元素设为枢轴值，对表进行划分
    while (low< high) { //循环跳出条件
        while (low< high && A[high] >= pivot)
            --high;
        A[low] = A[high]; //将比枢轴值小的元素移动到左端
        while (low< high && A[low]<= pivot)
            ++low;
        A[high] = A[low]; //将比枢轴值大的元素移动到右端
    }
    A[low] = pivot; //枢轴元素存放到最终位置
    return low; //返回存放枢轴元素的位置
}

7.3 选择排序 7.3.1 简单选择排序

void SelectSort(ElemType A[], int n) {
//对表A进行简单的选择排序，A[]从0开始存放元素
    for (int i = 0; i< n - 1; i++) { //一共进行n-1趟
        int min = i; //记录最小元素位置
        for (int j = i + 1; j< n; j++) //在A[1...n-1]中选择最小的元素
            if (A[j]< A[min]) min = j; //更新最小元素的位置
        if (min != i) swap(A[i], A[min]); //与第i个位置互换
    }
}

7.3.2 堆排序

建立大根堆
void BuildMaxHeap(ElemType A[], int len) {
    //建立大根堆
    for (int i = len / 2; i >0; i--) //从i=[n/2]～1，反复调整堆
    AdjustDown(A, i, len);
}
void AdjustDown(ElemType A[], int k, int len) {
//函数AdjustDown将元素k向下进行调整
    A[0] = A[k]; //A[0]暂存
    for (int i = 2 * k; i<= len; i *= 2) { //沿key较大的子结点向下筛选
    if (i< len && A[i]< A[i + 1])
        i++; //取key较大的子结点的下标
    if (A[0] >= A[i]) break; //筛选结束
    else {
        A[k] = A[i]; //将A[i]调整到双亲结点上
        k = i; //修改k值，以便继续向下筛选
    }
}//for
    A[k] = A[0]; //被筛选结点的值放入最终位置
}
堆排序算法
void HeapSort(ElemType A[], int len) {
//堆排序
BuildMaxHeap(A, len); //建立初始堆
for (int i = len; i >1; i--) { //n-1趟的交换和建堆过程
    swap(A[i], A[1]); //输出堆顶的元素（和堆底元素交换）
    AdjustDown(A, 1, i - 1); //整理，把剩余的i-1个元素整理成堆
}
}
向上调整堆的算法
void AdjustUp(ElemType A[], int k) {
    //参数k为向上调整的结点，也为堆的元素个数A[0] = A[k];
    int i = k / 2; //若结点值大于双亲结点,则将双亲结点下调，并继续向上比较
    while (i >0 && A[i]< A[0]) { //循环退出条件A[k] = A[i]; //双亲结点下调
        k = i;
        i = k / 2; //继续向上比较
    }//while
    A[k] = A[0]; //复制到最终位置
}

7.4 归并排序

ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));//辅助数组B
void Merge(ElemType A[],int low,int mid,int high){
    //表A的两端A[low...mid]和A[mid+1...high]各自有序，将它们合并成一个有序表
    for(int k=low;k<=high;k++)
        B[k]=A[k]; //将A中所有元素复制到B中
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){ 
        if(B[i]<=B[j]) //比较B的左右两段中的元素
            A[k]=B[i++]; //将较小值复制到A中
        else
            A[k]=B[j++];
    }//for
    while(i<=mid)
        A[k++]=B[i++]; //若第一个表未检测完，复制
    while(j<=high)
        A[k++]=B[j++]; //若第二个表未检测完，复制
}
void MergeSort(ElemType A[],int low,int high){ if(low< high){
    int mid=(low+high)/2; //从中间划分两个子序列
    MergeSort(A,low,mid); //对左侧子序列进行递归排序
    MergeSort(A,mid+1,high);//对右侧子序列进行递归排序
    Merge(A,low,mid,high); //归并
    }//if
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

新闻名称：【结构与算法】——数据结构代码总结|数据结构代码大全-创新互联
文章网址：http://hbruida.cn/article/coisph.html