数据结构-考研课程总结.ppt

2020 3 15 数据结构 1 数据结构 主讲刘铁铭单位工院一系二教Tel 31946 2020 3 15 数据结构 2 讲课安排 串讲全书内容典型习题分析前年 去年考题分析 2020 3 15 数据结构 3 第一章概论 2020 3 15 数据结构 4 2020 3 15 数据结构 5 2020 3 15 数据结构 6 逻辑结构 有时直接称为数据结构 线性结构 线性表 栈 队列 串 最多只有一个直接前趋和一个直接后继 非线性结构 树 图 多维数组 广义表说明 1 逻辑结构与数据元素本身的形式 内容无关2 逻辑结构与数据元素的相对位置无关3 逻辑结构与所含结点个数无关 2020 3 15 数据结构 7 存储结构 顺序存储方法 数据元素在内存中按序连续存储 结点间的逻辑关系由存储单元的邻接关系来体现链接存储方法 用指针指出其直接后继结点的存储位置 结点间的逻辑关系由存储单元的邻接关系来体现索引存储方法 数据元素连续存放 再设一个索引表 有序 索引表由索引项组成 每个索引项由关键字和地址构成分为稠密索引和稀疏索引散列存储方法 确定散列函数后 根据结点的关键字直接计算出该结点的存储地址 2020 3 15 数据结构 8 关系 逻辑结构是从逻辑关系上描述数据 与存储无关 是独立于计算机的 逻辑结构是从具体问题抽象出来的数学模型存储结构是逻辑结构用计算机语言的实现 亦称映象 数据的运算是定义在数据的逻辑结构上的一个运算的集合运算的实现与存储结构密切相关逻辑结构与存储结构是多对多的关系 2020 3 15 数据结构 9 例 一个学生成绩表 是一个数据结构每行是一个结点 或记录 由学号 姓名 各科成绩及平均成绩等数据项组成 逻辑关系 线性结构存储结构 表的运算 2020 3 15 数据结构 10 2020 3 15 数据结构 11 2020 3 15 数据结构 12 2020 3 15 数据结构 13 2020 3 15 数据结构 14 第一章概论 三 渐进 时间复杂度 O f n 当问题的规模n趋向无穷大时 时间复杂度T n 的数量级 阶 称为算法的渐近时间复杂度 简称时间复杂度四 最坏时间复杂度依据数据集中可能出现的最坏情况估算出的时间复杂度称为最坏时间复杂度 五 平均时间复杂度在假设数据集的分布是等概率的条件下 估算出的时间复杂度称为平均时间复杂度 例 顺序查找 2020 3 15 数据结构 15 五 空间复杂度S n 算法所耗费的存储空间 仍是问题规模n的函数 第一章概论 2020 3 15 数据结构 16 第一章概论 2020 3 15 数据结构 17 第二章线性表 本章要学习的主要内容1 线性表的逻辑结构及基本运算2 线性表的顺序存储结构3 线性表的链式存储结构 单链表 循环链表 双链表 静态链表4 顺序表和链表的比较 2020 3 15 数据结构 18 2020 3 15 数据结构 19 2020 3 15 数据结构 20 2020 3 15 数据结构 21 2020 3 15 数据结构 22 2020 3 15 数据结构 23 2020 3 15 数据结构 24 2020 3 15 数据结构 25 2020 3 15 数据结构 26 2020 3 15 数据结构 27 2020 3 15 数据结构 28 2020 3 15 数据结构 29 2020 3 15 数据结构 30 2020 3 15 数据结构 31 2020 3 15 数据结构 32 2 3 2单链表上的基本运算 实现 Linklist CREATLISTR1 charch linklist head s r head malloc sizeof linklist r head ch getchar while ch s malloc sizeof linklist s data ch r next s r s ch getchar r next NULL returnhead 2020 3 15 数据结构 33 2020 3 15 数据结构 34 按值查找即在链表中查找是否有值等于给定值key的结点 若有则返回首次找到的其值为key的结点的指针 否则返回NULL 算法描述如下 linklist locate head key linklist head datatyekey linklist p p head next 在等概率的情况下 该算法的平均时间复杂度亦为O n 2 按值查找LOCATE head key 2 3 2单链表上的基本运算 实现 while p NULL if p data key p p next elsebreak returnp 2020 3 15 数据结构 35 3 插入运算 1 后插操作 在指针p所指结点之后插入 2 前插操作 在指针p所指结点之前插入 时间复杂度度O 1 平均时间复杂度O n 先从头指针起 顺链找到 p的前趋结点 q 2020 3 15 数据结构 36 x 3 插入运算 将前插操作转变为后插操作 a 2020 3 15 数据结构 37 4 删除运算 时间复杂度O 1 删除指定结点的直接后继 r p next p next r next free r 删除指定结点 时间复杂度O n 链表的优点 在链表上实现插入 删除运算无须移动结点 仅须修改指针 2020 3 15 数据结构 38 2020 3 15 数据结构 39 2020 3 15 数据结构 40 DELETENODE p 删除双链表结点 p dlinklist p p prior next p next p next prior p prior free p 2020 3 15 数据结构 41 2020 3 15 数据结构 42 2 3 5静态链表 静态链表与动态链表的区别 2020 3 15 数据结构 43 2 静态链表存储结构描述如下 definemaxsize1024typedefintdatatype typedefintcursor typedefstruct datatypedata 数据域cursornext 游标 node nodenodepool maxsize 存储池cursorav 游标变量 2020 3 15 数据结构 44 2020 3 15 数据结构 45 2020 3 15 数据结构 46 4 节点的分配与回收 GETNODE 将表av上的第一个结点取出 并把该结点的位置付给pCursorGETNODE cursorp if av NULL p NULL else p av av nodepool av next returnp FREENODE p 将p所指的结点插入到表av的头上 FREENODE p nodepool p next av av p 2020 3 15 数据结构 47 2020 3 15 数据结构 48 2020 3 15 数据结构 49 2020 3 15 数据结构 50 2020 3 15 数据结构 51 2020 3 15 数据结构 52 2020 3 15 数据结构 53 2020 3 15 数据结构 54 2020 3 15 数据结构 55 2020 3 15 数据结构 56 4链栈上基本运算的实现 1 进栈PUSHLSTACK top x 2020 3 15 数据结构 57 2 退栈 POPLSTACK top datap 2020 3 15 数据结构 58 3 2栈的应用举例 1 文字编辑器2 函数的递归调用 p47 2020 3 15 数据结构 59 2020 3 15 数据结构 60 3队列的基本运算 1 SETNULL Q 置队空 2 EMPTY Q 判队空 3 FRONT Q 取队头元素 队中元素保持不变 4 ENQUEUE Q x 将元素x入队 5 DEQUEUE Q 出队 函数返回原队头元素 2020 3 15 数据结构 61 2020 3 15 数据结构 62 2020 3 15 数据结构 63 2020 3 15 数据结构 64 解决 假上溢 的方法有两种 2020 3 15 数据结构 65 采用循环队列后 进行入队和出队运算时 头 尾指针加1操作应如下进行 出队 sq front sq front 1 maxsize 入队 sq rear sq rear 1 maxsize 循环队列如何判断队空和队满 方法一 引入标志flag若 sq front sq rear flag 0 则队空 不能出栈 若 sq front sq rear flag 1 则队满 不能入栈 2020 3 15 数据结构 66 2020 3 15 数据结构 67 2020 3 15 数据结构 68 1 入队ENQUEUE q x 类似于单链表的尾插法 2020 3 15 数据结构 69 2020 3 15 数据结构 70 2020 3 15 数据结构 71 2020 3 15 数据结构 72 2020 3 15 数据结构 73 2020 3 15 数据结构 74 2020 3 15 数据结构 75 2020 3 15 数据结构 76 2020 3 15 数据结构 77 typedefstructlinknode chardata structlinknode next linkstring linkstring s 如果结点大小不为1 则此处应说明一个字符数组 链串存储结构描述如下 2020 3 15 数据结构 78 2020 3 15 数据结构 79 2020 3 15 数据结构 80 2020 3 15 数据结构 81 1 朴素的匹配算法 基本思想 初始时 从S的第一个字符开始将T的第一个字符与其进行比较 若相等 则继续逐个比较后续字符 如匹配成功 则返回子串在S中的位置 否则 将T向右移动一个字符位置 从T的第一个字符开始与S中第二个字符进行比较 并在相等的情况下逐个比较后续字符 进行第二趟匹配 成功则返回子串在S中的位置 否则 T再向右移动一个字符位置 进行第三趟匹配 如此反复 或匹配成功 或当T右移到无法与S继续进行比较时 匹配失败 2020 3 15 数据结构 82 设S ababcabcacbab T abcac i指针回溯的位置为 i i j 1 i的值为1 1 朴素的匹配算法 2020 3 15 数据结构 83 设S ababcabcacbab T abcac i指针回溯的位置为 i i j 1 i的值为2 2020 3 15 数据结构 84 设S ababcabcacbab T abcac i指针回溯的位置为 i i j 1 i的值为3 2020 3 15 数据结构 85 设S ababcabcacbab T abcac i指针回溯的位置为 i i j 1 i的值为4 2020 3 15 数据结构 86 设S ababcabcacbab T abcac i指针回溯的位置为 i i j 1 i的值为5 2020 3 15 数据结构 87 设S ababcabcacbab T abcac 返回子串的位置为 i j 1 6 串的起始位置从1开始算起 2020 3 15 数据结构 88 intindex s t seqstring s t inti 0 j 0 while i s curlen 朴素的模式匹配算法描述如下 2020 3 15 数据结构 89 2020 3 15 数据结构 90 2020 3 15 数据结构 91 2020 3 15 数据结构 92 2020 3 15 数据结构 93 2020 3 15 数据结构 94 2020 3 15 数据结构 95 2020 3 15 数据结构 96 3 确定aij与s k 的对应关系a 若i j则k i i 1 2 jb 若i j则k j j 1 2 i 这是由对称性质决定的 注意 进行压缩存储后 没有改变原采用二维数组存储时能进行随机访问的特性 综合a b 令I max i j J min i j 则k I I 1 2 J loc aij loc sa k loc sa 0 k d loc sa 0 I I 1 2 J d a00a10a11a20a21a22 aijan 1 0an 1 1an 1 2 an 1 n 1 2020 3 15 数据结构 97 2 三角矩阵 方阵 2020 3 15 数据结构 98 2020 3 15 数据结构 99 i n i 1 i 2 2020 3 15 数据结构 100 2020 3 15 数据结构 101 2020 3 15 数据结构 102 2020 3 15 数据结构 103 2 稀疏矩阵用三元组表实现压缩存储时的存储结构描述 defineSMAX16typedefstruct inti j datatypev node typedefstruct intm n t nodedata SMAX spmatrix spmatrix a 定义三元组结构 定义三元组表结构 2020 3 15 数据结构 104 3 运算 稀疏矩阵采用三元组表实现存储后 其矩阵运算的实现比采用二维数组存储时要复杂 2020 3 15 数据结构 105 2020 3 15 数据结构 106 2020 3 15 数据结构 107 十字链表 2020 3 15 数据结构 109 2020 3 15 数据结构 110 建立十字链表的算法分为两步 1 建立表头结点的循环链表2 依次读入非零元素的三元组 每读入一个三元组 生成一个表结点 并将其插入相应行 列链表中的正确位置上 2020 3 15 数据结构 111 2020 3 15 数据结构 112 2020 3 15 数据结构 113 2020 3 15 数据结构 114 2020 3 15 数据结构 115 5 3广义表的存储p83 1 单链表示法 模仿单链表结构 2 双链表示法 类似于第六章的二叉链表 2020 3 15 数据结构 116 第六章树 树形结构是一种重要的非线性结构 在我们的客观世界和现实生活中大量存在 树形结构 结点之间有分支 并且具有层次关系的结构 2020 3 15 数据结构 117 2020 3 15 数据结构 118 2020 3 15 数据结构 119 2020 3 15 数据结构 120 2020 3 15 数据结构 121 2020 3 15 数据结构 122 2020 3 15 数据结构 123 6 2二叉树 6 2 1二叉树的概念 一 二叉树的定义 二叉树 BinaryTree 是n n 0 个结点的有限集 它或者是空集 n 0 或者由一个根结点和两棵互不相交的 分别称为根的左子树和右子树的二叉树组成 可以看出 二叉树的定义和树的定义一样 均为递归定义 2020 3 15 数据结构 124 2020 3 15 数据结构 125 6 2 2二叉树的性质 性质1 二叉树第i层上的结点数目最多为2i 1 i 1 性质2 深度为k的二叉树至多有2k 1个结点 k 1 性质3 任意二叉树中 若叶结点的个数为n0 度为2的结点数为n2 则n0 n2 1 2020 3 15 数据结构 126 2020 3 15 数据结构 127 两种特殊形态的二叉树 满二叉树和完全二叉树深度为k且有2k 1个结点的二叉树称为满二叉树 对满二叉树的结点进行编号 约定编号从根结点起 自上而下 自左至右 深度为k的 有n个结点的二叉树 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应 则称之为完全二叉树 2020 3 15 数据结构 128 2020 3 15 数据结构 129 2020 3 15 数据结构 130 2020 3 15 数据结构 131 2020 3 15 数据结构 132 2020 3 15 数据结构 133 2020 3 15 数据结构 134 2020 3 15 数据结构 135 2020 3 15 数据结构 136 2020 3 15 数据结构 137 2020 3 15 数据结构 138 2020 3 15 数据结构 139 算法描述 preorder t bitree t if t printf t c t data preorder t lchild preorder t rchild 2020 3 15 数据结构 140 三种遍历算法的 1 printf 在算法中的位置不同2 执行时所 走 的路线是一样的 每个结点经过三次 3 访问结点的时机不同得到不同的遍历次序 递归算法看似简单 但执行过程相当复杂 P97 2020 3 15 数据结构 141 2020 3 15 数据结构 142 第一次经过的结点 第二次经过的结点 第三次经过的结点 a b d e c f d b a c e f d b e c f a 2020 3 15 数据结构 143 typedefbitree datatype typedefstructnode datatypedata structnode next linkstack inorder t bitree t linkstack top top NIL do while t NIL top pushlstack top t t t lchild if top NIL top poplstack top 算法描述如下 2020 3 15 数据结构 145 lorder t bitree t sequeue sq sq为循环队列指针 bitree xsetnull sq if t NULL enqueue sq t while empty sq x dequeue sq printf d t x data if x lchild NIL enqueue sq x lchild if x rchild NIL enqueue sq x rchild 2020 3 15 数据结构 147 6 4线索二叉树 问题单单依靠二叉树并不能直接得到结点在任一序列中的前趋和后继 这种信息只有在动态遍历中才能得到 所以某次遍历得到的信息 下次再用时 仍要重新遍历 一 如何保存在遍历过程中得到的信息 2020 3 15 数据结构 148 利用已有的指针域存放 利用二叉链表上的n 1个空指针域 存放指向结点在某种遍历次序下的前趋和后继结点的指针 由此得到的二叉链表称为线索链表 相应地采用这种存储结构的二叉树称为线索二叉树 线索链表中结点的结构 typedefstructnode intltag rtag datatypedata structnode lchild rchild bithptr bithptr p 2020 3 15 数据结构 149 线索化 建立某次序线索二叉树的步骤2 步骤1类似于二叉链表的建立过程 将二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化 具体地体现在将二叉链表变为线索链表 2020 3 15 数据结构 150 2020 3 15 数据结构 151 2020 3 15 数据结构 152 2020 3 15 数据结构 153 2020 3 15 数据结构 154 2020 3 15 数据结构 155 2020 3 15 数据结构 156 2020 3 15 数据结构 157 2020 3 15 数据结构 158 2 遍历线索二叉树 遍历二叉树 指按某种路径对树中结点访问且仅访问一次 遍历线索二叉树 从某次序下的开始结点出发 反复找到该结点在该次序下的后继 直至终端结点 算法要点 1 如果线索二叉树非空 则做 2 否则结束 2 找到某次序下的开始结点 3 访问该结点 4 找到该结点在该次序下的后继 5 不是空则转 3 否则结束 2020 3 15 数据结构 159 总结 1 遍历线索二叉树对中序和前序线索树 很容易实现 但后序不好实现 因为后序后继不能直接找到 2 比二叉树遍历算法简单易理解 且无需设栈 3 若一棵二叉树要经常进行遍历运算 或经常查找结点在某种指定次序下的前趋和后继 则选用线索二叉树 2020 3 15 数据结构 160 3 线索二叉树的插入 线索二叉树的优点 查找和遍历优于非线索树 线索二叉树的缺点 插入和删除不仅要修改指针 还要修改线索 线索二叉树的插入和删除也分为前序 中序和后序 2020 3 15 数据结构 161 2020 3 15 数据结构 162 2020 3 15 数据结构 163 2020 3 15 数据结构 164 2020 3 15 数据结构 165 2020 3 15 数据结构 166 2020 3 15 数据结构 167 2020 3 15 数据结构 168 3 孩子兄弟链表表示法 在存储结点信息的同时 附加两个分别指向该结点最左孩子和右邻兄弟的指针域 该方法实际上是用二叉链表实现树的储存 2020 3 15 数据结构 169 2020 3 15 数据结构 170 2020 3 15 数据结构 171 2020 3 15 数据结构 172 特点 1 前序遍历森林得到的序列与前序遍历对应二叉树得到的序列相同 2 后序遍历森林得到的序列与中序遍历对应二叉树得到的序列相同 2020 3 15 数据结构 173 2020 3 15 数据结构 174 2 哈夫曼算法 已知w1 w2 wn这n个权值后 如何构造哈夫曼树 1 哈夫曼算法思想 1 根据给定的n个权值w1 w2 wn构造n棵只有根结点的树 2 从中选两棵根结点权值最小的树进行合并 增加一个新结点作为新树的根 树的数目减少一棵 3 重复 2 直到F只含一棵二叉树为止 这棵二叉树便是哈夫曼树 10 9 5 6 2020 3 15 数据结构 177 哈夫曼树的特点哈夫曼树中只有0度和2度结点 不可能有1度结点 具有n个叶结点的哈夫曼树所含结点数必为2n 1 具有n个叶结点的哈夫曼树的最大高度为n 哈夫曼树的形式不是唯一的 但wpl值是唯一的 哈夫曼树不一定是朝一个方向的 2020 3 15 数据结构 178 2020 3 15 数据结构 179 构造最优 平均码长最短的 前缀码的方法如下 1 以字符集中每个字符出现的概率为权值 构造哈夫曼树 2 在哈夫曼树中每个分支结点的左分支上标上0 右分支上标上1 3 把从根到每个叶结点的路径上的所有0或1标号连接起来作为叶结点所代表的字符的编码 2020 3 15 数据结构 180 图是一种复杂的非线性结构 线性结构 树形结构中对结点而言 存在前趋和后继的概念 图中的结点 通常称为顶点 是否也有前趋和后继呢 不能一概而论 图G由两个集合V和E组成 记为G V E 其中V为顶点的有穷非空集合 E为V中顶点偶对 即边 的集合 图G的顶点集和边集分别记为V G 和E G E G 可以是空集 若E G 为空 则图G只有顶点而没有边 第七章图 有向图 图G中的每一条边都是有方向的 无向图 图中的每一条边都是无方向的 vi vj 2020 3 15 数据结构 181 简单图 以下我们讨论的图是满足下列两条件的简单图 1 不含顶点到自身的边 即若 Vi Vj 或 Vi Vj E G 则Vi Vj 2 不允许一条边在图中重复出现具有上述要求的图 其顶点数n和边数e满足下列关系 若G为无向图0 e n n 1 2若G为有向图0 e n n 1 2020 3 15 数据结构 182 恰好有n n 1 2条边的无向图称为无向完全图 恰好有n n 1 边的有向图称为有向完全图 若 vi vj 是一条无向边 则称顶点vi和vj互为邻结点 Adjacent vi vj 与顶点vi和vj相关联 Incident 若是一条有向边 则称顶点vi邻接到vj 顶点vj邻接于vi 与顶点vi和vj相关联 度 入度和出度的概念 无向图中顶点v的度为关联于该顶点的边的数目 记为D v 有向图中把以顶点v为终点的边的数目称为v的入度 记为ID v 把以顶点v为始点的边的数目称为v的出度 记为OD v 顶点的度定义为入度与出度之和 即D v ID v OD v 2020 3 15 数据结构 184 子图的概念 设G V E 是一个图 若V 是V的子集 E 是E的子集且E 中的边所关联的顶点均在V 中 则G V E 也是一个图 并称其为G的子图 V v0 v1 E v0 v2 G V E 不是图 也不可能是子图 第七章图 2020 3 15 数据结构 185 2020 3 15 数据结构 189 2 邻接矩阵存储结构描述 definen 图中顶点个数 definee 图中边 弧 条数 typedefcharvextype 顶点数据类型 typedeffloatadjtype 权值类型 typedefstruct vextypevexs n 数组vexs 用于存储顶点数据 adjtypearcs n n arcs 为邻接矩阵 graph 若图中顶点信息仅为编号 则仅需存储一个邻接矩阵即可表示图 采用邻接矩阵表示法实现图的存储 空间复杂度为O n2 2020 3 15 数据结构 192 2020 3 15 数据结构 193 typedefstrcut vextypevertex edgenode link vexnode 顶点表结点结构 vexnodega n 2 邻接表存储结构描述 typedefstructnode intadjvex structnode next edgenode 边表结点结构 2020 3 15 数据结构 194 2020 3 15 数据结构 195 2020 3 15 数据结构 197 7 总结 第七章图 2020 3 15 数据结构 198 定义图的遍历是指从图的某个顶点出发 沿着某条搜索路径对图中所有顶点访问且仅访问一次 7 3图的遍历 一 图遍历运算的基本概念 2020 3 15 数据结构 199 特点 遍历过程中尽可能地先对纵深方向进行搜索 2020 3 15 数据结构 200 DFSL i inti intj edgenode p printf node c n gl i vertex visited i TRUE p gl i link 取vi的边表头指针 while p NULL 依次搜索vi的邻接点 if visited p adjvex 从vi的未曾访问过的邻接点出发进行深度优先搜索 DFSL p adjvex p p next 找vi的下一邻接点 以邻接表为存储结构的深度优先算法 2020 3 15 数据结构 201 7 3图的遍历 DFS序列不唯一 它与遍历算法 图的存储结构以及初始出发点有关 3 算法分析 对于具有n个顶点 e条边的连通图 对图进行深度优先搜索得到的顶点序列称为深度优先搜索序列 简称为DFS序列 注意 2020 3 15 数据结构 202 7 3图的遍历 三 连通图的广度优先搜索遍历 BreadthFirstSearch 1 BFS基本思想从图G中任一顶点vi开始 首先访问顶点vi 接着依次访问vi的所有邻接点w0 w1 wt 然后再依次访问w0 w1 wt邻接的所有未被访问过的顶点 依次类推 直到图中所有和vi有路径相通的顶点都被访问过为止 特点 尽可能地先对横向进行搜索 BFS算法 符合先进先出性质 在算法实现过程中 引入队列作为辅助存储结构 存储已被访问的顶点 2 算法实现 2020 3 15 数据结构 203 BFSL intk inti edgenode p setnull q printf c n gl k vertex visited k true enqueue q k while empty q i dequeue q p gl i link while p null if visited p adjvex printf c n gl p adjvex vertex visited p adjvex true enqueue q p adjvex p p next 从vk出发广度优先搜索图 图G用邻接表表示 初始将队列q置空 访问出发点vk并置访问标志 已访问的顶点序号入队 队头元素序号出队列 取vi邻接表的头指针 访问vi未访问的邻接点 已访问的顶点序号入队 找vi的下一个邻接点 2020 3 15 数据结构 204 7 3图的遍历 对图进行广度优先搜索得到的顶点序列称为广度优先搜索序列 简称为BFS序列 两种遍历方法比较 BFS序列不唯一 BFS序列与遍历算法 图的存储结构以及初始出发点有关 3 算法分析 对于具有n个顶点 e条边的连通图 二者对顶点的搜索次序不同 两种遍历方法实现的手段不同 注意 2020 3 15 数据结构 205 7 3图的遍历 四 非连通图的遍历 非连通图具有两个或两个以上的连通分量 当从某个顶点vi开始对其进行深度或广度优先搜索只能遍历包含顶点vi的连通分量 非连通图的遍历须多次调用深度或广度优先搜索算法 2020 3 15 数据结构 206 7 3图的遍历 非连通图遍历算法描述 TRAVER inti for i 0 i n i visited i false for i 0 i n i if visited i DFS i 遍历各个连通分量 初始访问标志 深度优先搜索遍历非连通图算法 BFSL i 广度优先搜索遍历非连通图算法 如果图是连通的 则算法TRAVER只调用一次DFS 或BFS 如果图包含n个连通分量 则算法TRAVER调用n次DFS 或BFS 7 4生成树和最小生成树 1 定义 具有n个顶点的无向连通图G 其生成树为包含有n个顶点和n 1条边的无向连通子图 或生成树是连通图G的一个极小连通子图 1 无向连通图的生成树的定义 2 特点 a 无向连通图的生成树通常是不唯一的b 生成树满足连通性且边数最小 3 无向非连通图没有生成树 但其各个连通分量有生成树 各个连通分量的生成树形成一个森林 称为无向非连通图的生成森林 第七章图 2020 3 15 数据结构 209 2020 3 15 数据结构 210 2020 3 15 数据结构 211 Prim算法思想 假设G V E 为无向连通网 生成的最小生成树T U TE 求T 实际上求TE 的步骤为 1 初始化U u0 TE 2 在所有u U v V U的边 u v 中找一条权值最小的边 u0 v0 并入集合TE 同时v0并入U 3 若U V 算法结束 否则重复2 5 如何求无向连通网的最小生成树 prim算法的时间复杂度为O n2 与无向连通网中顶点数n有关 与边无关 因此该算法适合稠密连通网 2020 3 15 数据结构 212 Kruskal算法的初略描述 G V E T V while T中所含边数 n 1 从E中选取当前权值最小边 u v 从E中删去边 u v if u v 并入T之后不产生回路 将边 u v 并入T中 2020 3 15 数据结构 213 2020 3 15 数据结构 214 二 对给定的有向网G V E 和源点v 如何求单源最短路径 Dijkstra算法 1 Dijkstra算法思想 从给定的源点开始 按路径长度递增的顺序 逐步产生源点到其余各顶点的最短路径 2 算法思想的具体实现 2020 3 15 数据结构 215 1 基本原理 设置一个顶点集合S S中的所有顶点其最短路径已经求出 初始时S v 则尚未求出最短路径的顶点集为V S 另外 设置一个数组d 若顶点vi的最短路径已求出 则d i 存放的是最短路径长度 否则d i 存放的是从顶点v经S中的顶点到vi的所有路径中最短路径的长度 并称其为vi的距离 初始时wi若为G中的边d i 若不是G中的边 设vj为V S中距离最短的顶点 可以证明 1 d j 为vj的最短路径的长度 2 顶点vj为V S中最短路径长度最短的顶点 2020 3 15 数据结构 216 调整方法 对V S中任意顶点vj 若d j d k 则将d k 的值赋给d j 否则 d j 的值不变 2 Djkstra算法的粗略描述 S v 初始化V S中各顶点的距离值 while S中的顶点数 n 从V S中选取距离值最小的顶点vj S S vj 调整V S中各顶点的距离值 2020 3 15 数据结构 217 2020 3 15 数据结构 218 定义一个n n的方阵序列 A 1 A 0 A 1 A k A n 1 其中 A 1 i j c i j A k i j Min A k 1 i j A k 1 i k A k 1 k j 0 k n 1由上述公式可知 A 0 i j 是从顶点vi到vj的中间顶点序号不大于0的最短路径 A k i j 是从顶点vi到vj的中间顶点序号不大于k的最短路径 A n 1 i j 就是从顶点vi到vj的最短路径 2 实现原理 定义一个n n的方阵序列 2020 3 15 数据结构 219 3 具体实现a Floyd算法在具体实现时仅使用一个n n的方阵A 初始时A c i j 通过在A上进行n次迭代求得A n 1 由于是在同一个矩阵A中迭代 所以A k i j A k 1 i k A k 1 k j 是由A i j A i k A k j 实现的 因此要使迭代正确 必须保证 A i k A k 1 i k A k j A k 1 k j 即保证A i k 和A k j 在该次迭代中不发生变化 2020 3 15 数据结构 220 4 Floyd算法的具体描述 intpath n n floyd a c floata n c n inti j k next intmax 160 for i 0 i n i for j 0 j n j if c i j max path i j jelsepath i j 1 a i j c i j for k 0 k a i k a k j a i j a i k a k j path i j path i k for i 0 i d next next path next j printf d n j 进行n次迭代 输出各个顶点间最短路径的值 输出各个顶点间最短路径的顶点轨迹 2020 3 15 数据结构 222 2020 3 15 数据结构 223 2020 3 15 数据结构 224 2020 3 15 数据结构 225 2020 3 15 数据结构 226 2020 3 15 数据结构 227 3 拓扑算法梗概 1 扫描顶点表 将入度为零的顶点入栈 2 while 栈非空 将栈顶顶点vj弹出并输出之 检查vj的出边表 将每条出边 vj vk 的终点vk的入度减1 若vk的入度变为0 则把vk推入栈 3 若输出的顶点数小于n 则输出 有回路 否则拓扑排序正常结束 2020 3 15 数据结构 228 2020 3 15 数据结构 229 2020 3 15 数据结构 230 2020 3 15 数据结构 231 事件vj可能的最早发生时间ve j 应为从源点到顶点vj的最长路径长度弧表示的活动ai的最早开始时间e i 等于ve j 在不推迟整个工程完成的前提下 事件vk允许的最迟发生时间vl k 应等于汇点vn的最早发生时间ve n 减去vk到vn的最长路径长度 弧表示的活动ai的最迟开始时间l i 等于vl k 减去弧的权值 4 ve j e i vl k l i 2020 3 15 数据结构 232 5 关键活动 对活动ai而言 l i e i 为其在不延误整个工程工期情况下 可以延迟的时间 若e i l i 则称活动ai为关键活动 关键路径上的所有活动都是关键活动 缩短或延误关键活动的持续时间将提前或推迟整个工程的完工时间 2020 3 15 数据结构 233 2 求关键活动的算法 1 对AOE网进行拓扑排序 并按排序的次序求各顶点事件的ve值 若网有回路 则算法终止 否则执行步骤 2 2 按拓扑排序的逆序求各顶点事件的vl值 3 根据各顶点事件的ve值和vl值 求各活动ai的e i 和v i 若e i v i 则ai为关键活动 2020 3 15 数据结构 234 8 1基本概念 第八章排序 1 定义 排序的含义 对含有多个记录的文件进行整理 最终使得各个记录按关键字递增 或递减 的次序排列起来 这个整理的过程称为排序 2020 3 15 数据结构 235 2020 3 15 数据结构 236 2020 3 15 数据结构 237 2020 3 15 数据结构 238 2020 3 15 数据结构 239 2020 3 15 数据结构 240 2020 3 15 数据结构 241 2020 3 15 数据结构 242 2020 3 15 数据结构 243 2020 3 15 数据结构 244 8 2 2希尔排序 希尔排序的平均比较次数和移动次数约为n1 3 该排序方法是不稳定的 增量序列的选取没有唯一的方法 缺点 算法较复杂 是不稳排序 2020 3 15 数据结构 245 8 3交换排序 基本思想 两两比较待排序记录的关键字 发现两个记录的次序相反时即进行交换 直到没有反序的记录为止 8 3 1起泡排序 起泡排序快速排序 1 形象描述 R 0 R 1 R 2 R 3 R n 2 R n 1 R 0 R 1 R 2 R 3 R n 2 R n 1 R n 2 R n 1 第一趟比较 第二趟比较 第n 1趟比较 最小 有两种方法 2020 3 15 数据结构 246 为了判断在一趟排序中有没有交换位置 可引用一个布尔量noswap 每趟排序前先将它置为ture 排序过程中若有交换 则noswap置为true 当一趟排序结束时 我们再检查noswap 若仍为ture便终止算法 8 3 1起泡排序 2020 3 15 数据结构 247 2020 3 15 数据结构 248 2020 3 15 数据结构 249 8 3 2快速排序 1 基本思想 在当前无序区r l 至r h 中任选取一个记录作为比较的基准 假设为temp 用此基准将无序区分成两个较小的无序区 r l 至r i 1 和r i 1 至r h 且左边无序区中记录的键值均小于或等于基准的键值 右边无序区的键值均大于或等于基准的键值 若r l 至r i 1 和r i 1 至r h 非空 分别对它们进行上述的划分过程 直到所有无序区中记录均已排好为止 2020 3 15 数据结构 250 2020 3 15 数据结构 252 2020 3 15 数据结构 253 2020 3 15 数据结构 255 2020 3 15 数据结构 256 2020 3 15 数据结构 257 2020 3 15 数据结构 258 2020 3 15 数据结构 259 2020 3 15 数据结构 260 2020 3 15 数据结构 261 2020 3 15 数据结构 262 2020 3 15 数据结构 263 2 如何完成初始建堆工作 基本思想 依次将以序号为 由高至底 从 n 2 n 2 1 1的结点作为根的子树调用筛选算法即可 For i n 2 i 1 i SIFT R i n 2020 3 15 数据结构 264 3 堆排序算法1 首先初始建堆2 然后进行n 1趟堆排序 每一趟排序要做的工作是i 将当前堆顶和堆尾互换ii 去掉该堆尾后的序列重新建堆 2020 3 15 数据结构 265 HEAPSORT R rectypeR inti rectypetemp for i n 2 i 1 i SIFT R i n for i n i 1 i temp R 1 R 1 R i R i temp SIFT R 1 i 1 初始建堆 进行n 1趟堆排序 2020 3 15 数据结构 266 2020 3 15 数据结构 267 2020 3 15 数据结构 268 8 5归并排序 2020 3 15 数据结构 269 2020 3 15 数据结构 271 2020 3 15 数据结构 272 2020 3 15 数据结构 273 2020 3 15 数据结构 274 8 6分配排序 2020 3 15 数据结构 275 2020 3 15 数据结构 276 2020 3 15 数据结构 277 2020 3 15 数据结构 278 2020 3 15 数据结构 279 平均查找长度ASL AverageSearchLength 定义为 pi为查找第i个结点的概率 假定结点的查找是等概率的 则pi 1 n ci为查找第i个结点需进行比较的次数 说明 查找是对已存入计算机的数据所进行的操作 采用什么查找方法首先取决于所采用的数据结构 即表中的结点是按什么方式组织的 为了提高查找速度 我们常用某些特殊的数据结构来组织 所以 在选择查找方法时首先要弄清楚这些方法所需的数据结构 尤其是存储结构 2020 3 15 数据结构 280 2020 3 15 数据结构 281 2020 3 15 数据结构 282 2 二分查找 要求 线性表是有序表并且用向量作为存储结构 基本步骤 设表为升序 i 确定查找的起始空间low highii 求区间内中间结点的下标mid high mid 2 k与R mid 比较 若 查找成功若 low mid 1 high不变iii 判断查找区间是否还存在 low high 存在 重复2不存在 查找失败 返回 2020 3 15 数据结构 283 2020 3 15 数据结构 284 2020 3 15 数据结构 285 5 二分查找算法优缺点 优点 查找效率高缺点 需预先排序 O nlog2n 只适用于顺序存储结构 为保持有序性 插入删除必须移动大量结点适用范围 适用于一经建立就很少改动 而又经常需要查找的线性表 2020 3 15 数据结构 286 2020 3 15 数据结构 287 2020 3 15 数据结构 288 2020 3 15 数据结构 289 2020 3 15 数据结构 290 9 3树表的查找 当表采用二叉树实现存储时 这样的表称为树表 2020 3 15 数据结构 291 2020 3 15 数据结构 292 2020 3 15 数据结构 293 2 二叉排序树存储结构 typedefstructnode keytypekey datatypeother structnode lchild rchild bstnode 2020 3 15 数据结构 294 2020 3 15 数据结构 295 生成二叉排序树的思想 可通过多次调用插入过程来生成如 插入序列为2 1 7 8 5 2 二叉排序树的生成 2020 3 15 数据结构 296 2020 3 15 数据结构 297 2020 3 15 数据结构 298 2020 3 15 数据结构 299 2020 3 15 数据结构 300 2020 3 15 数据结构 301 2020 3 15 数据结构 302 3 AVL树的插入算法 首先 要搞清AVL树的结点结构 在二叉排序树的结点结构中增加一个平衡因子bf域 设 s是待插入的结点 s的左 右指针均为空 平衡因子为零 其次 我们要讨论以下几个关键问题 1 由于 s的插入而失去平衡时 如何找到最小不平衡子树 2 当 s插入树中后 如何修改有关结点的平衡因子 3 如何判别以 a为根的子树是否失去平衡 4 如何调整失去平衡的