计算机考研数据结构算法模板

前言

临近考研，想给考研党们分享一些比较通用的算法模板，让复习更高效一点。如果备考时间足够长，备考人应该有大量时间刷大量习题，会有自己总结的算法模板，笔者文章参考了王道考研系列教材和李春葆版的《新编数据结构习题与解析》，力求在最短的时间里练习一些重要的通用的代码块，希望可以帮助到一些朋友们，祝金榜题名！

手打不易，希望能给个三连支持。

本篇博客中有一些优先级低的知识点，已经标注为选看，还有408新增的并查集操作及应用，非统考生可以只关注简单实现。

顺序表部分

1.逆置

用于逆置顺序表，在很多场景下可以用到，如反序或者局部反序。一般作为题解的中间步骤。

参数left是局部逆置的起始点，right为局部逆置的终点，全局逆置只需将left置为0，right置为R的长度-1即可

void reverse(int R[], int left, int right){
  int k = left, j = right, tmp;
  while(k < j){
    tmp = R[k];
    R[k] = R[j];
    R[j] = tmp;
    k++;
    j--;
  }
}

2. 删除某类元素

以下两个模板本质上思想是一样的，时间紧的同学可以只练习一个。

此为删除某类元素的模板1，在下面注释中的if语句中为不等条件，即想删除等于某值的元素，if中要写为对立条件，即不等，此算法的原理是将删除的条件直接跨过，故步长即为表的最终长度。

在题解中，删除某类元素只需修改标注处if语句中的条件。

void delAll(SqList &L, ElemType x){
  int i, k = 0;
  for(i = 0; i < L.length; i++){
    if(L.data[i] != x){ //删除条件（逆）
      L.data[i] = L.data[i];
      k++;
    }
  }
  L.length = k;
}

此为删除某类元素的模板2，在下面的注释中的if语句中为等值条件，即想删除等于某值的元素，if中要写为等值条件，此算法的原理是将等于某元素的元素数量当作误差累计步长的误差，故表的最终长度为表长减去累计的误差。

void delAll(SqList &L, ElemType x){
  int i = 0, k = 0;
  while(i < L.length){
    if(data[i] == x) k++; //删除条件
    else
      L.data[i - k] = L.data[i];
    i++;
  }
  L.length -= k;
}

3. 按某一条件分区

按某一条件分区也即给定基准条件，前一部分如何，后一部分如何。

在本算法中，标注处条件中的条件可按需求变更，本算法的特点是用i、j向中间夹逼，能够保证不重不漏，注意前一部分和后一部分满足的条件应该是对立的，本例中是让前一部分为负数，后一部分为非负数。类似可以改为前一部分奇数，后一部分偶数…，同时应注意，本算法仅分区，并不会保证两个部分各自有序。

void move(SqList &L){
  ElemType temp;
  int i = 0, j = L.length - 1;
  while(i < j){
    while(i < j && L.data[i] < 0) i++; //while条件中的data[i] < 0为前一部分满足的条件
    while(i < j && L.data[j] >= 0) j--; //while条件中的data[i] >= 0为后一部分满足的条件
    if(i < j){
      temp = L.data[i];
      L.data[i] = L.data[j];
      L.data[j] = temp;
    }
  }
}

4. 删除相同元素且保持相对次序

算法核心思想：插入不排序

忆插入排序思想：将序列划分为有序区与待检测区，每次将待检测区的一个数据插入有序区，并保证有序区有序，有序区逐渐增大，待检测区慢慢减少，最终使有序区覆盖整张表，从而整体有序。

借鉴这种思想，把序列分为无重复区和待检测区，每次将待检测区的一个数据插入无重复区，无重复区逐渐增大，待检测区慢慢减少，最终将序列截断，使整个表无重复。

