1、第6章 图 6.1 图的基本概念图6.1 有向图和无向图示例图6.2 有向网和无向网示例图6.3 子图示例图6.4 非连通图的连通分量图6.5 非强连通图的强连通分量图6.6 G2的生成树 6.2 图的存储结构 6.2.1 邻接矩阵表示法 根据图的邻接矩阵表示法的性质，其具有如下特点：(1)无向图的邻接矩阵一定是对称矩阵。(2)对于无向图，其邻接矩阵的第i行(或第i列)中非0元素个数即为第i个顶点的度。(3)对于有向图，其邻接矩阵的第i行中非0元素个数即为第i个顶点的出度；第i列中非0元素个数即为第i个顶点的入度。(4)用邻接矩阵存储图，很容易确定图的任意两个顶点之间是否有边或弧相边。#def
2、ine MAXVEX 40 typedef char VEXTYPE typedef int ADJTYPE typedef struct VEXTYPE VexsMAXVEX;/图中顶点的信息 ADJTYPE ArcsMAXVEXMAXVEX;/邻接矩阵 int VexNum,ArcNum;/顶点数和边数 MGRAPH;下面是建立一个n个顶点e条边的无向图的算法：int Create_MGraph(MGRAPH*mg)int n,e,i,j,k,p;char b,t;printf(“请输入顶点数和边数：”);scanf(“%d,%d”,&n,&e);mg-VexNum=n;mg-ArcNum
3、=e;for(i=0;in;i+)for(j=0;jArcsij=0;for(i=0;in;i+)printf(“请输入第%d个顶点的信息：”，i+1);scanf(“%c”,&mg.Vexsi);for(k=0;ke;k+)printf(“请输入一条边的两个顶点：”)；scanf(“%c,%c”,&b,&t);i=j=-1;for(p=0;pVexsp=b)i=p;if(mg-Vexsp=t)j=p;if(i=-1|j=-1)printf(“输入顶点不存在!n”)；return 0;mg-Arcsij=1;return 1;/Create_MGraph 6.2.2 邻接表表示法图6.7 图的
4、邻接表和逆邻接表#define MAXLEN 40 typedef int VEXTYPE typedef struct Node int AdjVex;struct Node*Next;EDGENODE;typedef struct VEXTYPE VerTex;EDGENODE*Link;VEXNODE;typedef struct VEXNODE AdjListMAXLEN;int VexNum,ArcNum;ADJGRAPH;下面是建立具有n个顶点e条边的有向图的邻接表的算法：ADJGRAPH Create_AdjGraph()EDGENODE *p;int i,s,d;ADJGRAP
5、H Adjg;printf(“请输入顶点数和边数:”);scanf(%d,%d,&s,%d);Adjg.VexNum=s;Adjg.ArcNum=d;for(i=0;aAdjg.VexNum;i+)printf(“请输入第%d个顶点的信息:”,i+1);scanf(%d,&Adjg.AdjListi.VerTex);Adjg.AdjListi.Link=NULL;for(i=0;iAdjg.ArcNum;i+)printf(“请输入第%d条边的起始顶点和终止顶点的编号：”,i+1);scanf(%d,%d,&s,&d);while(sAdjg.VexNum|dAdjg.VexNum)print
6、f(“输入错误，请重新输入！n”);printf(“请输入第%d条边的起始顶点和终止顶点的编号：”,i+1);scanf(“%d,%d”,&s,&d);p=(EDGENODE*)malloc(sizeof(EDGEN-ODE);p-AdjVex=d-1;p-Next=Adjg.AdjLists-1.Link;Adjg.AdjLists-1.Link=p;return Adjg;/Create_AdjGraph 6.3 图的遍历 6.3.1 深度优先遍历 算法1：从顶点v出发按深度优先遍历图Adjg中与v有路径相通的各个顶点。void DFS(ADJGRAPH Adjg,int v)图6.8 无
7、向图G5 EDGENODE*p;int i;Visitedv-1=1;/访问标记置1 v-;printf(%d,Adjg.AdjListv.VerTex);/访问一个顶点：输出其值 p=Adjg.AdjListv.Link;while(p!=NULL)if(Visitedp-AdjVex=0)DFS(Adjg,(p-AdjVex)+1);p=p-Next;/DFS 算法2：图的深度优先遍历算法。void DFT(ADJGRAPH Adjg)int v;for(v=0;kAdjg.VexNum;v+)Visitedv=0;/所有标记清零 for(v=1;vAdjVex=0)Visitedp-Ad
8、jVex=1;printf(%d,Adjg.AdjListp-AdjVex.Ver-Tex);EnLinkQueue(q,(p-AdjVex)+1);p=p-Next;/BFS 算法2：图的广度优先遍历算法。void BFT(ADJGRAPH Adjg)int VisitedMAXLEN;int v;for(v=0;vAdjg.VexNum,v+)Visitedv=0;for(v=1;v=Adjg.VexNum;v+)if(Visitedv-1=0)BFS(Adjg,v);/BFT 6.4 图的连通性及最小生成树 6.4.1 Prim算法 设G=(V，E)是连通网，构造的最小生成树为T=(U，
9、TE)，求T的Prim算法为：图6.9 无向图G5的生成树 初始化U=u0，TE=，u0为网中任一 顶点；在所有uU，v(V-U)的边(u,v)E中，找一条权值最小的边(uk，vi)，将此边加入到TE中，并将vi加入到U中；重复，直到U=V为止。/从u0出发构造网mg的最小生成树，按普里姆算法输出生成树上各条边 struct ADJTYPE LowCost;int Vex;CloseDgeMAXVEX;int k,v,i;ADJTYPE MinCost;CloseDgeu0-1.LowCost=0;CloseDgeu0-1.Vex=0;for(k=0;kVexNum;k+)/对辅助数组初始化
10、if(k!=u0-1)CloseDgek.LowCost=mg-Arcsu0-1k;CloseDgek.Vex=u0;for(i=1;iVexNum;i+)MinCost=9999;/9999设为无穷大值 v=0;while(vVexNum&v!=u0-1)if(MinCostCloseDgev.LowCost and Close Dgev.LowCost!=0)MinCost=CloseDgev.LowCost;k=v;v=v+1;printf(%d,%d),CloseDgek.Vex,k);CloseDgek.LowCost=0;for(v=0;vVexNum;v+)if(mg-Arcsk
11、vArcskv;CloseDgev.Vex=k;Prim图6.10 连通网G6及其邻接矩阵图6.11 最小生成树的生成过程图6.12 构造最小生成树过程中辅助数组中各分量的变化情况 6.4.2 Kruskal算法 集合E中的边按权递增顺序排列为：(1，3)，(1，2)，(2，3)，(2，4)，(4，5)，(2，5)，(1，4)，(3，4)(1)初始时，T中只有5个顶点的非连通图，如图6.13(a)。(2)边(1，3)的两个顶点1，3分别属于两个连通分量，将边(1，3)加入T，如图6.13(b)。(3)同理，将边(1，2)加入T，如图6.13(c)。(4)由于边(2，3)的两个顶点2，3在同一个
12、连通分量中，因此舍去该边。(5)同理将边(2，4)，(4，5)加入T，如图6.13(d)和(e)所示。图6.13 图G6的最小生成树的构造过程 6.5 有向无环图及其应用 6.5.1 拓扑排序 拓扑排序的算法思想是：(1)在AOV网中选择一个入度为0的顶点，输出该顶点；图6.14 有向图G7(2)从AOV网中删除该顶点和所有以它为始点的弧；(3)重复执行(1)、(2)步直到找不到入度为0的顶点为止，拓扑排序完成。6.5.2 关键路径 利用AOE网进行工程管理，要解决的主要问题是：(1)完成整个工程至少需要多少时间？(2)哪些活动是影响工程进度的关键活动？图6.15 拓扑排序过程示意图 下面介绍
13、如何确定AOE网的关键路径。首先需要定义几个变量。1.事件j可能发生的最早时间eej 2.事件i允许的最迟发生时间lei 3.活动ak=的最早开始时间ek图6.16 一个AOE网 对于图6.16的AOE网，各活动的最早开始时间为：4.活动ak=的最晚开始时间lk 对于图6.16的AOE网，各活动的最晚开始时间为：各活动的松弛时间为：6.6 最短路径 Floyd算法如下：图6.17 图6.16的AOE网的关键路径 void ShortPath_Floyd(MGRAPH*mg,ADJ-TYPE AMAXVEXMAXVEX,int PathMAXVEXMAXVEX)int i,j,k;for(i=0
14、;iVexNum;i+)for(j=0;jVexNum;j+)Aij=mg-Arcsij;if(Aij!=MAX)Pathij=j+1;else Pathij=0;for(k=0;kVexNum;k+)for(k=0;kVexNum;k+)for(k=0;kVexNum;k+)if(AijAik+Akj)Aij=Aik+Akj;Pathij=k+1;/ShortPath_Floyd图6.18 带权有向网及其邻接矩阵图6.19 Floyd算法执行过程中方阵A和Path的变化情况第7章 查找 7.1 查找表的基本概念 7.1.1 查找 7.1.2 基本运算 查找表的基本运算包括查找、读表元、插入和
15、删除等。(1)建表Create(ST)，其功能是生成一个由给定的若干结点组成的静态查找表ST。(2)查找Search(ST,K),若ST中存在关键字值等于K的结点，运算结果为该结点在ST中的位置；否则，运算结果为一特殊标志。(3)读表元Get(ST，Pos)，其运算结果是取出ST中Pos位置上的结点。(4)初始化Initiate(ST)，其作用是设置一个空的动态查找表ST。(5)插入Insert(ST，K)，若ST中不存在关键字等于K的结点，则将关键字等于K的新结点插入到ST中。(6)删除Delete(ST，K)，当ST中存在关键字等于K的结点时，将其删除。7.1.3 性能分析 7.2 静态查
16、找表 静态查找表中结点的类型定义：typedef struct int Key;/关键字定义为整型，也可定义 为实数、字符串等 ElemType;静态查找表的顺序存储结构类型定义：typedef struct Elemtype*Elem;int n;/表长 SSTable;7.2.1 顺序查找(1)顺序查找的基本思想(2)顺序查找算法 int Search_seq(SSTable ST,int K)/K为给定值，在顺序表ST中从后往前查找关键字等于K的结点，/若找到则回送该元素在ST中的位置，否则回送0，标记查找不成功。ST.Elem0.Key=K;/0号单元设置“监视哨”For(i=ST.n
17、;ST.Elemi.Key!=K;i-);/未找到时修改比较位置，并继续查找 Return i;/回送结果i为关键字等于K的 结点在表ST中的序号/Search_seq(3)算法分析 查找成功的平均查找长度为：查找不成功的平均查找长度为：7.2.2 折半查找(1)折半查找的基本思想(2)折半查找过程 折半查找的基本步骤是：1)设Low=1，High=ST.n，则Low.High是当前的查找区间；2)确定该区间的中点位置Mid=(low+high)/2；3)然后将待查的K值与ST.ElemMid.Key 比较：若ST.ElemMid.Key=K，则查找成功并返回位置Mid；若ST.ElemMid
18、.KeyK，由表的有序性可知Mid.High区间上的Key均大于K，因此,若存在关键字等于K的结点,则该结点必定是在位置Mid左边的子表Low.Mid-1中,故新的查找区间是左子表Low.Mid-1。(3)折半查找算法 如果查找成功返回该结点在表中的位置 int BinSearch(SSTable ST,int K)int Low=1，High=ST.n;/置区间初值 while(LowK)High=Mid-1;/在左子区间中查找 else Low=Mid+1;/在右子区间中查找 return 0;/查找失败/BinSearch(4)折半查找算法分析图7.1 折半查找过程的判定树 7.2.3
19、分块查找(1)分块查找的基本思想(2)分块查找的查找过程(3)算法分析 7.3 动态查找表 7.3.1 二叉排序树(1)二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找树(Binary Search Tree)。其定义为：二叉排图7.2 查找表的分块及索引表序树或者是空树，或者是满足如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身也分别是一棵二叉排 序树。(2)二叉排序树的数据类型描述 typedef struct Node int Key；/关键字域 InfoTyp
20、e OtherInfo；/其他数据域，InfoType视应用情况而定 struct Node*Lchild，*Rchild；/左右孩子指针 BSTNode,*BSTree；/BSTree是二叉排序树的类型(3)二叉排序树的构造过程 对于给定值K，其构造过程是：若二叉排序树T为空，则将K作为根结点插入；若二叉排序树T不为空，则将K和根的关键字进行比较：若二者相等，则说明树中已有此关键字K，无须插入。若KKey，则将K插入根的左子树中。若KT-Key，则将K插入根的右子树中。图7.3 二叉排序树的生成过程(4)二叉排序树的生成、查找算法 1)生成二叉排序树的算法 void Insert(BSTre
21、e t,BSTNode s)/插入一个结点s到二叉排序树t中 if(t=NULL)t=s;else if(s-KeyKey)Insert(t-Lchild,s);/在左子树中插入 else Insert(t-Rchild,s);/在右子树中插入/Insert void CreatTree(BSTree t)/构造二叉排序树 int x;BSTNode q;do scanf(%d,&x);/输入关键字 q=(BSTNode*)malloc(sizeof(BSTNode);/生成一个结点 q-Key=x;q-Lchild=NULL;q-Rchild=NULL;Insert(t,q);while(x
22、!=-1);/CreatTree 2)二叉排序树的查找算法 算法如下：BSTNode Search(BSTree T,int K)BSTNode q;q=T;while(q!=NULL&q-Key!=K)if(kKey)q=q-Lchild;else q=q-Rchild;if(q=NULL)printf(no Node);else return(q);/Search(4)二叉排序树查找的性能分析 两棵树的平均查找长度如下：图7.4 不同形态的二叉排序树 7.3.2 平衡二叉树(1)平衡二叉树的定义图7.5 平衡二叉树与不平衡二叉树(a)(b)平衡二叉树；(c)(d)不平衡二叉树(2)不平衡二
23、叉树的平衡处理 1)LL型(左左型)2)LR型(左右型)图7.6 LL型平衡处理图7.7 LR型平衡处理 3)RR型(右右型)4)RL型(右左型)图7.8 RR型平衡处理图7.9 LR型平衡处理 7.4 散列表图7.10 平衡二叉树的生成过程 7.4.1 散列表的基本知识(1)散列表的概念(2)散列表的冲突现象 在采用散列技术进行查找时提出了下列两个重要问题：1)如何构造“均匀”的散列函数？2)用什么方法解决冲突？7.4.2 散列函数的构造方法图7.11 二叉排序树(1)直接定址法(2)平方取中法(3)数字分析法(4)除留余数法图7.12 利用数字分析法得到散列地址 7.4.3 处理冲突的方法
24、(1)开放定址法 开放定址法的一般形式：其中：Ai为探测到的后续散列地址序列，i=1，2，3，。H(Key)为散列函数,H(Key)=Key%P m为散列表长度 di为增量序列，当di=1,2,3,时，称为线性探测再散列 di=12,-12,22,-22,时，称为二次探 测再散列 di取伪随机数序列时，为伪随机探 测再散列 1)线性探测法 线性探测法生成的后续散列地址序列为：A1=(H(Key)+1)%m A2=(H(Key)+2)%m A3=(H(Key)+3)%m 2)二次探测法 二次探测法生成的后续散列地址序列为：图7.13 用线性探测法建立的散列表 A1=(H(Key)+12)%m A
25、2=(H(Key)-12)%m A3=(H(Key)+22)%m A4=(H(Key)-22)%m 3)随机探测法(2)链地址法 7.4.4 散列表的查找过程及查找算法(1)散列表类型说明#define m 997/表长度依赖于应用 typedef struct/散列表结点类型 int Key；InfoType otherinfo；NodeType；typedef NodeType HashTablem；/散列表类型(2)利用开放定址法解决冲突的算法 int Hash(int K，int i)/求K在散列表中第i次探测的散列地址Ai，0im-1 return(H(K)+Increment(i)
26、m；/Increment(i)相当于是di/Hash 其中：H是散列函数，Increment是求增量序列的函数，它依赖于解决冲突的方法。若散列函数用除留余数法构造，并假设使用线性探测的开放定址法处理冲突，则上述函数中的H(K)和Increment(i)可定义为：int H(int K)return KP；/P为选定的小于等于散列表长的质数/H int Increment(int i)return i;/用线性探测法求第i个增量di，若用二次探测法，则返回i*i/Increment(3)利用开放定址法的散列表查找算法 在散列表HT0.m-1中查找K，成功时返回OK，失败时返回ERROR。用*A保
27、存找到K或找到空位置时表中的地址 Status HashSearch(HashTable HT，int K，int*A)int i=0；/记录探测次数 do *A=Hash(K，i)；/求探测地址hi if(HT*A.Key=K)return OK；/查找成功返回 if(HT*A.Key=NULL)return ERROR /找到空位置，查找失败，返回 while(+im)/探测下一个位置，最多做m次探测 return ERROR；/表满且未找到时，查找失败，返回/HashSearch 7.4.5 散列表的查找性能分析 线性探测法的平均查找长度为：ASL=(1*7+2*4+4*1)/12=18
28、/121.58 链地址法的平均查找长度为：ASL=(1*7+2*4+3*1)/12=1.5(1)开放定址法查找的性能分析(2)链地址法查找的性能分析(3)注意图7.15 顺序存储的顺序表图7.16 折半查找的判定树 图7.17 二叉排序树 图7.18 平衡二叉树图7.19 用线性探测法建立的散列表图7.20 用链地址法建立的散列表第8章 内部排序 8.1 排序的基本概念 8.1.1 排序码与排序 8.1.2 排序方法 排序方法有5类：插入排序：直接插入排序，二分法插入排序，希尔排序 选择排序：直接选择排序，堆排序 交换排序：起泡排序，快速排序 分配排序：基数排序 归并排序 8.1.3 排序算法
29、分析(1)时间复杂度(2)空间复杂度(3)说明 typede struct int Key；int Info;NODE;8.2 插入排序 8.2.1 直接插入排序(1)直接插入排序的基本概念(2)直接插入排序的算法 void StrainSort(NODEr,int n)/rn+1为一维数组，其中r0为监视哨,r1到rn为待排序的n个记录，排序好的记录仍放在r中 int i,j;for(i=2;i=n;i+)/*共进行n-1趟*/r0=ri;/*设置副本、监视哨*/j=i-1;while(r0.Keyrj.Key)rj+1=rj;j=j-1;rj+1=r0;/StrainSort(3)直接插入
30、排序的算法复杂度 8.2.2 折半插入排序(1)折半插入排序的基本概念(2)折半插入排序的算法 voidBinarySort(NODE r,int n)/按关键字递增的次序对记录r1,r2,rn进行折半插入排序 int i,j;for(i=2;i=n;i+)r0=ri;l=1;h=i-1;while(l=h)Mid=(l+h)/2;if(r0.Key=l;j-)rj+1=rj;rl=r0;/BinarySort(3)折半插入排序的算法复杂度 8.2.3 希尔排序(1)希尔排序的基本概念(2)希尔排序的算法 void ShellSort(NODE r，int d，int n，int t)/r1到
31、rn为待排序记录，/*d1到dt为增量序列，假设d1d2dt=1 int i,j,k,dt;for(k=1;k=t;k+)dt=dk;for(i=dt+1；i=1&r0.Keyrj.Key)rj+d=rj;j=jdt;rj+dt=r0;/ShellSort(3)希尔排序的算法复杂度 8.3 选择排序 8.3.1 简单选择排序(1)简单选择排序的基本概念(2)简单选择排序的算法 void SelectSort(NODE r,int n)/r1到rn为待排序记录 int i,j,k;for(i=1；in；i+)/*作n-1趟选取*/k=i;for(j=i+1；j=n；j+)/在i开始的n-i+1个
32、记录中选关键码最小的记录 if(rj.Keyrk.Key)k=j；/k中存放关键码最小记录的下标 if(i!=k)/关键码最小的记录与第i个记录交换 r0=ri;ri=rk;rk=r0;/SelectSort(3)简单选择排序的算法复杂度 8.3.2 堆排序(1)堆的定义图8.1 堆的示例(2)堆排序的基本概念(3)如何建堆图8.2 初始建堆示例图8.3 重建堆(自堆顶到叶子的调整过程)建堆的算法:void Sift(NODE r,int l,int m)/对rl至rm的记录建堆 inti,j;i=l;j=2*i;r0=ri;while(j=m)if(jrj+1.Key)j+;/为排序码较小的
33、元素下标 if(r0.Keyrj.Key)ri=rj;i=j;j=2*i;else break;/rc应插入在位置i上 ri=r0;/插入/Sift(4)堆排序的算法 void HeapSort(NODE r,int n)/对r1至rn的记录进行堆排序 int i;for(i=n/2;i0;i-)Sift(r,i,n);/将r1.n建立初始堆 for(i=n;i1;i-)r0=r1;/堆顶r1与堆底ri交换 r1=ri;ri=r0;Sift(r,1,i-1);/将r1.i-1重新调整为堆 /HeapSort(5)堆排序的算法复杂度 8.4 交换排序 8.4.1 冒泡排序(1)冒泡排序的基本概念
34、(2)冒泡排序的算法 void BubbleSort(NODE r,int n)/对r1至rn的记录进行冒泡排序 inti,j,Flag=1;for(i=1;in&Flag=1;i+)/对n个记录的排序,进行n-1趟 Flag=0;for(j=1;jrj+1.Key)r0=rj;/rjrj+1 rj=rj+1;rj+1=r0;Flag=1;/标志变量置1，表明本趟进行过交换 /BubbleSort(3)冒泡排序的算法复杂度 8.4.2 快速排序(1)快速排序的基本概念(2)快速排序的算法 void Quick_Sort(NODE r,int Low,int High)/用递归方法对rLow到r
35、High的记录进行快速排序 int i,j;NODE Temp;if(Low=High)return;i=Low;j=High;Temp=ri;while(ij)while(i=Temp.Key)j-;/在序列的右端扫描 if(ij)ri=rj;i+;while(ij&ri.KeyTemp.Key)i+;/在序列的左端扫描 if(ij)rj=ri;j-;ri=Temp;/对子序列进行快速排序/if(Lowi-1)Quick_Sort(r,Low,i-1);if(j+1High)Quick_Sort(r,j+1,High);/Quick_Sort(3)快速排序的算法复杂度 8.5 二路归并排序
36、8.5.1 二路归并排序的基本概念 8.5.2 二路归并排序的算法(1)两两归并的算法 void Merge(int l,int m,int n,NODE r,NODE r2)/将有序表rl.m和rm+1n归并为有序的r2ln int i,j,k,c;i=l;j=m+1;k=l;while(i=m&j=n)if(ri.Key=rj.Key)r2k+=ri+;else r2k+=rj+;if(i=m)/序列2已归并完，将序列1剩余的记录顺序存放到r2中 for(c=i;c=m;c+)r2k+=rc;if(j=n)/序列1已归并完，将序列2剩 余的记录顺序存放到r2中 for(c=j;c=n;c+
37、)r2k+=rc;/Merge(2)一次归并算法 void MergePass(int b,int n,NODE r,NODE r2)/将r1.n中长度为b的相邻有序段两两归并，结果存入r21.n/int i=1，c;while(i=n-2*b+1)merge(i,i+b-1,i+2*b-1,r,r2);i+=2*b;if(i+b=n)merge(i,i+b-1,n,r,r2);else for(c=i;c=n;c+)/将原始序列中不足两组 的记录顺序存放到r2中 r2c=rc;/MergePass(3)二路归并排序算法 void MergeSort(NODE r,NODE r2,int n)
38、/对r1.n进行二路归并排序 int b=1,c;/归并长度由1开始 while(bn)MergePass(b,n,r,r2);b=b*2;/归并长度加1 for(c=1;c=1;i-)p=Head;Head=NULL;for(j=0;jKeyi;if(fk=NULL)fk=p;else ek-Next=p;ek=p;p=p-Next;j=0;do /收集操作 if(fj!=NULL)if(Head!=NULL)q-Next=fj;else Head=fj;q=ej;j+;while(j!=r);q-Next=NULL;return(Head);/RadSort 8.6.3 基数排序的算法复杂度 8.7 各种内部排序方法比较 8.8 外部排序简介
