说明 本文整合自王道和里昂学长的PPT（无盈��侵权必删），是完整的408代码大题解题方案，整合好的pdf文档可以联系我获取
快速排序 代码实现
快速排序算法以huafen()函数为核心
如何划分？ 第一趟
首先将左指针L对应的数组元素设为mid值，我们之后要将mid值和其他值对比然后找到mid值该在的位置
先从R向前寻找第一个小于mid的值（如果没有R- -一直找），如果有，就把他和目前存着mid值的A[L]互换位置
再从L向后寻找第一个大于mid的值（如果没有L++一直找），如果有，就把上一步的A[R]换过来
第二趟
上一趟完成了第一次交换，把小于mid的换到了右边，而把大于mid的换到了左边
第二趟又在新的R找到了小于mid的元素，放在之前发现的左边覆盖，以此类推
最后一趟
当最后一趟开始时，若是L++导致L==R则
A[L]换上了右边更小一点的元素。
而下一步L++，已不满足L<R的条件。而这一步的L就是上一步的R(L==R )，A[R]的值已经迁移到了其左边。
因此设A[L]=mid，就把两者很好的拆开了
当最后一趟开始时，若是R- -导致L==R则
也就是上一趟将**大于mid的A[L]**的值放到右边时，将较大的值换到了A[R]中。
此时R- -到R==L ，因此此时A[L]中的存储的是已经是到了还没有**R–**时的右边。
因此A[L]=mid，即可拆开
快速排序算法 因此在快排中调用这段代码
先将A中的LR成以mid为中间的两段，左边小于mid，右边大于mid
我们的划分传来的是mid的位置，因此要想把整个数组排序好，只需要排好左右一直调用。
将数组的最左边L和mid的前一个位置进行划分，穷举下去即可解决
完整代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 void Qsort (int A[], int L, int R) { if (L > R) return ; int M = huafen(A, L, R); Qsort(A, L, M-1 ); Qsort(A, M+1 , R); } int huafen (int A[], int L, int R) { int mid = A[L]; while (L < R) { while (A[R] >= mid && L < R) R--; A[L] = A[R]; while (A[L] <= mid && L < R) L++; A[R] = A[L]; } A[L] = mid; return L; }
划分函数的妙用 求数组中第k小元素的方法
按理说我们只需要快速排序好，再直接利用数组的随机查找特性找到A[k-1]就可以
但是huafen函数可以直接找到某个元素的具体位置，我们可以直接用M接收huafen函数传来的此时的位置
若这个位置比已知位置小，则k-1在M前面，则设L=M+1继续试
1 2 3 4 5 6 7 8 9 10 int func (int A[], int n, int k) { int L = 0 , R = n - 1 , M = 0 ; while (1 ) { M = huafen(A, L, R); if (M == k - 1 ) break ; else if (M > k - 1 ) R = M - 1 ; else if (M < k - 1 ) L = M + 1 ; } return A[k-1 ]; }
归并排序 归并排序用于两个数组排到一个数组里的排序中
1 2 3 4 5 6 7 8 9 10 11 12 13 14 int Merge (int A[], int N, int B[], int M, int C[]) { int i = 0 , j = 0 , k = 0 ; while (i < N && j < M) { if (A[i] <= B[j]) C[k++] = A[i++]; else C[k++] = B[j++]; } while (i < N) C[k++] = A[i++]; while (j < M) C[k++] = B[j++]; return 1 ; }
链表 查找+删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void deletX (LinkList L, int x) { LNode *pre = L; LNode *p = pre->next; while (p != NULL ) { if (p->data == x) { LNode *q = p; p = p->next; pre->next = p; free (q); } else { pre = p; p = p->next; } } }
查找+插入
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 void InsertX (LinkList L, int x) { LNode *pre = L; LNode *p = pre->next; while (p != NULL ) { if (p->data > x) { break ; } else { pre = p; p = p->next; } } LNode *q = (LNode *)malloc (sizeof (LNode)); q->data = x; q->next = p; pre->next = q; }
头插法（原地逆转链表）
在勾画的绿色部分正是逆置的核心出装，将新插入的结点（在原链表中更靠后）不断放前，而实现逆置
1 2 3 4 5 6 7 8 9 10 11 12 13 14 void ListReserve (LinkList L) { LinkList head = (LNode *) malloc (sizeof (LNode)); head->next = NULL ; while (L->next != NULL ){ LNode *p = L->next; L->next = L->next->next; p->next = head->next; head->next = p; } L->next = head->next; free (head); }
尾插法保持原序
以下是我自己写的代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 void ListPart (LinkList C) { LinkList A = (LNode*)malloc (sizeof (LNode)); LinkList B = (LNode*)malloc (sizeof (LNode)); A->next = NULL ; B->next = NULL ; int count = 1 ; LNode *q = A; while (C->next != NULL ) { LNode *p = C->next; C->next = C->next->next; if (count % 2 == 1 ) { p->next = NULL ; q->next = p; q = p; } else { p->next = B->next; B->next = p; } count++; } free (C); }
二叉树 前/中/后序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 typedef struct BiTNode { int data; struct BiTNode *lchild ,*rchild ; }BiTNode,*BiTree; void PreOrder (BiTree root) { if (root==NULL ) return ; visit(root); PreOrder(root->lchild); PreOrder(root->rchild); } void InOrder (BiTree root) { if (root==NULL ) return ; InOrder(root->lchild); visit(root); InOrder(root->rchild); } void PostOrder (BiTree root) { if (root==NULL ) return ; PostOrder(root->lchild); PostOrder(root->rchild); visit(root); }
层序遍历 在层序遍历中需要使用到队列，也就需要队列的操作
1 2 3 4 5 6 7 8 void InitQueue (Queue &Q) bool IsEmpty (Queue Q) void EnQueue (Queue &Q, BiTNode * x) void DeQueue (Queue &Q, BiTNode * &x)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 void LevelOrder (BiTree T) { Queue Q; InitQueue(Q); BiTree p; EnQueue(Q, T); while (!IsEmpty(Q)){ DeQueue(Q, p); visit(p); if (p->lchild != NULL ) EnQueue(Q, p->lchild); if (p->rchild != NULL ) EnQueue(Q, p->rchild); } }
求树高 （方法一）先序遍历 1 2 3 4 5 6 7 8 9 10 int height = 0 ; void PreOrder (BiTree T, int n) { if (T == NULL ) return ; if (n > height) height = n; PreOrder(T->lchild, n + 1 ); PreOrder(T->rchild, n + 1 ); }
调用时用**PreOrder(T, 1**)
原理是每过一层则+1并和目前高度比较
（方法二）后序遍历 1 2 3 4 5 6 7 8 9 10 int PostOrder (BiTree T) { if (T == NULL ) return 0 ; int left = PostOrder(T->lchild); int right = PostOrder(T->rchild); if (left > right) return left + 1 ; else return right + 1 ; }
以该图为例，g和h没有左右结点了，故直接返回0+1给e作为e的left和right，e再进行比较以大的深度+1作为自己的深度交给b，b也这么做并和c一起交给a
后序遍历以孩子出发从孩子开始数并返给根节点最长的版���
������宽
此处先用先序遍历统计每一层的结点数，也就是使用先序遍历先根后孩子的特点来统计
1 2 3 4 5 6 7 8 9 int width[MAX]; void PreOrder (BiTree T, int level) { if (T == NULL ) return ; width[level]++; PreOrder(T->lchild, level + 1 ); PreOrder(T->rchild, level + 1 ); }
再找到宽度数组中最大的一项，将其作为树宽
1 2 3 4 5 6 7 8 9 10 11 12 13 14 void treeWidth (BiTree T) { for (int i = 0 ; i < MAX; i++) width[i] = 0 ; PreOrder(T, 0 ); int maxWidth = 0 ; for (int i = 0 ; i < MAX; i++) { if (width[i] > maxWidth) maxWidth = width[i]; } printf ("树的宽度是%d" , maxWidth); }
树WPL
求树的WPL还是要使用树的先序遍历
使用了求树高和树宽的思想
先找到叶子节点（也就是左右孩子为空）并且将此处的带权路径长度加入WPL
如果不是叶子结点则向下找到其他叶子节点高度
1 2 3 4 5 6 7 void PreOrder (BiTree T, int level) { if (T == NULL ) return ; if (T->lchild==NULL && T->rchild==NULL ) WPL += level*T->weight; PreOrder(T->lchild, level + 1 ); PreOrder(T->rchild, level + 1 ); }
特殊树型判断 二叉排序树判定
中序遍历出来的序列是升序序列，所以���叉排序树序列中下一个结点必然大于前面所有的结点（也就是MAX{前面结点}）这里用temp表示
所以只要后面遍历到的小于temp，则直接判定��败
若不小于则继续向右子树遍历，直到为NULL退回
1 2 3 4 5 6 7 8 9 10 int temp=MIN_INT; bool isBST=true ; void InOrder (BiTree T) { if (T == NULL ) return ; InOrder(T->lchild); if (T->data >= temp) temp=T->data; else isBST=false ; InOrder(T->rchild); }
平衡二叉树判定
此树判定和方法二找树深一样
通过后序遍历的特点：先访问孩子再进行操作，由最后的孩子也就是结点A的左右子树都退回来自己的高度之后，再进行左右子树高度判断
1 2 3 4 5 6 7 8 9 10 11 12 13 14 bool isBalance=true ; int PostOrder (BiTree T) { if (T == NULL ) return 0 ; int left = PostOder(T->lchild); int right = PostOder(T->rchild); if (left-right>1 ) isBalance=false ; if (left-right<-1 ) isBalance=false ; if (left>right) return left+1 ; else return right+1 ; }
完全二叉树判定 这里先借用一下层序遍历的图
层序遍历，因为完全二叉树是按顺序排放，所以要看每一层的结点的逐个讨论、
四种情况分别在访问这个结点时讨论一次
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 bool isComplete = true ; bool flag = false ; void visit (BiTNode * p) { if (p->lchild == NULL && p->rchild == NULL ) { if (flag) { isComplete = false ; } flag = true ; } else if (p->lchild != NULL && p->rchild == NULL ) { if (flag) { isComplete = false ; } flag = true ; } else if (p->lchild == NULL && p->rchild != NULL ) { isComplete = false ; } else { if (flag) { isComplete = false ; } } }
图
图的数据结构定义 邻接矩阵 这是邻接矩阵的数据结构
这是邻接矩阵的初始化操作
邻接表 这是邻接表的数据结构，在图ALGraph中存储一个顶点表数组和顶点数和边数
在顶点表中存储这个结点的数据和第一个依附该点的边
边表则是指出这条边指向的点和下一条边的指针 以及该边权值
这个表依旧要执行初始化操作
先将顶点表数组中的第一条边全部置为NULL
再将其顶点数和边数先更新
用封装好的AddEdge(图,出点，入点，权值)函数添加边
AddEdge函数是这���写的
首先先创建一个边结点，将其的权值和指向的结点j配置好
再将他连接到i结点第一条边之前，让这条新边指向老的第一条边（类似头插法将靠后的插在头边）
最后让i的点表连接到这条边作为first
最后可以看到他的逻辑结构长这样
图的遍历 深度优先遍历
1 2 3 4 5 6 7 8 9 10 void DFS (MGraph G,int i) { visit(i); visited[i]=true ; for (int j=0 ;j<G.G.numVertices;j++) if (visited[j]==false &&G.edge[i][j]==1 ){ DFS(G,j); } }
首先先把第一个访问的结点打上true，对第一结点比如A，找他向别人发射过的边，直到j<G.vexnum（穷尽了所有点）
当到没有遍历到过的且存在的邻接点时，将其投DPS
然后一直DPS递归下去，直到再没有邻接的点，逐层返回没有访问完邻接点的结点中继续访问他们���接点
1 2 3 4 5 6 7 8 9 10 11 12 13 void DFS (ALGraph G,int i) { visit(i); visited[i]=true ; for (EdgeNode* p=G.VertexList[i].first ; p!=NULL ; p=p->next){ int j=p->index; if (visited[j]==false ){ DFS(G,j); } } }
前面步骤一样，依旧从i点开始遍历。先找到i点的第一个边，将其位置存放到p中
j就是此时p指向的点，若此点没��被访问过则开始深度遍历
直到遍历到最后一个���遍历到的点，就往上返回，继续访问之前没有访问完其他边的结���。
广度优先遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void BFS (MGraph G, int v) { visit(v); visited[v]=true ; EnQueue(Q, v); while (!isEmpty(Q)){ DeQueue(Q, v); for (int w=0 ; w<G.numVertices; w++){ if (visited[w]==false && G.edge[v][w]==1 ){ visit(w); visited[w]=true ; EnQueue(Q, w); } } } }
广度优先遍历类似于图的层序遍历
从v出发，先将v存入队列中
当队列不为空时就出队一个结点，并���从第0个结点开始遍历，寻找v指向的且没有被访问过的结点，找到一个入队一个直到找不到为止
然后从i结点找到的第一个结点开始继续重复这个步骤，直到所有结点都找完使队列为空
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 void BFS (ALGraph G, int v) { visit(v); visited[v]=true ; EnQueue(Q, v); while (!isEmpty(Q)){ DeQueue(Q, v); for (EdgeNode *p=G.VertexList[v].first; p!=NULL ; p=p->next){ int w = p->index; if (visited[w]==false ){ visit(w); visited[w]=true ; EnQueue(Q, w); } } } }
套路和上面一样，入队之后先找到第一个边指向的结点看是否被访问过，若没有则全部入队直到v结点没有邻接的点为止。
然后又从v第一条边邻接点继续广度优先遍历
拓扑排序 先按一下思路分析
拓扑排序的步骤:
选择入度为0的顶点并输出
从图中删除该顶点与所有以它为弧的边
重复步骤1、2，直到不存在入度为0的顶点
拓扑序列
条件
存在且唯一
每次选择结点都只有一个结点可选
存在不唯一
选择结点时不止一个结点可选
不存在
图中有环，环中顶点未被访问
先拿王道的流程图说一下思想
首先我们需要循环找到入度为0的点并且全部入队。
此处如果队列里元素个数超过1，
入度为0的点肯定超过2个也就是拓扑排序不唯一。
若是有多个连通分量，一个连通分量多个入度为0，另一个连通分量是有环图，则很明显不存在拓扑排序
然后当我们出队时，我们将计数器+1，来记录已经出队的数
出队之后将所有出队的点指向的点，把他们的入度-1，然后继续寻找入度为0的点循环这个过程
当队空之后我们根据count数进行判断
如果count等于顶点数，那么说明从顶点到最后一个点只有一条路径。没错，拓扑排序唯一 若count数不等于也就是小于顶点数，说明存在环路，始终有点入度不为0互相堵着
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 int uniquely1 (MGraph G) { int inDegree[MAXV] = {0 }; int queue [MAXV]; int front = 0 , rear = 0 ; int count = 0 ; for (int i = 0 ; i < G.vexnum; i++) { ArcNode *p = G.AdjList[i].firstarc; while (p != NULL ) { inDegree[p->adjvex]++; p = p->nextarc; } } for (int i = 0 ; i < G.vexnum; i++) { if (inDegree[i] == 0 ) queue [rear++] = i; } while (front < rear) { if (rear - front > 1 ) return 0 ; int v = queue [front++]; count++; ArcNode *p = G.AdjList[v].firstarc; while (p != NULL ) { inDegree[p->adjvex]--; if (inDegree[p->adjvex] == 0 ) queue [rear++] = p->adjvex; p = p->nextarc; } } if (count == G.vexnum) return 1 ; else return 0 ; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 int uniquely1 (MGraph G) { int inDegree[MAXV] = {0 }; int queue [MAXV]; int front = 0 , rear = 0 ; int count = 0 ; for (int i = 0 ; i < G.numVertices; i++) for (int j = 0 ; j < G.numVertices; j++) if (G.Edge[i][j] != 0 ) inDegree[j]++; for (int i = 0 ; i < G.numVertices; i++) if (inDegree[i] == 0 ) queue [rear++] = i; while (front < rear) { if (rear - front > 1 ) return 0 ; int v = queue [front++]; count++; for (int i = 0 ; i < G.numVertices; i++) if (G.Edge[v][i] != 0 ) { inDegree[i]--; if (inDegree[i] == 0 ) queue [rear++] = i; } } if (count == G.numVertices) return 1 ; else return 0 ; }