void delSame(SqList &L){
  int i, j = 0, k;
  for(i = 1; i < L.length; i++){  //for从下标1开始，第一个元素默认在无重复区中
    k = 0;
    /*
    待检测元素与无重复区的元素逐一比对，若不同则k增1
    while 中的条件：
      1.k <= j 表示至待检测元素在与无重复区元素对比
      2.L.data[k] != L.data[i] 表示待检测元素与当前无重复区中的元素不同
    */
    while(k <= j && L.data[k] != L.data[i]) k++; 
    if(k > j){          //与无重复区的元素比对完毕，无重复
      j++;          //无重复区长度加1
      L.data[j] = L.data[i];  //将检测成功的当前的待检测元素加入无重复区
    }
  }
  L.length = j + 1;
}

本算法不涉及排序，故不改变元素的相对次序，只会删除冗余元素，本算法也可用于求交集的思路中，那么本题更改为对两个表进行操作。

5. 有序顺序表的归并算法

算法思路：归并不排序

借鉴归并排序的方法，将两个有序表合并为一个大的有序表，集合类（求交并等）的题目，对于无序的可以用插入不排序的思想，对于有序的可以借鉴归并不排序的思想。

void Merge(SqList L1, SqList L2, SqList & L3){
  int i = 0, j = 0, k = 0;
  while(i < L1.length && j < L2.length){
    if(L1.data[i] < L2.data[j]){//小者留下
      L3.data[k] = L1.data[i];
      i++;
      k++;
    }
  }
  //下面两个while是处理剩下的元素，仅会执行一个
  while(i < L1.length){
    L3.data[k] = L1.data[i];
    j++;
    k++;
  }
  while(j < L2.length){
    L3.data[k] = L2.data[j];
    j++;
    k++;
  }
  L3.length = k;
}

6.原地归并（原地算法示例）

适用于解决前m个元素有序，后面剩余元素有序，在不借助额外辅助空间的情况下使整张表有序的问题。

void Merge(SqList &A, int m){
  int i = 0, j = m, k;        //j遍历后半部分的有序表，同时记录前半部分有序表的长度
  ElemType tmp;
  while(j < A.length && i < j){
    if(j < A.data[j] > A.data[j - 1]){  //整张表已有序
      break;
    } else if(A.data[j] < A.data[i]){ //将A.data[j]插入到前半部分中
      tmp = A.data[j];
      for(k = j - 1; k >= i; k--)   //将A.data[i]及之后的元素后移，给A.data[j]腾地方，i才是A.data[j]应该在的地方
        A.data[k + 1] = A.data[k];
      A.data[i] = tmp;        //将A.data[j]插入A.data[i]处
      i++;
      j++;
    }else{
      i++;
    }
  } 
}

链表

1.熟练掌握头插法、尾插法建表

对于建表算法，要求建表次序与原来次序相同，则应选择尾插；如果要求次序相反，则应采用头插法。

头插法：

void CreateListFLinkList(LinkList *&L, ElemType a[], int n){
  LinkList *s, int i;
  L = (LinkList *)malloc(sizeof(LinkList));
  L->next = NULL;
  for(i =0; i < n; i++){
    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = a[i];
    s>next = L->next;
    L->next = s;
  }
}

尾插法： 尾插一定要记录尾指针

void CreateListRLinkList(LinkList *&L, ElemType a[], int n){
  LinkList *s, *r, int i;
  L = (LinkList *)malloc(sizeof(LinkList));
  r = L;
  for(i = 0; i < n; i++){
    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = a[i];
    r->next = s;
    r = s;
  }
  r->next = NULL;
}

2. 有序单链表归并

顺序归并算法的链表版，无需过多解释。

void Merge(LinkList *L1, LinkList *L2, LinkList *&L3){
  LinkList *p = L1->next, *q = L2->next, *r, *s;
  L3 = (LinkList *)malloc(sizeof(LinkList));
  r = L3;
  while(p != NULL && q != NULL){
    if(p->data < q->data){
      s = (LinkList *)malloc(sizeof(LinkList));
      s->data = p->data;
      p = p->next;
      r->next = s;
      r = s;
    }else{
      s = (LinkList *)malloc(sizeof(LinkList));
      s->data = q->data;
      q = q->next;
      r->next = s;
      r = s;
    }
  }
  if(q != NULL) p = q;  //无论两个表剩下谁，统一处理p，减少代码量
  while(p != NULL){   //处理剩余元素
    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = p->data;
    p = p->next;
    r->next = s;
    r = s;
  }
  r->next = NULL;
}

