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

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