第一章 绪论 1
第一节 算法的复杂性 1
一、比较两对算法的效率 1
二、复杂性的计量 4
三、复杂性的渐近性态及其阶 7
四、复杂性渐近阶的重要性 10
五、算法复杂性渐近阶的分析 12
六、递归方程解的渐近阶的求法 16
第二节 算法表达中的抽象机制 26
一、从机器语言到高级语言的抽象 26
二、抽象数据类型 30
三、使用抽象数据类型带来的好处 34
四、数据结构、数据类型和抽象数据类型 35
习题 36
第二章 表 40
第一节 ADT表 40
第二节 表的实现 42
一、表的数组实现 42
二、表的指针实现 45
三、表的游标实现 48
四、循环链表 51
五、双链表 52
第三节 栈 54
一、ADT栈 54
二、栈的数组实现 55
三、栈的指针实现 57
第四节 队列 58
一、ADT队列 58
二、用指针实现队列 59
三、用循环数组实现队列 60
第五节 映射 64
一、ADT映射 64
二、用数组实现映射 64
三、用表实现映射 65
习题 67
第三章 串 71
第一节 ADT串 71
第二节 串的实现 72
一、串的数组实现 72
二、串的指针实现 73
三、串的块链表示法 73
四、串的堆结构 74
第三节 模式匹配 75
一、朴素的模式匹配算法 75
二、模式匹配的KMP算法 76
习题 82
第四章 树 84
第一节 树的定义 84
第二节 二叉对 86
第三节 树的遍历 88
第四节 ADT树 90
第五节 树的实现方法 92
一、父亲数组表示法 92
二、儿子链表表示法 93
三、左儿子右兄弟表示法 95
第六节 二叉树的实现及其应用 96
一、二叉树的顺序存储结构 96
二、二叉树的结点度表示法 98
三、二叉树的链式存储结构 98
四、果园或森林的二叉树表示 99
五、线索二叉树 100
六、二叉树的应用 102
习题 104
第五章 集合 108
第一节 以集合为基础的抽象数据类型 108
一、集合的定义和记号 108
二、定义在集合上的基本运算 109
三、集合的简单表示法 109
第二节 字典 113
一、实现字典的简单方法 113
二、用散列表实现字典 114
三、用散列表实现映射 123
第三节 有序字典 124
一、有序字典的定义 125
二、用数组实现有序字典 125
三、有二叉搜索实现有序字典 127
第四节 平衡树 134
一、红黑树 134
二、2—3树 147
第五节 优先队列 156
一、优先队列的定义 156
二、优先队列的字典式实现 157
三、优先级树和堆 160
四、用数组实现堆 161
第六节 并查集 163
一、并查集的定义及其简单实现 163
二、并查集的快速实现 165
三、并查集的树实现 167
第七节 检索树 169
一、检索树与检索树结点 169
二、用数组表示检索树结点 170
三、用链接表表示检索树结点 171
四、检索树的效率 172
习题 173
第六章 算法设计策略与技巧 177
第一节 递归技术与分治法 177
一、递归技术 177
二、分治法的基本思想 181
三、大整数的乘法 182
四、Strassen矩阵乘法 184
五、最接近点对问题 186
六、循环赛日程表 190
第二节 动态规划 191
一、计算矩阵连乘积 191
二、动态规划算法的基本要素 196
三、最长公共子序列 199
四、凸多边形的最优三角剖分 203
第三节 贪心算法 206
一、活动安排问题 206
二、贪心算法的基本要素 209
三、哈夫曼编码 211
四、贪心算法的理论基础 215
第四节 回溯法 220
一、回溯法的一般描述 220
二、n后问题 225
三、子集和问题 227
四、图的m-着色问题 230
五、回溯法的效率分析 233
第五节 限界剪枝法 236
一、最小耗费搜索法 236
二、限界与剪枝 241
三、旅行售贷员问题 245
习题 248
第七章 排序与选择 253
第一节 简单排序算法 253
一、冒泡排序 253
二、插入排序 254
三、选择排序 254
四、简单排序算法的计算复杂性 255
第二节 快速排序 256
一、算法的基本思想及其实现 256
二、快速排序的性能 258
三、随机快速排序算法 258
第三节 堆排序 259
一、堆排序算法的基本思想及其实现 259
二、堆排序算法的计算复杂性 261
第四节 线性时间排序 261
一、计数排序 262
二、桶排序 263
三、基数排序 264
第五节 中位数与第k小元素 267
一、平均情况下的线性时间选择算法 267
二、最坏情况下的线性时间选择算法 269
习题 271
第八章 图 275
第一节 图的基本概念 275
一、图及其相关术语 275
二、抽象数据类型ADT图 277
第二节 图的表示法 278
一、邻接矩阵表示法 278
二、邻接表表示法 279
第三节 图的遍历 281
一、深度优先搜索 281
二、广度优先搜索 283
第四节 图的连通性 284
一、深度优先生成森林 284
二、无圈有向图 285
三、有向图的强连通分支 286
四、无向图的割点和双连通分支 287
第五节 最小生成树 288
一、最小生成树性质 289
二、Prim算法 289
三、Kruskal算法 291
第六节 最短路径 293
一、单源最短路径 293
二、所有顶点对之间的最短路径 295
第七节 图匹配 298
习题 299
第九章 问题的计算复杂性 304
第一节 计算模型 304
一、随机存取机RAM 305
二、随机存取存储程序机RASP 310
三、RAM模型的变形与简化 314
四、图灵机 317
五、图灵机模型与RAM模型的关系 320
第二节 问题的计算时间下界 323
一、问题的输入、输出及平凡下界 323
二、信息论下界 323
三、对手论证方法 324
四、Ben_ Or下界定理 330
五、问题变换与计算复杂性归约 334
第三节 P类与NP类 337
一、非确定性图灵机 338
二、P类与NP类语言 339
三、“证书”与VP类语言 341
四、问题和语言 342
第四节 NP——完全性 343
一、多项式时间变换与NP——完全问题 343
二、Cook定理 344
三、几个典型的NP——完全问题 347
第五节 NP——完全问题的近似解法 357
一、近似算法的性能 358
二、顶点覆盖问题的近似算法 358
三、旅行售货员问题的近似算法 360
四、集合覆盖问题的近似算法 362
五、子集和问题的近似算法 365
习题 369
第十章 并行算法 372
第一节 并行计算模型 372
一、PRAM模型 372
二、同步与控制 374
三、并行算法的表达 374
四、并行算法的性能指标 375
五、运行时间和工作量有效性 375
第二节 并行算法的基本设计技术 376
一、平衡树方法 376
二、指针跳越技术 377
三、欧拉回路技术 380
四、并行分治法 382
五、划分原理 385
六、流水线技术 386
七、接力技术 388
八、递归的并行随机消元法 390
九、确定性破对称技术 393
第三节 EREW算法与CRCW算法的速度比较 398
一、并发读对提高速度的作用 398
二、并发写对提高速度的作用 400
三、CRCW算法速度的上界 401
习题 403
第十一章 高级专题 406
第一节 算法的分摊时间分析 406
一、累计方法 407
二、记帐方法 409
三、势能方法 410
四、自适应二叉搜索树 412
第二节 可并优先队列 418
一、可并优先队列的定义 418
二、用二项堆实现可并优先队列 419
三、用Fibonacci堆实现可并优先队列 430
第三节 数据结构的扩充与联合 442
一、动态选择树——红黑树的扩充 442
二、数据结构扩充的方法 446
三、区间树 447
四、数据结构的联合 451
第四节 静态数据结构的动态化方法 452
一、可分解搜索问题 453
二、静态数据结构的半动态化 454
三、静态数据结构的另一种半动态化方法 458
四、静态数据结构的全动态变换 460
五、其他动态化方法 461
习题 462
参考文献 465