3.原地归并

在本算法中，没有借用第三个表作为辅助空间，而是复用了L1的表头，将两个表连接起来。

void Merge(LinkList *L1, LinkList *L2, LinkList *&L3){
  LinkList *p = L1->next, *q = L2->next, *r;
  L3 = L1;
  free(L2);
  r = L3;
  while(p != NULL && q != NULL){
    if(p->data < q->data){
      r->next = p;
      r = p;
      p = p->next;
    }else{
      r->next = q;
      r = q;
      q = q->next;
    }
  }
  if(q != NULL) p = q; //剩余元素直接连接
  r->next = p;
}

4. 王道树经典递归法删除

此算法可以当作链表删除某类元素的模板

此处有个经典错误，很多同学会认为这里会断链，实际上在这个if语句中的L相当于上一层的L->next，L =L->next之后，对于上一层来说相当于L->next = L->next->next，那么原来的结构就已经发生改变，用p存下的L指的是要删除的节点，而原本的链表结构已经发生了变化，也就是应该被删的元素节点已经被摘下来了，它的位置已经被它的下一个节点取代了，因为被删节点已经不在原本的链表中了，那么删除它不会影响链表，更不会断链。要点：L = L->next是直接操作的原链表，直接对链表结构发生了改变

void Del_X_3(LinkList &L, ElemType x){
  LNode *p;
  if(L == NULL){
    return;
  }
  if(L.data == x){  //删除条件
    p = L;
    L = L->next;
    free(p);    //经典一问，会不会断链
    Del_X_3(L, x);
  }else{
    Del_X_3(L->next, x);
  }
}

5. 链表题目常用方法

双指针（野辅联动）：

用两个指针，一个基准指针，一个辅助指针，形如：

void xxx(LinkList *&L){
  LNode *pre = L, *p = L->next;
  while(p != NULL){
    //代码块
    pre = p;
    p = p->next;
  }
}

基准指针在辅助指针的前面还是后面要按具体题目情况和自己的思路来，两个指针也并不一定紧挨，while中的条件也是可以按照具体情况需求更改while(p != NULL && [条件])

例：删除所有值为x的节点

void Del_X_1(LinkList *&L, ElemType x){
  LNode *pre = L, *p = L->next, *q;
  while(p != NULL){
    if(p->data == x){
      q = p;
      p = p->next;
      pre->next = p;
      free(q);
    }else{
      pre = p;
      p = p->next;
    }
  }
}

如果两个解决不了怎么办，那就三个！

三指针（野中辅联动）：

仍然是一个基准指针，只是辅助多了一个

三个指针，基准指针具体是在中间还是在两头，要看题目具体情况发挥，三个指针也不一定要紧挨，可以迎合具体条件，while中的条件也可以灵活按需变通while(p != NULL && [条件])

void xxx(LinkList *&L){
  LNode *prepre = L, *pre = prepre->next, *p;
  while(p != NULL){
    //代码块
    prepre = pre;
    pre = p;
  }
}

例：逆置L

void Reverse2(LinkList *&L){
  LinkList *pre = L-next, *p, *post;
  p = pre->next;
  pre->next = NULL;
  while(p != NULL){
    post = p->next;
    p->next = pre;
    pre = p;
    p = post;
  }
  L->next = pre;
}

当然，不嫌麻烦还可以有更多的指针，应该就没有必要了

二叉树

二叉树部分的代码与线性表相比，其实要简单，因为树部分的算法题，遍历就是王道，怎么做都是跟遍历有关，线性表比较灵活，容易结合很多的数学问题，或者原地要求，时间复杂度要求，解法极其灵活。

树的算法题，遍历是王道

首先，要对二叉树的数据结构定义了然

链式：

typedef struct BiNode{
  ElemType data;
  struct BiNode *lchild, *rchild;
}

顺序：

T[i] i是数据单元下标

1. 顺序二叉树找公共祖先结点

顺序二叉树掌握一个原则，那就是对于i来说，2i为左孩子2i+1为右孩子

