1、数据(Data) ：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(Data Element) ：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。 数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={‘A’,’B’,’C,…} 。
数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型，如图1-3所示。
① 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。 ② 线性结构：结构中的数据元素之间存在一对一的关系。 ③ 树型结构：结构中的数据元素之间存在一对多的关系。
④ 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。 2、顺序结构：数据元素存放的地址是连续的；
链式结构：数据元素存放的地址是否连续没有要求。
数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。
3、C语言中用带指针的结构体类型来描述 typedef struct Lnode
{ ElemType data; /*数据域，保存结点的值 */ struct Lnode *next; /*指针域*/ }LNode; /*结点的类型 */ 4、循环队列为空：front=rear 。
循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。
i-1
5、性质1：在非空二叉树中，第i层上至多有2个结点(i≧1)。
k
性质2：深度为k的二叉树至多有2-1个结点（k≧1) 。
性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。
k
一棵深度为k且有2-1个结点的二叉树称为满二叉树(Full Binary Tree)。 完全二叉树的特点：若完全二叉树的深度为k ，则所有的叶子结点都出现在第k层或
k-1层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。
专业整理 知识分享
完美WORD格式
性质4：n个结点的完全二叉树深度为：㏒2n +1。
性质5：若对一棵有n个结点的完全二叉树(深度为└㏒2n┘+1)的结点按层（从第1层
到第㏒2n +1层)序自左至右进行编号,则对于编号为i（1≦i≦n)的结点：
⑴ 若i=1：则结点i是二叉树的根，无双亲结点；否则，若i>1，则其双亲结点编号是
i/2 。
⑵ 如果2i>n：则结点i为叶子结点，无左孩子；否则，其左孩子结点编号是2i。 ⑶ 如果2i+1>n：则结点i无右孩子；否则，其右孩子结点编号是2i+1。
6、线索二叉树：设一棵二叉树有n个结点，则有n-1条边(指针连线) ， 而n个结点共有
2n个指针域(Lchild和Rchild) ，显然有n+1个空闲指针域未用。则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。
7、Huffman树：具有n个叶子结点(每个结点的权值为wi) 的二叉树不止一棵，但在所有的
这些二叉树中，必定存在一棵WPL值最小的树，称这棵树为Huffman树(或称最优树) 。
专业整理 知识分享
完美WORD格式
8、完全无向图：对于无向图，若图中顶点数为n ，用e表示边的数目，则e [0，n(n-1)/2] 。具有n(n-1)/2条边的无向图称为完全无向图。 完全有向图：对于有向图，若图中顶点数为n ，用e表示弧的数目，则e[0，n(n-1)] 。具有n(n-1)条边的有向图称为完全有向图。
生成树、生成森林：一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树 关于无向图的生成树的几个结论：
1) 一棵有n个顶点的生成树有且仅有n-1条边；
2) 如果一个图有n个顶点和小于n-1条边，则是非连通图； 3) 如果多于n-1条边，则一定有环； 4) 有n-1条边的图不一定是生成树。
9、最小生成树(Minimum Spanning Tree) ：带权连通图中代价最小的生成树称为最小生成树。
最小生成树在实际中具有重要用途，如设计通信网。设图的顶点表示城市，边表示两个城市之间的通信线路，边的权值表示建造通信线路的费用。n个城市之间最多可以建n(n-1)/2条线路，如何选择其中的n-1条，使总的建造费用最低?
专业整理 知识分享
完美WORD格式
10、工程完成最短时间：从起点到终点的最长路径长度(路径上各活动持续时间之和) 。长度最长的路径称为关键路径，关键路径上的活动称为关键活动。关键活动是影响整个工程的
关键。
11、查找方法比较
ASL 表结构
顺序查找 最大
折半查找 最小
分块查找 两者之间 分块有序表 顺序存储结构
有序表、无序表 有序表 顺序存储结构
存储结构
线性链表
顺序存储结构
线性链表
12、在随机情况下，二叉排序树的平均查找长度ASL和㏒(n)(树的深度)是等数量级的。
专业整理 知识分享
完美WORD格式
二叉排序树(Binary Sort Tree或Binary Search Tree) 的定义为：二叉排序树或者是空树，或者是满足下列性质的二叉树。
(1) ：若左子树不为空，则左子树上所有结点的值(关键字)都小于根结点的值； (2) ：若右子树不为空，则右子树上所有结点的值(关键字)都大于根结点的值； (3) ：左、右子树都分别是二叉排序树。
结论：若按中序遍历一棵二叉排序树，所得到的结点序列是一个递增序列。
13、平衡二叉树或者是空树，或者是满足下列性质的二叉树。 ⑴：左子树和右子树深度之差的绝对值不大于1； ⑵：左子树和右子树也都是平衡二叉树。
平衡因子(Balance Factor) ：二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子。
平衡二叉排序树上进行查找的平均查找长度和㏒2n是一个数量级的，平均时间复杂度为O(㏒2n)。
四种平衡化旋转，其正确性容易由“遍历所得中序序列不变”来证明。并且，无论是哪种情况，平衡化旋转处理完成后，形成的新子树仍然是平衡二叉排序树，且其深度和插入前以a为根结点的平衡二叉排序树的深度相同。所以，在平衡二叉排序树上因插入结点而失衡，仅需对失衡子树做平衡化旋转处理。
14、一棵m阶B_树，或者是空树，或者是满足以下性质的m叉树： ⑴ 根结点或者是叶子，或者至少有两棵子树，至多有m棵子树；
⑵ 除根结点外，所有非终端结点至少有m/2棵子树，至多有m棵子树； ⑶ 所有叶子结点都在树的同一层上； ⑷ 每个结点应包含如下信息：
(n，A0，K1，A1，K2，A2，… ，Kn，An)
其中Ki(1≤i≤n)是关键字，且Ki 即在含有n个关键字的B_树上进行查找时，从根结点到待查找记录关键字的结点的路径上所涉及的结点数不超过1+ ㏒m/2((n+1)/2) 。 ++ 15、m阶B树。 它与B_树的主要不同是叶子结点中存储记录。在B树中，所有的非叶子结点可以看成是索引，而其中的关键字是作为“分界关键字”，用来界定某一关键字的记录 + 所在的子树。一棵m阶B树与m阶B_树的主要差异是： ⑴ 若一个结点有n棵子树，则必含有n个关键字； ⑵ 所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接； 专业整理 知识分享 完美WORD格式 ⑶ 所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大(或最小)关键字。 16、哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。可写成：addr(ai)=H(ki) ，其中i是表中一个元素，addr(ai)是ai的地址， ki是ai的关键字。 哈希表：应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。 哈希查找(又叫散列查找)：利用哈希函数进行查找的过程叫哈希查找。 例1 ：设散列表长为7，记录关键字组为：15, 14, 28, 26, 56, 23，散列函数：H(key)=key MOD 7，冲突处理采用线性探测法。 解：H(15)=15 MOD 7=1 H(14)=14 MOD 7=0 H(28)=28 MOD 7=0 冲突 H1(28)=1 又冲突H2(28)=2 H(26)=26 MOD 7=5 H(56)=56 MOD 7=0 冲突 H1(56)=1 又冲突 H2(56)=2 又冲突 H3(56)=3 H(23)=23 MOD 7=2 冲突 H1(23)=3 又冲突 H3(23)=4 各种散列函数所构造的散列表的ASL如下： 17、排序的稳定性 若记录序列中有两个或两个以上关键字相等的记录： Ki =Kj(i≠j，i, j=1, 2, … n)，且在排序前Ri先于Rj(i 专业整理 知识分享 完美WORD格式 18、插入排序采用的是以 “玩桥牌者”的方法为基础的。即在考察记录Ri之前，设以前的所有记录R1, R2 ,…., Ri-1已排好序，然后将Ri插入到已排好序的诸记录的适当位置。 ============================================================================ 最基本的插入排序是直接插入排序(Straight Insertion Sort) 。 ⑴ 最好情况：若待排序记录按关键字从小到大排列(正序)，算法中的内循环无须执行，则一趟排序时：关键字比较次数1次，记录移动次数2次 ⑵ 最坏情况：若待排序记录按关键字从大到小排列(逆序)，则一趟排序时：算法中的内循环体执行i-1，关键字比较次数i次，记录移动次数i+1。 一般地，认为待排序的记录可能出现的各种排列的概率相同，则取以上两种情况的平均值，作为排序的关键字比较次数和记录移动次数，约为n2/4，则复杂度为O(n2) 。 算法实现 void straight_insert_sort(Sqlist *L) { int i, j ; for (i=2; i<=L->length; i++) { L->R[0]=L->R[i]; j=i-1; /* 设置哨兵 */ while( LT(L->R[0].key, L->R[j].key) ) { L->R[j+1]=L->R[j]; j--; } /* 查找插入位置 */ L->R[j+1]=L->R[0]; /* 插入到相应位置 */ } } =============================================================================== 折半插入排序 当将待排序的记录R[i] 插入到已排好序的记录子表R[1…i-1]中时，由于R1, R2 ,…, Ri-1已排好序，则查找插入位置可以用“折半查找”实现，则直接插入排序就变成为折半插入排序。 从时间上比较，折半插入排序仅仅减少了关键字的比较次数，却没有减少记录的移动次数，故时间复杂度仍然为O(n2) 。 排序示例： 设有一组关键字30, 13, 70, 85, 39, 42, 6, 20，采用折半插入排序方法排序的过程 专业整理 知识分享 完美WORD格式 ⑴ 算法实现 void Binary_insert_sort(Sqlist *L) { int i, j, low, high, mid ; for (i=2; i<=L->length; i++) { L->R[0]=L->R[i]; /* 设置哨兵 */ low=1 ; high=i-1 ; while (low<=high) { if ( LT(L->R[0].key, L->R[mid].key) ) high=mid-1 ; else low=mid+1 ; } /* 查找插入位置 */ for (j=i-1; j>=high+1; j--) L->R[j+1]=L->R[j]; L->R[high+1]=L->R[0]; /* 插入到相应位置 */ }} ==============================================================================2-路插入排序 排序示例：设有初始关键字集合{49, 38, 65, 13, 97, 27, 76} ，采用2-路插入排序的过 程 例：设有关键字集合{49, 38, 65, 97, 76, 13, 27, 49} ，采用表插入排序的过程 专业整理 知识分享 完美WORD格式 ===============================================================================希尔排序(Shell Sort，又称缩小增量法)是一种分组插入排序方法。 排序示例 设有10个待排序的记录，关键字分别为9, 13, 8, 2, 5, 13, 7, 1, 15, 11，增量序列是5, 3, 1，希尔排序的过程： 算法实现 先给出一趟希尔排序的算法，类似直接插入排序。 void shell_pass(Sqlist *L, int d) /* 对顺序表L进行一趟希尔排序, 增量为d */ { int j, k ; for (j=d+1; j<=L->length; j++) { L->R[0]=L->R[j] ; /* 设置监视哨兵 */ k=j-d ; while (k>0&<(L->R[0].key, L->R[k].key) ) {L->R[k+d]=L->R[k] ; k=k-d ; } L->R[k+j]=L->R[0] ; 专业整理 知识分享 完美WORD格式 } } void shell_sort(Sqlist *L, int dk[], int t) /* 按增量序列dk[0 … t-1],对顺序表L进行希尔排序 */ { int m ; for (m=0; m<=t; m++) shll_pass(L, dk[m]) ; } ===============================================================================冒泡排序 排序示例 ： 设有9个待排序的记录，关键字分别为23, 38, 22, 45, 23, 67, 31, 15, 41，冒泡排序的过程： void Bubble_Sort(Sqlist *L) { int j ,k , flag ; for (j=0; j for (k=1; k<=L->length-j; k++) /* 一趟排序 */ if (LT(L->R[k+1].key, L->R[k].key ) ) { flag=FALSE ; L->R[0]=L->R[k] ; L->R[k]=L->R[k+1] ; L->R[k+1]=L->R[0] ; } if (flag==TRUE) break ; } } 算法分析: 时间复杂度: 最好情况(正序)：比较次数：n-1；移动次数：0； 最坏情况(逆序)： 故时间复杂度：T(n)=O(n²) 空间复杂度：S(n)=O(1) 专业整理 知识分享 完美WORD格式 ===============================================================================快速排序的平均时间复杂度是：T(n)=O(n㏒2n) 从所需要的附加空间来看，快速排序算法是递归调用，系统内用堆栈保存递归参数，当每次划分比较均匀时，栈的最大深度为[㏒2n]+1 。 ∴ 快速排序的空间复杂度是：S(n)=O(㏒2n) 从排序的稳定性来看，快速排序是不稳定的。 一趟排序示例 设有6个待排序的记录，关键字分别为29, 38, 22, 45, 23, 67，一趟快速排序的过程 算法实现 ⑴ 一趟快速排序算法的实现 int quick_one_pass(Sqlist *L , int low, int high) L->R[0]=L->R[i] ; /* R[0]作为临时单元和哨兵 */ do { while (LQ(L->R[0].key, L->R[j].key)&&(j>i)) j-- ; if (j>i) { L->R[i]=L->R[j] ; i++; } while (LQ(L->R[i].key, L->R[0].key)&&(j>i)) i++ ; if (j>i) { L->R[j]=L->R[i] ; j--; } } while(i!=j) ; /* i=j时退出扫描 */ L->R[i]=L->R[0] ; return(i) ; } 递归算法 void quick_Sort(Sqlist *L , int low, int high) { int k ; if (low 专业整理 知识分享 完美WORD格式 quick_Sort(L, k+1, high); } /* 序列分为两部分后分别对每个子序列排序 */ } 非递归算法 # define MAX_STACK 100 void quick_Sort(Sqlist *L , int low, int high) { int k , stack[MAX_STACK] , top=0; do { while (low stack[++top]=high ; stack[++top]=k+1 ; /* 第二个子序列的上,下界分别入栈 */ high=k-1 ; } if (top!=0) { low=stack[top--] ; high=stack[top--] ; } }while (top!=0&&low 例：设有关键字序列为：7, 4, -2, 19, 13, 6，直接选择排序的过程 算法实现 void simple_selection_sort(Sqlist *L) { int m, n , k; for (m=1; m for (n=m+1; n<=L->length; n++) if ( LT(L->R[n].key, L->R[k].key) ) k=n ; if (k!=m) /* 记录交换 */ { L->R[0]=L->R[m]; L->R[m]=L->R[k]; L->R[k]=L->R[0]; } } } 算法分析 专业整理 知识分享 完美WORD格式 整个算法是二重循环：外循环控制排序的趟数，对n个记录进行排序的趟数为n-1趟；内循环控制每一趟的排序。 进行第i趟排序时，关键字的比较次数为n-i，则： ∴ 时间复杂度是：T(n)=O(n) 空间复杂度是：S(n)=O(1) 从排序的稳定性来看，直接选择排序是不稳定的。 ===============================================================================堆的定义 是n个元素的序列H={k1, k2 , … kn} ，满足： 2 堆的性质 ① 堆是一棵采用顺序存储结构的完全二叉树， k1是根结点； ② 堆的根结点是关键字序列中的最小(或最大)值，分别称为小(或大)根堆； ③ 从根结点到每一叶子结点路径上的元素组成的序列都是按元素值(或关键字值)非递减(或非递增)的； (4)堆中的任一子树也是堆。 利用堆顶记录的关键字值最小(或最大)的性质，从当前待排序的记录中依次选取关键字最小(或最大)的记录，就可以实现对数据记录的排序，这种排序方法称为堆排序。 堆排序思想 ① 对一组待排序的记录，按堆的定义建立堆； ② 将堆顶记录和最后一个记录交换位置，则前n-1个记录是无序的，而最后一个记录是有序的； ③ 堆顶记录被交换后，前n-1个记录不再是堆，需将前n-1个待排序记录重新组织成为一个堆，然后将堆顶记录和倒数第二个记录交换位置，即将整个序列中次小关键字值的记录调整(排除)出无序区； ④ 重复上述步骤，直到全部记录排好序为止。 结论：排序过程中，若采用小根堆，排序后得到的是非递减序列；若采用大根堆，排序后得到的是非递增序列。 专业整理 知识分享 完美WORD格式 堆排序算法实现 堆的根结点是关键字最小的记录，输出根结点后，是以序列的最后一个记录作为根结点，而原来堆的左、右子树都是堆，则进行一次筛选就可以成为堆。 void Heap_Sort(Sqlist *H) { int j ; for (j=H->length/2; j>0; j--) Heap_adjust(H, j , H->length) ; /* 初始建堆 */ for (j=H->length/2; j>=1; j--) { H->R[0]=H->R[1] ; H->R[1]=H->R[j] ; H->R[j]=H->R[0] ; /* 堆顶与最后一个交换 */ Heap_adjust(H, 1, j-1) ; } } 堆排序的比较次数的数量级为： T(n)=O(n㏒2n)；而附加空间就是交换时所用的临时空间，故空间复杂度为： S(n)=O(1) ===============================================================================归并(Merging) ：是指将两个或两个以上的有序序列合并成一个有序序列。若采用线性表(无论是那种存储结构)易于实现，其时间复杂度为O(m+n) 。 归并排序的算法 专业整理 知识分享 完美WORD格式 开始归并时，每个记录是长度为1的有序子序列，对这些有序子序列逐趟归并，每一趟归并后有序子序列的长度均扩大一倍；当有序子序列的长度与整个记录序列长度相等时，整个记录序列就成为有序序列。算法是： void Merge_sort(Sqlist *L, RecType DR[]) { int d=1 ; while(d { Merge_pass(L->R, DR, d, L->length) ; Merge_pass(DR, L->R, 2*d, L->length) ; d=4*d ; } } 具有n个待排序记录的归并次数是㏒2n，而一趟归并的时间复杂度为O(n)，则整个归并排序的时间复杂度无论是最好还是最坏情况均为O(n㏒2n)。在排序过程中，使用了辅助向量DR，大小与待排序记录空间相同，则空间复杂度为O(n)。归并排序是稳定的。 ===============================================================================各种内部排序的比较: 各种内部排序按所采用的基本思想(策略)可分为：插入排序、交换排序、选择排序、归并排序和基数排序，它们的基本策略分别是： 1 插入排序：依次将无序序列中的一个记录，按关键字值的大小插入到已排好序一个子序列的适当位置，直到所有的记录都插入为止。具体的方法有：直接插入、表插入、2-路插入和shell排序。 2 交换排序：对于待排序记录序列中的记录，两两比较记录的关键字，并对反序的两个记录进行交换，直到整个序列中没有反序的记录偶对为止。具体的方法有：冒泡排序、快速排序。 3 选择排序：不断地从待排序的记录序列中选取关键字最小的记录，放在已排好序的序列的最后，直到所有记录都被选取为止。具体的方法有：简单选择排序、堆排序。 4 归并排序：利用“归并”技术不断地对待排序记录序列中的有序子序列进行合并，直到合并为一个有序序列为止。 5 基数排序：按待排序记录的关键字的组成成分(“位”)从低到高(或从高到低)进行。每次是按记录关键字某一“位”的值将所有记录分配到相应的桶中，再按桶的编号依次将记录进行收集，最后得到一个有序序列。 各种内部排序方法的性能比较如下表。 文件的基本概念 ⑴ 数据项(Item或field) ：数据文件中最小的基本单位，反映实体某一方面的特征—属性的数据表示。 专业整理 知识分享 完美WORD格式 ⑵ 记录(Record) ：一个实体的所有数据项的集合。 用来标识一个记录的数据项集合(一个或多个)称为关键字项(Key) ，关键字项的值称为关键字；能唯一标识一个记录的关键字称为主关键字(Primary Key)，其它的关键字称为次关键字(Secondary Key) 。 利用外存对数据文件进行排序称为外部排序。 算法部分： 素数的判断算法。 Void prime( int n) /* n是一个正整数 */ { int i=2 ; while ( (n% i)!=0 && i*1.0< sqrt(n) ) i++ ; if (i*1.0>sqrt(n) ) printf(“&d 是一个素数\\n” , n) ; else printf(“&d 不是一个素数\\n” , n) ; } ---------------------------------------------------------------------- 冒泡排序法。 Void bubble_sort(int a[]，int n) { change=false; for (i=n-1; change=TURE; i>1 && change; --i) for (j=0; j { a[j] ←→a[j+1] ; change=TURE ; } } – 最好情况：0次 – 最坏情况：1+2+3+⋯+n-1=n(n-1)/2 2 – 平均时间复杂度为： O(n) --------------------------------------------------------------------------------- 算法说明 ：算法中pa ，pb分别是待考察的两个链表的当前结点，pc是合并过程中合并的链表的最后一个结点。 LNode *Merge_LinkList(LNode *La， LNode *Lb) /* 合并以La, Lb为头结点的两个有序单链表 */ { LNode *Lc, *pa , *pb , *pc, *ptr ; Lc=La ; pc=La ; pa=La->next ; pb=Lb->next ; while (pa!=NULL && pb!=NULL) { if (pa->data { pc->next=pa ; pc=pa ; pa=pa->next ; } /* 将pa所指的结点合并，pa指向下一个结点 */ if (pa->data>pb->data) { pc->next=pb ; pc=pb ; pb=pb->next ; } 专业整理 知识分享 完美WORD格式 /* 将pa所指的结点合并，pa指向下一个结点 */ if (pa->data==pb->data) { pc->next=pa ; pc=pa ; pa=pa->next ; ptr=pb ; pb=pb->next ; free(ptr) ; } /* 将pa所指的结点合并，pb所指结点删除 */ } if (pa!=NULL) pc->next=pa ; else pc->next=pb ; /*将剩余的结点链上*/ free(Lb) ; return(Lc) ; } 采用静态顺序栈方式实现 void conversion(int n , int d) /*将十进制整数N转换为d(2或8)进制数*/ { SqStack S ; int k, *e ; S=Init_Stack(); while (n>0) { k=n%d ; push(S , k) ; n=n/d ; } /* 求出所有的余数，进栈 */ while (S.top!=0) /* 栈不空时出栈，输出 */ { pop(S, e) ; printf(“%1d” , *e) ; } } 求转置矩阵的算法如下： void TransMatrix(TMatrix a , TMatrix b) { int p , q , col ; b.rn=a.cn ; b.cn=a.rn ; b.tn=a.tn ; /* 置三元组表b.data的行、列数和非0元素个数 */ if (b.tn==0) printf(“ The Matrix A=0\\n” ); else { q=0; for (col=1; col<=a.cn ; col++) /* 每循环一次找到转置后的一个三元组 */ for (p=0 ;p { b.data[q].row=a.data[p].col ; b.data[q].col=a.data[p].row ; b.data[q].value=a.data[p].value; q++ ; } } 专业整理 知识分享 完美WORD格式 } 先序遍历的递归算法 void PreorderTraverse(BTNode *T) { if (T!=NULL) { visit(T->data) ; /* 访问根结点 */ PreorderTraverse(T->Lchild) ; PreorderTraverse(T->Rchild) ; } } 非递归算法 设T是指向二叉树根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T； ⑴ 访问p所指向的结点； ⑵ q=p->Rchild ，若q不为空，则q进栈； ⑶ p=p->Lchild ，若p不为空，转(1)，否则转(4)； ⑷ 退栈到p ，转(1)，直到栈空为止。 算法实现： #define MAX_NODE 50 void PreorderTraverse( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T, *q ; int top=0 ; if (T==NULL) printf(“ Binary Tree is Empty!\\n”) ; else { do { visit( p-> data ) ; q=p->Rchild ; if ( q!=NULL ) stack[++top]=q ; p=p->Lchild ; if (p==NULL) { p=stack[top] ; top-- ; } } while (p!=NULL) ; } } ==============================================================================中序遍历的递归算法 void InorderTraverse(BTNode *T) { if (T!=NULL) { InorderTraverse(T->Lchild) ; visit(T->data) ; /* 访问根结点 */ InorderTraverse(T->Rchild) ; } } 非递归算法 设T是指向二叉树根结点的指针变量，非递归算法是： 专业整理 知识分享 完美WORD格式 若二叉树为空，则返回；否则，令p=T ⑴ 若p不为空，p进栈， p=p->Lchild ； ⑵ 否则(即p为空)，退栈到p，访问p所指向的结点； ⑶ p=p->Rchild ，转(1)； 直到栈空为止。 算法实现： #define MAX_NODE 50 void InorderTraverse( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T ; int top=0 , bool=1 ; if (T==NULL) printf(“ Binary Tree is Empty!\\n”) ; else { do { while (p!=NULL) { stack[++top]=p ; p=p->Lchild ; } if (top==0) bool=0 ; else { p=stack[top] ; top-- ; visit( p->data ) ; p=p->Rchild ; } } while (bool!=0) ; } } =============================================================================== 后序遍历的递归算法 void PostorderTraverse(BTNode *T) { if (T!=NULL) { PostorderTraverse(T->Lchild) ; PostorderTraverse(T->Rchild) ; visit(T->data) ; /* 访问根结点 */ } } 非递归算法 在后序遍历中，根结点是最后被访问的。因此，在遍历过程中，当搜索指针指向某一根结点时，不能立即访问，而要先遍历其左子树，此时根结点进栈。当其左子树遍历完后再搜索到该根结点时，还是不能访问，还需遍历其右子树。所以，此根结点还需再次进栈，当其右子树遍历完后再退栈到到该根结点时，才能被访问。 因此，设立一个状态标志变量tag ： 0 ： 结点暂不能访问 1 ： 结点可以被访问 其次，设两个堆栈S1、S2 ，S1保存结点，S2保存结点的状态标志变量tag 。S1和S2共用一个栈顶指针。 设T是指向根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T； ⑴ 第一次经过根结点p，不访问： p进栈S1 ， tag 赋值0，进栈S2，p=p->Lchild 。 ⑵ 若p不为空，转(1)，否则，取状态标志值tag ： ⑶ 若tag=0：对栈S1，不访问，不出栈；修改S2栈顶元素值(tag赋值1) ，取S1栈顶元 专业整理 知识分享 完美WORD格式 素的右子树，即p=S1[top]->Rchild ，转(1)； ⑷ 若tag=1：S1退栈，访问该结点； 直到栈空为止。 算法实现： #define MAX_NODE 50 void PostorderTraverse( BTNode *T) { BTNode *S1[MAX_NODE] ,*p=T ; int S2[MAX_NODE] , top=0 , bool=1 ; if (T==NULL) printf(“Binary Tree is Empty!\\n”) ; else { do {while (p!=NULL) { S1[++top]=p ; S2[top]=0 ; p=p->Lchild ; } if (top==0) bool=0 ; else if (S2[top]==0) { p=S1[top]->Rchild ; S2[top]=1 ; } else { p=S1[top] ; top-- ; visit( p->data ) ; p=NULL ; /* 使循环继续进行而不至于死循环 */ } } while (bool!=0) ; } } =============================================================================== 设T是指向根结点的指针变量，层次遍历非递归算法是： 若二叉树为空，则返回；否则，令p=T，p入队； ⑴ 队首元素出队到p； ⑵访问p所指向的结点； ⑶将p所指向的结点的左、右子结点依次入队。直到队空为止。 #define MAX_NODE 50 void LevelorderTraverse( BTNode *T) { BTNode *Queue[MAX_NODE] ,*p=T ; int front=0 , rear=0 ; if (p!=NULL) { Queue[++rear]=p; /* 根结点入队 */ while (front Queue[++rear]=p; /* 左结点入队 */ if (p->Rchild!=NULL) Queue[++rear]=p; /* 左结点入队 */ } 专业整理 知识分享 完美WORD格式 } } =============================================================================== 利用层次遍历算法可以直接求得二叉树的深度。 算法实现： #define MAX_NODE 50 int search_depth( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T; int front=0 , rear=0, depth=0, level ; /* level总是指向访问层的最后一个结点在队列的位置 */ if (T!=NULL) { Queue[++rear]=p; /* 根结点入队 */ level=rear ; /* 根是第1层的最后一个节点 */ while (front Queue[++rear]=p; /* 左结点入队 */ if (p->Rchild!=NULL) Queue[++rear]=p; /* 左结点入队 */ if (front==level) /* 正访问的是当前层的最后一个结点 */ { depth++ ; level=rear ; } } } } =============================================================================== 先序线索化二叉树 void preorder_Threading(BiThrNode *T) { BiThrNode *stack[MAX_NODE]; BiThrNode *last=NULL, *p ; int top=0 ; if (T!=NULL) { stack[++top]=T; while (top>0) { p=stack[top--] ; if (p->Lchild!=NULL) p->Ltag=0 ; else { p->Ltag=1 ; p->Lchild!=last ; } if (last!=NULL) if (last->Rchild!=NULL) last->Rtag=0 ; else { last->Rtag=1 ; last->Rchild!=p ; } last=p ; if (p->Rchild!=NULL) stack[++top]=p->Rchild ; if (p->Lchild!=NULL) 专业整理 知识分享 完美WORD格式 stack[++top]=p->Lchild ; } Last->Rtag=1; /* 最后一个结点是叶子结点 */ } } ===============================================================================中序线索化二叉树 void inorder_Threading(BiThrNode *T) { BiThrNode *stack[MAX_NODE]; BiThrNode *last=NULL, *p=T ; int top=0 ; while (p!=NULL||top>0) if (p!=NULL) { stack[++top]=p; p=p->Lchild; } else { p=stack[top--] ; if (p->Lchild!=NULL) p->Ltag=0 ; else { p->Ltag=1 ; p->Lchild!=last ; } if (last!=NULL) if (last->Rchild!=NULL) last->Rtag=0 ; else { last->Rtag=1 ; last->Rchild!=p ; } last=p ; P=p->Rchild; } last->Rtag=1; /* 最后一个结点是叶子结点 */ } } ===============================================================================Huffman树的生成 算法实现 void Create_Huffman(unsigned n, HTNode HT[ ], unsigned m) /* 创建一棵叶子结点数为n的Huffman树 */ { unsigned int w ; int k , j ; for (k=1 ; k } /* 输入时，所有叶子结点都有权值 */ else HT[k].weight=0; /* 非叶子结点没有权值 */ HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0 ; } /* 初始化向量HT */ for (k=n+1; k /* w1 , w2分别保存权值最小的两个权值 */ 专业整理 知识分享 完美WORD格式 int p1=0 , p2=0 ; /* p1 , p2保存两个最小权值的下标 */ for (j=1 ; j<=k-1 ; j++) { if (HT[k].Parent==0) /* 尚未合并 */ { if (HT[j].Weight w1=HT[j].Weight ; p1=j ; } for ( ; fp!=0 ;p=fp , fp=HT[p].parent) /* 从叶子结点到根逆向求编码 */ if (HT[fp].parent==p) cd[--sp]=‘0’ ; else cd[--sp]=‘1’ ; HC[k]=(char *)malloc((n-sp)*sizeof(char)) ; /* 为第k个字符分配保存编码的空间 */ trcpy(HC[k] , &cd[sp]) ; } free(cd) ; } ===============================================================================void DFS(ALGraph *G , int v) { LinkNode *p ; Visited[v]=TRUE ; Visit[v] ; /* 置访问标志，访问顶点v */ p=G->AdjList[v].firstarc; /* 链表的第一个结点 */ while (p!=NULL) { if (!Visited[p->adjvex]) DFS(G, p->adjvex) ; /* 从v的未访问过的邻接顶点出发深度优先搜索 */ p=p->nextarc ; } } void DFS_traverse_Grapg(ALGraph *G) { int v ; for (v=0 ; v Visited[v]=FALSE ; /* 访问标志初始化 */ p=G->AdjList[v].firstarc ; for (v=0 ; v ==============================================================================typedef emnu {FALSE , TRUE} BOOLEAN ; BOOLEAN Visited[MAX_VEX] ; typedef struct Queue { int elem[MAX_VEX] ; int front , rear ; 专业整理 知识分享 完美WORD格式 }Queue ; /* 定义一个队列保存将要访问顶点 */ void BFS_traverse_Grapg(ALGraph *G) { int k ,v , w ; LinkNode *p ; Queue *Q ; Q=(Queue *)malloc(sizeof(Queue)) ; Q->front=Q->rear=0 ; /* 建立空队列并初始化 */ for (k=0 ; k Visited[k]=FALSE ; /* 访问标志初始化 */ for (k=0 ; k { v=G->AdjList[k].data ; /* 单链表的头顶点 */ if (!Visited[v]) /* v尚未访问 */ { Q->elem[++Q->rear]=v ; /* v入对 */ while (Q->front!=Q->rear) { w=Q->elem[++Q->front] ; Visited[w]=TRUE ; /* 置访问标志 */ Visit(w) ; /* 访问队首元素 */ p=G->AdjList[w].firstarc ; while (p!=NULL) { if (!Visited[p->adjvex]) Q->elem[++Q->rear]=p->adjvex ; p=p->nextarc ; } } /* end while */ } /* end if */ } /* end for */ } ===============================================================================求最小生成树的Prime算法 typedef struct MSTEdge { int vex1, vex2 ; /* 边所依附的图中两个顶点 */ WeightType weight ; /* 边的权值 */ }MSTEdge ; 算法实现 #define INFINITY MAX_VAL /* 最大值 */ MSTEdge *Prim_MST(AdjGraph *G , int u) /* 从第u个顶点开始构造图G的最小生成树 */ { MSTEdge TE[] ; // 存放最小生成树n-1条边的数组指针 int j , k , v , min ; for (j=0; j closedge[j].lowcost=G->adj[j][u] ; } /* 初始化数组closedge[n] */ closedge[u].lowcost=0 ; /* 初始时置U={u} */ 专业整理 知识分享 完美WORD格式 TE=(MSTEdge *)malloc((G->vexnum-1)*sizeof(MSTEdge)) ; for (j=0; j for (v=0; v if (closedge[v].lowcost!=0&& closedge[v].Lowcost closedge[k].lowcost=0 ; /* 将顶点k并入U中 */ for (v=0; v if (G->adj[v][k] } /* 修改数组closedge[n]的各个元素的值 */ } return(TE) ; } /* 求最小生成树的Prime算法 */ =============================================================================== 用Kruskal算法构造图G的最小生成树 MSTEdge *Kruskal_MST(ELGraph *G) /* 用Kruskal算法构造图G的最小生成树 */ { MSTEdge TE[] ; int j, k, v, s1, s2, Vset[] ; WeightType w ; Vset=(int *)malloc(G->vexnum*sizeof(int)) ; for (j=0; j Vset[j]=j ; /* 初始化数组Vset[n] */ sort(G->edgelist) ; /* 对表按权值从小到大排序 */ j=0 ; k=0 ; while (k /* 若边的两个顶点的连通分量编号不同, 边加入到TE中 */ if (s1!=s2) { TE[k].vex1=G->edgelist[j].vex1 ; TE[k].vex2=G->edgelist[j].vex2 ; TE[k].weight=G->edgelist[j].weight ; k++ ; for (v=0; v if (Vset[v]==s2) Vset[v]=s1 ; } j++ ; } 专业整理 知识分享 完美WORD格式 free(Vset) ; return(TE) ; } /* 求最小生成树的Kruskal算法 */ ===============================================================================统计各顶点入度的函数 void count_indegree(ALGraph *G) { int k ; LinkNode *p ; for (k=0; k G->adjlist[k].indegree=0 ; /* 顶点入度初始化 */ for (k=0; k while (p!=NULL) /* 顶点入度统计 */ { G->adjlist[p->adjvex].indegree++ ; p=p->nextarc ; } } } ===============================================================================拓扑排序算法 int Topologic_Sort(ALGraph *G, int topol[]) /* 顶点的拓扑序列保存在一维数组topol中 */ { int k, no, vex_no, top=0, count=0, boolean=1 ; int stack[MAX_VEX] ; /* 用作堆栈 */ LinkNode *p ; count_indegree(G) ; /* 统计各顶点的入度 */ for (k=0; k if (G->adjlist[k].indegree==0) stack[++top]=G->adjlist[k].data ; do { if (top==0) boolean=0 ; else { no=stack[top--] ; /* 栈顶元素出栈 */ topl[++count]=no ; /* 记录顶点序列 */ p=G->adjlist[no].firstarc ; while (p!=NULL) /*删除以顶点为尾的弧*/ { vex_no=p->adjvex ; G->adjlist[vex_no].indegree-- ; if (G->adjlist[vex_no].indegree==0) stack[++top]=vex_no ; p=p->nextarc ; } } }while(boolean==0) ; if (count 专业整理 知识分享 完美WORD格式 else return(1) ; } =============================================================================== 从图G中的顶点v出发到其余各顶点的最短路径Dijkstra BOOLEAN final[MAX_VEX] ; int pre[MAX_VEX] , dist[MAX_VEX] ; void Dijkstra_path (AdjGraph *G, int v) /* 从图G中的顶点v出发到其余各顶点的最短路径 */ { int j, k, m, min ; for ( j=0; j dist[v]=0 ; final[v]=TRUE ; /* 设置S={v} */ for ( j=0; j while (final[m]) m++; /* 找不在S中的顶点vk */ min=INFINITY ; for ( k=0; k { if (!final[k]&&dist[m] final[m]=TRUE ; /* 将第k个顶点并入S中 */ for ( j=0; j { if (!final[j]&&(dist[m]+G->adj[m][j] } /* 修改dist和pre数组的值 */ } /* 找到最短路径 */ } ===============================================================================int A[MAX_VEX][MAX_VEX] ; int Path[MAX_VEX][MAX_VEX] ; void Floyd_path (AdjGraph *G) { int j, k, m ; for ( j=0; j { A[j][k]=G->adj[j][k] ; Path[j][k]=-1 ; } /* 各数组的初始化 */ for ( m=0; m for ( j=0; j 专业整理 知识分享 完美WORD格式 if ((A[j][m]+A[m][k]) for ( j=0; j { printf(“%d到%d的最短路径为:\\n”, j, k) ; printf(“%d ”,j) ; prn_pass(j, k) ; printf(“%d ”, k) ; printf(“最短路径长度为: %d\\n”,A[j][k]) ; } } /* end of Floyd */ void prn_pass(int j , int k) { if (Path[j][k]!=-1) { prn_pass(j, Path[j][k]) ; printf(“, %d” , Path[j][k]) ; prn_pass(Path[j][k], k) ; } } ===============================================================================折半查找 当n很大 (n>50)时， ASL≈ ㏒2(n+1)-1。 查找思想 用Low、High和Mid表示待查找区间的下界、上界和中间位置指针，初值为Low=1，High=n。 ⑴ 取中间位置Mid：Mid=(Low+High)/2 ； ⑵ 比较中间位置记录的关键字与给定的K值： ① 相等： 查找成功； ② 大于：待查记录在区间的前半段，修改上界指针： High=Mid-1，转⑴ ； ③ 小于：待查记录在区间的后半段，修改下界指针：Low=Mid+1，转⑴ ； 直到越界(Low>High)，查找失败。 int Bin_Search(SSTable ST , KeyType key) { int Low=1，High=ST.length, Mid ; while (Low if (EQ(ST. elem[Mid].key, key)) return(Mid) ; else if (LT(ST. elem[Mid].key, key)) Low=Mid+1 ; else High=Mid-1 ; } return(0) ; /* 查找失败 */ } ============================================================================== 专业整理 知识分享 完美WORD格式 递归算法 BSTNode *BST_Serach(BSTNode *T , KeyType key) { if (T==NULL) return(NULL) ; else { if (EQ(T->key, key) ) return(T) ; else if ( LT(key, T->key) ) return(BST_Serach(T->Lchild, key)) ; else return(BST_Serach(T->Rchild, key)) ; } } ⑵ 非递归算法 BSTNode *BST_Serach(BSTNode *T , KeyType key) { BSTNode p=T ; while (p!=NULL&& !EQ(p->key, key) ) { if ( LT(key, p->key) ) p=p->Lchild ; else p=p->Rchild ; } if (EQ(p->key, key) ) return(p) ; else return(NULL) ; } =============================================================================== 专业整理 知识分享 因篇幅问题不能全部显示，请点此查看更多更全内容