第1章 绪论 1
1.1 计算机与算法 2
1.1.1 古埃及人的绳索 2
1.1.2 欧几里德的尺规 3
1.1.3 起泡排序 4
1.1.4 算法 5
1.1.5 算法效率 8
1.2 复杂度度量 8
1.2.1 问题规模、运行时间及时间复杂度 9
1.2.2 渐进复杂度 9
1.2.3 空间复杂度 11
1.3 复杂度分析 12
1.3.1 常数复杂度O（1） 12
1.3.2 对数复杂度O（logn） 13
1.3.3 线性复杂度O（n） 14
1.3.4 多项式复杂度O（polynomial（n）） 15
1.3.5 指数复杂度O（2n） 15
1.3.6 复杂度层次 16
1.3.7 输入规模 16
1.4 递归 17
1.4.1 线性递归 17
1.4.2 递归分析 18
1.4.3 递归模式 20
1.4.4 递归消除 22
1.4.5 二分递归 24
1.5 抽象数据类型 27
习题 28
第2章 向量 31
2.1 从数组到向量 32
2.1.1 数组 32
2.1.2 向量 32
2.2 接口 33
2.2.1 ADT接口 33
2.2.2 操作实例 34
2.2.3 Vector模板类 34
2.3 构造与析构 36
2.3.1 默认构造方法 36
2.3.2 基于复制的构造方法 36
2.3.3 析构方法 37
2.4 动态空间管理 37
2.4.1 静态空间管理 37
2.4.2 可扩充向量 38
2.4.3 扩容 38
2.4.4 分摊分析 39
2.4.5 缩容 40
2.5 向量 41
2.5.1 直接引用元素 41
2.5.2 置乱器 41
2.5.3 判等器与比较器 42
2.5.4 无序查找 43
2.5.5 插入 44
2.5.6 删除 45
2.5.7 唯一化 46
2.5.8 遍历 47
2.6 有序向量 49
2.6.1 比较器 49
2.6.2 有序性甄别 49
2.6.3 唯一化 49
2.6.4 查找 52
2.6.5 二分查找（版本A） 53
2.6.6 Fibonacci查找 56
2.6.7 二分查找（版本B） 59
2.6.8 二分查找（版本C） 60
2.7 排序与下界 61
2.7.1 有序性 61
2.7.2 排序及其分类 62
2.7.3 下界 62
2.7.4 比较树 63
2.7.5 估计下界 64
2.8 排序器 64
2.8.1 统一入口 64
2.8.2 起泡排序 65
2.8.3 归并排序 66
习题 69
第3章 列表 73
3.1 从向量到列表 74
3.1.1 从静态存储到动态存储 74
3.1.2 由秩到位置 75
3.1.3 列表 75
3.2 接口 75
3.2.1 列表节点 75
3.2.2 列表 76
3.3 列表 79
3.3.1 头、尾节点 79
3.3.2 默认构造方法 79
3.3.3 由秩到位置的转换 80
3.3.4 查找 80
3.3.5 插入 81
3.3.6 基于复制的构造 83
3.3.7 删除 84
3.3.8 析构 85
3.3.9 唯一化 86
3.3.10 遍历 86
3.4 有序列表 87
3.4.1 唯一化 87
3.4.2 查找 88
3.5 排序器 88
3.5.1 统一入口 88
3.5.2 插入排序 89
3.5.3 选择排序 91
3.5.4 归并排序 92
习题 94
第4章 栈与队列 97
4.1 栈 98
4.1.1 概述 98
4.1.2 ADT接口 99
4.1.3 操作实例 99
4.1.4 Stack模板类 99
4.2 栈与递归 100
4.2.1 递归的实现 101
4.2.2 避免递归 102
4.3 典型应用 103
4.3.1 逆序输出 103
4.3.2 递归嵌套 105
4.3.3 延迟缓冲 108
4.3.4 逆波兰表达式 113
4.4 试探回溯法 116
4.4.1 试探与回溯 116
4.4.2 八皇后 117
4.4.3 迷宫寻径 119
4.5 队列 122
4.5.1 概述 122
4.5.2 ADT接口 122
4.5.3 操作实例 123
4.5.4 Queue模板类 124
4.6 队列应用 124
4.6.1 循环分配器 124
4.6.2 银行服务模拟 125
习题 126
第5章 二叉树 129
5.1 二叉树及其表示 130
5.1.1 树 130
5.1.2 二叉树 131
5.1.3 多叉树 132
5.2 编码树 134
5.2.1 二进制编码 134
5.2.2 二叉编码树 136
5.3 二叉树的实现 137
5.3.1 二叉树节点 137
5.3.2 二叉树节点操作接口 140
5.3.3 二叉树 141
5.4 Huffman编码 146
5.4.1 PFC编码 146
5.4.2 最优编码树 149
5.4.3 Huffman编码树 152
5.4.4 Huffman编码算法 154
5.5 遍历 160
5.5.1 递归式遍历 161
5.5.2 迭代版先序遍历 163
5.5.3 迭代版中序遍历 165
5.5.4 迭代版后序遍历 169
5.5.5 层次遍历 171
习题 172
第6章 图 175
6.1 概述 176
6.2 抽象数据类型 179
6.2.1 操作接口 179
6.2.2 Graph模板类 180
6.3 邻接矩阵 181
6.3.1 原理 181
6.3.2 实现 182
6.3.3 时间性能 184
6.3.4 空间性能 184
6.4 邻接表 184
6.4.1 原理 184
6.4.2 复杂度 184
6.5 图遍历算法概述 185
6.6 广度优先搜索 186
6.6.1 策略 186
6.6.2 实现 186
6.6.3 实例 187
6.6.4 复杂度 187
6.6.5 应用 188
6.7 深度优先搜索 188
6.7.1 策略 188
6.7.2 实现 189
6.7.3 实例 190
6.7.4 复杂度 191
6.7.5 应用 192
6.8 拓扑排序 192
6.8.1 应用 192
6.8.2 有向无环图 193
6.8.3 算法 193
6.8.4 实现 193
6.8.5 实例 194
6.8.6 复杂度 194
6.9 双连通域分解 195
6.9.1 关节点与双连通域 195
6.9.2 蛮力算法 195
6.9.3 算法 196
6.9.4 实现 196
6.9.5 实例 198
6.9.6 复杂度 199
6.10 优先级搜索 199
6.10.1 优先级与优先级数 199
6.10.2 基本框架 200
6.10.3 复杂度 201
6.11 最小支撑树 201
6.11.1 支撑树 201
6.11.2 最小支撑树 201
6.11.3 歧义性 201
6.11.4 蛮力算法 202
6.11.5 Prim算法 202
6.12 最短路径 204
6.12.1 最短路径树 204
6.12.2 歧义性 205
6.12.3 Dijkstra算法 205
习题 208
第7章 搜索树 211
7.1 搜索 212
7.1.1 循关键码访问 212
7.1.2 词条 213
7.1.3 序与比较器 213
7.2 二叉搜索树 213
7.2.1 顺序性 213
7.2.2 中序遍历序列 214
7.2.3 BST模板类 214
7.2.4 查找算法及其实现 215
7.2.5 插入算法及其实现 217
7.2.6 删除算法及其实现 218
7.3 平衡二叉搜索树 220
7.3.1 树高与性能 220
7.3.2 理想平衡与适度平衡 221
7.3.3 等价二叉搜索树 222
7.3.4 等价变换与局部调整 222
7.4 AVL树 223
7.4.1 AVL树 223
7.4.2 节点插入 225
7.4.3 节点删除 228
7.4.4 统一重平衡算法 230
习题 232
第8章 高级搜索树 235
8.1 伸展树 236
8.1.1 局部性 236
8.1.2 逐层伸展 237
8.1.3 双层伸展 238
8.1.4 分摊分析 240
8.1.5 伸展树的实现 243
8.2 B-树 247
8.2.1 多路平衡搜索 247
8.2.2 ADT接口及其实现 249
8.2.3 关键码查找 251
8.2.4 性能分析 252
8.2.5 关键码插入 253
8.2.6 上溢与分裂 254
8.2.7 关键码删除 257
8.2.8 下溢与合并 258
8.3 红黑树 263
8.3.1 概述 263
8.3.2 红黑树接口定义 265
8.3.3 节点插入算法 266
8.3.4 节点删除算法 269
8.4 kd-树 275
8.4.1 范围查询 275
8.4.2 kd-树 278
8.4.3 基于2d-树的范围查询算法 279
习题 280
第9章 词典 283
9.1 词典 284
9.1.1 操作接口 284
9.1.2 操作实例 285
9.1.3 接口定义 286
9.1.4 判等器 286
9.1.5 实现方法 287
9.2 跳转表 287
9.2.1 Skiplist模板类 287
9.2.2 总体逻辑结构 288
9.2.3 四联表 288
9.2.4 查找 290
9.2.5 空间复杂度 292
9.2.6 时间复杂度 292
9.2.7 插入 293
9.2.8 删除 296
9.3 散列表 298
9.3.1 完美散列 298
9.3.2 装填因子与空间利用率 299
9.3.3 散列函数 300
9.3.4 散列表 303
9.3.5 冲突及其排解 305
9.3.6 开放定址策略 307
9.3.7 查找与删除 309
9.3.8 插入 310
9.3.9 更多开放定址策略 312
9.3.10 散列码转换 314
9.4 散列应用 316
9.4.1 桶排序 316
9.4.2 最大间隙 317
9.4.3 基数排序 318
习题 319
第10章 优先级队列 323
10.1 优先级队列 324
10.1.1 优先级与优先级队列 324
10.1.2 关键码、比较器与偏序关系 325
10.1.3 操作接口 325
10.1.4 操作实例：选择排序 325
10.1.5 接口定义 326
10.1.6 应用实例：Huffman编码树 326
10.2 堆 328
10.2.1 完全二叉堆 329
10.2.2 元素插入 331
10.2.3 元素删除 333
10.2.4 建堆 335
10.2.5 就地堆排序 338
10.3 左式堆 341
10.3.1 堆合并 341
10.3.2 单侧倾斜 341
10.3.3 PQ_LeftHeap模板类 342
10.3.4 空节点路径长度 342
10.3.5 左倾性与左式堆 343
10.3.6 右侧链 343
10.3.7 合并算法 344
10.3.8 合并操作merge（）的实现 344
10.3.9 实例 345
10.3.10 复杂度 345
10.3.11 基于合并的插入和删除操作 346
习题 347
第11章 串 349
11.1 串及串匹配 350
11.1.1 串 350
11.1.2 串匹配 351
11.1.3 测评标准与策略 352
11.2 蛮力算法 353
11.2.1 算法描述 353
11.2.2 算法实现 353
11.2.3 时间复杂度 354
11.3 KMP算法 355
11.3.1 构思 355
11.3.2 next表 356
11.3.3 KMP算法 357
11.3.4 next［0］＝-1 357
11.3.5 构造next表 358
11.3.6 性能分析 358
11.3.7 继续改进 359
11.4 BM算法 361
11.4.1 思路与框架 361
11.4.2 坏字符策略 362
11.4.3 好后缀策略 364
11.4.4 综合性能 368
11.5 Karp-Rabin算法 369
11.5.1 构思 369
11.5.2 算法与实现 370
习题 373
第12章 排序 375
12.1 快速排序 376
12.1.1 分治策略 376
12.1.2 轴点 376
12.1.3 快速排序算法 377
12.1.4 快速划分算法 377
12.1.5 复杂度 379
12.1.6 应对退化 381
12.2 选取与中位数 382
12.2.1 概述 382
12.2.2 主流数 383
12.2.3 归并向量的中位数 385
12.2.4 基于优先级队列的选取 388
12.2.5 基于快速划分的选取 389
12.2.6 k-选取算法 390
12.3 希尔排序 392
12.3.1 递减增量策略 392
12.3.2 增量序列 394
习题 397
附录 399
插图索引 400
表格索引 406
算法索引 407
代码索引 408
关键词索引 414