ElemType Comm_Ancestor(SqTree T, int i, int j){
  if(T[i] != '#' && T[j] != '#'){
    while(i != j){
      if(i > j)   //谁更靠后，谁往上找
        i = i / 2;
      else 
        j = j / 2;
    }
    return T[i];
  } 
}

2. 三序遍历（递归）

分别对应根左右、左根右、左右根，是又简单又重要的模板段。

先序遍历：

void PreOrder(BiTree T){
  if(T != NULL){
    //代码块
    PreOrder(T->lchild);
    PreOrder(T->rchild);
  }
}

中序遍历：

void InOrder(BiTree T){
  if(T != NULL){
    InOrder(T->lchild);
    //代码块
    InOrder(T->rchild);
  }
}

后序遍历：

void PostOrder(BiTree T){
  if(T != NULL){
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    //代码块
  }
}

3. 层次遍历

层次遍历也是一种重要的遍历算法，它可以用于与树高有关的题目中

void LevelOrder(BiTree T){
  queue Q;
  InitQueue(Q);
  BiTree p;
  EnQueue(Q,T);
  while(!IsEmpty(Q)){
    DeQueue(Q,p);
    //代码段
    if(p->lchild != NULL)
      EnQueue(Q,p->lchild);
    if(p->rchild != NULL)
      EnQueue(Q,p->rchild);
  }
}

判断当前是否还在某一层内，应该在一次遍历开始前记录下本结点的右孩子，那么在遍历过程中碰到记录的父节点的右孩子表明到了尽头。

层次遍历（队列符号形应用）：求树高

本算法与上面描述的算法模板本质是一样的，仅仅是这种符号形属于使用数组模拟了队列的数据结构。使用last标记记录了每一层的最后一个结点的标号。

int Btdepth(BiTree T){
  if(!T){
    return 0;
  }
  int front = -1, rear = -1;
  int last = 0, level = 0;
  BiTree Q[MaxSize];
  Q[++rear] = T;
  BiTree p;
  while(front < rear){
    p = Q[++front];
    if(p->lchild)
      Q[++rear] = p->lchild;
    if(p->rchild)
      Q[++rear] = p->rchild;
    if(front == last){
      level++;
      last = rear;
    }
  }
  return level;
}

4. 非递归的后序遍历（选看）

建议以下二叉树部分的代码，读者在抓细节难以理解时，可以自顶向下，跳出来看整体，会理解的效果好一些

这一部分算法用于解决寻找祖先，这是后序遍历的特点，可以回溯找到所有的祖先结点，非递归的后序遍历的要点是区分遍历顺序是返回根结点时是从左子树返回的还是从右子树返回的，所以，使用辅助指针r，指向最近访问过的结点，也可以增加一个标志域，记录是否已被访问。

辅助指针型：

void PostOrder(BiTree T){
  stack S;
  BiNode p, r;
  InitStack(S);
  p = T;
  r = NULL;
  while(p || IsEmpty(S)){
    if(p){
      Push(S, p);
      p = p->lchild;
    }else{
      GetTop(S, p);
      if(p->rchild && p->rchild != r){ //若右孩子被访问过，则p->child == r，就可以输出根结点了，否则，仍要继续遍历右子树
        p = p->rchild;
        Push(S, p);
        p = p->lchild;
      }else{
        Pop(S, p);
        //visit(p->data) 代码段
        r = p;
        p = NULL;
      }
    }
  }
}

标志域型：（案例：打印x的所有祖先）：

typedef struct {
  BiTree t;
  int tag;
} Stack;//tag=0表示左孩子被访问，tag=1表示右孩子被访问
void Search(BiTree bt, ElemType x){
  Stack s[];
  top = 0;
  while(bt != NULL || top > 0){
    while(bt != NULL && bt->data != x){ //移到最左端，或者还没到最左端遇到了x
      s[++top].t = bt;
      s[top].tag = 0;         //左孩子访问标志
      bt = bt->lchild;
    }
    if(bt->data == x){          //若在途中偶遇了x，那么栈中结点即为其祖先
      printf("所查结点的所有祖先结点的值为：\n");
      for(int i = 1; i <= top; i++)
        printf("%d",s[i].t->data);
      exit(1);
    }
    while(top != 0 && s[top].tag == 1)  //本结点的右孩子已经访问，说明本结点的左右子树均已访问完成，可以退栈
      top--;
    if(top != 0){           //若本结点的右孩子未被访问，遍历右子树
      s[top].tag = 1;
      bt = s[top].t->rchild;
    }
  }
}

