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

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