数据结构复习与习题解析.ppt

数据结构 与 算法,复习与习题解析(第6-8讲）,第6讲 图,图的相关定义(无向完全图、有向完全图、网、连通图、强连通图、度、入度、出度、生成树和生成森林) 图的存储方式 邻接矩阵 无向图邻接矩阵 有向图邻接矩阵 网的邻接矩阵 每个结点的出度？入度？度？ 图的边数？ 邻接表 每个结点的出度？入度？度？ 图的边数？,04/04/2019,2,例已知某网的邻接（出边）表，请画出该网络。,当邻接表的存储结构形成后，图便唯一确定！,例题解析,04/04/2019,3,图的遍历,广度优先搜索 从图的某一结点出发，首先依次访问该结点的所有邻接顶点 V1, V2, , Vn 再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止。 深度优先搜索 1、访问指定的起始顶点； 2、若当前访问的顶点的邻接顶点有未被访问的，则任选一个访问之；反之，退回到最近访问过的顶点；直到与起始顶点相通的全部顶点都访问完毕； 3、若此时图中尚有顶点未被访问，则再选其中一个顶点作为起始顶点并访问之，转 2； 反之，遍历结束。,04/04/2019,4,例题解析,04/04/2019,5,熟悉图的存储结构，画出右边有向图的邻接矩阵、邻接表、逆邻接表。写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。,深度优先遍历序列为ABCFED，广度优先遍历序列为ABDCEF,邻接矩阵如下,邻接表如下,逆邻接表如下,【答】,最小生成树,普里姆（Prim）算法 将顶点进行归并 克鲁斯卡尔（Kruscal）算法 将边进行归并,04/04/2019,6,例：Prim算法,最小代价生成树的生成过程,U,V0,V1,V3,V2,V4,V5,6,1,6,5,5,5,6,3,4,2,V0,V1,V3,V2,V4,V5,1,5,3,4,2,(4),(1),(3),(2),(5),04/04/2019,7,例： Kruscal 算法,实例的执行过程,图G,1、初始连通分量： 0,1,2,3,4,5 2、反复执行添加、放弃动作。 条件：边数不等于 n-1时 边 动作 连通分量 (0,2) 添加 0,2,1,3,4,5 (3,5) 添加 0,2,3, 5,1,4 (1,4) 添加 0,2,3, 5,1,4 (2,5) 添加 0,2,3,5,1,4 (0,3) 放弃 因构成回路 (2,3) 放弃 因构成回路 (1,2) 添加 0,2,3,5,1,4,最小代价生成树,V0,V1,V3,V2,V4,V5,6,1,6,5,5,5,6,3,4,2,V0,V1,V3,V2,V4,V5,1,5,3,4,2,5,5,04/04/2019,8,例题解析,请分别用Prim算法和Kruskal算法构造以下网络的最小生成树，并求出该树的代价。,04/04/2019,9,例题解析,04/04/2019,10,【解析】Prim算法的操作步骤：首先从一个只有一个顶点的集合开始，通过加入与其中顶点相关联的最小代价的边来扩充顶点集，直到所有顶点都在一个集合中。,例题解析,04/04/2019,11,【解析】Kruscal算法的操作步骤： 首先将n个顶点看成n个互不连通的分量，从边集中找最小代价的边，如果落在不同连通分量上，则将其加入最小生成树，直到所有顶点都在同一连通分量上。,单源最短路径,在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。 迪杰斯特拉 (Dijkstra) 算法： 按路径长度递增次序产生最短路径 1、把 V 分成两组： (1) S：已求出最短路径的顶点的集合。 (2) V - S = T：尚未确定最短路径的顶点集合。 2、将 T 中顶点按最短路径递增的次序加入到 S 中，保证： (1) 从源点 v0 到 S 中各顶点的最短路径长度都不大于 从 v0 到 T 中任何顶点的最短路径长度。 (2) 每个顶点对应一个距离值： S中顶点：从 v0 到此顶点的最短路径长度。 T中顶点：从 v0 到此顶点的只包括 S 中顶点作中间顶点的 最短路径长度。,04/04/2019,12,Dijkstra 算法步骤：,T 中顶点对应的距离值用辅助数组 D 存放。,Di 初值：若 存在，则为其权值；否则为。,v2,13 8 30 32,v2,8,13 13 30 32,v3,v1,v1,13,13 30 22 20,v3,8+5 v2,19 22 20,v4,v4,8+5+6 v2-v3,21 20,v6,v5,13+7 v1,21,v5,v6,初始时令 S=v0, T=其余顶点。,v0,从 T 中选取一个其距离值最小的顶点 vj，加入 S。,对 T 中顶点的距离值进行修改：若加进 vj 作中间顶点，从 v0 到 vi 的距离值比 不加 vj 的路径要短，则修改此距离值。,重复上述步骤，直到 S = V 为止。,8+5 +6+2 v2-v3-v4,04/04/2019,13,拓扑排序,AOV网： 在一个有向图中，若用顶点表示活动，有向边表示活动间先后关系，称该有向图叫做顶点表示活动的网络(Activity On Vertex network)简称为AOV网。 拓扑排序的方法： 在有向图中选一个没有前驱的顶点且输出之。 从图中删除该顶点和所有以它为起点的弧。 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。,04/04/2019,14,例题解析,拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。,04/04/2019,15,【解析】解题关键是弄清拓扑排序的步骤,（1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。,【答案】（1）0132465 （2）0123465,关键路径,AOE(Activity on Edge)网络：定义结点为事件，有向边的指向表示事件的执行次序。单位是时间（时刻）。有向边定义为活动，它的权值定义为活动进行所需要的时间。 对AOE网，我们关心两个问题： (1)完成整项工程至少需要多少时间？ (2)哪些活动是影响工程进度的关键？ 关键路径路径长度最长的路径。路径长度路径上各活动持续时间之和,ve(j) 表示事件 vj 的最早发生时间。,vl(j) 表示事件 vj 的最迟发生时间。,ee(i) 表示活动 ai 的最早开始时间。,el(i) 表示活动 ai 的最迟开始时间。,el(i) - ee(i) 表示完成活动 ai 的时间余量。,关键活动 关键路径上的活动，即 el(i) = ee(i) 的活动。,04/04/2019,16,如何找 el(i) = ee(i) 的关键活动？,设活动 ai 用弧 表示，其持续时间记为：dut() 则有： (1) ee(i) = ve(j) (2) el(i) = vl(k) - dut(),(1) 从 ve(1) = 0 开始向前递推,(2) 从 vl(n) = ve(n) 开始向后递推,如何求 ve(j) 和 vl(j) ？,04/04/2019,17, ,求关键路径步骤： 求 ve(i)、vl(j) 求 ee(i)、el(i) 计算 el(i) - ee(i),0 6 4 5 7 7 16 14 18,0 6 6 8 7 10 16 14 18,04/04/2019,18,图,存储结构,遍 历,邻接矩阵,邻 接 表,十字链表,邻接多重表,深度优先搜索DFS,广度优先搜索BFS,无向图的应用,应用,图的连通分量,图的生成树,最小生成树,Prim算法,Kruskal算法,Dijkstra算法,Floyd算法,（利用DFS）,有向图的应用,DAG图,拓扑排序,关键路径,04/04/2019,19,第7讲 查找,基本概念：表/记录/关键字/静态查找表/动态查找表/平均查找长度 顺序表查找和“哨兵” 有序查找：折半查找/插值查找/斐波那契查找 线性索引：稠密索引/分块索引/倒排索引 二叉排序树/平衡二叉树：构建/插入/删除/保持平衡 B-树/B+树：构建/插入/删除操作 散列表：散列函数的选择和处理冲突的方法,04/04/2019,20,例题解析,设有序表为(a, b, c, d, e, f, g, h, i, j, k, p, q)，请分别画出对给定值a, g和n进行折半查找的过程。,04/04/2019,21,【答】,例题解析,构造有12个元素的二分查找的判定树，并求解下列问题： （1）各元素的查找长度最大是多少？ （2）查找长度为1、2、3、4的元素各有多少？具体是哪些元素？ （3）查找第5个元素依次要比较哪些元素？ 【答】 12个元素的判断树如下图所示：,04/04/2019,22,（1）最大查找长度是树的深度4。,（2）查找长度为1的元素有1个，为第6个，查找长度为2的元素有2个，为第3个和第9个，查找长度为3的元素有4个，为第1、4、7、11个，查找长度为4的元素有5个，为第2、5、8、10、12个。,（3）查找第五个元素依次比较6，3，4，5。,例：设有一组关键字32,75,63,48,94,25,36,18,70，采用哈希函数：H(key)=key MOD 11并采用步长为1的线性探测法解决冲突，试在0-10的散列地址空间中对该关键字序列构造哈希表。,【答】依题意，m=11，线性探测再散列的下一地址计算公式为： d1=H(key)， dj+1=(dj+1) MOD 11；j=1,2,. 其计算过程如下： H(32)=32 MOD 11=10 H(75)=75 MOD 11=9 H(63)=63 MOD 11=8 H(48)=48 MOD 11=4 H(94)=94 MOD 11=6 H(25)=25 MOD 11=3 H(36)=36 MOD 11=3(冲突) H(36)=(3+1) MOD 11=4(仍冲突) H(36)=(4+1) MOD 11=5 H(18)=18 MOD 11=7 H(70)=70 MOD 11=4 (冲突) H(70)=(4+1) MOD 11=5 (仍冲突) H(70)=(10+1) MOD 11=0,例题解析,04/04/2019,23,第八讲 排序,简单排序方法（0（n2） 插入排序（稳定排序） 选择排序（不稳定排序） 冒泡排序（不稳定排序） 先进排序方法（ O(nlogn)） 快速排序（不稳定排序） 归并排序（稳定排序） 堆排序（不稳定排序）,04/04/2019,24,一、时间性能,时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序，其中以 快速排序为最好。,时间复杂度为 O(n2)：直接插入排序、起泡排序和简单选择排序， 其中以直接插入为最好，特别是对那些对关 键字基本有序的记录序列尤为如此。,时间复杂度为 O(n*d)：基数排序。,1. 按平均时间性能来分，有三类排序方法：,2. 当待排序列按关键字顺序有序时，直接插入排序和起泡排序能 达到 O(n) 的时间复杂度，快速排序的时间性能蜕化为 O(n2) 。,3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中 关键字的分布而改变。,3.5 各种排序方法的综合比较,04/04/2019,25,二、空间性能,指的是排序过程中所需的辅助空间大小。,所有的简单排序方法(包括：直接插入、冒泡和简单选择) 和 堆排序的空间复杂度为 O(1)；,快速排序为 O(logn)，为递归程序执行过程中，栈所需的辅助 空间；,3. 归并排序所需辅助空间最多，其空间复杂度为 O(n)；,4. 链式基数排序需附设队列首尾指针，则空间复杂度为 O(2*rd+n),三、排序方法的稳定性能,1. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳 定的排序方法。,2. 对于不稳定的排序方法，只要能举出一个实例说明即可。,3. 快速排序、堆排序是不稳定的排序方法。,04/04/2019,26,各种内部排序方法的比较,04/04/2019,27,例题解析,设待排序的排序码序列