5. 线索化二叉树（选看）

这部分内容不在某些学校的考纲中，所以时间紧张的可以先过。线索化二叉树是利用了二叉树中的空指针域，将空指针域（即左孩子为空或右孩子为空）连接其前驱或后驱结点，以便于遍历，故线索话的算法中处理的是左孩子为空和右孩子为空的结点，将他们的空域分别指向其前驱或后继，并置ltag或rtag为1.线索二叉树的数据结构定义：

typedef struct ThreadNode{
  ElemType data;
  struct ThreadNode *lchild, *rchild;
  int ltag, rtag;
} ThreadNode, *ThreadTree;

通过中序遍历对二叉树线索化的递归算法：

void InThread(Thread Tree &p, ThreadTree &pre){
  if(p != NULL){
    InThread(p->lchild, pre); //递归，线索化左子树
    if(p->lchild == NULL){
      p->lchild = pre;
      p->ltag = 1;
    }
    if(pre != NULL && pre->rchild == NULL){//条件pre != NULL这个条件是对第一个进行特殊处理的，不做操作，仅仅更新pre指针
      pre->rchild = p;
      pre->rtag = 1;
    }
    pre = p;          //及时更新pre
    InThread(p->rchild, pre); //递归，线索化右子树
  }
}
void CreateInThread(ThreadTree T){
  ThreadTree pre = NULL;
  if(T != NULL){
    InThread(T, pre);
    //下面是处理遍历的最后一个结点，算法使然
    pre->rchild = NULL;
    pre->rtag = 1;
  }
}

线索二叉树的遍历：

求中序线索二叉树中中序序列下的第一个结点：

ThreadNode *Firstnode(ThreadNode *p){
  while(p->ltag == 0) p = p->lchild; //找到最左下的结点
  return p;
}

求中序线索二叉树中结点p在中序序列下的后继结点：

ThreadNode *Nextnode(ThreadNode *p){
  if(p->rtag == 0) return Firstnode(p->rchild);
  else return p->rchild;
}

中序遍历

void Inorder(ThreadNode *T){
  for(ThreadNode *p == Firstnode(T); p != NULL; p = Nextnode(p)){
    //visit(p)  代码段
  }
}

图

2021 408真题中首次出现了图的算法题，并且，是遍历邻接矩阵的算法题，所以邻接矩阵和邻接表的数据结构定义最好还是需要知晓的。图的算法使用DFS与BFS对于考研要求基本足够。

邻接矩阵：

typedef struct{
  VertexType Vex[MaxVertexNum];       //顶点表
  EdgeType Edge[MaxVertexNum][MaxVertexNum];  //邻接矩阵，边表
  int vexnum, arcnum;             //图的当前顶点数和弧数
} MGraph;

邻接表：

typedef struct ArcNode{             //边表结点
  int adjvex;                 //该弧指向的顶点的位置
  struct ArcNode *next;           //指向下一条弧的指针
  InfoType info;                //权值
}ArcNode;
typedef strcut VNode{             //顶点表结点
  VertexType data;              //顶点信息
  ArcNode *first;               //指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxVertexNum];
typedef struct{                 //邻接表
  AdjList vertices;             //图的顶点数和弧数
  int vexnum, arcnum;
}ALGraph;

1. 深度优先遍历

Traverse中的循环是为了，避免整个图中有多个连通分量而导致遍历不全的情况。

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){
  for(v = 0; v < G.vexnum; ++v)
    visited[v] = FALSE;
  for(v = 0; v < G.vexnum; ++v)
    if(!visited[v])
      DFS(G,v);
}
void DFS(Graph G, int v){
  visit(v);
  visited[v] = TRUE;
  for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
    if(!visited[w])
      DFS(G, w);
}

