数据结构 复习课 王彦 博士，副教授 wangyan8383@sjtu.edu.cn

第三次复习课 图 查找 排序

图 考核内容及要求： 熟练掌握图的相关概念、性质、存储结构 熟练掌握遍历：深度优先遍历、广度优先遍历过程； 熟练掌握连通分量的求法； 熟练掌握最小生成树、最短路径概念与方法； 掌握拓扑排序、关键路径的求法及实现方法。

图的定义、术语和存储结构 图：图结构中，任意两个结点之间的关系是任意的，图中任意两个数据元素之间都可能相关 图的抽象数据类型 顶点、弧、边 有向图（digraph) 有向图G1=(V1,{A1})，其中V1={v1,v2,v3,v4},A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>} 无向图(undigraph) 无向图G2=(V2,{E2}) V2={v1,v2,v3,v4,v5}, E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)} V1 V2 V3 V4 有向图 V1 V2 V4 V5 V3 无向图

图的定义、术语和存储结构 无向图： 有向图： 顶点数n和边(弧)的数目e： 完全图：有n(n-1)/2条边的无向图; 稀疏图、稠密图 子图：G=(V,{E}),G’=(V’,{E’})，若V’ V,且E’ E,则称G’为G的子图 邻接点：无向图中，(v,v’)∈E，则v,v’互为邻接点； 顶点v的度：与v相关联的边的数目，TD(v) 有向图中,若<v,v’>∈A，则顶点v邻接到顶点v’，而顶点v’邻接自v 出度：以v为尾的弧的数目，OD(v) 入度：以v为头的弧的数目，ID(v) TD(v)=OD(v)+ID(v)

图的定义、术语和存储结构 路径： 连通图、连通分量、强连通图、强连通分量： A B L M C D E F G H I J K A B L 回路（环） 简单路径：顶点序列中顶点不重复的路径。 连通图、连通分量、强连通图、强连通分量： A B L M C D E F G H I J K A B L M C F J D E G H I K

图的定义、术语和存储结构 一个连通图的生成树：一个极小连通子图，含有图中全部结点，但只有足以构成一棵树的n-1条边。 一棵有n个顶点的生成树有且仅有n-1条边 但有n-1条边的图不一定是生成树 有向图：如果有一个顶点的入度为0，其余顶点的入度都为1，则是一棵有向树。 A B L M C F J

图的存储结构 V1 V2 V3 V4 G1.VEXS[4]=[V1 V2 V3 V4] G1.arcs= 0 1 1 0 0 0 0 0 数组表示法（邻接矩阵）： 用两个数组分别存放顶点信息和边（弧）信息 V1 V2 V3 V4 G1.VEXS[4]=[V1 V2 V3 V4] G1.arcs= 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 G1 V1 V2 V4 V5 V3 G2.arcs= 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 G2

图的邻接矩阵 图的存储结构 A[i][j]=1 //若<vi,vj>存在 无向图：第i行分量的和为结点vi的度 有向图：第i行分量的和为结点vi的出度； 第i列分量的和为结点vi的入度 网的邻接矩阵 A[i][j]=无穷大 <vi, vj>间无边 =权 <vi, vj>间有边 问题：为什么放无穷大而不放0

图的存储结构 V1 V2 V3 V4 data firstarc adjvex nextarc info 邻接表：一种链式存储结构 为图中的每一个顶点创建一个单链表，其中的结点表示依附于顶点的边(以该顶点为尾的弧) V1 V2 V3 V4 data firstarc 头结点 adjvex nextarc info 表结点 v1 v2 v3 v4 1 2 3 ^

图的存储结构 无向图的邻接表中，顶点v的度就是该顶点的单链表中的结点数； 有向图中，第i个链表的结点数是该顶点的出度； 如何求有向图中顶点的入度？——有向图的逆邻接表。 v1 v2 v3 v4 1 2 3 ^ v1 v2 v3 v4 1 2 3 ^ 有向图G1的邻接表 有向图G1的逆邻接表

