第一部分 基础知识 2
第1章 导论 2
1.1 算法 2
目录 2
1.2 问题示例：连通性（connectivity） 4
练习 7
1.3 并集—查找算法 7
练习 17
1.4 展望 18
练习 19
1.5 小结 19
第2章 算法分析原理 22
2.1 实现与试验分析 22
练习 25
2.2 算法分析 25
2.3 函数增长 27
练习 27
练习 32
2.4 O记号 32
练习 35
2.5 基本递推式 36
练习 38
2.6 算法分析示例 39
练习 43
2.7 保证、预测与限制 44
练习 46
第一部分参考文献 47
第二部分 数据结构 49
第3章 基本数据结构 49
3.1 基石 50
3.2 数组 57
练习 57
练习 63
3.3 链表 64
练习 69
3.4 基本表处理 70
练习 77
3.5 表的内存分配 77
练习 80
3.6 串 80
练习 84
3.7 复合数据结构 84
练习 92
第4章 抽象数据类型 93
4.1 抽象对象与对象集合 95
4.2 下推栈ADT 97
练习 97
练习 99
4.3 栈ADT客户程序示例 99
练习 104
4.4 栈ADT实现 105
练习 108
4.5 创建新ADT 109
练习 111
4.6 FIFO队列及广义队列 111
练习 117
4.7 重复项和索引项 118
练习 121
4.8 一级ADT 122
练习 130
4.9 ADT应用示例 131
练习 134
4.10 展望 135
第5章 递归和树 136
5.1 递归算法 136
练习 141
5.2 分治 142
练习 155
5.3 动态规划 156
练习 160
5.4 树 163
练习 168
5.5 二叉树的数学性质 169
练习 171
5.6 树遍历 172
练习 175
5.7 递归二叉树算法 177
练习 181
5.8 图遍历 182
练习 187
5.9 展望 188
第二部分参考文献 189
第三部分 排序 191
第6章 基本排序方法 191
6.1 游戏规则 192
练习 195
6.2 选择排序 196
练习 197
6.3 插入排序 198
练习 199
6.4 冒泡排序 200
6.5 基本排序的性能特征 201
练习 201
练习 206
6.6 希尔排序 206
练习 212
6.7 其他数据类型的排序 214
练习 217
6.8 索引与指针排序 218
练习 223
6.9 链表的排序 223
练习 225
6.10 键索引计数 226
练习 228
第7章 快速排序 229
7.1 基本算法 229
7.2 快速排序的性能特征 233
练习 233
练习 236
7.3 栈大小 236
练习 239
7.4 小子文件 239
练习 240
7.5 三元素中值法划分 242
练习 245
7.6 重复键 245
练习 246
7.7 串和向量 248
练习 249
7.8 选择 249
练习 251
第8章 归并和归并排序 253
8.1 二路归并 254
8.2 抽象就位归并 255
练习 255
练习 256
8.3 自顶向下归并 257
练习 259
8.4 基本算法的改进 259
练习 261
8.5 自底向上归并排序 261
练习 265
8.6 归并排序的性能特征 265
练习 266
8.7 归并排序的链式实现 267
练习 269
8.8 回顾递归 270
练习 271
第9章 优先队列与堆排序 272
9.1 基本实现方法 274
练习 274
练习 276
9.2 堆数据结构 277
练习 278
9.3 堆的算法 278
练习 284
9.4 堆排序 285
练习 291
9.5 优先队列ADT 292
练习 295
9.6 索引项的优先队列 295
练习 298
9.7 二项式队列 298
练习 306
第10章 基数排序 307
10.1 位（bit）、字节（byte）和字（word） 308
10.2 二分快速排序 310
练习 310
练习 314
10.3 MSD基数排序 315
练习 321
10.4 三路基数快速排序 321
练习 325
10.5 LSD基数排序 325
练习 329
10.6 基数排序的性能特征 329
练习 332
10.7 亚线性时间排序 332
练习 335
第11章 特殊目的排序方法 336
11.1 巴切奇偶归并排序 337
11.2 排序网络 341
练习 341
练习 347
11.3 外部排序 349
练习 353
11.4 排序归并的实现 353
练习 358
11.5 并行排序归并 359
练习 361
第三部分参考文献 362
第四部分 搜索 365
第12章 符号表和二叉搜索树 365
12.1 符号表抽象数据类型 366
练习 369
12.2 键索引搜索 370
12.3 顺序搜索 372
练习 372
练习 376
12.4 二分搜索 377
练习 381
12.5 二叉搜索树（BST） 381
练习 387
12.6 BST的性能特征 388
练习 390
12.7 符号表的索引实现 392
练习 394
12.8 在BST根部的插入 395
练习 399
12.9 其他ADT函数的BST实现 400
练习 406
第13章 平衡树 408
13.1 随机BST 410
练习 410
练习 415
13.2 分裂BST 416
练习 422
13.3 自顶向下2-3-4树 422
练习 427
13.4 红-黑树 427
练习 434
13.5 跳表 436
练习 443
13.6 性能特征 443
练习 445
第14章 哈希方法 446
14.1 哈希函数 446
练习 453
14.2 分离链 454
练习 457
14.3 线性探测法 458
练习 461
14.4 双哈希法 462
练习 466
14.5 动态哈希表 467
练习 469
14.6 展望 470
练习 473
第15章 基数搜索 474
15.1 位搜索树 474
练习 478
15.2 Trie 479
练习 485
15.3 Patricia Tries 486
练习 492
15.4 多路trie和TST 493
练习 504
15.5 文本串索引算法 506
练习 508
第16章 外部搜索 510
16.1 游戏规则 511
16.2 索引顺序访问 512
练习 515
16.3 B树 515
练习 524
16.4 可扩展哈希法 525
练习 533
16.5 展望 534
练习 534
第四部分参考文献 536