2. 广度优先遍历

BFS需要借助队列实现，与二叉树的层次遍历路子差不多，事实上DFS需要借助栈，但函数嵌套的递归本身就在栈中工作。

bool visited[MAX_VERTEX_NUM];
void BFSTraverse(Graph G){
  for(i = 0; i < G.vexnum; i++)
    visited[i] = FASLE;
  InitQueue(Q);
  for(i = 0; i < G.vexnum; ++i)
    if(!visited[i])
      BFS(G, i);
}
void BFS(Graph G, int v){
  visit(v);
  visited[v] = TRUE;
  EnQueue(Q, v);
  while(!isEmpty(Q)){
    DeQueue(Q, v);
    for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){
      if(!visited[w]){
        visit(w);
        visited[w] = TRUE;
        EnQueue(Q, w);
      }
    }
  }
}

排序

1. 插入排序

直接插入排序：

//0相当于哨兵
void InsertSort(int a[],int n){
    for(int i=2;i<=n;i++){
        a[0] = a[i];
        int j;
        for(j=i-1;a[0]<a[j];j--){
            a[j+1] = a[j];
        }
        a[j+1] = a[0];
    }
}

折半插入排序：

//0相当于哨兵
void InsertSort(int a[],int n){
    for(int i=2;i<=n;i++){
        a[0] = a[i];
        int low = 1,high = i-1;
        while(low<=high){
            int mid = low+high>>1;
            if(a[mid]>a[0]) high = mid-1;
            else low = mid+1;
        }
        for(int j=i-1;j>=low;j--){
            a[j+1] = a[j];
        }
        a[low] = a[0];
    }
}

2. 冒泡排序

//冒泡排序，元素下标从1开始，从后往前冒泡
void BubbleSort1(int a[],int n){
    for(int i=1;i<n;i++){
        bool flag = false;
        for(int j=n;j>i;j--){
            if(a[j-1]>a[j]){
                swap(a[j-1],a[j]);
                flag = true;
            }
        }
        if(!flag) return ;
    }
}
//冒泡排序，元素下标从1开始，从前往后冒泡
void BubbleSort2(int a[],int n){
    for(int j=n;j>1;j--){
        bool flag = false;
        for(int i=1;i<j;i++){
            if(a[i]>a[i+1]){
                swap(a[i],a[i+1]);
                flag = true;
            }
        }
        if(!flag) return;
    }
}

3. 快速排序

int Partition(int a[],int low,int high){
    int 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;
}
//快速排序
void QuickSort(int a[],int low,int high){
    if(low<high){
        int pivotpos = Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
    }
}

4. 简单选择排序

//下标从1开始
void SelectSort(int a[],int n){
    for(int i=1;i<=n;i++){
        int tmp=i;
        for(int j=i+1;j<=n;j++){
            if(a[j]<a[tmp]){
                tmp=j;
            }
        }
        swap(a[tmp],a[i]);
    }
}

查找

1.折半查找

int Binary_Search(SeqList L, ElemType key){
  int low = 0, high = L.TableLen - 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;
}

并查集（选看）

此部分为408考研新大纲中的新增内容，统考生应重点关注

1. 简单并查集的实现

#define SIZE 10000
//初始化并查集
void Initial(int S[]){
  for(int i=0;i<SIZE;i++)
    S[i]=-1;
}
//Find“查"操作，找x所属集合(返回x所属根结点)
int Find(int S[],int x){
  while(S[x]>=0)      // 循环寻找x的根
    x=S[x];
  return x;       //根的S[]小于0
}
//Union“并"操作，将两个集合合并为一个
void Union(int S[],int Rootl,int Root2 ) {
  //要求Root1与Root2是不同的集合
  if (Root1==Root2) return; 
  //将根Root2连接到另-根Root1下面
  S[Root2]=Root1 ;
}

2. 优化后的并查集

下面是优化后的并查集实现，Union操作采用”小树并入大树"的优化策略，Find操作采用“压缩路径”的优化策略