图的存储结构 十字链表：有向图的链式存储 V1 V2 V3 V4 tailvex headvex hlink tlink info 弧结点 data firstin firstout 顶点结点 v1 v2 v3 v4 1 2 3 ^

图的存储结构 邻接多重表：无向图的另一种链式存储结构。 V1 V2 V3 V4 V5 1 2 3 4 ^ V1 V2 V4 V5 V3

图的遍历 图的遍历目标是解决图的连通性问题、拓扑排序问题、关键路径问题。 图的遍历方法：深度优先算法、广度优先算法

深度优先遍历 深度优先搜索遍历：类似于树的先根遍历，是树的先根遍历的推广 算法： 1.假设图中所有顶点的初始状态为：未访问； 2.从图中某个未访问的顶点v出发，访问此结点； 3.依次从v的邻接点出发深度优先遍历图，直到图中所有与v有路径的顶点都被访问到； 4.若图中还有未访问结点，则另选一个结点作起始点，重复2、3过程。

图解深度优先遍历过程 v1 V2 v6 v4 v5 v8 v3 v7 v1 v3 V2 v7 v6 v4 v8 v5

可能的遍历序列：A L M J B F C D E G I H K 图的遍历 一个非连同图的深度优先遍历过程图解 A B L M C D E F G H I J K A B D E C F G H H I K J L M 可能的遍历序列：A L M J B F C D E G I H K 注：图的存储结构没有给定的情况下，图的遍历序列不是唯一的。

广度优先遍历 广度优先搜索遍历类似于树的层次遍历 算法 v1 V2 v6 v4 v5 v8 v3 v7 v1 v3 V2 v5 v7 v6

可能的遍历序列：A L F C B M D E G I H K 图的遍历 一个非连同图的广度优先遍历过程图解 A B L M C D E F G H I J K A B D E C F G H H I K J L M 可能的遍历序列：A L F C B M D E G I H K

图的连通性问题—掌握连通分量求法 A B L M C D E F G H I J K H A B L M C D E F G I J K 无向图的连通分量和生成树 由图的遍历得出： 对于连通图，从图中任一顶点出发，可以访问到图中的所有顶点； 对于非连通图，需要从多个顶点出发，搜索到树的各个连通分量中的顶点集。 A B L M C D E F G H I J K H A B L M C D E F G I J K

最小生成树的概念和求法 最小生成树 构造连通网的最小代价生成树。 MST性质：假设N=(V,{E})是一个连通网，U是顶点集V上的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V-U,则必存在一棵包含边(u,v)的最小生成树。 构造最小生成树的算法：Prin算法和Kruskal算法。

最小生成树的概念和求法 Prim算法构造最小生成树的过程： V1 V2 V3 V4 V5 V6 6 5 1 2 4 3 V1 V2 V3

Kruskal算法构造最小生成树的过程 V1 V2 V3 V4 V5 V6 V1 V2 V3 V4 V5 V6 6 5 1 2 4 3 V1 两种算法的区别： 普鲁姆算法：基于连通地选择，避免回路 克鲁斯卡儿算法：离散地选择，避免回路

拓扑排序 拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序，就是拓扑排序。 偏序：集合中仅有部分成员之间可以比较； 全序：集合中全体成员之间均可比较。 AOV网：顶点表示活动，弧表示活动之间的优先关系的有向图称为顶点表示活动的网。 v1 v2 v3 v4 v1 v2 v3 v4 偏序 全序

拓扑排序 进行拓扑排序的方法： 在有向图中选一个没有前驱的顶点且输出； 从图中删除该结点和所有以该结点为尾的弧。 重复上述操作。若可以输出全部顶点，则该图中不存在环，否则存在环。 例如： 算法实现： 以邻接表的方法存储有向图； 头结点增加信息：顶点入度； 增加一个栈：存放入度为0的顶点。 v1 v2 v3 v4

