数据结构经典算法总复习（下卷）

第五章:树和二叉树

先序遍历二叉树的非递归算法。

void PreOrderTraverse(BiTree T, void (*Visit)(TElemType)) {//表示用于查找的函数的指针Stack S; BiTree p = T;InitStack(S);//S模拟工作栈while (p || !StackEmpty(S)) {//S为空且下一个结点为空，意味着结束遍历if (p) {//p有值，则Push进栈为一个工作进程Visit(p->data); Push(S, p); p = p->lchild;//先序遍历，先Visit} else {
//p为空，则它的上级被Pop出去，成为新的p，再取右孩子。在下一个循环中如果它的上级没右孩子，则说明它的上级是叶子结点（或两端已经工作栈弹出了），则再Pop出它的上级的上级（此时它的上级已经无用，工作栈弹出），取它上级的兄弟结点Pop(S, p); p = p->rchild;}}
}

利用工作栈的思想，过程十分复杂，多多复习，巩固加深！

层序遍历二叉树

void LayerTraverse(BiTree T, void (*Visit)(TElemType)) {Queue Q; BiTree p;InitQueue(Q);EnQueue(Q, T);while (!QueueEmpty(Q)) {DeQueue(Q, p);
//每有一个父母结点出队列，就把它的左右孩子放到队尾排队，确保一层一层遍历if (p) {Visit(p->data);EnQueue(Q, p->lchild); EnQueue(Q, p->rchild);}}
}

计算二叉树中每个结点的层次

void LevelRecur(BiTree T, int lev) {if (T) {++lev;//准备遍历下一层cout << T->data << ' ' << lev << endl;LevelRecur(T->lchild, lev);LevelRecur(T->rchild, lev);//下一层启动}
}
void Level(BiTree T) {LevelRecur(T, 0);
}

输出二叉树根结点到所有叶子结点的路径

void OutPath(BiTree T, Stack &S) {//使用一个栈存储路径，起到回溯的作用if (T) {Push(S, T);if (!T->lchild && !T->rchild)PrintStack(S);//S栈中元素依次输出，不取出OutPath(T->lchild, S);OutPath(T->rchild, S);Pop(S, T);//该节点左右孩子搜索完，则出栈，不再计入路径中}
}

由扩展的先序序列，即波兰式，建立二叉树

void CreateBiTree(BiTree &T) {// 读入扩展的先序序列，假定数据元素为字符型，#表示NULLchar ch; scanf("%c", &ch);if (ch == '#') T = NULL;else {T = new BiTNode; T->data = ch;CreateBiTree(T->lchild);//依次建立二叉树CreateBiTree(T->rchild);}
}

先根遍历树，孩子链表实现

void PreOrderRecur(CTree T, int loc, void (*Visit)(TElemType)) {if (loc == -1) return;Visit(T.nodes[loc].data);//先查询根结点ChildPtr p;for (p = T.nodes[loc].firstchild; p; p = p->next) {PreOrderRecur(T, p->child, Visit);//取出下个孩子，并查询}
}
void PreOrderTree(CTree T, void (*Visit)(TElemType)) {PreOrderRecur(T, T.root, Visit);
}

计算树的深度，孩子兄弟链表实现

int TreeDepth(CSTree T) {if (!T) return 0;//最简单情况，遍历结束条件CSTree p; int maxh = 0;//maxh为全局变量for (p = T->firstchild; p; p = p->nextsibling) {//到T的下一个孩子，并且遍历其孩子的兄弟int h = TreeDepth(p);//当前遍历结点的深度if (h > maxh) maxh = h;}return maxh + 1;
}

构造huffman树

typedef unsigned int WeightType;
typedef struct {TElemType data;WeightType weight; // 叶子权值的类型int parent, lchild, rchild; // 三叉静态链表
} HTNode, *HuffmanTree;
void CreateHuffmanTree(HuffmanTree &HT, int n) {int m = 2*n-1; // 最终将得到2n-1个结点HT = new HTNode[m];for (i=0; i<n; ++i) {cin >> HT[i].data >> HT[i].weight;HT[i].lchild = HT[i].rchild = HT[i].parent = -1;//-1即示意为为null}//输入结点值for (i=n; i<m; ++i) {Select(HT, i-1, s1, s2); HT[s1].parent=HT[s2].parent=i;HT[i].weight = HT[s1].weight + HT[s2].weight;//两个结点的父母的权值为它们加和HT[i].lchild=s1; HT[i].rchild=s2; HT[i].parent = -1;}
}const unsigned int MAX_WEIGHT = UINT_MAX;
void Select(HuffmanTree HT, int s, int &l, int &r) {// 本函数的作用是从HT[0..s]中找到权值最小的两个结点WeightType WL = MAX_WEIGHT, WR = MAX_WEIGHT;for (i=0; i<=s; ++i) {if (HT[i].parent == -1) {if (HT[i].weight < WL) {WR = WL; WL = HT[i].weight; r=l; l=i;} else if (HT[i].weight < WR) {WR = HT[i].weight; r=i;}}}
}

第六章：图

深度优先遍历DFS

bool visited[MAX_VERTEX_NUM];
void DFS(Graph G, int v) {//类似于先根遍历Visit(v); visited[v] = true;for (int w=AdjVex(G, v); w != -1; w=AdjVex(G, v, w)) {if (!visited[w])DFS(G, w);}
}
void DFSTraverse(Graph G) {for (int v=0; v<G.vexnum; ++v)visited[v] = false;//初始化visited表for (int v=0; v<G.vexnum; ++v)if (!visited[v])DFS(G, v);//如果没有查找到没遍历过的，则弹出工作栈，返回上一级
}
int AdjVex(MGraph G, int v, int w=-1) {//邻接矩阵for (int j=w+1; j<G.vexnum; ++j)if (G.arcs[v][j] != INFINITY) return j;//找找它可能的出路return -1;
}int AdjVex(ALGraph G, int v, int w=-1) {//邻接表ArcNode *p = G.vertices[v].firstarc;if (w != -1) {while (p && p->adjvex != w) p = p->nextarc;if (p) p = p->nextarc;}return p ? p->adjvex : -1;
}

广度优先搜索BFS

bool visited[MAX_VERTEX_NUM];
void BFS(Graph G, int v) {//类似于层序遍历Visit(v); visited[v] = true;Queue Q; InitQueue(Q); EnQueue(Q, v);while (!QueueEmpty(Q)) {DeQueue(Q, v);for (int w=AdjVex(G, v); w != -1; w=AdjVex(G, v, w)) {if (!visited[w]) {Visit(w); visited[w] = true; EnQueue(Q, w);}}}
}
void BFSTraverse(Graph G) {for (int v=0; v<G.vexnum; ++v)visited[v] = false;//初始化for (int v=0; v<G.vexnum; ++v)if (!visited[v])BFS(G, v);
}

利用DFS求简单路径

bool visited[MAX_VERTEX_NUM];
bool DFS_SimplePathRecur(Graph G, int vi, int vj, Stack &S) {Push(S, vi); visited[vi] = true;//S存储过往路径if (vi == vj) {Print(S); return true;}for (int w=AdjVex(G, vi); w != -1; w=AdjVex(G, vi, w)) {if (!visited[w]) {if (DFS_SimplePathRecur(G, w, vj, S))return true;}}Pop(S, vi); visited[vi] = false; return false;
}
void DFS_SimplePath(Graph G, int vi, int vj) {Stack S; InitStack(S);for (int v=0; v<G.vexnum; ++v)visited[v] = false;if (DFS_SimplePathRecur(G, vi, vj, S))cout << "Found a path" << endl;
}

使用Prim算法，得出最小生成树

void Prim(MGraph G, int v0) {// 用于存储F集合的两个数组：邻接顶点和最小边int adjvex[MAX_VERTEX_NUM], lowcost[MAX_VERTEX_NUM];for (int j=0; j<G.vexnum; ++j) {if (j!=v0) {adjvex[j] = v0;lowcost[j] = G.arcs[v0][j];}}lowcost[v0] = INFINITY;for (int i=0; i<G.vexnum-1; ++i) { // 循环n-1次int k = MinEdge(lowcost, G.vexnum);//该顶点的连接的最小边printf("(%d, %d): %d\n", k, adjvex[k], lowcost[k]);lowcost[k] = INFINITY;for (int j=0; j<G.vexnum; ++j) {if (G.arcs[k][j] < lowcost[j]) {adjvex[j] = k;lowcost[j] = G.arcs[k][j];}}}
}

得出拓扑排序

void TopologicalSort(ALGraph G) {//思路找头结点，并删除它和它连接的路径，继续下一个int InDegree[MAX_VERTEX_NUM];FindInDegree(G, InDegree);Stack S; InitStack(S);for (int i=0; i<G.vexnum; ++i)if (!InDegree[i]) Push(S, i);int count = 0; // 统计输出顶点的个数while (!StackEmpty(S)) {int i; Pop(S, i); ++count;cout << G.vertices[i].data << endl; ArcNode *p;for (p=G.vertices[i].firstarc; p; p=p->nextarc) {k = p->adjvex;if (!(--InDegree[k])) Push(S, k);}}if (count<G.vexnum)cout << "The graph has loop" << endl;
}void FindInDegree(ALGraph G, int *InDegree) {for (int i=0; i<G.vexnum; ++i) InDegree[i] = 0;for (int i=0; i<G.vexnum; ++i) {for (ArcNode *p=G.vertices[i].firstarc; p; p=p->nextarc) {InDegree[p->adjvex]++;}}
}

第七章：查找表

二分查找（折半查找）静态表

int Search_Bin(StaticSearchTable ST, KeyType key) {//其中ST为从小到大的顺序表int low=1, high=ST.length;while (low <= high) {mid = (low + high) / 2;if (key == ST.data[mid].key) return mid;else if (key < ST.data[mid].key) high = mid - 1;//取前一半else low = mid + 1;//取后一半}return 0;
}

二叉查找树的查找方法（递归算法）

BiTree Search_BST(BiTree T, KeyType key) {//题外话：对二叉查找树进行中序遍历可得到有序数列if (!T || key == T->data.key)return T;else if (key < T->data.key)//此时的左右孩子被赋予了更多意义return Search_BST(T->lchild, key);elsereturn Search_BST(T->rchild, key);
}

二叉查找树的查找方法（非递归算法）

bool SearchBST(BiTree T, KeyType key, BiTree &p, BiTree &f) {// 若查找到key，则返回true，此时p指向等于key的// 结点，f是p的双亲（若p等于根结点，则f为NULL）// 若查找不到key，则返回false，此时p为NULL，f// 指向查找过程中最后一个比较的结点f = NULL; p = T;while (p && key != p->data.key) {f = p;//保存f，则允许了回溯到父母结点的操作if (key < p->data.key) p = p->lchild;//向左走呢，还是向右走呢？else p = p->rchild;}if (!p) return false;else return true;
}

二叉查找树的插入

bool InsertBST(BiTree &T, KeyType key) {BiTree p, f;bool found = SearchBST(T, key, p, f);if (found) return false;//查找成功，则不插入；
//反之，在查找失败的查找路径上最后一个结点的左或右插入BiTree t = new BiTNode;t->data.key = key; t->lchild = t->rchild = NULL;if (!f) T = t;//如果二叉树为空，则插入第一条数据else if (key < f->data.key) f->lchild = t;else f->rchild = t;return true;
}

二叉查找树的删除

bool DeleteBST(BiTree &T, KeyType key) {BiTree p, f;bool found = SearchBST(T, key, p, f);if (!found) return false;if (p->lchild && p->rchild) {//有左右孩子的条件BiTree q = p, t = p->rchild;//将结点替代为右子树上最小的结点（也可为左子树上最大的结点）while (t->lchild) { q = t; t = t->lchild; }//一直向左子树查找，找到“最左”的t，即最小p->data = t->data;//替代if (q != p) q->lchild = t->rchild;//q为t的双亲，由于t无左子树，则只需要将t的右子树接到q上即可完成交接t的转移。else q->rchild = t->rchild; delete t;//如果p是t的双亲，则直接插上} else {BiTree q = p->lchild ? p->lchild : p->rchild;if (!f) T = q;else if (p == f->lchild) f->lchild = q;else f->rchild = q; delete p;}return true;
}

写出判别一颗二叉树是否为二叉排序树的算法，设二叉排序树中不存在关键字值相同的结点。

elemType arr[MAXN]; // 存放中序遍历结果
int k=0; // 记录访问过的结点数
void Inorder_Traversal (TreeNode∗ T){if (!T) return;Inorder_Traversal (T−>left);arr [k] = T−>val; // 记录结点值k++;Inorder_Traversal (T−>right, arr);
}bool Is_Binary_Sort_Tree(TreeNode∗ T){Inorder_Traversal (T); // 先中序遍历for (int i=1; i<k; i++)if (arr [ i ] <= arr[i−1]) // 判断是否递增return false ;return true;
}

第八章：排序

简单排序

void SelectSort(SqTable &L) {for (int i=1; i<L.len; ++i) {int j=i;for (int k=L.len; k>i; --k)if (L.r[k].key < L.r[j].key) j=k;if (i!=j) {// 这里我们将L.r[i]和L.r[j]交换// 另一种做法是将L.r[i..j-1]各个后移一位，然后令L.r[i]=L.r[j]RcdType tmp = L.r[i]; L.r[i] = L.r[j]; L.r[j] = tmp;}}
}

冒泡排序

void BubbleSort(SqTable &L) {bool change = true;for (int i=n; i>=2 && change; --i) {// 这里我们设置一个标记，如果j从1到i-1循环中没有发生元素的互换// 说明整个序列已经是有序的了，无需考虑更小的ichange = false;for (int j=1; j<=i-1; ++j) {if (L.r[j].key > L.r[j+1].key) {RcdType tmp = L.r[j]; L.r[j] = L.r[j+1]; L.r[j+1] = tmp;change = true;}}}
}

插入排序

void InsertSortSub(SqTable &L, int low, int high) {// 这个子函数对L.r[low..high]做简单插入排序for (int i=low+1; i<=high; ++i)if (L.r[i].key < L.r[i-1].key) {RcdType tmp = L.r[i];for (int j=i-1; tmp.key < L.r[j].key && j>=low; --j)L.r[j+1] = L.r[j]; // 元素后移L.r[j+1] = tmp;      // 插入到合适位置}
}
void InsertSort(SqTable &L) {InsertSortSub(L, 1, L.len);
}

希尔排序

void ShellSortSub(SqTable &L, int dk) {// 一趟增量为dk的插入排序for (int i=dk+1; i<=L.len; ++i) {if (L.r[i].key < L.r[i-dk].key) {RcdType tmp = L.r[i];for (int j=i-dk; tmp.key < L.r[j].key && j>=1; j-=dk)L.r[j+dk] = L.r[j];L.r[j+dk] = tmp;}}
}
void ShellSort(SqTable &L, int delta[], int k) {// delta是每趟排序的增量值for (int i=0; i<k; ++i)ShellSortSub(L, delta[i]);
}

快速排序

void QSort(SqTable &L, int low, int high) {// 对L[low..high]进行快速排序if (low < high) {int pivotloc = Partition(L, low, high);QSort(L, low, pivotloc-1);QSort(L, pivotloc+1, high);}
}
void QuickSort(SqTable &L) {QSort(L, 1, L.len);
}
int Partition(SqTable &L, int low, int high) {// 选择一个枢轴，将L.r[low..high]分为两部分// 返回枢轴最后所在的位置，以便进一步划分// 划分以后，在枢轴之前（之后）的元素都小于（大于）或等于枢轴int pivotloc = low; // 枢轴可以任意选取，例如取第一个位置RcdType tmp = L.r[pivotloc];KeyType pivotkey = tmp.key;while (low<high) {while (low<high && L.r[high].key>=pivotkey) --high;L.r[low] = L.r[high];while (low<high && L.r[low].key<=pivotkey) ++low;L.r[high] = L.r[low];}L.r[low] = tmp;return low;
}

堆排序

void HeapAdjust(SqTable &L, int s, int m) {// 已知L.r[s..m]中除了L.r[s]以外，都满足大顶堆的定义// 本函数通过调整，使得L.r[s..m]成为一个大顶堆RcdType tmp = L.r[s];for (int i=2*s; i<=m; i*=2) { // 每次向下一层if (i<m && L.r[i].key<L.r[i+1].key) ++i;if (tmp.key >= L.r[i].key) break; // 已经找到合适的位置L.r[s] = L.r[i]; s = i; // 与孩子换位}L.r[s] = tmp;
}
void HeapSort(SqTable &L) {int i; RcdType tmp;for (i=L.len/2; i>0; --i)HeapAdjust(L, i, L.len); // 构造初始大顶堆for (i=L.length; i>1; --i) {tmp = L.r[i];L.r[i] = L.r[1];L.r[1] = tmp; // 将最大的关键字放到L.r[i]HeapAdjust(L, 1, i-1); // 对L.r[1..i-1]调用筛选法重新调整为堆}
}

归并排序

void Merge(RcdType* Rs, RcdType* Rt, int s, int m, int t) {// 已知Rs[s..m]和Rs[m+1..t]都是有序表，将它们归并存储到Rt[s..t]int i,j,k;for (i=s, j=m+1, k=s; i<=m && j<=t; ++k) {//两表的排序在此处if (Rs[i].key <= Rs[j].key) Rt[k] = Rs[i++];else Rt[k] = Rs[j++];}for (; i<=m; ++i, ++k) Rt[k] = Rs[i];//当一个有序表取完时，剩下直接安进去for (; j<=t; ++j, ++k) Rt[k] = Rs[j];
}
void MSort(RcdType* Rs, RcdType* Rt, int low, int high) {//递归算法if (low < high) {//low=high时，无需归并int mid = (low+high)/2;MSort(Rs, Rt, low, mid); MSort(Rs, Rt, mid+1, high);Merge(Rs, Rt, low, mid, high);for (int i=low; i<=high; ++i) Rs[i] = Rt[i];//将Rt复制到Rs上}
}
void MergeSort(SqTable &L) {RcdType* tmp = new RcdType[L.len+1];MSort(L.r, tmp, 1, L.len);delete []tmp;
}

基数排序

const int RADIX = 128; // 每个“基本关键字”的取值范围，称为基数
const int KEY_LENGTH = 5; // 共有5个“基本关键字”
typedef char KeyType[KEY_LENGTH]; // 关键字类型为长度为5的字符串
void RadixPass(RcdType *R, RcdType *T, int n, int k) {int j; int count[RADIX];for (j=0; j<RADIX; ++j) count[j] = 0;for (j=1; j<=n; ++j) count[R[j].key[k]]++;for (j=1; j<RADIX; ++j) count[j] = count[j-1] + count[j];for (j=n; j>0; --j) {int p = R[j].key[k]; T[count[p]] = R[j]; count[p]--;}for (j=1; j<=n; ++j) R[j] = T[j];
}
void RadixSort(SqTable &L) {RcdType *tmp = new RcdType[L.len+1];for (int k = KEY_LENGTH-1; k>=0; --k)RadixPass(L.r, tmp, L.len, k);delete []tmp;
}