第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常数0（1） 12
1.3.2对数0（logn） 12
1.3.3线性0（n） 13
1.3.4多项式0（polynomial（n）） 14
1.3.5指数0（2n） 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递归消除 21
1.4.5二分递归 22
1.5抽象数据类型 26
第2章 向量 27
2.1从数组到向量 28
2.1.1数组 28
2.1.2向量 29
2.2接口 29
2.2.1 ADT接口 29
2.2.2操作实例 30
2.2.3 Vector模板类 30
2.3构造与析构 32
2.3.1默认构造方法 32
2.3.2基于复制的构造方法 32
2.3.3析构方法 33
2.4动态空间管理 33
2.4.1静态空间管理 33
2.4.2可扩充向量 34
2.4.3扩容 34
2.4.4分摊分析 35
2.4.5缩容 36
2.5常规向量 37
2.5.1直接引用元素 37
2.5.2置乱器 37
2.5.3判等器与比较器 38
2.5.4无序查找 39
2.5.5插入 40
2.5.6删除 40
2.5.7唯一化 42
2.5.8遍历 43
2.6有序向量 44
2.6.1比较器 44
2.6.2有序性甄别 44
2.6.3唯一化 45
2.6.4查找 47
2.6.5二分查找（版本A） 48
2.6.6 Fibonacci查找 52
2.6.7二分查找（版本B） 54
2.6.8二分查找（版本C） 56
2.7排序与下界 57
2.7.1有序性 57
2.7.2排序及其分类 57
2.7.3下界 57
2.7.4比较树 58
2.7.5估计下界 59
2.8排序器 59
2.8.1统一入口 59
2.8.2起泡排序 60
2.8.3归并排序 61
第3章 列表 65
3.1从向量到列表 66
3.1.1从静态到动态 66
3.1.2由秩到位置 67
3.1.3列表 67
3.2接口 67
3.2.1列表节点 67
3.2.2列表 68
3.3列表 71
3.3.1头、尾节点 71
3.3.2默认构造方法 71
3.3.3由秩到位置的转换 72
3.3.4查找 72
3.3.5插入 72
3.3.6基于复制的构造 74
3.3.7删除 75
3.3.8析构 76
3.3.9唯一化 76
3.3.10遍历 77
3.4有序列表 77
3.4.1唯一化 77
3.4.2查找 78
3.5排序器 78
3.5.1统一入口 78
3.5.2插入排序 79
3.5.3选择排序 80
3.5.4归并排序 82
第4章 栈与队列 85
4.1栈 86
4.1.1 ADT接口 86
4.1.2操作实例 87
4.1.3 Stack模板类 88
4.2栈与递归 88
4.2.1函数调用栈 88
4.2.2避免递归 89
4.3栈的典型应用 90
4.3.1逆序输出 90
4.3.2递归嵌套 91
4.3.3延迟缓冲 94
4.3.4逆波兰表达式 96
4.4试探回溯法 99
4.4.1试探与回溯 99
4.4.2八皇后 100
4.4.3迷宫寻径 102
4.5队列 105
4.5.1概述 105
4.5.2 ADT接口 105
4.5.3操作实例 106
4.5.4 Queue模板类 106
4.6队列应用 107
4.6.1循环分配器 107
4.6.2银行服务模拟 107
第5章 二叉树 109
5.1二叉树及其表示 110
5.1.1树 110
5.1.2二叉树 111
5.1.3多叉树 112
5.2编码树 114
5.2.1二进制编码 114
5.2.2二叉编码树 116
5.3二叉树的实现 117
5.3.1二叉树节点 117
5.3.2二叉树节点操作接口 119
5.3.3二叉树 120
5.4遍历 124
5.4.1递归式遍历 124
5.4.2迭代版先序遍历 126
5.4.3迭代版中序遍历 128
5.4.4迭代版后序遍历 132
5.4.5层次遍历 133
5.5 Huffman编码 136
5.5.1 PFC编码及解码 136
5.5.2最优编码树 139
5.5.3 Huffman编码树 141
5.5.4 Huffman编码算法 143
第6章 图 149
6.1概述 150
6.2抽象数据类型 153
6.2.1操作接口 153
6.2.2 Graph模板类 153
6.3邻接矩阵 155
6.3.1原理 155
6.3.2实现 155
6.3.3时间性能 157
6.3.4空间性能 157
6.4邻接表 158
6.4.1原理 158
6.4.2复杂度 158
6.5图遍历算法概述 159
6.6广度优先搜索 159
6.6.1策略 159
6.6.2实现 160
6.6.3实例 161
6.6.4复杂度 161
6.6.5应用 161
6.7深度优先搜索 162
6.7.1策略 162
6.7.2实现 162
6.7.3实例 163
6.7.4复杂度 165
6.7.5应用 165
6.8拓扑排序 165
6.8.1应用 165
6.8.2有向无环图 166
6.8.3算法 166
6.8.4实现 167
6.8.5实例 168
6.8.6复杂度 168
6.9双连通域分解 168
6.9.1关节点与双连通域 168
6.9.2蛮力算法 169
6.9.3可行算法 169
6.9.4实现 170
6.9.5实例 171
6.9.6复杂度 172
6.10优先级搜索 172
6.10.1优先级与优先级数 172
6.10.2基本框架 173
6.10.3复杂度 174
6.11最小支撑树 174
6.11.1支撑树 174
6.11.2最小支撑树 174
6.11.3歧义性 175
6.11.4蛮力算法 175
6.11.5 Prim算法 175
6.12最短路径 178
6.12.1最短路径树 178
6.12.2 Dijkstra算法 178
第7章 搜索树 181
7.1查找 183
7.1.1循关键码访问 183
7.1.2词条 183
7.1.3序与比较器 183
7.2二叉搜索树 184
7.2.1顺序性 184
7.2.2中序遍历序列 184
7.2.3 BST模板类 185
7.2.4查找算法及其实现 185
7.2.5插入算法及其实现 188
7.2.6删除算法及其实现 189
7.3平衡二叉搜索树 191
7.3.1树高与性能 191
7.3.2理想平衡与适度平衡 192
7.3.3等价变换 192
7.3.4旋转调整 193
7.4 AVL树 194
7.4.1定义及性质 194
7.4.2节点插入 196
7.4.3节点删除 198
7.4.4统一重平衡算法 200
第8章 高级搜索树 203
8.1伸展树 204
8.1.1局部性 204
8.1.2逐层伸展 205
8.1.3双层伸展 206
8.1.4伸展树的实现 208
8.2 B-树 212
8.2.1多路平衡查找 212
8.2.2 ADT接口及其实现 215
8.2.3关键码查找 216
8.2.4性能分析 218
8.2.5关键码插入 219
8.2.6上溢与分裂 219
8.2.7关键码删除 222
8.2.8下溢与合并 223
8.3红黑树 227
8.3.1概述 228
8.3.2红黑树接口定义 230
8.3.3节点插入算法 231
8.3.4节点删除算法 234
8.4 kd-树 239
8.4.1范围查询 239
8.4.2 kd-树 242
8.4.3基于2d-树的范围查询 243
第9章 词典 245
9.1词典ADT 247
9.1.1操作接口 247
9.1.2操作实例 247
9.1.3接口定义 248
9.1.4实现方法 248
9.2跳转表 249
9.2.1 Skiplist模板类 249
9.2.2总体逻辑结构 250
9.2.3四联表 250
9.2.4查找 252
9.2.5空间复杂度 253
9.2.6时间复杂度 254
9.2.7插入 255
9.2.8删除 258
9.3散列表 259
9.3.1完美散列 259
9.3.2装填因子与空间利用率 260
9.3.3散列函数 261
9.3.4散列表 264
9.3.5冲突及其排解 266
9.3.6闭散列策略 268
9.3.7查找与删除 271
9.3.8插入 272
9.3.9更多闭散列策略 273
9.3.10散列码转换 275
9.4散列应用 277
9.4.1桶排序 277
9.4.2最大间隙 278
9.4.3基数排序 279
第10章 优先级队列 281
10.1优先级队列ADT 282
10.1.1优先级与优先级队列 282
10.1.2关键码、比较器与偏序关系 283
10.1.3操作接口 283
10.1.4操作实例：选择排序 283
10.1.5接口定义 284
10.1.6应用实例：Huffman编码树 284
10.2堆 286
10.2.1完全二叉堆 286
10.2.2元素插入 289
10.2.3元素删除 291
10.2.4建堆 292
10.2.5就地堆排序 295
10.3左式堆 297
10.3.1堆合并 297
10.3.2单侧倾斜 298
10.3.3 PQ_LeftHeap模板类 298
10.3.4空节点路径长度 299
10.3.5左倾性与左式堆 299
10.3.6最右侧通路 300
10.3.7合并算法 300
10.3.8实例 301
10.3.9合并操作merge（）的实现 302
10.3.10复杂度 303
10.3.11基于合并的插入和删除 303
第11章 串 305
11.1串及串匹配 306
11.1.1串 306
11.1.2串匹配 307
11.1.3测评标准与策略 308
11.2蛮力算法 309
11.2.1算法描述 309
11.2.2算法实现 309
11.2.3时间复杂度 310
11.3 KMP算法 311
11.3.1构思 311
11.3.2 next表 312
11.3.3 KMP算法 312
11.3.4 next[0]=-1 313
11.3.5 next[j+1] 313
11.3.6构造next表 314
11.3.7性能分析 314
11.3.8继续改进 315
11.4 BM算法 317
11.4.1思路与框架 317
11.4.2坏字符策略 318
11.4.3好后缀策略 321
11.4.4 GS[]表构造算法 323
11.4.5算法纵览 326
11.5 Karp-Rabin算法 327
11.5.1构思 327
11.5.2算法与实现 328
第12章 排序 333
12.1快速排序 334
12.1.1分治策略 334
12.1.2轴点 334
12.1.3快速排序算法 335
12.1.4快速划分算法 335
12.1.5复杂度 338
12.1.6应对退化 339
12.2选取与中位数 341
12.2.1概述 341
12.2.2众数 342
12.2.3归并向量的中位数 343
12.2.4基于优先级队列的选取 346
12.2.5基于快速划分的选取 347
12.2.6 k-选取算法 348
12.3希尔排序 350
12.3.1递减增量策略 350
12.3.2增量序列 353
附录 357
参考文献 358
插图索引 362
表格索引 369
算法索引 370
代码索引 371
关键词索引 377