第1章 绪论 1
1.1计算机与算法 2
1.1.1古埃及人的绳索 2
1.1.2欧几里得的尺规 3
1.1.3起泡排序 4
1.1.4算法 5
1.1.5算法效率 7
1.2复杂度度量 8
1.2.1时间复杂度 8
1.2.2渐进复杂度 9
1.2.3空间复杂度 11
1.3复杂度分析 11
1.3.1常数σ（1） 12
1.3.2对数σ（logn） 12
1.3.3线性σ（n） 13
1.3.4多项式σ（polynomial（n）） 14
1.3.5指数σ（2 n） 14
1.3.6复杂度层次 15
1.3.7输入规模 16
1.4递归 16
1.4.1线性递归 17
1.4.2递归分析 17
1.4.3递归模式 19
1.4.4递归消除 22
1.4.5二分递归 23
1.5抽象数据类型 26
习题 26
第2章 向量 31
2.1从数组到向量 32
2.1.1数组 32
2.1.2向量 33
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有序向量 48
2.6.1比较器 48
2.6.2有序性甄别 49
2.6.3唯一化 49
2.6.4查找 51
2.6.5二分查找（版本A） 52
2.6.6 Fibonacci查找 55
2.6.7二分查找（版本B） 58
2.6.8二分查找（版本C） 59
2.7排序与下界 60
2.7.1有序性 60
2.7.2排序及其分类 60
2.7.3下界 61
2.7.4比较树 62
2.7.5估计下界 62
2.8排序器 63
2.8.1统一入口 63
2.8.2起泡排序 64
2.8.3归并排序 65
习题 68
第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插入 80
3.3.6基于复制的构造 82
3.3.7删除 83
3.3.8析构 84
3.3.9唯一化 84
3.3.10遍历 85
3.4有序列表 85
3.4.1唯一化 85
3.4.2查找 86
3.5排序器 86
3.5.1统一入口 86
3.5.2插入排序 87
3.5.3选择排序 88
3.5.4归并排序 89
习题 91
第4章 栈与队列 93
4.1栈 94
4.1.1 ADT接口 94
4.1.2操作实例 95
4.1.3 Stack模板类 95
4.2栈与递归 96
4.2.1递归的实现 96
4.2.2避免递归 98
4.3典型应用 99
4.3.1逆序输出 99
4.3.2递归嵌套 100
4.3.3延迟缓冲 103
4.3.4逆波兰表达式 107
4.4试探回溯法 110
4.4.1试探与回溯 110
4.4.2八皇后 111
4.4.3迷宫寻径 113
4.5队列 116
4.5.1概述 116
4.5.2 ADT接口 116
4.5.3操作实例 117
4.5.4 Queue模板类 117
4.6队列应用 117
4.6.1循环分配器 117
4.6.2银行服务模拟 118
习题 119
第5章 二叉树 123
5.1二叉树及其表示 124
5.1.1树 124
5.1.2二叉树 125
5.1.3多叉树 126
5.2编码树 128
5.2.1二进制编码 128
5.2.2二叉编码树 130
5.3二叉树的实现 131
5.3.1二叉树节点 131
5.3.2二叉树节点操作接口 133
5.3.3二叉树 134
5.4Huffman编码 138
5.4.1 PFC编码及解码 138
5.4.2最优编码树 141
5.4.3 Huff man编码树 143
5.4.4 Huffman编码算法 145
5.5遍历 151
5.5.1递归式遍历 151
5.5.2迭代版先序遍历 153
5.5.3迭代版中序遍历 155
5.5.4迭代版后序遍历 159
5.5.5层次遍历 161
习题 162
第6章 图 165
6.1概述 166
6.2抽象数据类型 169
6.2.1操作接口 169
6.2.2 Graph模板类 169
6.3邻接矩阵 171
6.3.1原理 171
6.3.2实现 171
6.3.3时间性能 173
6.3.4空间性能 173
6.4邻接表 174
6.4.1原理 174
6.4.2复杂度 174
6.5图遍历算法概述 175
6.6广度优先搜索 175
6.6.1策略 175
6.6.2实现 176
6.6.3实例 177
6.6.4复杂度 177
6.6.5应用 177
6.7深度优先搜索 178
6.7.1策略 178
6.7.2实现 178
6.7.3实例 179
6.7.4复杂度 181
6.7.5应用 181
6.8拓扑排序 181
6.8.1应用 181
6.8.2有向无环图 182
6.8.3算法 182
6.8.4实现 183
6.8.5实例 184
6.8.6复杂度 184
6.9双连通域分解 184
6.9.1关节点与双连通域 184
6.9.2蛮力算法 185
6.9.3算法 185
6.9.4实现 186
6.9.5实例 187
6.9.6复杂度 188
6.10优先级搜索 188
6.10.1优先级与优先级数 188
6.10.2基本框架 189
6.10.3复杂度 189
6.11最小支撑树 190
6.11.1支撑树 190
6.11.2最小支撑树 190
6.11.3歧义性 190
6.11.4蛮力算法 191
6.11.5 Prim算法 191
6.12最短路径 193
6.12.1最短路径树 193
6.12.2歧义性 194
6.12.3 Dijkstra算法 194
习题 196
第7章 搜索树 199
7.1查找 201
7.1.1循关键码访问 201
7.1.2词条 201
7.1.3序与比较器 201
7.2二叉搜索树 202
7.2.1顺序性 202
7.2.2中序遍历序列 202
7.2.3 BST模板类 203
7.2.4查找算法及其实现 203
7.2.5插入算法及其实现 205
7.2.6删除算法及其实现 206
7.3平衡二叉搜索树 208
7.3.1树高与性能 208
7.3.2理想平衡与适度平衡 209
7.3.3等价二叉搜索树 210
7.3.4等价变换与局部调整 210
7.4 AVL树 211
7.4.1定义及性质 211
7.4.2节点插入 213
7.4.3节点删除 215
7.4.4统一重平衡算法 217
习题 219
第8章 高级搜索树 221
8.1伸展树 222
8.1.1局部性 222
8.1.2逐层伸展 223
8.1.3双层伸展 224
8.1.4分摊分析 226
8.1.5伸展树的实现 228
8.2 B-树 232
8.2.1多路平衡查找 232
8.2.2 ADT接口及其实现 235
8.2.3关键码查找 236
8.2.4性能分析 238
8.2.5关键码插入 239
8.2.6上溢与分裂 239
8.2.7关键码删除 242
8.2.8下溢与合并 243
8.3红黑树 247
8.3.1概述 248
8.3.2红黑树接口定义 250
8.3.3节点插入算法 251
8.3.4节点删除算法 254
8.4 kd-树 259
8.4.1范围查询 259
8.4.2 kd-树 262
8.4.3基于2d-树的范围查询 263
习题 265
第9章 词典 269
9.1词典ADT 271
9.1.1操作接口 271
9.1.2操作实例 271
9.1.3接口定义 272
9.1.4实现方法 272
9.2跳转表 273
9.2.1 Skiplist模板类 273
9.2.2总体逻辑结构 274
9.2.3四联表 274
9.2.4查找 276
9.2.5空间复杂度 277
9.2.6时间复杂度 278
9.2.7插入 279
9.2.8删除 282
9.3散列表 283
9.3.1完美散列 283
9.3.2装填因子与空间利用率 284
9.3.3散列函数 285
9.3.4散列表 289
9.3.5冲突及其排解 290
9.3.6闭散列策略 292
9.3.7查找与删除 295
9.3.8插入 296
9.3.9更多闭散列策略 297
9.3.10散列码转换 299
9.4散列应用 301
9.4.1桶排序 301
9.4.2最大间隙 302
9.4.3基数排序 303
习题 304
第10章 优先级队列 309
10.1优先级队列ADT 310
10.1.1优先级与优先级队列 310
10.1.2关键码、比较器与偏序关系 311
10.1.3操作接口 311
10.1.4操作实例：选择排序 311
10.1.5接口定义 312
10.1.6应用实例：Huffman编码树 312
10.2堆 314
10.2.1完全二叉堆 314
10.2.2元素插入 317
10.2.3元素删除 319
10.2.4建堆 321
10.2.5就地堆排序 323
10.3左式堆 325
10.3.1堆合并 325
10.3.2单侧倾斜 326
10.3.3 PQ_LeftHeap模板类 326
10.3.4空节点路径长度 327
10.3.5左倾性与左式堆 327
10.3.6右侧链 328
10.3.7合并算法 328
10.3.8实例 328
10.3.9合并操作merge（）的实现 329
10.3.10复杂度 330
10.3.11基于合并的插入和删除 330
习题 331
第11章 串 335
11.1串及串匹配 336
11.1.1串 336
11.1.2串匹配 337
11.1.3测评标准与策略 338
11.2蛮力算法 339
11.2.1算法描述 339
11.2.2算法实现 339
11.2.3时间复杂度 340
11.3 KMP算法 341
11.3.1构思 341
11.3.2 next表 342
11.3.3 KMP算法 342
11.3.4 next［0］=-1 343
11.3.5 next［j+1］ 343
11.3.6构造next表 344
11.3.7性能分析 344
11.3.8继续改进 345
11.4 BM算法 347
11.4.1思路与框架 347
11.4.2坏字符策略 348
11.4.3好后缀策略 351
11.4.4 GS［］表构造算法 353
11.4.5算法纵览 356
11.5 Karp-Rabin算法 357
11.5.1构思 357
11.5.2算法与实现 357
习题 361
第12章 排序 363
12.1快速排序 364
12.1.1分治策略 364
12.1.2轴点 364
12.1.3快速排序算法 365
12.1.4快速划分算法 365
12.1.5复杂度 368
12.1.6应对退化 369
12.2选取与中位数 371
12.2.1概述 371
12.2.2主流数 372
12.2.3归并向量的中位数 373
12.2.4基于优先级队列的选取 376
12.2.5基于快速划分的选取 377
12.2.6 k-选取算法 378
12.3希尔排序 380
12.3.1递减增量策略 380
12.3.2增量序列 382
习题 385
附录 387
参考文献 388
插图索引 391
表格索引 398
算法索引 399
代码索引 400
关键词索引 406