最短路径 从某个源点到其余各顶点的最短路径 100 60 30 10 20 50 5 Dijkstra算法：按路径长度递增的次序产生最短路径 D[i]表示当前所找到的从点v到每个终点vi的最短路径的长度。 D[i]初值：v到vi的弧的权值；则： 初值最小的路径就是从v出发的最短的一条路径 下面按照长度递增多次序产生各个终点的最短路径 v1 v2 v3 v4 v0 v5 100 50 60 20 10 30 5

最短路径 100 60 30 10 20 50 5 Dijkstra算法 求最短路径 v1 v2 v3 v4 v0 v5 终点 从v0到各终点的D值和最短路径的求解过程 i=1 i=2 i=3 i=4 i=5 v1 ∞ 无 v2 10 (v0,v2) v3 60 (v0,v2,v3) 50 (v0,v4,v3) v4 30 (v0,v4) v5 100 (v0,v5) 90 (v0,v4,v5) (v0,v4,v3,v5) vj S {v0,v2} v1 v2 v3 v4 v0 v5 100 50 60 20 10 30 5

查找 考核内容及要求： 熟练掌握顺序查找、有序表的查找、索引顺序查找、二分查找法及HASHING查找技术； 理解查找速度的分析及比较、算法复杂性的级别。

顺序表的查找 物理存储： 顺序表方式： typedef struct { ElemType *elem; int length; } SSTable 查找过程：从表中最后一个元素开始，逐个比较，相等则比较成功，否则直到第一个元素。

