目录 1
第一章 算法的设计与分析 1
1.1 从问题到程序 1
1.2 抽象数据类型 13
1.3 数据类型、数据结构及抽象数据类型 17
1.4 程序的运行时间 21
1.5 程序运行时间的计算 28
1.6 程序设计的实践 36
1.7 超级Pascal 39
2.1 抽象数据类型“表” 49
第二章 基本的抽象数据类型 49
2.2 表的实现 54
2.3 栈 70
2.4 队 75
2.5 映射 82
2.6 栈与递归过程 86
第三章 树 100
3.1 基本术语 100
3.2 ADT树 109
3.3 树的实现 113
3.4 二叉树 123
4.1 集合 139
第四章 集合上的基本操作 139
4.2 带有UNION，INTERSECTION和DEFFERENCE操作的ADT 142
4.3 用位向量实现集合 147
4.4 用链接表实现集合 149
4.5 字典 154
4.6 实现字典的简单方法 155
4.7 散列表 158
4.8 散列函数效率的估计 167
4.9 抽象数据类型MAPPING的实现 175
4.10 优先队列 176
4.11 优先队列的实现 179
4.12 复杂数据集合的表示 187
第五章 进一步的集合表示法 199
5.1 二叉搜索树 199
5.2 二叉搜索树操作的时间分析 204
5.3 检索树 208
5.4 集合的平衡树表示 215
5.5 具有操作MERGE和FIND的集合 229
5.6 具有操作MERGE和SPLIT的ADT 240
第六章 有向图 250
6.1 基本概念 250
6.2 有向图的表示 251
6.3 单源最短路问题 256
6.4 所有点对之间的最短路问题 261
6.5 有向图的遍历 269
6.6 无圈有向图 274
6.7 强连通分支 278
第七章 无向图 286
7.1 定义 286
7.2 最小耗费生成树 289
7.3 遍历 297
7.4 割点和双连通分支 302
7.5 图匹配 304
第八章 整序 312
8.1 内部整序模型 312
8.2 一些简单的整序算法 313
8.3 快速整序 321
8.4 堆整序 332
8.5 箱整序 337
8.6 通过比较的整序算法的下界 346
8.7 顺序统计量 351
第九章 算法分析技巧 360
9.1 算法的效率 360
9.2 递归程序的分析 361
9.3 递归方程的解法 363
9.4 一类递归方程的解 367
第十章 算法设计技巧 375
10.1 分治法 375
10.2 动态规划 381
10.3 贪婪法 392
10.4 回溯法 396
10.5 局部搜索算法 410
第十一章 利用外存贮器的数据结构与算法 421
11.1 外部计算模型 421
11.2 外部整序 423
11.3 在外存文件中存贮信息 438
11.4 外部搜索树 447
第十二章 存贮器管理 459
12.1 存贮器管理中的一些问题 459
12.2 大小相同的字块的管理 464
12.3 对尺寸相同字块的垃圾收集算法 466
12.4 大小不同的字块的分配 477
12.5 伙伴系统 486
12.6 存贮器紧缩 492
参考文献 500
汉英名词索引 507