考研心得：考研数据结构算法大全

考研心得：考研数据结构算法大全 PCGuo999 于2022-04-22 19:09:39发布 6768 收藏 286 分类专栏： 数据结构 文章标签： 数据结构 算法 链表 排序算法 哈希算法 数据结构 专栏收录该内容 11 篇文章 19 订阅 订阅专栏

本人考研的算法笔记，包含考研数据结构会涉及到的算法，全部掌握让你考研算法题稳稳拿下！！

一、排序 1.插入排序

算法思想：第i次插入排序：向i-1个有序数列中插入一个元素，使之称为含有i个元素的有序子序列。将当前元素和前驱元素比较，若大于则表示有序，不用改变；否则将该元素插入到前面，并且前面比它大的元素后移。

void InsertSort ( int a[] , int n ) { int temp , i , j; for( i = 1 ; i<n ; ++i ) //从第二个元素开始 If( a[i] < a[i-1] ) { temp = a[i]; //保存该元素值 for( j = i-1 ; a[j] > temp; --j)//前面大于的依次后移 a[j+1] = a[j]; a[j+1] = temp; //放到应该在的位置 } } 2.希尔排序

算法思想：也叫缩小增量排序。取一个小于n的整数d作为增量，把数据分组，所有距离为d的倍数的记录放在同一个组中，在各组内进行直接插入排序。初次取序列的一半为增量，以后每次减半，直到增量为1，即排序结束。

void ShellSort ( int a[] , int n ) 相当于插入排序中的1换成d { int temp , i , j; for( d = n/2 ; d >=1 ; d = d/2) //步长变化 for( i = d + 1 ; i<n ; i+=d ) //从第二个元素开始 if( a[i] < a[i-d] ) { temp = a[i]; //保存该元素值 for( j = i-d ; a[j] > temp ; j-=d ) //前面大于的依次后移 a[j+d] = a[j]; a[j+d] = temp; //放到应该在的位置 } } 3.折半排序

算法思想：直接插入排序的改进，在插入到前面有序子队列时使用折半查找方式进行查找。

void BInsertSort( int a[] , int n ) { int low , high , mid , temp , i , j; for( i = 1 ; i<n ; ++i ) if( a[i] < a [i-1] ) { temp = a[i]; //保存元素 low = 0; high = i-1; while(low<high) //二分查找位置 { mid = (low + high)/2; if( a[mid] > temp ) high = mid-1; //查找左边 else low = mid+1; //查找右边 } a[low] = temp; //放到指定位置 } } 4.冒泡排序

算法思想：每次都从第一个元素开始，依次两个两个比较，小的放前面，使得前i个元素的最大放在第i的位置，在算法中设置flag=1标志，若此次发生交换则flag设置为1，若未发生变换则flag=0说明整个数组有序，排序结束

void BubbleSort( int a[] , int n ) { int flag = 1; ​ for (int i = n-1 ; i>0 && flag ==1 ; i--) //对前i个元素进行冒泡，因为是两两比较，所有i>0，不能等于0 ​ { ​ flag = 0; //初始化flag ​ for (int j = 0 ; j<i ; j++) ​ if( a[j] >a[j+1] ) //若大于后继，则互换 ​ { ​ Swap( a[j] = a[j+1]); ​ flag = 1; //更新flag ​ } ​ } } 5.双向冒泡排序

算法思想：每次先从前往后冒泡，当一次往后之后再从后往前冒泡一遍，并且每次冒泡后都需要更新上下界

void bubble2(int a[], int n)//交替 { ​ int low = 0, high = n - 1; ​ bool flag = true;//一趟冒泡后记录元素是否发生交换的标志，若没有发生则表示已经有序 ​ while (low < high&&flag) ​ { ​ flag = false;//每次排序初始化flag为false ​ for (int i = low; i < high; i++)//从前往后冒泡 ​ if (a[i] > a[i + 1])//大的往后 ​ { ​ swap(a[i], a[i + 1]); ​ flag = true; ​ } ​ high--;//更新上界 ​ for (int i = high; i > low; i--)//从后往前冒泡 ​ if (a[i] < a[i - 1])//小的往前 ​ { ​ swap(a[i], a[i - 1]); ​ flag = true; ​ } ​ low++;//更新下界 ​ } } 5.快速排序

算法思想：使用分治算法的思想，将数据进行拆分，直至拆到最小再进行排序合并。首先选取第一个数作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序，之后递归直至所有元素排完。

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); ​ } } int Partition(int a[], int low, int high) //从表的两端交替向中间扫描，一趟划分 { ​ int pivot = a[low]; //将表第一个元素设置为中心点 while (low < high) ​ { ​ while (low < high && a[high] >= pivot) --high; //先从后往前找第一个小于pivot的位置 ​ a[low] = a[high]; //更新 ​ while (low < high && a[low] <= pivot) ++low; //再从前往后找第一个大于pivot的位置 ​ a[high] = a[low]; //更新 ​ } ​ a[high] = pivot; //pivot放入，这时high=low ​ return high; } 6.简单选择排序

算法思想：每次都从序列后的n-i+1个元素中选出最小的元素与该元素组的第1个元素交换，即与整个序列的第i个元素交换。依此类推，直至i=n-1为止。也就是说，每一趟排序从未排好顺序的那些元素中选择一个最小的元素，然后与这些未排好序的元素的第一个元素互换

void SelectSort(int a[], int n) { ​ int min; ​ for (int i = 0; i < n; i++) ​ { ​ min = i; //记录最小元素位置 ​ for (int j = i + 1; j < n; j++) //找最小 ​ if (a[min] > a[j]) min = j; //更新最小元素位置 ​ if (min != i) //若i不是最小的元素，则互换 ​ Swap(a[min] , a[j]) ​ } } 7.堆排序

算法思想：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

void buildmaxheap(int a[], int n) //创建大根堆 { ​ for (int i = len / 2; i > 0; i--) //从n/2~1贩反复调整堆 ​ headadjust(a, i, n); } void headadjust(int a[ ], int k, int n) //将元素k为根的子树进行调整 { ​ a[0] = a[k]; ​ for (int i = 2 * k; i <= n; i *= 2) //一层一层向下 ​ { ​ if (i < n&&a[i] < a[i + 1]) i++; //取key较大的子结点 ​ if (a[0] > a[i]) break; //若较大的子结点小于k，则不用再比 ​ else ​ { ​ a[k] = a[i]; //若子结点小于k，则和子结点互换 ​ k = i; //指向k的新位置，以便继续向下筛选 ​ } ​ } ​ a[k] = a[0]; //被筛选的值放在最终位置 } void heapsort(int a[ ], int n) { ​ buildmaxheap(a, n); //初始建堆 ​ for (int i = n; i > 1; i--) //将堆顶和最后一个结点互换，放到其排序的位置 ​ { ​ Swap(a[1],a[i]); //互换 ​ headadjust(a, 1, i - 1); //i-1之后的已经有序，只用排之前的 ​ } } 8.归并排序

算法思想：使用分治算法的思想。使用递归方法来实现归并排序时，核心思想是两个有序子序列的合并，注意这里是有序子序列的合并，因此下面要做两件事，整个过程：

(1)将待排序序列从中间一分为二，对左右两边再进行递归分割操作，得到n个相互独立的子序列；

(2)对n个独立的子序列递归的执行合并操作，最终得到有序的序列。

void MergeSort(int 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); //将[low-mid]和[mid+1-high]归并 ​ } } int *b = (int*)malloc(n*sizeof(int)); //辅助函数b void Merge(int a[], int low, int mid, int high) //将序列[low-mid]和[mid+1-high]合并成一个有序序列 { ​ int i = low, j = mid + 1, k = low; ​ for (int p = low; p <= high; p++) b[p] = a[p]; //将a[ ]中元素都复制到b[ ]中 ​ while (i <= mid && j <= high) //合并放入a[ ] ​ { ​ if (b[i] < b[j]) a[k++] = b[i++]; //将小的放入 ​ else a[k++] = b[j++]; ​ } ​ while (i <= mid) a[k++] = b[i++]; //若没有排完添加到后面 ​ while (j <= high) a[k++] = b[j++]; } 二、查找 1.一般线性表顺序查找

算法思想：查找全部元素，若找到则输出，未找到则输出-1

int Search(int a[], int n, int x) { ​ for (int i = 0; i < n; i++) ​ if (a[i] == x) return i; ​ return -1; } 2.有序表的顺序查找

算法思想：当当前元素小于关键字则向后找，若大于关键字或者遍历完，则返回-1

int Search(int a[], int n, int x) { ​ for (int i = 0; i < n ***\*&& a[i] > x\****; i++) ​ if (a[i] == x) return i; ​ return -1; } 3.折半查找

算法思想：将表分为两部分，关键字和中间的元素比较，若小于则在左边查找，若大于则在右边查找，直至找到，若未找到返回-1

int BSearch(int a[], int n, int x) { ​ int low = 0, high = n - 1, mid; ​ while (low <= high) ​ { ​ mid = (low + high) / 2; ​ if (a[mid] == x) return mid; ​ if (a[mid] > x) high = mid - 1; //从前半部分找 ​ else low = mid + 1; //从后半部分找 ​ } ​ return -1; } 三、图 存储结构：

①邻接矩阵

typedef struct MGraph{ char Vex[Max_VexNum]; //顶点表 int Edge[Max_Vexnum] [Max_Vexnum]; //邻接矩阵，边表 int vexnum,arcnum; //顶点数和边数 }MGraph;

②邻接表法

typedef struct ArcNode{ //边表结点 int adjvex; //改弧指向的顶点位置 struct ArcNode *next; //指向下一条弧的指针 }ArcNode; typedef struct VNode{ //顶点表结点 char data; //顶点信息 ArcNode *first; //指向第一条依附该顶点的弧的指针 }VNode, AdjList[Max_VexNum]; typedef struct ALGraph{ //是以邻接表存储的图类型 AdjList vertices; //邻接表 Int vexnum,arcnum; //图的顶点数和弧数 }ALGraph; 1.广度优先算法BFS

算法思想：类似树的层序遍历，1.访问完当前顶点的所有邻接点。2.访问当前已在集合内的顶点的邻接点（邻接点不包括已在集合内的）

bool visited[max_vex_num]; //访问标记数组 void BFSTraverse(Graph G) { ​ for (int i = 0; i < G.Vexnum; i++) ​ visited[i] = false; //初始化访问标记数组 ​ for (int j = 0; j < G.Vexnum; j++) //从0号开始遍历 ​ if (!visited[j]) //对每一连通分量调用一次BFS ​ BFS(G, j); } void BFS(Graph G, int v) //从顶点v出发开始广度优先遍历 { ​ int p; ​ int Q[G.Vexnum]; //建立队列（和DFS的差别就是这个队） ​ int front = 0, rear = 0; //初始化队列 ​ visit(v); //访问初始结点 ​ visited(v) = true; //标记访问 ​ Q[rear++] = v; //入队 ​ while (front!=rear) //队列非空 ​ { ​ p =Q[front++]; //顶点出队 ​ for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) //检测v所有邻接点 ​ if (!visited[w]) //若w为v尚未访问的邻接点 ​ { ​ visit(w); //访问结点 ​ visited(w) = true; //标记访问 ​ Q[rear++] = w; //入队 ​ } ​ } } 2.BFS算法求单源最短路径问题

算法思想：因为BFS算法是以根开始广度优先遍历

bool visited[max_vex_num]; //访问标记数组 void BFS_Min_Distance(Graph G, int u) //d[i]表示从u到i结点的最短路径 { ​ visited[u] = true; //初始化根结点 ​ d[u] = 0; ​ for (i = 0; i < G.vexnum; i++) //初始化路径长度 ​ d[i] = ∞; ​ int Q[G.vexnum]; //创建队列 ​ int front = 0, rear = 0, x ; //初始化队列 ​ Q[rear++] = u; //u入队 ​ while (front != rear) ​ { ​ x = Q[front++]; //出队 ​ for (int w = FirstNeighbor(G, x); w >= 0; w = NextNeighbor(G, x, w)) ​ if (!visited[w]) ​ { ​ visited[w] = true; ​ d[w] = d[u]+1; //路径长度+1 ​ Q[rear++] = w; ​ } ​ ​ } } 3.深度优先算法DFS

算法思想：类似树的先序。首先访问图中某一起始点v，然后由v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2，重复上述操作。当不能继续向下访问时，退回到最近被访问的顶点，若它还有邻接点未被访问，则从该顶点继续上述搜索过程，直至图中所有结点都被访问。

bool visited[max_vex_num]; //访问标记数组 void DFSTraverse(Graph G) { ​ for (int i = 0; i < G.Vexnum; i++) ​ visited[i] = false; //初始化访问标记数组 ​ for (int i = 0; i < G.Vexnum; i++) ​ if (!visited[i]) ​ DFS(G, i); } void DFS(Graph G, int v) { ​ visit(v); ​ visited[v] = true; ​ for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) //w为u的尚未访问的邻接顶点 ​ if (!visited[w]) ​ DFS(G, w); } 四、树 1.递归遍历 void Track(BiTree p) { if(p) { //1.先序 Track(p->lchild); //2.中序 Track(p->rchild); //3.后序 } } 2.先序/中序遍历

算法思想（先序）：1.沿着根的左孩子，依次入栈并访问，直到孩子为空。2.栈顶元素出战，并开始遍历右子树

算法思想（中序）：1.沿着根的左孩子，依次入栈，直到孩子为空。2.栈顶元素出栈并访问，并开始遍历右子树

void Order(BiTree T) { ​ if (T) ​ { ​ BiTNode *Stack[Max_Size]; //建栈并初始化 ​ int top = -1; ​ BiTNode *p = T; ​ while (top != -1 || p != NULL) //栈非空并且树未遍历完时 ​ { ​ if (p) ​ { ​ //1.先序 ​ Stack[++top] = p; //入栈 ​ p = p->lchild; //遍历左子树 ​ } ​ else ​ { ​ p = Stack[top--]; //出栈 ​ //2.中序 ​ p = p->rchild; //遍历右子树 } } } } 3.后序遍历（双栈/单栈标记法）

①双栈法

算法思想：用两个栈来存储，1.先将根结点入栈1；2.出栈顶元素入站2，依次将左右子树入栈1。重复操作2直至栈1为空，再将所有栈2元素出栈

void Post_order(BiTree T) { ​ if (!T) return; ​ BiTNode * stack1[Max_Size], * stack2[Max_Size]; ​ int top1 = -1, top2 = -1; ​ BiTNode * p; ​ stack1[++top1] = T; //根入栈1 ​ while (top1 != -1) ​ { ​ p = stack1[top1--];//1栈顶元素出栈入栈2 ​ stack2[++top2] = p; ​ if (p->lchild) //左右子树入栈1 ​ stack1[++top1] = p->lchild; ​ if (p->rchild) ​ stack1[++top1] = p->rchild; ​ }//while end ​ while (top2 != -1) //栈2所有元素出栈 ​ { ​ p = stack2[top2--]; ​ visit(p); } }

②单栈标记法

算法思想：1.沿着根的左孩子，依次入栈，直至左孩子为空；2.栈顶元素出栈，若其右孩子不空且未被访问过，则右孩子入栈执行1；否则栈顶元素出栈访问并且标记。因为后序遍历，当前结点若右子树存在，则当前结点的前驱为其右孩子

void Post_order(BiTree T) { ​ BTNode *stack[Max_Size]; //建栈并初始化 ​ int top = -1; ​ BTNode *p = T, *r = NULL; //r指向最近访问的点 ​ while (top != -1 || p != NULL) //栈非空或树未遍历完时 ​ { ​ if (p) //走到最左边 ​ { ​ stack[++top] = p; //入栈 ​ p = p->lchild; //遍历左子树 ​ } ​ else //向右 ​ { ​ p = stack[top--]; //出栈 ​ if (p->rchild && p->rchild != r) //若右子树存在并且未被访问 ​ { ​ stack[++top] = p; //再次入栈，因为还没访问完 ​ p = p->rchild; //遍历右子树 ​ } ​ else //否则，弹出结点并访问 ​ { ​ visit(p); //执行结点 ​ r = p; //标记结点 ​ p = NULL; //指针设为空，因为要返回双亲结点 ​ } ​ } ​ } } 4.层序遍历

算法思想：借助队列,1.将根结点入队。2.出队并将其左右子树（若存在）依次入队。重复2，直至队空

void Level_order(BiTree T) { ​ if (!T) return; ​ BTNode* Q[10]; //初始化队 ​ int front = 0, rear = 0; ​ BTNode *p = NULL; ​ Q[rear++] = T; ​ while (front < rear) //队非空 ​ { ​ p = Q[front++]; //出队 ​ visit(p); ​ if (p->lchild) //左右子树入队 ​ Q[rear++] = p->lchild; ​ if (p->rchild) ​ Q[rear++] = p->rchild; ​ } } 5.求二叉树的层数

①非递归（层序遍历）

算法思想：设置标记层数的depth和一个指向下一行最后一个结点的指针p。1.根入队，设置p=rear2.队头出队并将左右子树入队，若当前行已经遍历完即front=tag，则层数+1并且更新p=rear。

int Tree_Depth2(BiTree T) { ​ if (T == NULL) return 0; ​ BiTree Q[Max_Size], p; //创建队列和辅助指针p ​ int front = 0, rear = 0; ​ Q[rear++] = T; //根入队 ​ int depth = 0, tag = rear; //下一层最后一个为rear=1 ​ while (front < rear) //队非空 ​ { ​ p = Q[front++]; //队头出队 ​ if (p->lchild) Q[rear++] = p->lchild; ​ if (p->rchild) Q[rear++] = p->rchild; ​ if (front == tag) //当遍历完当前行最后一个后 ​ { ​ depth++; //层数增加并更新标记最后结点的tag ​ tag = rear; ​ } ​ } ​ return depth; }

②递归

int Tree_Depth(BiTree T) { ​ if (T == NULL) ​ return 0; ​ int ldepth = Tree_Depth(T->lchild); ​ int rdepth = Tree_Depth(T->rchild); ​ if (ldepth > rdepth) ​ return ldepth+1; ​ else ​ return rdepth+1; } 6.求结点所在层数

①非递归（简化）

用5①的非递归，当发现所查结点时输出depth+1（因为这时当前行还没运行完，depth还没有+1）

while (front < rear) //队非空 { ​ p = Q[front++]; //队头出队 ​ if (p == x) return depth + 1; //若找到则返回深度 ​ if (p->lchild) Q[rear++] = p->lchild; ​ if (p->rchild) Q[rear++] = p->rchild; ​ if (front == tag) //当遍历完当前行最后一个后 ​ { ​ depth++; //层数增加并更新标记最后结点的tag ​ tag = rear; ​ } }

②递归

思想：若当前结点为空则返回0；若找到该结点则返回该结点的层数；遍历左右子树，若左右子树大于0则表示找到了，返回左/右子树的返回值

int Level(BTree T, BTNode* p, int depth) { if(!T) return 0; if(T==p) return depth; int L = Level(T->lchild, p, depth+1); if(L>0) return L; //即找到了 int R = Level(T->lchild, p, depth+1); if(R>0) return R; //即找到了 return -1; //未找到 } 7.求树的宽度

①非递归int Width_Depth(BiTree T)（简化）

算法思想：利用5①的非递归遍历，在遍历每一行的时候都计算下一行的个数count=front-rear

int count=1, width=1; //count表示下一行的结点个数，max表示树的宽度(最大count) ​ while (front < rear) //队非空 ​ { ​ p = Q[front++]; //队头出队 ​ if (p->lchild) Q[rear++] = p->lchild; ​ if (p->rchild) Q[rear++] = p->rchild; ​ if (front == tag) //当遍历完当前行最后一个后 ​ { tag = rear; width= rear - front; //计算当前行的个数 ​ if (width> max) max = width; //更新最大width ​ } ​ } ​ return width; //返回width

②递归

算法思想：开辟一个数组count[二叉树高度],遍历每一个节点,然后根据当前节点所在层次i,则执行count[i]++;最后遍历完求出最大的count即为二叉树宽度

int count[10]; int Max = -1; void FindWidth(BiTree T, int k) { ​ if (!T) return; ​ count[k]++; //k层结点数+1 ​ if (Max < count[k]) Max = count[k]; //更新最大的count ​ FindWidth(T->lchild, k + 1); //遍历左右子树 ​ FindWidth(T->rchild, k + 1); } 8.交换二叉树所有结点的左右子树

①算法思想：使用层序遍历，但是在每次将左右子树入队时改为右左的顺序入队

②递归：算法思想：先序遍历（中序也可）左右子树，并且每次遍历将左右子树互换

void swap(BiTree T) { BiTree q; //左右子树互换 ​ q = T->lchild; ​ T->lchild = T->rchild; ​ T->rchild = q; swap(T->lchild);//递归交换左右孩子的左右子树 ​ swap(T->rchild); } 9.求叶子结点个数-递归

算法思想：1.若结点为空则返回0；2.若结点为叶子结点则返回1；3.否则返回左子树和右子树叶子结点的和。递归调用

int Degree0(BiTree T) { ​ if (!T) return 0; ​ if (T->lchild == NULL && T->rchild == NULL) return 1; //若为叶子结点，返回1 ​ else return Degree0(T->lchild) + Degree0(T->rchild); //否则返回左右子树叶子数相加 } 10.求度为2的结点个数-递归

算法思想：1.若结点为空则返回0；2.若结点度为2则返回1+左右子树度为2的结点之和；3.否则返回左子树和右子树叶子结点的和。递归调用

int Degree2(BiTree T) { ​ if (!T) return 0; ​ if (T->lchild != NULL && T->rchild != NULL) //若度为2，则 return 1+ Degree2(T->lchild) + Degree2(T->rchild); //返回左右子树的度为2的结点个数和+1 ​ else return Degree2(T->lchild) + Degree2(T->rchild); //否则当前结点不是度为2，结点数不+1 } 11.求度为1的结点个数-递归

算法思想：1.若结点为空则返回0；2.若结点度为2则返回1+左右子树度为2的结点之和；3.否则返回左子树和右子树叶子结点的和。递归调用

int Degree1(BiTree T) { ​ if (!T) return 0; ​ if (T->lchild != NULL && T->rchild == NULL) ​ return 1+ Degree1(T->lchild) + Degree1(T->rchild); else if (T->lchild == NULL && T->rchild != NULL) ​ return 1+ Degree1(T->lchild) + Degree1(T->rchild); ​ else return Degree1(T->lchild) + Degree1(T->rchild); } 12.找最近公共祖先（求祖先都用后序遍历，因为栈保存的都是其祖先）

算法思想：后序遍历当找到任意一个时保存当前栈中的元素，若两个都找到后退出循环并遍历找公共组先

BTNode* PrintParents_qp(BiTree T, BTNode *x,BTNode *y) { ​ if (!T) return NULL; ​ BTNode *stack[10], *a[10], *b[10], *p = T, *r = NULL;//初始化栈 ​ int top = -1, pa = 0, pb = 0; ​ while (top != -1 || p != NULL) //栈非空或树未遍历完 ​ { ​ if (p) //走到最左边 ​ { ​ if (p == x) //若找到x，则保存此时的栈 ​ { ​ for (int i = 0; i <=top; i++) ​ a[i] = stack[i]; ​ pa = top; ​ } ​ if (p == y) //若找到y，则保存此时的栈 ​ { ​ for (int i = 0; i <= top; i++) ​ b[i] = stack[i]; ​ pb = top; ​ } stack[++top] = p; ​ p = p->lchild; ​ } ​ else ​ { ​ p = stack[top--];//出栈 ​ if (p->rchild&&p->rchild != r) //若右子树并且未遍历 ​ { ​ stack[++top] = p; //再把结点入栈并退出循环 ​ p = p->rchild; //右子树入栈 ​ } ​ else //否则直接继续循环 ​ { ​ r = p; ​ p = NULL; ​ } ​ } ​ } ​ //找公共祖先 ​ int i=0; ​ for(i=0; a[i] == b[i]&&i<=pa&&i<=pb;i++) //找第一个不同的点 ​ return a[i - 1];//返回前驱 } 13**.已知一颗满二叉树的先序序列为pre，求其后续序列post,二分法**

算法思想：因为先序第一个是根结点，后续最后一个是根结点，并且满二叉树的任意一个结点的左右子树均有相等的结点数，所以将先序的第一个放到后续的最后一个，再将先序除第一个结点的剩下所有结点分成两份继续执行上述操作。

void pre_post1(int pre[], int a1, int a2, int post[], int b1, int b2) { ​ int half; ​ if (a1 <= a2)//若pre[]的首和尾位置合法 ​ { ​ post[b2] = pre[a1]; ​ half = (a2 - a1) / 2; ​ pre_post(pre, a1 + 1, a1 + half, post, b1, b1 + half - 1); ​ pre_post(pre, a1 + half + 1, a2, post, b1 + half, b2-1); ​ } } 14.二叉排序树（BST） 14.1二叉排序树插入操作

算法思想：若根为空将要插入的值设置为根节点；若树中存在相同的值则返回0；若小于结点的值则插入到左子树中；若大于结点的值则插入到右子树

int BST_Insert(BiTree &T, int key)//二叉树插入操作，因为会改变树所以用&T { ​ if (T == NULL) //原树为空，新插入的记录为根节点 ​ { ​ T = (BTNode *)malloc(sizeof(BTNode)); ​ T->data = key; ​ T->lchild = T->rchild = NULL; ​ return 1; //返回1，插入成功 ​ } ​ else if (T->data == key)//若树中存在相同关键字，则插入失败 ​ return 0; ​ else if (T->data > key) //插入到T的左子树中 ​ return BST_Insert(T->lchild, key); ​ else //插入到T的右子树中 ​ return BST_Insert(T->rchild, key); } 14.2二叉排序树搜索操作

算法思想：若等于结点的值或结点为空则返回结点；若小于结点的值则搜索左子树；若大于结点的值则搜索右子树

BTNode * BST_Search(BiTree T, int key)//非递归查找算法 { ​ while (T&&T->data != key)//若树非空或不等于结点值 ​ { ​ if (key < T->data) T = T->lchild;//若小于则向左查找 ​ else T = T->rchild; //若大于则向右查找 ​ } ​ return T; } 14.3二叉排序树构造操作

算法思想：通过二叉树的插入算法，将数组中的所有结点都依次插入到二叉排序树中

void Creat_BST(BiTree &T, int str[], int n)//构造二叉树 { ​ T = NULL; //初始时T为空树 ​ int i = 0; ​ while (i < n) //依次将数组中的关键字插入到二叉排序树中 ​ { ​ BST_Insert(T, str[i]); ​ i++; ​ } } 14.4判断是否是二叉排序树

算法思想：若当前结点小于左子树或者小于右子树则返回false，若为空返回true，否则返回左右子树相与

bool Decide(BiTree T) { ​ if (!T) return true; ​ if (T->lchild&&T->lchild->data > T->data) return false; ​ if (T->rchild&&T->rchild->data < T->data) return false; ​ return Decide(T->lchild) && Decide(T->lchild); } 15.判断是否是平衡二叉树

算法思想:设置二叉树的平衡标记balance，标记返回二叉树T是否为平衡二叉树，若为平衡二叉树则返回1，否则返回0；h为二叉树T的高度。采用后序遍历的递归算法：

①若T为空，则高度为0，balance=1；

②若T为仅有根结点（即叶子结点），则高度为1，balance=1；

③否则，对T的左右子树进行递归操作，返回左右子树的高度和平衡标记，

T的高度为最高的子树的高度+1.

若左右子树的高度差大于1，则balance=0；

若左右子树的高度差小于等于1，*且左右子树都平衡时*，balance=1，否则balance=0.

void Judge_AVL(BiTree T, int &balance, int &h)//加上取地址符 //balance返回是否是平衡二叉树，若是则返回1，否则返回0；h是二叉树的高度 { ​ int bl = 0, br = 0, hl = 0, hr = 0; //左右子树的平衡标记和高度 ​ if (!T) //空树，高度为0 ​ { ​ h = 0; ​ balance = 1; ​ } ​ else if (T->lchild == NULL && T->rchild == NULL) ​ { //若为根结点，则高度为1 ​ h = 1; ​ balance = 1; ​ } ​ else ​ { ​ Judge_AVL(T->lchild, bl, hl); //判断左子树 ​ Judge_AVL(T->rchild, br, hr); //判断右子树 ​ h = (hl > hr ? hl : hr) + 1; ​ balance = bl&&br; //若左右子树都平衡时，二叉树平衡 ​ else ​ balance = 0; ​ } } 五、串 1.存储结构

①定长顺序存储

typedef struct SString selected选定 { char ch[Max_Size]; //每个分量存储一个字符 int length; //串的实际长度 }SString;

②堆分配存储

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

③块链存储(eg大小为1的链表)

typedef struct LString { char data; //按串长分配存储区，ch指向串的基地址 struct LString *Next; //指向下一个结点 }LString; 2.KMP void get_next(String T, int next[]) { ​ int i = 1, j = 0; //i表示next的位置 ​ next[1] = 0; //初始化第一个值 ​ while (i < T.length) ​ { ​ if (j == 0 || T.c[i] == T.c[j]) ​ { ​ next[++i] = ++j; //若pi=pj，则next[j+1]=next[j]+1 ​ } ​ else ​ j = next[j]; //否则令j=next[j]，循环继续 ​ } } int KMP(String S, String T, int next[]) { ​ int i = 1, j = 1; ​ while (i < S.length&&j < T.length) ​ { ​ if (j == 0 || S.c[i] == T.c[j]) ​ { ​ i++; j++; ​ } ​ else ​ j = next[j]; ​ } ​ if (j > T.length)//此时j=T.length+1；因为上面一步会j++ ​ return i - T.length;//匹配成功 ​ else ​ return 0; } 六、栈和队列 1.栈的存储结构

①顺序存储

typedef struct Stack //顺序栈 { ​ int data[Max_Size]; //值域 ​ int top; //栈顶指针 }Stack;

②链式存储：入栈和出栈在对头进行

typedef struct LStack //链式队列 { ​ int data; //值域 ​ struct LStack *Next; //指针域 }LStack; 2.队列的存储结构

①顺序存储

typedef struct Queue //顺序队列的结点 { ​ int data[Max_size]; //值域 ​ int front, rear; //队头指针和队尾指针 }Queue;

②链式存储

typedef struct LinkNode //链式队列的结点 { ​ int data; //值域 ​ struct LinkNode *Next; //指针域 }LinkNode; typedef struct LQueue //链式队列 { ​ struct LinkNode *front, *rear; //队列的头结点和尾结点 }LQueue; 七、线性表 存储结构

①顺序存储

静态分配：

typedef struct SqList { int data[Max_Size]; //顺序表元素 int length; //表长度 }SqList;

②堆分配存储

typedef struct SqList { int * data; //动态分配数组的指针 int length; //表长度 }SqList;

②链式存储

typedef struct LNode //单链表 { ​ int data; //值域 ​ struct LNode *Next; //指针域 }LNode;