Int Search_Seq(SSTable ST, KeyType key) { //当比到0下标才成功则查找不成功，返回0 //否则返回下标i ST.elem[0].key = key; for (i=ST.length; !EQ(ST.elem[i].key, key); --i); return i; }//Search-Seq 0下标为监视哨,时间复杂度O(n) 平均查找长度： ASL =sum(pici) i=1…n

查找成功： pi = 1/n ci= 1,2,3…n ASL=1/n[1+2+…+n] = (n+1)/2 查找不成功：ASL = n+1 , (n, n-1…1, 0) 成功和不成功同概率：1/2 ASL = ½*1/n[1+2+…+n]+1/2(n+1) = ¾(n+1)

有序表的查找 5 13 19 21 37 56 64 75 80 88 93 折半查找：先确定待查记录的范围，逐步缩小范围直到找到或找不到。 例：在下列数据元素中查找关键字为21和85的数据元素 分析：设置两个指针low ,high指示待查元素所在范围的上界和下界。mid＝（low+high）/2 ST.elem[mid].key=key:查找成功 ST.elem[mid].key<key：low=mid+1 ST.elem[mid].key>key: high=mid-1 low=high:查找不成功 5 13 19 21 37 56 64 75 80 88 93 high low mid

int Search_Bin (SSTable ST, KeyTable key) { //对有序表的查找采用折半查找，逐步缩小 //查找范围，直到找到或找不到，返回值为 //找到返回下标，找不到返回0 low = 1; high = ST.length; while (low<=high) { mid = (low+high)/2; if EQ(key, ST.elem[mid].key) return mid; else if LT(key, ST.elem[mid].key) high = mid –1; else low = mid +1; } return OK; } //Search_Bin 时间复杂度：O(log2n), ASL = log2(n+1)+1 (按照满二叉树)

动态查找表——二叉排序树 例 已知如下长度为8的表，试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概率下查找成功的平均查找长度。 （Mon, Tiger, Win, Butter, Fish, Fly, Pig,Cat)

哈希表 确定的对应关系f：记录的存储位置 关键字 对应关系f就是哈希函数：f(K) 哈希函数是一个映象，构造哈希函数的方法： 直接定址法； 哈希地址：直接取关键字或者关键字的线性函数 H(key)=key; or H(key)=a*key+b 数字分析法； 分析关键字，取关键字的若干数位组成哈希地址。 平方取中法； 取关键字平方后的中间几位为哈希地址——较为常用的方法 折叠法：分割关键字、叠加 除留余数法：H(key)=key MOD p p<=哈希表长m

哈希表 冲突现象：当K1≠K2时f(K1)=f(K2) 解决冲突的方法 开放定址法； Hi=(H(key)+di) MOD m i=1,2,···k (k<=m-1) m为哈希表长度；di为增量,di的取法： (1)线性探测再散列；di=1,2,3,··· (2)二次探测再散列；di=±k2 (3)伪随机探测再散列 ：di=伪随机数序列 再哈希：Hi=RHi(key) 链地址：所有关键字为同义词的记录存储在同一线性链表中 公共溢出区：发生冲突时填入溢出表。

排序 考核要求： 熟练掌握插入排序、快速排序、堆及选择排序、归并排序、基数排序法； 了解最好、最坏、平均排序的时间复杂性分析方法。

插入排序 插入排序的思想：将一个元素插入到一个有序表中。 根据寻找插入位置的方法不同分为：直接插入、折半插入、2路插入、表插入等。 直接插入排序：最简单的排序方法 思想：将一个元素向一个有序序列插入 做法：0位监测哨，从一个元素逐步扩大有序序列。 举例 49 38 65 97 76 13 27 49

直接插入排序算法： void InsertSort(SqList &L){ //对顺序表L作直接插入排序 for (i=2;i<L.length;++i) if (L.r[i].key<L.r[i-1].key){ L.r[0]=L.r[i]; L.r[i]=L.r[i-1]; for (j=i-2;L[0].key<L[j].key;--j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; }

折半插入排序 查找过程用折半查找方法。 49 38 65 97 76 13 27 49 void BInsertSort(SqList &L){ for (i=2;i<=L.length;++i){ L.r[0]=L.r[i]; low=1;high=i-1; while (low<=high){ m=(low+high)/2; if (L.r[0].key<L.[m].key) high=m-1; else low=m+1; }//while for(j=i-1;j<=high+1;--j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; }//for }//BInsertSort

希尔排序 算法思想：先将整个待排序记录分割成若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再进行一次全体记录的插入排序。 具体操作： 49 38 65 97 76 13 27 49 55 04 第一次分组 49 13 38 27 65 49 76 04 这就是第一趟排序结果 13 27 49 55 04 49 38 65 97 76 第二趟的“增量”就要缩小了！ 13 55 38 76 27 04 65 49 49 97

希尔排序算法: void ShellInsert (SqList &L,int dk){ //对顺序表L作一趟希尔排序。 for (i=dk+1;i<=L.length;++i) if (L.r[i].key<L.r[i-dk].key){ L.r[0]=L.r[i]; for (j=k-dkl;j>0&L.r[0].key<L.r[j].key;j-=dk) L.r[j+dk]=L.r[j]; L.r[j+dk]=L.r[0]; } }//shelinsert void ShellSort(SqList &L,int dlta[],int t){ //按增量序列dlta[0..t-1]对顺序表L作希尔排序 for (k=0;k<t;++k) ShellInsert(L,dlta[k]);

快速排序 冒泡排序： 具体做法：依次比较第i个关键字和第i+1个关键字，大者排后，一趟得到最大值。（i=1,2,3,4,---n-1) 49 38 65 97 76 13 27 49 38 49 65 76 13 97 27 49 38 49 65 97 76 13 27 49 38 49 65 76 13 27 97 49 38 49 65 76 13 27 49 97 38 49 65 76 97 13 27 49

冒泡排序算法 void Bubble Sort (SqList &L ){ for (k=L.length-1;k>=1;k--) for (i=0;i<=k-1;k++) if (L.r[i].key>L.r[i+1].key) {交换两个记录} } 时间复杂度：O(n2)

快速排序的算法 49 38 65 97 76 13 27 49 low high 27 38 13 76 97 65 49 low high 49 38 65 97 76 13 27 49 low high 27 38 13 76 97 65 49 low high 27 38 65 97 76 13 49 low high 27 38 97 76 13 65 49 low high 27 38 13 97 76 65 49 low high

快速排序算法： Int Partition (SqList &L,int low,int high){ L.r[0]=L.r[low]; pivotkey=L.r[low].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]=L.r[0]; return low; }// 平均时间： K为常数因子。就平均时间而言快速排序是目前被认为最好的一种内部排序方法。

选择排序 选择排序基本思想：每一趟在n-i+1(i=1,2,···,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。 简单选择排序： Void SelectSort(SqList &L){ for (i=1;i<L.length;++i){ j=SelectMinKey(L,i);//从L.r[i..L.length]中选择key最小的记录 if (i!=j) L.r[i] L.r[j]; }

堆排序 堆的定义：n个元素的序列{k1,k2,,kn}当且仅当满足下列关系时，称为堆： 思想：每趟选取最小关键字、次小关键字、次次小关键字---。 做法：建立一个完全二叉树，任何非终端结点的值均不大于其左、右孩子结点的值。输出堆顶，将其余的元素建立新的堆。 ki≤k2i ki≤k2i+1 ki≥k2i ki≥k2i+1

49 38 65 97 76 13 27 49 49 38 65 49 76 13 27 97 49 38 65 27 13 76 97 97 49 38 65 27 13 76 49 38 13 49 76 65 27 97 49 38 13 49 76 65 27 97 49 38 13 27 65 76 97 49 13 38 27 65 76 97

归并排序 思想：将两个或两个以上的有序表组合成一个新的有序表。 具体做法：以两路归并示例 n个记录看成n个有序的序列 [49] [38] [65] [97] [76] [13] [27] 第一趟合并 [ 38 49 ] [ 65 97 ] [ 13 76 ] [27] 第二趟合并 [ 38 49 65 97 ] [13 27 76] 第三趟合并 [ 13 27 38 49 65 76 97]

典型例题 已知图G的邻接表如下图所示，从其顶点V1出发的深度优先搜索序列和广度优先搜索序列分别写出来，并按图中给出的存储结构给出深度优先生成树和广度优先生成树。 V1 V2 V3 V4 V5 V6 4 1 3 2 5

典型例题 已知以二维数组表示的图的邻接矩阵如下，分别画出自顶点1出发进行遍历得到的深度优先和广度优先生成树 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0

典型例题 给出如图所示的无向图的邻接矩阵和邻接表，并从其顶点V1出发的深度优先搜索序列和广度优先搜索序列分别写出来。 V1 V2 V4 V5

典型例题 已知图2所示的图，若从顶点A出发按深度优先搜索法进行遍历，则可能得到的遍历序列为： A) A,B,E,C,D,F B)A,C,F,E,B,D C) A,E,B,C,F,D D) A,E,D,F,C,B A B C E D F

典型例题 已知含12个关键字的有序表及其相应权值如下，画出对以下有序表进行折半查找的判断树。 关键字 A B C D E F G H I J K L 权值 8 2 3 4 9 6 7 1

典型例题 以关键字序列(53, 87, 12, 61,98,17, 97, 75, 53, 26)为例，手工执行以下排序算法，写出每一趟排序结束时的关键字状态： (1) 希尔排序(增量d[1]=5) (2) 快速排序 (3)堆排序

典型例题 判别以下序列是否为堆，如果不是，则把它调整为堆。 (1) (100,86,48,73,35,39,42,57,66,21); (2) (12,70,33,65,24,56,48,92,86,33)

考试题型 选择题（20题，每题一分，共20分） 填空题（10空，每空一分） 算法填空题（5空，每空两分） 简答题（一般4～5个大题目，共40分） 算法设计题（2题，每题10分）

祝考试顺利！ 注意复习的原则：简单为主！