1、什么是外排序
外排序是指数据存放在外存中，数据排序时涉及内、外存数据交换的排序方法。
存储在外存上的数据以文件为基本单位。
2、外排序的基本方法
外排序的基本方法时归并排序法。它分为以下两个步骤：
(1) 生成若干初始归并段(顺串)：这一过程也称为文件预处理。一种常规的方法如下：
① 把含有n个记录的文件，按内存大小w分成若干长度为w的子文件(归并段)；
② 分别将各子文件调入内存，采用有效的内排序方法排序后送回外存，产生n/2↑个初始归并段。
(2) 多路归并：对这些初始归并段进行多遍归并，使得有序的归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。
详细的过程见PPT。
归并过程的性能与 记录读写次数、内存中归并时需要关键字比较次数 有关。
外排序方法与各种外存设备的特征有关。
外存设备大体上可分为两类：
- 顺序存取设备，例如磁带。
- 直接存取设备，例如磁盘。
另一种方法：采用一种称为 置换–选择 排序方法用于生成初始归并段。
置换–选择排序方法:
（1）从待排文件Fin中按内存工作区WA的容量w读入w个记录。设归并段编号i=1。
（2）使用败者树从WA中选出关键字最小的记录Rmin。
（3）将Rmin记录输出到Fout中，作为当前归并段的一个成员。
（4）若Fin不空，则从Fin中读入下一个记录x放在Rmin所在的工作区位置代 替Rmin。
（5）在工作区中所有≥Rmin的记录中选择出最小记录作为新的Rmin，转 （3），直到选不出这样的Rmin。
（6）设i=i+1，开始一个新的归并段。
（7）若工作区已空，则初始归并段已全部产生；否则转（2）。
置换–选择排序中关键字比较次数分析：
共有n个记录，内存工作区WA的容量为w：
- 若在w各记录中选取最小关键字采用简单比较方法，每次需要w-1次比较。
- 总的时间复杂度为O(nw)。
1、k路平衡归并概述
(1) 什么是k路平衡归并
2路平衡归并：每一趟从m个归并段得到m/2↑个归并段。
一般地，2路平衡归并的前提：初始归并段的记录个数都相同。→可以推广到k路平衡归并
(2) 影响k路平衡归并的因素
影响k路平衡归并效率的因素：
- 归并时需要读写磁盘的次数
- 归并时需要关键字比较的次数
(3) k路平衡归并时读写磁盘次数的计算
例如，m=8，假设每个归并段4个记录，k=2。
读记录次数=WPL=8*4*3=96.(如果每个记录占用一个物理块，读写磁盘次数=96*2=192次)
采用k路平衡归并时，通常k越大，读写磁盘次数会减少。
(4) k路平衡归并时关键字比较次数的计算
1、查找的定义
查找表：是由一组记录组成的表或文件，而每个记录由若干个 数据项组成，并假设每个记录都有一个能唯一标识该记录的关键字。
2、内查找和外查找
若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。
3、查找的数据组织
采用何种存储结构？(1）顺序表 （2）链表 （3）其他
若在查找的同时对表做修改操作（如插入和删除）， 则相应的表称之为动态查找表；否则称之为静态查找表。
线性表查找的主要方法有：顺序查找、二分查找、分块查找
思路：
从表的一端开始，顺序扫描线性表，依次将扫描到的关 键字和给定值k相比。若当前扫描到的关键字与k相等，则查找成功；若扫描结束后， 仍未找到关键字等于k的记录，则查找失败。
代码：
int SeqSearch(SeqList R,int n,KeyType k){
int i=0;
while(i<n && R[i].key!=k) //从表头往后找
i++;
if(i>=n) //未找到返回0
return 0;
else return i+1; //找到返回逻辑序号i+1
}
①成功情况下的平均查找长度ASL=(n+1)/2
②不成功情况下的平均查找长度ASL=n
折半查找也称为二分查找，要求线性表中的记录必须己按关键 字值有序（递增或递减）排列。
代码：
//迭代版本
int BinSearch(SeqList R,int n,KeyType k){
int low=0,hight=n-1,mid;
while(low<=high){
mid=(low+high)/2;
if(R[mid].key==k) //查找成后返回其逻辑序号mid+1
return mid+1;
if(k<R[mid].key) //继续在R[low..mid-1]中查找
high=mid-1;
else low =mid+1; //继续在R[mid+1..hight]中查找
}
return 0;
}
//递归版本
int BinSearch(SeqList R,KeyType k,int l,int r){
int mid;
if(l<=r){
mid=(l+r)/2;
if(R[mid].key==k)
return mid+1;
else if(k<R[mid].key)
return BinSearch(R,k,l,mid-1);
else return BinSearch(R,k,mid+1,r);
}
return 0;
}
①成功情况下的平均查找长度ASL=log2 n
1、索引存储结构
索引存储结构 = 数据表 + 索引表
索引表中的每一项称为索引项，索引项的一般形式是： （关键字，地址）
关键字唯一标识一个节点，地址作为指向该关键字对应节点的指针， 也可以是相对地址。
2、分块查找
分块查找方法：
索引表(有序)：可以顺序查找块，也可以二分查找块。
数据块(无序)：只能顺序查找块中的元素。
分块查找的效率介于顺序查找和二分查找之间。
以二叉树或树作为表的组织形式，称为树表，它是一类动 态查找表，不仅适合于数据查找，也适合于表插入和删除操作。
常见的树表：
(1) 二叉排序树 (2) 平衡二叉树
(3) B-树 (4) B+树
二叉树→(满足节点值约束)→二叉排序树→(所有节点的平衡因子的绝对值<=1,结构约束)→平衡二叉树
二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉 排序树或者是空树，或者是满足如下性质（BST性质）的二叉树：
①若它的左子树非空，则左子树上所有节点值（指关键字值）均小于根 节点值；
②若它的右子树非空，则右子树上所有节点值均大于根节点值；
③左、右子树本身又各是一棵二叉排序树。
注意：二叉排序树中没有相同关键字的节点。
1、二叉排序树上的查找
二叉排序树可看做是一个有序表，所以在二叉排序树上进行查 找，和二分查找类似，也是一个逐步缩小查找范围的过程。
代码：
BSTNode *SearchBST(BSTNode *bt,KeyType k){
if(bt==NULL||bt->key==k) //递归出口
return bt;
if(k< bt->key)
return SearchBST(bt->left,k); //在左子树中递归查找
else
return SearchBST(bt->right,k); //在右子树中递归查找
}
2、二叉排序树的插入和生成
在二叉排序树中插入一个关键字为k的新节点，要保证插入后 仍满足BST性质。
插入过程：
(1) 若二叉排序树T为空，则创建一个key域为k的节点，将它作为根节点；
(2) 否则将k和根节点的关键字比较，若两者相等，则说明树中已有此关键字k，无须插入，直接返回0；
(3) 若k< T->key，则将k插入根节点的左子树中；
(4) 否则将它插入右子树中。
代码：
int InsertBST(BSTNode *&p,KeyType k) {
if(p==NULL){ //原树为空，新插入的记录为根节点
p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k; p->left=p->right=NULL;
return 1;
}else if(k==p->key) //存在相同关键字的节点，返回0
return 0;
else if(k< p->key)
return InsertBST(p->left,k); //插入到左子树中
else
return InsertBST(p->right,k); //插入到有右子树中
}
//利用数组创建二叉排序树
BSTNode *CreatBST(KeyTypeA[],int n){ //返回树根指针
BSTNode *bt=NULL; //初始时bt为空树
int i=0;
while(i<n){
InsertBST(bt,A[i]); //将A[i]插入二叉排序树T中
i++;
}
return bt; //返回建立的二叉排序树的根节点
}
注意：任何节点插入到二叉排序树时，都是以叶节点插入的。
二叉排序树的特点：
(1) 二叉排序树的中序序列是一个递增有序序列
(2) 根节点的最左下节点时关键字最小的节点
(3) 根节点的最右下节点时关键字最大的节点
3、 二叉排序树的节点删除
（1）被删除的节点是叶子节点：直接删去该节点。
（2） 被删除的节点只有左子树或者只有右子树，用其左子树或者 右子树替换它（节点替换）。
（3）被删除的节点既有左子树，也有右子树
以其中序前趋值替换之（值替换） ，然后再删除该前趋节点。 前趋是左子树中最大的节点。
也可以用其后继替换之，然后再删除该后继节点。后继是右子树 中最小的节点。
算法实现：如何删除仅仅有右子树的节点*p:
//1.查找被删节点
int deletdk(BSTNode *&bt,KeyType k){
if(bt!=NULL){
if(k==bt->key){
deletep(bt);
return 1;
}
else if(k< bt->key)
deletek(bt->left,k);
else
deletek*bt->right,k);
}
else return 0;
}
//2.删除节点*p
void deletep(BSTNode *&p){
BSTNode *q;
q=p;
p=p->right; //用其右孩子节点替换它
free(q);
}
在二叉排序树bt中删除节点的算法：
int DeleteBST(BSTNode *&bt,KeyType k){
if(bt==NULL) return 0; //空树删除失败
else{
if(k< bt->key) return DeleteBST(bt->left,k); //递归在左子树中删除为k的节点
else if(k> bt->key) return DeleteBST(bt->right,k); //递归在右子树中删除为k的节点
else{
Delete(bt); //调用Delete(bt)函数删除*bt节点
return 1;
}
}
}
void Delete(BSTNode *&p){ //从二叉排序树中删除*p节点
BSTNode *q;
if(p->right==NULL){ //*p节点没有右子树的情况
p=q;p=p->left; //用其左孩子节点替换它
free(q);
}else if(p->left==NULL){ //*p节点没有左子树的情况
p=q;p=p->right; //用其右孩子节点替换它
free(q);
}else Delete1(p,p->left); //*p节点既没有左子树右没有右子树的情况
}
void Delete1(BSTNode *p, BSTNode *&r) {
//p指向待删除的节点，r指向其左孩子节点
//当被删*p节点有左右子树时的删除过程
BSTNode *q;
if(r->right!=NULL)
Delete1(p,r->right); //递归找*r的最右下节点
else{ //r指向最右下节点
p->key=r->key; p->data=r->data; //值替换
q=r; r=r->left; //删除原*r节点
free(q); //释放原*r的空间
}
}
1、 什么是平衡二叉树
若一棵二叉树中每个节点的左、右子树的高度至多相差1,则称 此二叉树为平衡二叉树（AVL）。
平衡因子：该节点左子树的高度减去右子树的高度。
若一棵二叉树中所有节点的平衡因子的绝对值小于或等于1， 该二叉树称为平衡二叉树。
2、平衡二叉树的插入调整
平衡二叉树中插入新节点方式与二叉排序树相似，只是插入后 可能破坏了平衡二叉树的平衡性，解决方法是调整。
调整操作可归纳为4种情况：
(1) LL型调整 (2) RR型调整 (3) LR型调整 (4) RL型调整
3、平衡二叉树的查找
含有n个节点的平衡二叉树的平均查找长度为O(log2 n)。
B-树又称为多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构。
B-树的定义：
一棵m阶B-树或者是一棵空树，或者是满足要求的m叉树：
(1) 树中每个节点至多有m个孩子节点(即至多有m-1个关键字)，最多关键字个数Max=m-1
(2) 除根节点外，其他非叶子节点至少有 m/2↑ 个孩子节点，最少关键字个数Min=m/2↑ -1
(3) 若根节点不是叶子节点，则根节点至少有两个孩子节点；
(4) 每个节点的结构 指针和关键字交叉排列，节点中按关键字大小顺序排列；
(5) 所有外部节点都在同一层上。B-树是所有节点的平衡因子均等于0的多路查找树。
在计算B-树的高度时，需要计入最底层的外部节点
说明：外部节点就是失败节点，指向它的指针为空，不含有任何信 息，是虚设的。一棵B-树中总有n个关键字，则外部节点个数为n+1。
在B-树的存储结构中，节点的类型定义如下：
typedef struct node{
int keynum; //节点当前拥有的关键字的个数
KeyType key[MAXM]; //[1..keynum]存放关键字
struct node *parent; //双亲节点指针
struct node *ptr[MAXM]; //孩子节点指针数组[0..keynum]
}BTNode;
B+树的定义：
一棵m阶B+数满足下列要求：
(1) 每个分支节点至多有m棵子树。
(2) 根节点或者没有子树，或者至少有两棵子树。
(3) 除根节点外，其他每个分支节点至少有m/2↑棵子树。（↑表示向上取整）
(4) 有n棵子树的节点恰好有n个关键字。
(5) 所有叶子节点包含全部关键字及指向相应记录的指针，而且叶子节 点按关键字大小顺序链接。并将所有叶子节点链接起来。
(6) 所有分支节点（可看成是索引的索引）中仅包含它的各个子节点（即下级索引的索引块）中最大关键字及指向子节点的指针。
哈希函数：把关键字为ki的对象存放在相应的哈希地址中
哈希冲突：对于两个关键字分别为ki和kj（i≠j）的记录，有ki≠kj，但h(ki)=h(kj)。 把这种现象叫做哈希冲突（同义词冲突）。
1、哈希表设计
哈希表设计主要需要解决哈希冲突。实际中哈希冲突是难以避 免的，主要与3个因素有关：
(1) 与装填因子有关。装填因子α=存储的记录个数/哈希表的大小 =n/m α越小，冲突的可能性就越小； α越大（最大可取1）， 冲突的可能性就越大。通常使最终的控制在0.6～0.9的范围内。
(2) 与所采用的哈希函数有关。好的哈希函数会减少冲突的发生；不好的哈希函数会增加冲突的发生。
(3) 与解决冲突方法有关。好的哈希冲突解决方法会减少冲突的发生。
(1) 直接定址法 (2) 除留余数法 (3) 数字分析法
1、开放地址法：冲突时找一个新的空闲的哈希地址。
（1）线性探查法 （2）平方探查法
2、拉链法：拉链法是把所有的同义词用单链表链接起来的方法。
####6.1.1 图的定义
图(Graph)G由顶点集合V(G)和边集合E(G)构成。
G=(V,E)
V={0,1,2,3,4}
E={(0,1),(0,4),(1,2),(1,3),(2,3),(3,4)}
图抽象数据类型 = 逻辑结构 + 基本运算
图的基本运算如下：
在图G中，如果代表边的顶点对是无序的，则称G为无序图。用圆括号序偶表示无向边。(0,1)
如果表示边的顶点对是有序的，则称G为有向图。用尖括号序偶表示有向边。<0,1>
1.端点和邻接点
无向图：若存在一条边(i,j) → 顶点 i 和顶点 j 为端点，它们互为邻接点。
有向图：若存在一条边<i,j> → 顶点 i 为起始端点(简称为起点)，顶点 j 为终止端点(简称终点)，他们互为邻接点。
2.顶点的度、入度和出度
无向图：以顶点 i 为端点的边数成为该顶点的度。
有向图：以顶点 i 为终点的入边的数目，成为该顶点的入度。以顶点 i 为起始点的出边的数目，成为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。
3.完全图
无向图：每两个顶点之间都存在着一条边，成为完全无向图，包含有 n(n-1)/2 条边。
有向图：每两个顶点之间都存在着方向相反的两条边，成为完全有向图，包含 n(n-1) 条边。
4.稠密图、稀疏图
当一个图接近完全图时，则称为稠密图。
相反，当一个图含有较少的边数时，则称为稀疏图。
5.子图
设有两个图G=(V,E)和G’=(V’,E’)，若V’是V的子集 且 E’是E的子集，则称G’是G的子图。
6.路径和路径长度
路径长度是指一条路径上经过的边的数目。
若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。
7.回路或环
若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环。
开始点与结束点相同的简单路径被称为简单回路或简单环。
8.连通、连通图和连通分量
无向图：若从顶点 i 到顶点 j 有路径，则称顶点 i 和 j 是连通的。
若图中任意两个顶点都连通，则称为连通图，否则称为非连通图。
无向图G中的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。
9.强连通图和强连通分量
有向图：若从顶点 i 到顶点 j 有路径，则称从顶点 i 到 j 是连通的。
若图G中的任意两个顶点 i 和 j 都连通，即从顶点 i 到 j 和从顶点 j 到 i 都存在路径，则称图G是强连通图。
在一个非强连通中找强联通分量的方法：
① 在图中找有向环。
② 扩展该有向环：如果某个订单到该环中任一顶点有路径，并且该环中任一顶点到这个顶点也有路径，则加入这个顶点，
10.权和网
图中每一条边都可以附带有一个对应的数值，这种与边先关的数值成为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。
边上带有权的图成为带权图，也称作网。
图的两种主要存储结构：邻接矩阵、邻接表。
无序图的邻接矩阵一定是对称的，有序图的邻接矩阵不一定对称。
邻接矩阵的主要特点：
① 一个图的邻接矩阵表示是唯一的。
② 特别适合稠密图的存储，存储空间为O(n^2)。
图的邻接矩阵存储类型定义如下：
#define MAXV<最大顶点个数>
typedef struct{
int no; //顶点编号
InfoType info; //顶点其他信息
}VertexType;
//声明的邻接矩阵类型
typedef struct{ //图的定义
int edges[MAXV][MAXV]; //邻接矩阵
int n,e; //顶点数，边数
VertexType vexs[MAXV]; //存放顶点信息
}MGraph;
① 对图中么个顶点 i 建立一个单链表，将顶点 i 的所有邻接点链起来。
② 每个单链表上添加一个表头节点（表示顶点信息）。并将所有表头节点构成一个数组，下标为 i 的元素表示顶点 i 的表头节点。
图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。
有两类节点：头节点、边节点
邻接表的特点如下：
//声明边界点类型
typedef struct ANode{
int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
InfoType info; //该边的权值等信息
}ArcNode;
//声明邻接表头节点类型
typedef struct VNode{
Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条边
}
//声明图邻接表类型
typedef struct{
VNode adjlist[MAXV]; //邻接表
int n,e; //图中顶点数n和边数e
}ALGraph;
从给定图中任意指定的顶点出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。
图的遍历得到的顶点序列称为图遍历序列。
根据搜索方法的不同，图的遍历方法分为两种：深度优先遍历（DFS）、广度优先遍历（BFS）
深度优先遍历过程：
(1)从图中某个初始顶点v出发，首先访问初始顶点v。
(2)选择一个与顶点v相邻且没有被访问过的顶点w，再从w出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。
算法设计思路：
(1)深度优先遍历的过程体现出后进先出的特点：用栈或递归方式实现。
(2)如何确定一个顶点是否访问过？设置一个visited[]全局数组，visited[i]=0表示顶点i没有访问；visited[i]=1表示顶点i已经访问过。
void DFS(ALGraph *G,int v){
ArcNode *p;int w;
visited[v] = 1; //置已访问标记
printf("%d",v); //输出被访问顶点的编号
p=G->adjlist[v].firstarc; //p指向顶点v的第一条边的边头节点
while(p!=NULL){
w=p->adjvex;
if(visited[w]==0)
DFS(G,w); //若w顶点未访问，递归访问它
p=p->nextarc; //p指向顶点v的下一条边的边头节点
}
}
广度优先遍历的过程：
(1) 访问初始点v，接着访问v的所有未被访问过的邻接点。
(2) 按照邻接点的次序访问每一个顶点的所有未被访问过的邻接点。
(3) 依次类推，知道图中所有和初始点v有路径相同的顶点都被访问过为止。
算法设计思路：
(1) 广度优先搜索遍历体现先进先出的特点，用队列实现。
(2) 如何确定一个顶点是否访问过？设置一个visited[]数组，visited[i]=0表示顶点 i 没有访问；visited[i]=1表示顶点 i 已经访问过。
采用邻接表的BFS算法：
void BFS(ALGraph *G,int v){
ArcNoed *p;int w,i;
int queue[MAXV],front=0,rear=0; //定义循环队列
int visited[MAXV];
for(i=0;i<G->n;i++)
visited[i]=0; //访问标志数组初始化
printf("%2d",v); //输出被访问顶点的编号
visited[v]=1; //置已访问标记
rear=(rear+1)%MAXV;
queue[rear]=v; //v进队
while(front!=rear){ //队列不空时循环
front=(front+1)%MAXV;
w=queue[front]; //出队并赋给w
p=G->adjlist[w].firstarc; //找w的第一个的邻接点
while(p!=NULL){
if(visited[p->adjvex]==0){
printf("%2d",p->adjvex)； //访问之
visited[p->adjvex]=1;
rear=(rear+1)%MAXV; //相邻顶点进队
queue[rear]=p->adjvex;
}
p=p->nextarc; //找下一个邻接顶点
}
}
}
无向连通图：调用一次DFS或BFS，能够访问到图中的所有顶点。
无向非连通图：调用一次DFS或BFS，只能访问到初始点所在连通分量中的所有顶点，不可能访问到其他连通分量中的顶点。
可以分别遍历每个连通分量，才能够访问到图中的所有顶点。
采用深度优先遍历方法遍历非连通图的算法如下：
void DFS1(ALGraph *G){
int i;
for(i=0;i<G->n;i++) //遍历所有未访问过的顶点
if(visited[i]==0)
DFS(G,I);
}
采用广度优先遍历方法遍历非连通图的算法如下：
void BFS1(ALGraph *G){
int i;
for(i=;i<G->n;i++) //遍历所有未访问过的顶点
if(visited[i]==0)
BFS(G,I);
}
例6-2
假设图G采用邻接表存储，设计一个算法，判断顶点 u→v 是否有简单路径。
解：从顶点u开始进行深度优先遍历，当搜索到顶点v时表名从顶点u到v有路径，用形参has表示顶点 u→v 是否有路径。
void ExistPath(AGraph *,int u,int v,bool &has){
//has表示u到v是否有路径，初值为false;
int w;ArcNode *p;
visited[u]=1; //置以访问标记
if(u==v){ //找到了一条路径
has=true; //置has为true并结束算法
return
}
p=G->adjlist[u].firstarc; //p指向顶点u的第一个相邻点
while(p!=NULL){
w=p->adjvex;
if(visited[w]==0) //若w顶点未访问，递归访问它
ExistPath(G,w,v,has)
p=p->nextarc; //p指向顶点u的下一个相邻点
}
}
一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点和构成一棵树的(n-1)条边。
深度优先生成树、广度优先生成树
最小生成树的概念：
(1) 对于带权连通图G（每条边上的权均为大于0的实数），可能有多棵不同生成树。
(2) 每棵生成树的所有边的权值之和可能不同。
(3) 其中权值之和最小的生成树成为图的最小生成树。
连通图：仅需调用遍历过程一次，从图中任一顶点出发，便可以遍历图中的各个顶点，产生相应的生成树。
非连通图：需多次调用遍历，生成森林。
Prim算法是一种构造性算法，用于构造最小生成树，更适合稠密图求最小生成树。
(1) 初始化U={v}。v到其他顶点的所有边为候选边。
(2) 重复以下步骤n-1次，使得其他n-1个顶点被加入到U中：
① 从候选变中挑选权值最小的边输出，设该边在V-U中的顶点是k，将k加入U中；
② 考察当前V-U找那个的所有顶点j，修改候选变：若(j,k)的权值小于原来和顶点k关联的候选边，则用(k,j)取代后者作为候选边。
算法设计（解决4个问题）：
(1) 如何求U、V-U两个顶点集之间的最小边？
答：只考虑V-U中顶点 j 到 U 顶点集的最小边（无向图），比较来找最小边。
(2) 如何存储顶点 j 到 U 顶点集的最小边？
答：closes[j]表示顶点 j 到 U 集合的最小顶点，(j,closest[j])是顶点j的最小边，权值为lowcost[j]。
(3) 一个顶点属于哪个集合
答：lowcost[k]=0 表示属于U集合，lowcost[k]!=0 表示属于V-U集合。
(4) 图采用哪种存储结构更合适？
答：邻接矩阵。
void Prim(MGraph g,int v){
int lowcost[MAXV];
int min;
int closest[MAXV],i,j,k;
for(i=0;i<g.n;i++){ //初始化
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for(i=1;i<g.n;i++){ //输出n-1条边
min=INF;
for(j=0;j<g.n;j++) //在V-U中找出离U最近的顶点k
if(lowcost[j]!=0 && lowcost[j]<min){
min=lowcost[j];
k=j; //k记录最近顶点编号
}
printf(" 边(%d,%d)权为:%d\n",closest[k],k,min); //这里可以建树
lowcost[k]=0; //标记k已经加入U
for(j=0;j<g.n;j++) //修改数组lowcost和closest
if(lowcost[j]!=0 && g.edges[k][j]<lowcost[j]){
lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
Kruskal算法也是一种求带权无向图的最小生成树的构造性算法。
按权值的递增次序选择合适的边来构造最小生成树的方法。
Kruskal算法过程：
(1) 置U的初值等于V，表示最小生成树的边集TE的初值为空集。
(2) 将图G中的边按权值从小到大的顺序依次选取：
① 若选取的边未使生成树T形成回路，则加入TE；
② 否则舍弃，直到TE中包含(n-1)条边为止。
算法设计（解决3个问题）:
(1) 图采用哪种存储结构更合适？ 邻接矩阵
(2) 边的排序问题？ 这里采用直接插入排序算法
(3) 如何解决加入一条边后是否出现回路？ 采用连通分量编号或顶点集合编号
假设给定一个加权连通图G，G的边集合为E，顶点个数为n，要求其一棵最小生成树T。
假设T中的边和顶点均涂成红色，其余边为白色。开始时G中的边均为白色。
1）将所有顶点涂成红色；
2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红；
3）重复2）直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合。
注意到在算法执行过程中，红色顶点和红色边会形成一个或多个连通分支，它们都是G的子树。一条边与红色边形成圈当且仅当这条边的两个端点属于同一个子树。因此判定一条边是否与红色边形成圈，只需判断这条边的两端点是否属于同一个子树。
上述判断可以如此实现：给每个子树一个不同的编号，对每一个顶点引入一个标记t，表示这个顶点所在的子树编号。当加入一条红色边，就会使该边两端点所在的两个子树连接起来，成为一个子树，从而两个子树中的顶点标记要改变成一样。综上，可将Kruskal算法细化使其更容易计算机实现。
考虑带权有向图，把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径长度。
从源点到终点可能不止一条路径，把路径长度最短的那条路径 称为最短路径。
问题描述：给定一个带权有向图G与源点v，求从v到G中其 他顶点的最短路径，并限定各边上的权值大于或等于0。
单源最短路径问题：Dijkstra算法
求解思路：
把图中顶点集合V分成两组：
(1) 第1组为已求出最短路径的顶点集合，用S表示。
(2) 第2组为其余未求出最短路径的顶点集合，用U表示。
每一步求出v到U中一个顶点u的最短路径，并将u移动到S中，直到U为空。
算法过程：
(1) 初始化：S只包含源点即S={v}，v的最短路径为0。U包含除 v 外的其他顶点，U中顶点 i 距离为边上的权值或无穷大。
(2) 从U中选取一个距离 v 最小的顶点 u，把 u 加入S中(该选定的距离就是v→u的最短路径长度)。
(3) 以u为新考虑的中间点，修改U中各顶点 j 的最短路径长度：若从源点 v 到顶点 j 的最短路径长度(经过顶点u)比原来最短路径长度(不经过顶点u)短，则修改顶点 j 的最短路径长度。
顶点 v→j 的最短路径长度 = MIN(Cvk+Wkj,Cvj)
(4) 重复步骤(2) 和(3) 知道所有顶点都包含在S中。
算法设计：
(1) 如何存放最短路径长度：
用一维数组dist[j]存储！
源点v默认，dist[j]表示源点→顶点j的最短路径长度。
如dist[2]=12表示源点→顶点2的最短路径长度为12。
(2) 如何存放最短路径：
从源点到其他顶点的最短路径有n-1条，一条最短路径用一个一维数组表示，如从顶点0→5的最短路径为0、2、3、5，表示为path[5]={0,2,3,5}。
所有n-1条在最短路径可以用二维数组path[][]存储。
改进：用一维数组path[]记录每个顶点到源点的最短路径中的前驱节点。
狄克斯特拉算法如下(v为源点编号)，复杂度为O(n^2):
void Dijkstra(MGraph g,int v){
int dist[MAXV],path[MAXV];
int s[MAXV];
int mindis,i,j,u;
//dist和path数组初始化
for(i=0;i<g.n;i++){
dist[i]=g.edges[v][i]; //距离初始化
s[i]=0; //s[]置空
if(g.edges[v][i]<INF) //路径初始化
path[i]=v; //顶点v到i有边时
else path[i]=1; //顶点v到i没边时
}
s[v]=1; //源点v放入S中
for(i=0;i<g.n;i++){
mindis=INF;
for(j=0;j<g.n;j++)
if(s[j]==0&&dis[j]<mindis){
u=j;
mindis=dist[j];
}
s[u]=1; //顶点u加入S中
for(j=0;j<g.n;j++) //修改不在s中的顶点的距离
if(s[j]==0)
if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j]){
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
Dispath(dist,path,s,g.n,v); //输入最短路径
}
问题表述：对于一个各边权值均大于零的有向图，对每一对顶点i!=，求出顶点 i 与 顶点 j 之间的最短路径和最短路径长度。
多源最短路径问题：Floyd算法
| Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行 | V | 次Dijkstra算法，也要高于执行V次。 |
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。
缺点：时间复杂度比较高，不适合计算大量数据。
算法：迭代(递推)思路
假设有向图G=(V,E)采用邻接矩阵存储。设置一个二维数组A用于存放当前顶点之间的最短路径长度，分量A[i][j]
表示当前顶点i→j的最短路径长度。
A[i][j]：i→j的路径上所经过的顶点编号不大于k的最短路径长度。
(1) 初始时，有A-1[i][j]=g.edges[i][j]。
(2) 考虑从 i→j 的最短路径进过编号为k顶点的情况：
Ak[i,j]=MIN{Ak-1[i,j]，Ak-1[i,k]+Ak-1[k,j]}
算法设计（解决2个问题）：
(1) 用二维数组A存储最短路径长度：
Ak[i][j]表示考虑顶点0~k后得出的 i→j的最短路径长度。
An-1[i][j]表示最终的 i→j的最短路径长度。
(2) 用二维数组path存放最短路径：
pathk[i][j]表示考虑顶点0~k后得出的i→j的最短路径。
pathn-1[i][j]表示最终 i→j 的最短路径。
弗洛伊德算法如下(算法复杂度为O(n^3))：
void Floyd(MatGraph g){ //求每对顶点之间的最短路径
int A[MAXVEX][MAXVEX]; //建立A数组
int path[MAXVEX][MAXVEX]; //建立path数组
int i,j,k;
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++){
A[i][j]=g.edges[i][j];
if(i!=j ^ g.edges[i][j]<INF)
path[i][j]=i; //i和j顶点之间有一条边时
else path[i][j]=-1; //i和j顶点之间没有一条边时
}
for(k=0;k<g.n;k++) //求Ak[i][j]
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
if(A[i][j]>A[i][k]+A[k][j]){ //找到更短路径
A[i][j]=A[i][k]+A[k][j]; //修改路径长度
path[i][j]=path[k][j]; //修改最短路径为经过顶点k
}
}
Floyd算法共享前面路径比较所得到的信息A
设G=(V,E)是一个具有n个顶点的有向图，V中顶点序列v1，v2,…,vn称为一个拓扑序列，当且仅当该顶点蓄力满足下列条件：若<i,j>是图中的边(或从顶点i→j有一条路径)：则在拓扑序列中顶点i必须排在顶点j之前。
在一个有向图中找一个拓扑序列的过程称为拓扑排序。
拓扑排序步骤：
(1) 从有向图中选择一个没有前驱的顶点并且输出它。
(2) 从图中删去该顶点，并且删去从该顶点发出的全部有向边。
(3) 重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。
拓扑排序算法设计：
将邻接表定义中的VNode类型修改如下：
typedef struct{ //表头节点类型
Vertex data; //顶点信息
int count; //存放顶点入度
ArcNode *firstarc; //指向第一条边
}
拓扑排序算法如下：
void TopSort(VNode adj[],int n){
int i,j;int St[MAXV],top=-1; //栈St的指针为top
ArcNode *p;
for(i=0;i<n;i++)
if(adj[i].count==0){ //入度为0的顶点进栈
top++;
St[top]=i;
}
while(top>-1){ //栈不为空时循环
i=St[top];top--; //出栈
printf("%d",i);
p=adj[i].firstarc;
while(p!=NULL){
j=p->adjvex;adj[j].count--;
if(adj[j].count==0){
top--;
St[top]=j;
}
p=p->nextarc; //找下一个相邻顶点
}
}
}
(1) 用一个带权有向图(DAG)描述工程的预计进度。
(2) 顶点表示事件，有向边表示活动，边e的权c(e)表示完成活动e所需的时间。
(3) 图中入度为0的顶点表示工程的开始时间，出度为0的顶点表示工程的结束事件。
从AOE网中源点到汇点的最长路径，具有最大长度的路径叫关键路径。
关键路径是由关键活动构成的，关键路径可能不唯一。
关键路径为源点到汇点的最长路径，这样转变为查找图中最长路径问题。
求解方法：求一个AOE的关键路径→求AOE的关键活动
(1) 事件的最早开始和最迟开始时间
事件v的最早开始时间：规定源点事件的最早开始时间为0。定义图中任一事件v的最早开始时间，ee(v)等于x、y、z到v所有路径长度的最大值：
ee(v)=0; //当v为源点时
ee(v)=MAX{ee(x)+a，ee(yy)+b，ee(z)+c} //否则
事件v的最迟开始时间：定义在不影响整个工程进度的前提下，事件v必须发生的时间成为v的最迟开始时间。le(v)应等于ee(y)与v到汇点的最长路径长度之差：
le(v)=ee(v) //当v为汇点时
le(v)=MIN{le(x)-1，le(y)-b，le(z)-c} //否则
(2) 活动的最早开始时间和最迟开始时间
活动a的最早开始时间e(a)指该活动起点x事件的最早开始时间，即：e(a)=ee(x)
活动a的最迟开始时间l(a)指该活动终点y事件的最迟开始时间与该活动所需时间之差，即：l(a)=le(y)-c
(3) 求关键活动
对于每个活动a，求出d(a)=l(a)-e(a)，若d(a)为0，则称活动a为关键活动。
对于关键活动来说，不存在富余时间。
树形式化定义：T={D,R}。D是包含n个节点的有限集合。当n=0时为空树，否则关系R满足以下条件：
有且仅有一个节点对于关系R来说没有前驱节点，称作根节点。
除根节点外，每个节点有且仅有一个前驱节点。
D中每个节点可以有零个或多个后继节点。
1、节点的度与树的度：
树中一个节点的子树的个数成为该节点的度。树中各节点的度的最大值称为树的度，通常将度为m的树成为m次树或m叉树。
2、分支节点与叶节点：
度不为零的节点称为非终端节点，又叫分支节点。度为零的节点称为终端节点或叶节点。
度为1的节点称为单分支节点；度为2的节点称为双分支节点。
3、路径与路径长度：
两个节点之间的节点序列称为路径。
路径长度等于路径所通过的节点数目减一。
4、有序数和无序树：
若树中各节点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。
5、森林：
n个互不相交的树的集合称为森林。
性质1 树中的节点数等于所有节点的度数加1。
性质2 度为m的树中第i层上至多有m^(i-1)个节点(i>=1)。
性质3 高度为h的m次树至多有 (m^h - 1)/(m-1)个节点。
性质4 具有n个节点的m次树的最小高度为
查找、插入或删除、遍历。
主要的遍历方法：
先根遍历：若树不空，则先访问根节点，然后依次先根遍历各棵子树。
后根遍历：若树不空，则先依次后根遍历各棵子树，然后访问根节点。
层次遍历：若树不空，则自上而下、自左至右访问树中每个节点。
注意：先根和后跟遍历算法都是递归的。
1、双亲存储结构：每一个节点都有一个指针指向双亲位置。
2、孩子链存储结构：每个节点都有一组指针指向一棵子树。
3、孩子兄弟链存储结构：每个节点都有三个域，数据元素域、第一个孩子节点指针域、一个兄弟节点指针域。
满二叉树：高度为h的二叉树恰好有2^h-1个节点。
完全二叉树：在一棵二叉树中
最多只有下面两层的节点的度数小于2
并且最下面一层的叶节点都依次排列在该层最左边的位置上。
完全二叉树实际上是对应的满二叉树删除叶节点层最右边若干个节点得到的。
性质1 非空二叉树上叶节点数等于双分支节点数加1。
性质2 非空二叉树上第i层上至多有2^(i-1)个节点。
性质3 高度为h的二叉树至多有2^h-1个节点。
性质4 完全二叉树性质：
若i<(n/2)，则编号为i的节点为分支节点，否则为叶节点。
除树根节点外，若一个节点的编号为i，则它的双亲节点的编号为i/2。
若编号为i的节点有左孩子节点，则左孩子节点的编号为2i；
若编号为i的节点有右孩子节点，则右孩子节点的编号为2i+1。
对于完全二叉树来说，顺序存储是十分合适的。
对于非完全二叉树来说，浪费空间惊人。
在顺序存储结构中，找一个节点的双亲和孩子都很容易。
二叉链比较节省存储空间。占用的存储空间只与树中节点个数有关。
在二叉链中，找一个节点的孩子很容易，但找其双亲不方便。
//二叉树查找一个元素的算法
BTNode *FindNode(BTNode *b,ElemType x){
BTNode *p;
if(b==NULL) return NULL;
else if (b->data==xx) return b;
else {
p=FindNode(b->left,x);
if(p!=NULL) return p;
else return FindNode(b->right,x);
}
}
//求树的高度
int BTNodeDepth(BTNode *b){
int ldep,rdep;
if(b==NULL) return 0; //空树
else{
ldep = BTNodeDepth(b->left); //求左子树的高度
rdep = BTNodeDepth(b->right); //求右子树的高度
return ldep>rdep?(ldep+1):(rdep+1);
}
}
//先序遍历的递归算法 NLR
void PreOrder(BTNode *b){
if(b!=NULL){
printf("%c",b->data); //访问根节点
PreOrder(b->left);
PreOrder(b->right);
}
}
//中序遍历的递归算法 LNR
void InOrder(BTNode *b){
if(b!=NULL){
PreOrder(b->left);
printf("%c",b->data); //访问根节点
PreOrder(b->right);
}
}
//后序遍历的递归算法 LRN
void PostOrder(BTNode *b){
if(b!=NULL){
PreOrder(b->left);
PreOrder(b->right);
printf("%c",b->data); //访问根节点
}
}
//层次遍历算法，从上到下，从左到右遍历
/*思路：使用一个队列,时间复杂度为O(n)
1.将根节点进队
2.队不空时循环：从队列中拿出一个节点*p，访问它；
若它有左孩子节点，将左孩子节点进队
若它有右孩子机电，将右孩子节点进队。*/
void LevelOrder(BTNode *b){
BTNode *p;
BTNode *qu[MaxSize]; //定义环形队列，存放节点指针
int front,rear;
front = rear = 0; //置队列为空队列
rear++;
qu[rear]=b;
while(front!=rear){ //队列不为空循环
front=(front+1)%MaxSize;
p=qu[front]; //队头出队列
printf("%c",->data); //访问节点
if(p->left!=NULL){ //有左孩子时将其进队
rear = (rear+1)%MaxSize;
qu[rear] = p->left;
}
if(p->right!=NULL){ //有右孩子时将其进队
rear = (rear+1)%MaxSize;
qu[rear] = p->right;
}
}
}
假设二叉树采用二叉链存储结构存储，设计一个算法，计算一棵给定二叉树的所有节点个数。
int Nodes(BTNode *b){
int num1,num2;
if(b==NULL) return 0;
else
return Nodes(b->left)+Nodes(b->right)+1;
//先左子树，再右子树，再加1，后序遍历的思想
//三者顺序不同，递归的方式也不同
}
假设二叉树采用二叉链存储结构存储，设计一个算法，计算一棵给定二叉树的所有叶子结点个数。
int LeafNodes(BTNode *b){
int num1,num2;
if(b==NULL) return 0;
else if(b->left==NULL && b->right==NULL)
return 1;
else{
num1 = LeafNodes(n->left);
num2 = LeafNodes(b->right);
return (num1+num2);
}
//先左子树，再右子树，再相加，后序遍历的思想
//三者顺序不同，递归的方式也不同
}
假设二叉树采用二叉链存储结构，设计一个算法把二叉树b复制到二叉树t中。
void Copy(BTNode *b,BTNode *&t){
if(b==NULL) t=NULL;
else{
t=(BTNode*)malloc(sizeof(BTNode));
t->data = b->data; //复制一个根节点*t
Copy(b->left,t->left); //递归复制左子树
Copy(b->right,t->right); //递归复制右子树
}
}
void Copy(BTNode *b,BTNode *&t){
if(b==NULL) t=NULL;
else{
t=(BTNode*)malloc(sizeof(BTNode));
t->data = b->data; //复制一个根节点*t
Copy(b->left,t->left); //递归复制左子树
Copy(b->right,t->right); //递归复制右子树
}
}
设二叉树采用二叉链存储结构，设计一个算法把二叉树b的左、右子树进行交换。要求不破坏元二叉树。
void Swap(BTNode *b,BTNode *&t){
if(b==NULL) t=NULL;
else{
t=(BTNode*)malloc(sizeof(BTNode));
t->data = b->data; //复制一个根节点*t
Swap(b->left,t->right); //递归交换左子树
Swap(b->right,t->left); //递归交换右子树
}
}
假设二叉树采用二叉链存储结构，设计一个算法Level()求二叉树b中值为x的节点的层次。
解：设Level(b,x,h)返回二叉树b中data值为x的节点的层次，其中h表示b所指节点的层数。
当在二叉树b中找到data值为x的节点，返回其层次；若没有找到，则返回0。
递归算法一定要先设计递归模型，确定终结条件。
int Level(BTNode *b,ElemType x,int h){
if(b==NULL) return 0; //空树时返回0
else if(b->data==x) return h; //找到节点时
else {
int l=Level(b->left,h+1); //在左子树中查找
if(l==0) //左子树中未找到时在右子树中查找
return Level(b->right,x,h+1);
return l;
}
}
假设二叉树采用二叉链存储结构，设计一个算法输出从根节点到每个叶子节点的逆路径。
相关概念：
采用某种方法遍历二叉树的结果是一个节点的线性序列。
修改空链域改为存放指向节点的前趋和后继节点的地址。
这样的指向该线性序列中的“前趋”和“后继”的指针，称作线索。
创建线索的过程称为线索化。
显然线索二叉树与采用的遍历方法相关，有先序线索二叉树、中序线索二叉树和后序线索二叉树。
在节点的存储结构上增加两个标志位来区分这两种情况：
左标志ltag：0表示left指向左孩子节点，1表示left指向前趋节点，即左线索
右标志rtag：0表示right指向右孩子节点，1表示right指向后继节点，即右线索
建立某种次序的线索二叉树过程：
- 以该遍历方法遍历一棵二叉树。
- 在遍历的过程中，检查当前访问节点的左、右指针域是否为空：
如果左指针域为空，将它改为指向前趋节点的线索；
如果右指针域为空，将它改为指向后继节点的线索；
前驱、后继节点与遍历方式有关。
建立线索二叉树的目的：
对二叉树中序遍历，递归算法：时间复杂度均为O(n)，空间复杂度均为O(h)
对二叉树中序遍历，非递归算法：时间复杂度均为O(n)，空间复杂度均为O(h)
对中序线索二叉树中序遍历，时间复杂度均为O(n)，空间复杂度均为O(1)
建立中序线索二叉树的算法：
CreatTherad(b)算法：对以二叉链存储的二叉树b进行中序线索化，并返回线索化后头节点的指针root。
Thread(p)算法：对以*p为根节点的二叉树子树的中序线索化。
二叉树中序序列的开始节点是根节点的最左下节点，尾节点是根节点的最右下节点。
在中序遍历中：
p总是指向当前线索化的节点。
pre作为全局变量，指向刚刚访问过的节点。
pre是p的中序前趋节点，p是pre的中序后继节点。
TBTNode
TBTNode *pre; //全局变量
TBTNode *CreatThread(TBTNode *b){ //中序线索化二叉树
TBTNode *root;
root = (TBTNode *)malloc(sizeof(TBTNode)); //创建头节点
root->ltag=0; root->rtag=1; root->right=b;
if(b==NULL) root->left = root; //空二叉树
else {
root->left = b; //让头节点的left指针指向b
pre = root; //pre是*p的前趋节点，供加线索用
Thread(b); //中序遍历线索化二叉树
pre->right = root; //最后处理，加入指向头节点的线索
pre->rtag = 1;
root->right = pre; //头节点右线索化
}
return root;
}
void Thread(TBTNode *&p){
if(p!=NULL){
Thread(p->left); //左子树线索化
if(p->left == NULL){ //前趋线索化
p->left=pre; //建立当前节点的前趋线索
p->ltag=1;
}else p->ltag=0;
if(pre->right == NULL){ //后继线索化
pre->right=p; //建立前趋节点的后继线索
pre->right=1;
}else pre->right=0;
pre = p;
Thread(p->right); //递归调用右子树线索化
}
}
//上代码是中序遍历两个Thread及中间部分
遍历某种次序的线索二叉树，就是从该次序下的开始节点出发，反复找到该节点在该次序下的后继节点，直到头节点。
在中序线索二叉树中中序遍历的过程：
/*
p指向根节点;
while p != root 时循环{
找开始节点*p;
访问*p节点;
while(*p节点有右线索)
一直访问下去;
p转向右孩子节点;
}
*/
void ThInOrder(TBTNode *tb){
TBTNode *p=tb->left; //p指向根节点
while(p!=tb){
while(p->ltag==0) p=p->left; //找开始节点
printf("%c",p->data); //访问开始节点
while(p->rtag==1 && p->right!=tb){
p=p->right;
printf("%c",p->data);
}
p=p->right;
}
}
优点：中序遍历算法既没有递归也没有用栈，空间效率得到提高。
设二叉树具有n个带权值的叶节点，那么从根节点到各个叶节点的路径长度为相应节点权值的乘积的和，叫做二叉树的带权路径长度。
具有在最小带权路径长度的二叉树成为哈夫曼树（最优树）。
权值是指该节点的优先级，越大，表示搜索的频率越高。越靠近根节点，编码越短。
构造哈夫曼树的原则：
权值越大的叶节点越靠近根节点
权值越小的叶节点越远离根节点
构造哈夫曼树的过程：
在节点集合中选取根节点的权值最小和次小的两个二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根节点的权值为其左、右子树根节点权值之和。然后不断重复，直到生成一棵哈夫曼树。
规定哈夫曼树中的左分支为0，右分支为1，则从根节点到每个叶节点所经过的分支对应的0和1组成的序列便为该节点对应字符的编码。这样的编码成为哈夫曼编码。
哈夫曼编码特点：权值越大的字符编码越短，反之越长。
在一组字符的哈夫曼编码中，不可能出现一个字符的哈夫曼编码是另一个字符哈夫曼编码的前缀。
假设二叉树采用二叉链存储结构，设计一个算法求二叉树b中度为2的节点个数。
int dnodes(BTNode *b){
if(b==NULL) return 0;
if(b->left!=NULL && b->right!=NULL)
return 1+dnodes(b->left)+dnodes(b->right);
else
return dnodes(b->left)+dnodes(b->right);
}
假设二叉树采用二叉链存储结构，设计一个算法求二叉树b中第k层的节点个数。
解：设计算法为knumber(b,h,k,&n)，h表示b所指的节点层次，n是引用型参数，用于保存第k层的节点个数。 初始调用时，b为根节点指针，h为1，n赋值为0，即调用方式是：n=0; knumber(b,1,k,n)。
void knumber(BTNode *b,int h,int k,int &n){
if(b==NULL) return; //空树直接返回
else{ //处理非空树
if(h==k) n++; //当前访问的节点在第k层时，n增1
else if(h<k){ //若当前节点层次小于k,递归处理左、右子树
knumber(b->left,h+1,k,n);
knumber(b->right,h+1,k,n);
}
}
}
void knumber(BTNode *b,int h,int k,int &n){
if(b==NULL) return; //空树直接返回
else{ //处理非空树
if(h==k) n++; //当前访问的节点在第k层时，n增1
else if(h<k){ //若当前节点层次小于k,递归处理左、右子树
knumber(b->left,h+1,k,n);
knumber(b->right,h+1,k,n);
}
}
}
假设二叉树采用二叉链存储结构，设计一个算法求二叉树b的宽度。
解：levelnumber(BTNode *b,int h,int a[])：求二叉树b中所有层的节点个数，存放在a数组中，a[h]表示第h层节点个数。
//将每一层的节点数存入数组a中
void levelnumber(BTNode *b,int h,int a[]){
if(b==NULL) return; //空树直接返回
else{ //处理非空树
a[h]++;
levelnumber(b->left,h+1,a);
levelnumber(b->right,h+1,a);
}
}
//具体求解
int BTWidth1(BTNode *b){
int width=0,i; int a[MaxSize];
for(i=1;i<MaxSize;i++)
a[i]=0; //设置所有元素初始化为0
levelnumber(b,1,a);
i=1;
while(a[i]!=0){ //求a中最大元素即宽度
if(a[i]>width)
width=a[i];
i++;
}
return width;
}
假设二叉树采用二叉链存储结构，设计一个算法求二叉树b的宽度（采用层次遍历方法）。
int BTWidth2(BTNode *b){
struct{
int lno; //节点的层次
BTNode *p; //节点指针
}Qu[MaxSize]; //定义非环形队列
int front,rear; //定义队头和队尾指针
int lnum,width,i,n;
front=rear=0; //置队列为空队
if(b!=NULL){
rear++;
Qu[rear].p=b; //根节点进队
Qu[rear].lno=1; //根节点的层次为1
while(rear!=front){ //队不空时循环
front++;
b=Qu[front].p; //出队节点p
lnum=Qu[front].lno;
if(b->left!=NULL){ //有左孩子，将其进队
rear++;
Qu[rear].p=b->left;
Qu[rear].lno=lnum+1;
}
if(b->right!=NULL){ //有右孩子，将其进队
rear++;
Qu[rear].p=b->right;
Qu[rear].lno=lnum+1;
}
}
width=0;lnum=1;i=1; //width存放宽度
while(i<rear){
n=0;
while(<rear && Qu[i].lno==lnum){
n++; //n累计一层中的节点个数
i++; //i扫描队列中所有节点
}
lnum=Qu[i].lno;
if(n>width) width=n;
}
return width;
}
else return 0;
}
直接递归和间接递归（两个函数互相调用）。
如果一个递归函数中递归调用语句是最后一条执行语句，则称这种递归调用为尾递归。
尾递归算法：可以用循环语句转换成等价的非递归算法
其他递归算法：可以通过栈来转换为等价的非递归算法
递归模型是递归算法的抽象，它反映一个递归问题的递归结构。
一般地，一个递归模型是由递归出口（fun(1)=1）和递归体（fun(n)=n*fun(n-1)）两部分组成。
- 设计求解问题的递归模型
- 转换成对应的递归算法
求递归模型的步骤：
(1)对原问题f(s)进行分析，称为“大问题”，假设出合理的“小问题”；
(2)假设f(s’)是可解的，在此基础上确定f(s)的解，即给出f(s)与f(s’)之间的关系 → 递归体。
(3)确定一个特定情况（如f(1)或f(0)）的解 → 递归出口。
基于递归数据结构的递归算法设计：
递归数据结构的数据特别适合递归处理 → 递归算法。
//正向显示所有节点值
void traverse(Node *L){
if(L==NULL) return;
printf("%d",L->data);
traverse(L->next);
}
//反向显示所有节点值
void traverseR(Node *L){
if(L==NULL) return;
traverseR(L->next);
printf("%d",L->data);
}
基于递归求解方法的递归算法设计：
采用递归方法求解问题时，需要对问题本身进行分析，确定大、小问题解之间的关系，构造合理的递归体。
- 确定问题的形式化描述
- 确定哪些是大问题，哪些是小问题
- 确定大、小问题的关系
- 确定特殊（递归结束）的情况
例题：假设a素组含有1,2,…,n,求其全排列。
解：设f(a,n,k)为a[0..k]（k+1个元素）的所有元素的全排序，为大问题。
则f(a,n,k-1)为a[0..k-1]（k个元素）的所有元素的全排序，为小问题。
void perm(inta[],int n,int k){
int i,j;
if(k==0){
for(j=0;j<n;k++)
printf("%d",a[j]);
printf("\n");
}else
for(i=0;i<=k;i++){
swap(a[k],a[i]);
perm(a,n,k-1);
swap(a[k],a[i]);
}
}
递归调用后面的语句表示该子问题执行完毕后要完成的功能。
void fun(int n){
if(n>=1){
printf("n1=%d\n",n);
fun(n-1);
printf("n2=%d\n",n);
}
}
设计顺序串上实现串比较运算 strcmp(s,t)的算法。 ab<abcd，abcd<abd
解：算法思路如下：
(1)比较s和t两个串共同长度范围内的对应字符：
①若s的字符>t的字符，返回1；
②若s的字符<t的字符，返回-1；
③若s的字符=t的字符，按上述规则继续比较。
(2)当(1)中对应字符均相同时，比较s和t的长度：
①两者相等时，返回0；
②s的长度>t的长度，返回1；
③s的长度<t的长度，返回-1。
int Strcmp(SqString s,SqString t){
int i,comlen;
if(s.length<t.length) comlen=s.length; //求s和t的共同长度
else comlen=t.length;
for(i=0;i<comlen;i++)
if(s.data[i]>t.data[i])
return 1;
else if(s.data[i]<t.data[i])
return -1;
if(s.length=t.length)
return 0; //s==t
else if(s.length<t.length)
return 1; //s>t
else return -1; //s<t
}
在链串中，设计一个算法把最先出现的子串”ab”改为”xyz”。
解：
①查找：p->data=’a’ && p->next->data=’b’
②替换：
void Repl(LiString *&s){
LiString *p = s->next,*q;
int find = 0;
while(p->next!=NULL && find==0){ //查找ab子串
if(p->data=='a'&&p->next->data=='b'){
p->data='x';p->next->data='z';
q=(LiString *)malloc(sizeof(LiString));
q->data='y';q->next=p>next;p->next=q;
find=1;
}
else p=p->next;
}
}
Brute-Force——BF算法，简单匹配算法。时间复杂度 O(n*m)
int index(SqString s,SqString t){
int i=0,j=0; //i指向s，j指向t
while(i<s.length && j<t.length){
if(s.data[i] == t.data[j]){ //继续匹配下一个字符
i++; //主串和子串依次匹配下一个字符
j++;
}else{ //主串、子串指针回溯重新开始下一次匹配
i=i-j+1; //主串从下一个位置开始匹配
j=0; //子串从头开始匹配
}
}
if(j>=t.length)
return (i-t.length); //返回匹配的第一个字符的下标
else
return -1; //模式匹配不成功
}
KMP算法：消除了主串指针的回溯。平均时间复杂度为O(n+m)，最坏时间复杂度为O(n*m)
//由模式串t求next值的算法
void GetNext(SqString t,int next[]){
int j,k;
j=0;k=-1;next[0]=-1;
while(j<t.length-1){
if(k==-1||t.data[j]==t.data[k]){
j++;k++;
next[j]=k;
}
else k=next[k];
}
}
//KMP算法
int KMPIndex(SqString s,SqString t){
int next[MaxxSize],i=0,j=0;
GetNext(t,next);
while(i<s.length && j<t.length){
if(j==-1||s.data[i]==.data[j]){
i++;j++; //i、j各增1
}else
j=next[j]; //i不变，j后退
}
if(j>=t.length)
return (i-t.length); //返回匹配模式串的首字符下标
else return -1; //返回不匹配标志
}
//由模式串t求next值改为求nextval,将KMP算法中的next改为nextval
void GetNextval(SqString t,int nextval[]){
int l=nextval.length,j=1;
int next[] = new int[l];
nextval[0]=-1;
GetNext(t,next);
while(j<l){
if(t[j]==t[next[j]]){
nextval[j]=nextval[next[j]];
}else
nextval[j]=next[j];
j++;
}
}
假设串采用顺序结构存储。设计一个算法求串s中出现的第一个最长重复子串的下标和长度。
解：(i,len)记录当前重复子串，(maxi,maxlen)记录第一个最长重复子串。
void maxsubstr(SqString s,SqString &t){
int maxi=0,maxlen=0,len,i,j,k;
i=0;
while(i<s.length){ //从下标为i的字符开始
j=i+1; //从i的下一个位置开始找重复子串
while(j<s.length){
if(s.data[i])==s.data[j]){ //找一个子串，其起始下标为i,长度为len
len=1;
for(=1;s.data[i+k]==s.data[j+k];k++) //将较大长度者赋给maxi与maxlen
len++;
if(len>maxlen){
maxi=i;
maxlen=len;
}
j+=len;
}
else j++;
}
i++; //继续扫描第i字符之后的字符
}
t.length=maxlen; //将最长重复子串赋给t
for(i=0;i<maxlen;i++)
t.data[i] = s.data[maxi+i];
}