#define SIZE 10000
//初始化并查集
void Initial(int S[]){
  for(int i = 0; i < SIZE; i++)
  S[i]=-1;
}
//Find“查" 操作优化，先找到根节点，再进行"压缩路径”
int Find(int S[], int x){
  int root = X;
  while(S[root] >= 0) root = S[root]; //循环找到根
  while(x!=root){ //压缩路径
  int t = S[x]; // t指向x的父节点
  S[x]=root;    //x直接挂到根节点下
  x=t;
  return root;  //返回根节点编号
}
//Union "“并" 操作，小树合并到大树
void Union(int S[], int Root1, int Root2) {
  if(Root1==Root2) return ;
  if(S[Root2]>S[Root1]) { //Root2结 点数更少
    S[Root1] += S[Root2]; //累加结点总数
    S[Root2] = Root1; //小树合并到大树
  } else {
  S[Root2] += S[Root1]; //累加结点总数
  S[Root1] = Root2;
  }
}

3. 求无向图中的连通分量

例：二维数组int g[5][5]表示无向图G的邻接矩阵，使用并查集的基本操作，求无向图G中有几个连通分量

//用并查集判断一个图有几个连通分量(图用邻接矩阵表示)
int ComponentCount(int g[5][5]){
  //g[5][5]是二维数组表示的邻接矩阵
  int S[5]; //定义、 初始化并查集
  for (int i=0;i<5;i++) S[i]=-1;
  //遍历各条边(无向图，遍历上三角部分即可)
  for (int i=0;i<5;i++)
    for (int j=i+1;j<5;j++)
      if (g[i][j]>0){ //结点i、j之间有边
        int iRoot=Find(S,i); //通过并 查集找到i所属集合
        int jRoot=Find(S,j); //通过并查集找到j所属集合
        if (iRoot!=jRoot) //i、 j并入同一集合
        Union(S,iRoot, jRoot);
      }
  //统计有几个连通分量
  int count=0;
  for (int i=0;i<5;i++)
    if(S[i]<0) count++;
  return count;
}

4. 判断无向图是否有环

例：二维数组int g[5][5]表示无向图G的邻接矩阵，使用并查集的基本操作，判断无向图G中是否有环

//用并查集判断一个图是否有环(图用邻接矩阵表示)
int hasAcyclic(int g[5][5]){//g[5][5]是二维数组表示的邻接矩阵
  int S[5]; 人//定义、初始化并查集
  for (int i=0;i<5;i++) S[i]=-1;//遍历各条边(无向图，遍历上三角部分即可)
  for (int i=0;i<5; i++)
    for (int j=i+1;j<5;j++)
      if (g[i][j]>0){ //结点i、j之间有边
        int iRoot=Find(S,i); //通过并查集找到i所属集合
        int jRoot=Find(S,j); //通过并查集找到j所属集合
        if(iRoot !=jRoot) //i、j不在同一个集合，Union 
          Union(S,iRoot， jRoot);
        else //i、j原本就在同一个集合，即原本就连通
        return 1; //在一个连通子图中， 但凡再多-条边，必有环
      }
  return 0;//图中没有环
}

创作不易，谢邀三连，感谢支持！

CSDN：Moresweet猫甜

计算机考研数据结构算法模板

计算机考研数据结构算法模板

前言

顺序表部分

1.逆置

2. 删除某类元素

3. 按某一条件分区

4. 删除相同元素且保持相对次序

5. 有序顺序表的归并算法

6.原地归并（原地算法示例）

链表

1.熟练掌握头插法、尾插法建表

2. 有序单链表归并

3.原地归并

4. 王道树经典递归法删除

5. 链表题目常用方法

二叉树

1. 顺序二叉树找公共祖先结点

2. 三序遍历（递归）

3. 层次遍历

4. 非递归的后序遍历（选看）

5. 线索化二叉树（选看）

图

1. 深度优先遍历

2. 广度优先遍历

排序

1. 插入排序

2. 冒泡排序

3. 快速排序

4. 简单选择排序

查找

1.折半查找

并查集（选看）

1. 简单并查集的实现

2. 优化后的并查集

3. 求无向图中的连通分量

4. 判断无向图是否有环

热门文章

最新文章

相关课程

相关电子书

相关实验场景