| 作者 |
| 罗德·斯蒂芬斯 迈克尔 T. 古德里奇 |
| 丛书名 |
| 计算机科学丛书 |
| 出版社 |
| 机械工业出版社 |
| ISBN |
| 9782101251627 |
| 简要 |
| 简介 |
| 内容简介书籍计算机书籍 ---------------------------算法基础：Python和C#语言实现（原书第2版）--------------------------- 本书第2版进行了全面修订与更新，更加易于学习。书中描述了那些重要且经典的算法，并且说明了不同算法的适用情境。跟随作者的讲解，读者将学会分析既有算法，进而理解算法背后的原理。同时，读者也将学习创建新的算法，以适应未来的新需求。这些有用的算法包括：操作常用数据结构的方法，高级数据结构，网络算法，以及数值算法。此外，书中还包含通用的问题求解技巧。除了描述算法，作者还详细介绍了如何分析算法的性能。书中提供大量练习，读者可以自己探索修改算法的方法，以便将其应用于新的情境。 ---------------------------数据结构与算法：Python语言实现--------------------------- 本书采用Python语言介绍数据结构和算法，包括其设计、分析和实施。本书源代码简洁、明确，面向对象的观点贯穿始终，通过继承最大限度地提高代码重用，同时彰显不同抽象数据类型和算法之间的异同。 |
| 目录 |
---------------------------算法基础：Python和C#语言实现（原书第2版）--------------------------- 出版者的话 译者序 前言 作者简介 第1章 算法基础 1 1.1 方法 1 1.2 算法和数据结构 2 1.3 伪代码 2 1.4 算法的特点 4 1.4.1 大O符号 5 1.4.2 常用的运行时间函数 7 1.4.3 运行时间函数的可视化比较 11 1.5 实际考虑 12 1.6 本章小结 13 1.7 练习题 14 第2章 数值算法 16 2.1 数据随机化 16 2.1.1 随机数生成器 16 2.1.2 随机化数组 20 2.1.3 生成非均匀分布 21 2.1.4 随机行走 22 2.2 查找最大公约数 25 2.2.1 计算最大公约数 25 2.2.2 最大公约数算法的扩展应用 27 2.3 计算乘幂 28 2.4 处理素数 29 2.4.1 查找素数因子 29 2.4.2 查找素数 31 2.4.3 素性检验 32 2.5 计算数值积分 33 2.5.1 矩形法则 34 2.5.2 梯形法则 34 2.5.3 自适应积分算法 35 2.5.4 蒙特卡罗积分法 37 2.6 方程求解 38 2.7 高斯消元法 40 2.7.1 前向消元 40 2.7.2 后向代换 41 2.7.3 算法实现 42 2.8 最小二乘法拟合 42 2.8.1 线性最小二乘法 43 2.8.2 多项式最小二乘法 44 2.9 本章小结 45 2.10 练习题 46 第3章 链表 48 3.1 基本概念 48 3.2 单向链表 49 3.2.1 遍历链表 49 3.2.2 查找节点 49 3.2.3 使用哨兵 50 3.2.4 在顶部添加节点 51 3.2.5 在尾部添加节点 51 3.2.6 在指定节点后插入节点 52 3.2.7 删除节点 52 3.3 双向链表 53 3.4 有序链表 54 3.5 自组织链表 55 3.5.1 前移方法 56 3.5.2 交换方法 56 3.5.3 计数方法 56 3.5.4 混合方法 56 3.5.5 伪代码 57 3.6 链表算法 57 3.6.1 复制链表 58 3.6.2 插入排序 58 3.6.3 选择排序 60 3.7 多线链表 61 3.8 循环链表 61 3.8.1 标记节点 62 3.8.2 使用哈希表 63 3.8.3 链表回溯 64 3.8.4 链表反转 65 3.8.5 龟兔赛跑算法 66 3.8.6 双向链表中的环路 68 3.9 本章小结 68 3.10 练习题 68 第4章 数组 70 4.1 基本概念 70 4.2 一维数组 72 4.2.1 查找数组元素 72 4.2.2 查找最大值、最小值和平均值 72 4.2.3 查找中值 73 4.2.4 查找众数 74 4.2.5 插入数组元素 76 4.2.6 删除数组元素 77 4.3 非零数组下界 77 4.3.1 二维数组 78 4.3.2 高维数组 78 4.4 三角形数组 81 4.5 稀疏数组 83 4.5.1 查找行或列 84 4.5.2 获取元素的值 85 4.5.3 设置元素的值 86 4.5.4 删除数组元素 87 4.6 矩阵 89 4.7 本章小结 91 4.8 练习题 91 第5章 堆栈和队列 93 5.1 堆栈 93 5.1.1 链表堆栈 94 5.1.2 数组堆栈 95 5.1.3 双堆栈 96 5.1.4 堆栈算法 97 5.2 队列 101 5.2.1 链表队列 101 5.2.2 数组队列 102 5.2.3 特殊队列 104 5.3 二项堆 105 5.3.1 二项树的定义 105 5.3.2 二项堆的定义 106 5.3.3 合并树 107 5.3.4 合并堆 108 5.3.5 入队操作 111 5.3.6 出队操作 111 5.3.7 运行时间分析 112 5.4 本章小结 113 5.5 练习题 113 第6章 排序 115 6.1 O(N 2)算法 115 6.1.1 数组的插入排序算法 115 6.1.2 数组的选择排序算法 116 6.1.3 冒泡排序算法 117 6.2 O(NlogN)算法 119 6.2.1 堆排序算法 120 6.2.2 快速排序算法 124 6.2.3 合并排序算法 130 6.3 小于O(NlogN)的算法 132 6.3.1 计数排序算法 132 6.3.2 鸽巢排序算法 133 6.3.3 桶排序算法 135 6.4 本章小结 136 6.5 练习题 137 第7章 查找 139 7.1 线性查找算法 139 7.2 二分查找算法 140 7.3 插值查找算法 141 7.4 多数投票算法 142 7.5 本章小结 143 7.6 练习题 144 第8章 哈希表 145 8.1 哈希表的基本概念 145 8.2 链接哈希表 146 8.3 开放寻址哈希表 147 8.3.1 删除数据项 148 8.3.2 线性探测 149 8.3.3 二次探测 150 8.3.4 伪随机探测 151 8.3.5 双重哈希 151 8.3.6 有序哈希 152 8.4 本章小结 154 8.5 练习题 154 第9章 递归 156 9.1 基本算法 156 9.1.1 阶乘 156 9.1.2 斐波那契数 158 9.1.3 棒料切割问题 159 9.1.4 汉诺塔 161 9.2 图形算法 163 9.2.1 科赫曲线 163 9.2.2 希尔伯特曲线 165 9.2.3 谢尔宾斯基曲线 166 9.2.4 垫圈图案 168 9.2.5 天际线问题 168 9.3 回溯算法 172 9.3.1 八皇后问题 173 9.3.2 骑士巡游问题 175 9.4 组合与排列 177 9.4.1 基于循环的组合 178 9.4.2 允许重复项的组合 179 9.4.3 不允许重复项的组合 180 9.4.4 允许重复项的排列 181 9.4.5 不允许重复项的排列 182 9.4.6 轮询调度算法 183 9.5 递归的删除 188 9.5.1 尾部递归的删除 188 9.5.2 动态规划 189 9.5.3 自底向上编程 190 9.5.4 删除递归的通用方法 191 9.6 本章小结 193 9.7 练习题 194 第10章 树 196 10.1 有关树的术语 196 10.2 二叉树的性质 198 10.3 树的表示 200 10.3.1 构建常规树 200 10.3.2 构建完全树 203 10.4 树的遍历 203 10.4.1 前序遍历 204 10.4.2 中序遍历 206 10.4.3 后序遍历 206 10.4.4 广度优先遍历 207 10.4.5 遍历的应用 207 10.4.6 遍历的运行时间分析 208 10.5 有序树 208 10.5.1 添加节点 209 10.5.2 查找节点 210 10.5.3 删除节点 211 10.6 最小共同祖先 212 10.6.1 在有序树中查找最小共同祖先 212 10.6.2 使用指向父节点的指针 213 10.6.3 使用指向父节点的指针和深度字段 214 10.6.4 常规树 214 10.6.5 欧拉环游 216 10.6.6 所有节点对的最小共同祖先 217 10.7 线索树 217 10.7.1 构建线索树 218 10.7.2 线索树的应用 220 10.8 特殊的树算法 221 10.8.1 动物游戏 221 10.8.2 表达式求值 223 10.9 区间树 224 10.9.1 构建区间树 225 10.9.2 与点相交 226 10.9.3 与区间相交 226 10.9.4 四叉树 228 10.9.5 字符串树 231 10.10 本章小结 235 10.11 练习题 235 第11章 平衡树 239 11.1 AVL树 239 11.1.1 添加值 239 11.1.2 删除值 240 11.2 2-3树 241 11.2.1 添加值 242 11.2.2 删除值 242 11.3 B树 244 11.3.1 添加值 245 11.3.2 删除值 245 11.4 平衡树的变种 246 11.4.1 自顶向下的B树 246 11.4.2 B+树 247 11.5 本章小结 248 11.6 练习题 248 第12章 决策树 250 12.1 搜索博弈树 250 12.1.1 极小极大算法 251 12.1.2 初始移动和响应 254 12.1.3 博弈树启发式算法 254 12.2 搜索常规决策树 255 12.2.1 优化问题 256 12.2.2 穷举搜索 257 12.2.3 分支定界搜索 258 12.2.4 决策树启发式算法 259 12.2.5 其他决策树问题 264 12.3 群集智能 267 12.3.1 蚁群优化算法 268 12.3.2 蜂群算法 268 12.3.3 群集仿真 269 12.4 本章小结 270 12.5 练习题 271 第13章 基本网络算法 274 13.1 有关网络的术语 274 13.2 网络的表示 276 13.3 遍历 278 13.3.1 深度优先遍历 278 13.3.2 广度优先遍历 280 13.3.3 连通性测试 281 13.3.4 生成树 282 13.3.5 最小生成树 283 13.3.6 欧几里得最小生成树 284 13.3.7 构建迷宫 284 13.4 强连通组件 285 13.4.1 Kosaraju算法 285 13.4.2 关于Kosaraju算法的讨论 286 13.5 查找路径 288 13.5.1 查找任意路径 288 13.5.2 标签设置最短路径 289 13.5.3 标签修正最短路径 291 13.5.4 所有节点对的最短路径 292 13.6 传递性 295 13.6.1 传递闭包 295 13.6.2 传递归约 296 13.7 最短路径算法的改进 298 13.7.1 形状点 298 13.7.2 提前终止 299 13.7.3 双向搜索 299 13.7.4 最佳优先搜索 299 13.7.5 转弯惩罚和禁行 299 13.8 本章小结 302 13.9 练习题 302 第14章 高级网络算法 304 14.1 拓扑排序 304 14.2 回路检测 306 14.3 地图着色 307 14.3.1 双色地图 307 14.3.2 三色地图 308 14.3.3 四色地图 309 14.3.4 五色地图 309 14.3.5 其他地图着色算法 312 14.4 最大流量 312 14.4.1 工作分配 314 14.4.2 最小流量切割 314 14.5 网络克隆 316 14.5.1 字典 316 14.5.2 克隆引用 317 14.6 节点团 318 14.6.1 暴力破解方法 318 14.6.2 Bron-Kerbosch算法 319 14.6.3 查找三角形节点团 323 14.7 社区检测 324 14.7.1 极大节点团 325 14.7.2 Girvan-Newman算法 325 14.7.3 派系过滤法 326 14.8 欧拉路径和欧拉回路 326 14.8.1 暴力破解方法 327 14.8.2 弗莱里算法 327 14.8.3 Hierholzer算法 327 14.9 本章小结 328 14.10 练习题 329 第15章 字符串算法 331 15.1 匹配括号 331 15.1.1 算术表达式求值 332 15.1.2 构建解析树 332 15.2 模式匹配 333 15.2.1 DFA 333 15.2.2 为正则表达式构建DFA 335 15.2.3 NFA 336 15.3 字符串搜索 337 15.4 计算编辑距离 340 15.5 语音算法 342 15.5.1 Soundex 342 15.5.2 Metaphone 343 15.6 本章小结 344 15.7 练习题 344 第16章 密码学 347 16.1 术语 347 16.2 置换加密算法 348 16.2.1 行/列置换加密算法 348 16.2.2 列置换加密算法 349 16.2.3 路由加密算法 351 16.3 替换加密算法 351 16.3.1 恺撒替换加密算法 351 16.3.2 维吉尼亚加密算法 352 16.3.3 简单替换加密算法 354 16.3.4 一次性便笺加密器 354 16.4 分组加密算法 355 16.4.1 替换-置换网络加密算法 355 16.4.2 菲斯特尔加密算法 356 16.5 公开密钥加密与RSA 357 16.5.1 欧拉函数 358 16.5.2 乘法逆元 358 16.5.3 RSA示例 358 16.5.4 实际考虑 359 16.6 密码学的其他应用场景 359 16.7 本章小结 360 16.8 练习题 360 第17章 计算复杂性理论 362 17.1 标记法 362 17.2 算法复杂性类别 363 17.3 归约 365 17.3.1 3SAT 366 17.3.2 二分图匹配 366 17.4 NP难问题 367 17.5 检测问题、报告问题和优化问题 367 17.5.1 检测问题≤p报告问题 368 17.5.2 报告问题≤p优化问题 368 17.5.3 报告问题≤p检测问题 368 17.5.4 优化问题≤p报告问题 369 17.5.5 近似优化 369 17.6 NP完全问题 369 17.7 本章小结 371 17.8 练习题 372 第18章 分布式算法 374 18.1 并行计算的类型 374 18.1.1 脉动阵列 374 18.1.2 分布式计算 376 18.1.3 多CPU处理 378 18.1.4 竞争条件 378 18.1.5 死锁 381 18.1.6 量子计算 382 18.2 分布式算法 382 18.2.1 调试分布式算法 383 18.2.2 密集并行算法 383 18.2.3 合并排序算法 384 18.2.4 哲学家就餐问题 385 18.2.5 两个将军问题 387 18.2.6 拜占庭将军问题 388 18.2.7 一致性问题 390 18.2.8 领导选举 393 18.2.9 快照技术 393 18.2.10 时钟同步 394 18.3 本章小结 395 18.4 练习题 395 第19章 面试难题 397 19.1 面试官提出面试难题 398 19.2 应聘者回答面试难题 399 19.3 本章小结 402 19.4 练习题 403 附录 练习题参考答案 ---------------------------数据结构与算法：Python语言实现--------------------------- 出版者的话 译者序 前言 致谢 作者简介 第1章 Python入门 1 1.1 Python概述 1 1.1.1 Python解释器 1 1.1.2 Python程序预览 1 1.2 Python对象 2 1.2.1 标识符、对象和赋值语句 2 1.2.2 创建和使用对象 4 1.2.3 Python的内置类 4 1.3 表达式、运算符和优先级 8 1.4 控制流程 12 1.4.1 条件语句 12 1.4.2 循环语句 14 1.5 函数 16 1.5.1 信息传递 17 1.5.2 Python的内置函数 19 1.6 简单的输入和输出 20 1.6.1 控制台输入和输出 21 1.6.2 文件 21 1.7 异常处理 22 1.7.1 抛出异常 23 1.7.2 捕捉异常 24 1.8 迭代器和生成器 26 1.9 Python的其他便利特点 28 1.9.1 条件表达式 29 1.9.2 解析语法 29 1.9.3 序列类型的打包和解包 30 1.10 作用域和命名空间 31 1.11 模块和import语句 32 1.12 练习 34 扩展阅读 36 第2章 面向对象编程 37 2.1 目标、原则和模式 37 2.1.1 面向对象的设计目标 37 2.1.2 面向对象的设计原则 38 2.1.3 设计模式 39 2.2 软件开发 40 2.2.1 设计 40 2.2.2 伪代码 41 2.2.3 编码风格和文档 42 2.2.4 测试和调试 43 2.3 类定义 44 2.3.1 例子：CreditCard类 45 2.3.2 运算符重载和Python的特殊方法 48 2.3.3 例子：多维向量类 50 2.3.4 迭代器 51 2.3.5 例子：Range类 52 2.4 继承 53 2.4.1 扩展CreditCard类 54 2.4.2 数列的层次图 57 2.4.3 抽象基类 60 2.5 命名空间和面向对象 62 2.5.1 实例和类命名空间 62 2.5.2 名称解析和动态调度 65 2.6 深拷贝和浅拷贝 65 2.7 练习 67 扩展阅读 70 第3章 算法分析 71 3.1 实验研究 71 3.2 本书使用的7种函数 74 3.2.1 常数函数 74 3.2.2 对数函数 74 3.2.3 线性函数 75 3.2.4 n-log-n函数 75 3.2.5 二次函数 76 3.2.6 三次函数和其他多项式 77 3.2.7 指数函数 77 3.2.8 比较增长率 79 3.3 渐近分析 79 3.3.1 大O符号 80 3.3.2 比较分析 82 3.3.3 算法分析示例 84 3.4 简单的证明技术 89 3.4.1 示例 89 3.4.2 反证法 89 3.4.3 归纳和循环不变量 90 3.5 练习 91 扩展阅读 95 第4章 递归 96 4.1 说明性的例子 96 4.1.1 阶乘函数 96 4.1.2 绘制英式标尺 97 4.1.3 二分查找 99 4.1.4 文件系统 101 4.2 分析递归算法 104 4.3 递归算法的不足 106 4.4 递归的其他例子 109 4.4.1 线性递归 109 4.4.2 二路递归 112 4.4.3 多重递归 113 4.5 设计递归算法 114 4.6 消除尾递归 115 4.7 练习 116 扩展阅读 118 第5章 基于数组的序列 119 5.1 Python序列类型 119 5.2 低层次数组 119 5.2.1 引用数组 121 5.2.2 Python中的紧凑数组 122 5.3 动态数组和摊销 124 5.3.1 实现动态数组 126 5.3.2 动态数组的摊销分析 127 5.3.3 Python列表类 130 5.4 Python序列类型的效率 130 5.4.1 Python的列表和元组类 130 5.4.2 Python的字符串类 134 5.5 使用基于数组的序列 136 5.5.1 为游戏存储高分 136 5.5.2 为序列排序 138 5.5.3 简单密码技术 140 5.6 多维数据集 142 5.7 练习 145 扩展阅读 147 第6章 栈、队列和双端队列 148 6.1 栈 148 6.1.1 栈的抽象数据类型 148 6.1.2 简单的基于数组的栈实现 149 6.1.3 使用栈实现数据的逆置 152 6.1.4 括号和HTML标记匹配 152 6.2 队列 155 6.2.1 队列的抽象数据类型 155 6.2.2 基于数组的队列实现 156 6.3 双端队列 160 6.3.1 双端队列的抽象数据类型 160 6.3.2 使用环形数组实现双端队列 161 6.3.3 Python collections模块中的双端队列 162 6.4 练习 163 扩展阅读 165 第7章 链表 166 7.1 单向链表 166 7.1.1 用单向链表实现栈 169 7.1.2 用单向链表实现队列 171 7.2 循环链表 173 7.2.1 轮转调度 173 7.2.2 用循环链表实现队列 174 7.3 双向链表 175 7.3.1 双向链表的基本实现 177 7.3.2 用双向链表实现双端队列 179 7.4 位置列表的抽象数据类型 180 7.4.1 含位置信息的列表抽象数据类型 182 7.4.2 双向链表实现 183 7.5 位置列表的排序 186 7.6 案例研究：维护访问频率 186 7.6.1 使用有序表 187 7.6.2 启发式动态调整列表 188 7.7 基于链接的序列与基于数组的序列 190 7.8 练习 192 扩展阅读 195 第8章 树 196 8.1 树的基本概念 196 8.1.1 树的定义和属性 196 8.1.2 树的抽象数据类型 199 8.1.3 计算深度和高度 201 8.2 二叉树 203 8.2.1 二叉树的抽象数据类型 204 8.2.2 二叉树的属性 206 8.3 树的实现 207 8.3.1 二叉树的链式存储结构 207 8.3.2 基于数组表示的二叉树 212 8.3.3 一般树的链式存储结构 214 8.4 树的遍历算法 214 8.4.1 树的先序和后序遍历 214 8.4.2 树的广度优先遍历 216 8.4.3 二叉树的中序遍历 216 8.4.4 用Python实现树遍历 217 8.4.5 树遍历的应用 220 8.4.6 欧拉图和模板方法模式* 223 8.5 案例研究：表达式树 227 8.6 练习 230 扩展阅读 235 第9章 优先级队列 236 9.1 优先级队列的抽象数据类型 236 9.1.1 优先级 236 9.1.2 优先级队列的抽象数据类型的实现 236 9.2 优先级队列的实现 237 9.2.1 组合设计模式 237 9.2.2 使用未排序列表实现优先级队列 238 9.2.3 使用排序列表实现优先级队列 239 9.3 堆 241 9.3.1 堆的数据结构 241 9.3.2 使用堆实现优先级队列 242 9.3.3 基于数组的完全二叉树表示 244 9.3.4 Python的堆实现 246 9.3.5 基于堆的优先级队列的分析 248 9.3.6 自底向上构建堆* 248 9.3.7 Python的heapq模块 251 9.4 使用优先级队列排序 252 9.4.1 选择排序和插入排序 253 9.4.2 堆排序 254 9.5 适应性优先级队列 255 9.5.1 定位器 256 9.5.2 适应性优先级队列的实现 256 9.6 练习 259 扩展阅读 263 第10章 映射、哈希表和跳跃表 264 10.1 映射和字典 264 10.1.1 映射的抽象数据类型 264 10.1.2 应用：单词频率统计 266 10.1.3 Python的MutableMapping抽象基类 267 10.1.4 我们的MapBase类 267 10.1.5 简单的非有序映射实现 268 10.2 哈希表 269 10.2.1 哈希函数 270 10.2.2 哈希码 271 10.2.3 压缩函数 274 10.2.4 冲突处理方案 274 10.2.5 负载因子、重新哈希和效率 276 10.2.6 Python哈希表的实现 278 10.3 有序映射 281 10.3.1 排序检索表 282 10.3.2 有序映射的两种应用 286 10.4 跳跃表 288 10.4.1 跳跃表中的查找和更新操作 289 10.4.2 跳跃表的概率分析* 292 10.5 集合、多集和多映射 294 10.5.1 集合的抽象数据类型 294 10.5.2 Python的MutableSet抽象基类 295 10.5.3 集合、多集和多映射的实现 297 10.6 练习 298 扩展阅读 302 第11章 搜索树 303 11.1 二叉搜索树 303 11.1.1 遍历二叉搜索树 303 11.1.2 搜索 305 11.1.3 插入和删除 306 11.1.4 Python实现 307 11.1.5 二叉搜索树的性能 311 11.2 平衡搜索树 312 11.3 AVL树 316 11.3.1 更新操作 318 11.3.2 Python实现 320 11.4 伸展树 322 11.4.1 伸展 322 11.4.2 何时进行伸展 323 11.4.3 Python实现 324 11.4.4 伸展树的摊销分析* 325 11.5 （2，4）树 328 11.5.1 多路搜索树 328 11.5.2 （2，4）树的操作 330 11.6 红黑树 334 11.6.1 红黑树的操作 335 11.6.2 Python实现 341 11.7 练习 343 扩展阅读 348 第12章 排序与选择 349 12.1 为什么要学习排序算法 349 12.2 归并排序 349 12.2.1 分治法 349 12.2.2 基于数组的归并排序的实现 351 12.2.3 归并排序的运行时间 353 12.2.4 归并排序与递归方程* 354 12.2.5 归并排序的可选实现 355 12.3 快速排序 357 12.3.1 随机快速排序 361 12.3.2 快速排序的额外优化 362 12.4 再论排序：算法视角 364 12.4.1 排序下界 365 12.4.2 线性时间排序：桶排序和基数排序 366 12.5 排序算法的比较 367 12.6 Python的内置排序函数 369 12.7 选择 370 12.7.1 剪枝搜索 370 12.7.2 随机快速选择 371 12.7.3 随机快速选择分析 371 12.8 练习 372 扩展阅读 376 第13章 文本处理 377 13.1 数字化文本的多样性 377 13.2 模式匹配算法 378 13.2.1 穷举 378 13.2.2 Boyer-Moore算法 379 13.2.3 Knuth-Morris-Pratt算法 382 13.3 动态规划 385 13.3.1 矩阵链乘积 385 13.3.2 DNA和文本序列比对 386 13.4 文本压缩和贪心算法 389 13.4.1 霍夫曼编码算法 390 13.4.2 贪心算法 391 13.5 字典树 391 13.5.1 标准字典树 391 13.5.2 压缩字典树 394 13.5.3 后缀字典树 395 13.5.4 搜索引擎索引 396 13.6 练习 397 拓展阅读 400 第14章 图算法 401 14.1 图 401 14.2 图的数据结构 405 14.2.1 边列表结构 406 14.2.2 邻接列表结构 407 14.2.3 邻接图结构 408 14.2.4 邻接矩阵结构 409 14.2.5 Python实现 409 14.3 图遍历 412 14.3.1 深度优先搜索 413 14.3.2 深度优先搜索的实现和扩展 416 14.3.3 广度优先搜索 419 14.4 传递闭包 421 14.5 有向非循环图 424 14.6 最短路径 426 14.6.1 加权图 427 14.6.2 Dijkstra算法 428 14.7 最小生成树 434 14.7.1 Prim-Jarník算法 435 14.7.2 Kruskal算法 438 14.7.3 不相交分区和联合查找结构 442 14.8 练习 445 扩展阅读 451 第15章 内存管理和B树 452 15.1 内存管理 452 15.1.1 内存分配 452 15.1.2 垃圾回收 453 15.1.3 Python解释器使用的额外内存 455 15.2 存储器层次结构和缓存 456 15.2.1 存储器系统 456 15.2.2 高速缓存策略 456 15.3 外部搜索和B树 460 15.3.1 （a，b）树 460 15.3.2 B树 462 15.4 外部存储器中的排序 462 15.5 练习 464 拓展阅读 465 附录A Python中的字符串 466 附录B 有用的数学定理 469 参考文献 474 |