第1章 绪论 1
1.1变量 1
1.2数据类型 1
1.3数据结构 2
1.4抽象数据类型 2
1.5什么是算法 3
1.6为什么需要分析算法 3
1.7算法分析的目的 3
1.8什么是运行时间分析 3
1.9如何比较算法 4
1.10什么是增长率 4
1.11常用的增长率 4
1.12算法分析的类型 5
1.13渐近符号 5
1.14 O符号 6
1.15Ω符号 7
1.16 ？符号 8
1.17为什么称为渐近分析 9
1.18渐近分析的准则 9
1.19渐近符号的性质 11
1.20常用的对数公式和求和公式 11
1.21分治法的主定理 11
1.22与分治法主定理相关的问题 12
1.23减治递推的主定理 13
1.24减治主定理的另一种形式 13
1.25猜测与确认的方法 13
1.26平摊分析 15
1.27关于算法分析的问题集 15
第2章 递归与回溯 28
2.1引言 28
2.2什么是递归 28
2.3为什么需要递归 28
2.4递归函数的格式 28
2.5递归与内存（图形化演示） 29
2.6递归与迭代 30
2.7递归的要点 30
2.8递归算法举例 30
2.9关于递归的问题集 31
2.10什么是回溯 32
2.11回溯算法举例 32
2.12关于回溯的问题集 32
第3章 链表 35
3.1什么是链表 35
3.2链表的抽象数据类型 35
3.3为什么需要链表 35
3.4数组回顾 35
3.5链表与数组、动态数组的比较 37
3.6单链表 37
3.7双链表 43
3.8循环链表 48
3.9一种存储高效的双链表 54
3.10松散链表 55
3.11跳表 61
3.12关于链表的问题集 64
第4章栈 87
4.1什么是栈 87
4.2如何使用栈 87
4.3栈的抽象数据类型 87
4.4栈的应用 88
4.5栈的实现 88
4.6栈实现的比较 94
4.7关于栈的问题集 94
第5章 队列 114
5.1什么是队列 114
5.2如何使用队列 114
5.3队列的抽象数据类型 114
5.4操作异常 115
5.5队列的应用 115
5.6队列的实现 115
5.7关于队列的问题集 121
第6章树 127
6.1什么是树 127
6.2相关术语 127
6.3二叉树 128
6.4 1L种特殊的二叉树 128
6.5二叉树的性质 129
6.6二叉树的遍历 131
6.7一般的树（N叉树） 153
6.8线索二叉树的遍历（与栈／队列无关的遍历） 159
6.9表达树 166
6.10 XOR树 168
6.11二叉搜索树 169
6.12平衡二叉搜索树 184
6.13 AVL树 184
6.14其他形式的树 200
第7章 优先队列和堆 204
7.1什么是优先队列 204
7.2优先队列的抽象数据类型 204
7.3优先队列的应用 205
7.4优先队列的实现 205
7.5堆和二项堆 206
7.6二项堆 207
7.7堆排序 213
7.8关于优先队列（堆）的问题集 214
第8章 不相交集 226
8.1引言 226
8.2等价关系和等价类 226
8.3不相交集的抽象数据类型 227
8.4不相交集的应用 227
8.5不相交集实现的折中方案 227
8.6快速查找Fast FIND的实现（Quick FIND） 227
8.7快速合并Fast UNION的实现（Quick UNION） 228
8.8快速合并Fast UNION的实现（Slow FIND） 228
8.9快速合并Fast UNION的实现（Quick FIND） 231
8.10小结 234
8.11关于不相交集的问题集 234
第9章 图算法 235
9.1引言 235
9.2相关术语 235
9.3图的应用 238
9.4图的表示 238
9.5图的遍历 242
9.6拓扑排序 249
9.7最短路径算法 250
9.8最小生成树 256
9.9关于图算法的问题集 259
第10章 排序 280
10.1什么是排序 280
10.2为什么需要排序 280
10.3排序算法的分类 280
10.4其他分类方式 281
10.5冒泡排序 281
10.6选择排序 282
10.7插入排序 283
10.8希尔排序 285
10.9归并排序 287
10.10堆排序 289
10.11快速排序 289
10.12树排序 292
10.13排序算法的比较 292
10.14线性排序算法 292
10.15计数排序 293
10.16桶排序（或箱排序） 293
10.17基数排序 294
10.18拓扑排序 295
10.19外部排序 295
10.20关于排序的问题集 296
第11章 搜索 306
11.1什么是搜索 306
11.2为什么需要搜索 306
11.3搜索的类型 306
11.4无序线性搜索 306
11.5排序／有序线性搜索 307
11.6二分搜索 307
11.7基本搜索算法的比较 308
11.8符号表和散列 308
11.9字符串搜索算法 308
11.10关于搜索的问题集 308
第12章 选择算法（中位数） 333
12.1什么是选择算法 333
12.2基于排序的选择 333
12.3基于划分的选择算法 333
12.4线性选择算法——Median of Median算法 333
12.5按序寻找第k小元素 333
12.6关于选择算法的问题集 334
第13章 符号表 343
13.1引言 343
13.2什么是符号表 343
13.3符号表的实现 343
13.4符号表实现的比较 344
第14章 散列法 346
14.1什么是散列法 346
14.2为什么需要散列法 346
14.3散列表的抽象数据类型 346
14.4理解散列法 346
14.5散列法的构成要素 347
14.6散列表 348
14.7散列函数 348
14.8装填因子 348
14.9冲突 349
14.10解决冲突的方法 349
14.11拉链法 349
14.12开放地址法 349
14.13冲突解决方法的比较 351
14.14如何得到复杂度为O（1）的散列法 352
14.15散列技术 352
14.16不合适构造散列表的问题 352
14.17 Bloom过滤器 353
14.18关于散列法的问题集 355
第15章 字符串算法 366
15.1引言 366
15.2字符串匹配算法 366
15.3蛮力法 366
15.4 Robin-Karp字符串匹配算法 367
15.5基于有限自动机的字符串匹配 368
15.6 KMP算法 370
15.7 Boyce-Moore算法 373
15.8字符串的存储结构 373
15.9字符串的散列表 374
15.10字符串的二叉搜索树 374
15.11字典树 374
15.12三叉搜索树 377
15.13二叉搜索树、字典树和三叉搜索树的比较 380
15.14后缀树 380
15.15关于字符串的问题集 384
第16章 算法设计技巧 393
16.1引言 393
16.2算法的分类 393
16.3基于实现方法的算法分类 393
16.4基于设计方法的算法分类 394
16.5其他方式的算法分类 395
第17章 贪婪算法 396
17.1引言 396
17.2贪婪策略 396
17.3贪婪算法的要素 396
17.4贪婪技术总是奏效吗 396
17.5贪婪方法的优缺点 396
17.6贪婪技术的应用 397
17.7理解贪婪技术 397
17.8关于贪婪算法的问题集 400
第18章 分治算法 407
18.1引言 407
18.2什么是分治策略 407
18.3分治法总是奏效吗 407
18.4分治法原理的图形化演示 407
18.5理解分治法 408
18.6分治法的优点 408
18.7分治法的缺点 409
18.8主定理 409
18.9分治法的应用 409
18.10关于分治法的问题集 409
第19章 动态规划 422
19.1引言 422
19.2什么是动态规划策略 422
19.3动态规划策略的性质 422
19.4动态规划可以求解所有的问题吗 422
19.5动态规划方法 422
19.6动态规划算法举例 423
19.7理解动态规划 423
19.8最长公共子序列 426
19.9关于动态规划的问题集 429
第20章 复杂性类 461
20.1引言 461
20.2多项式／指数时间 461
20.3什么是判定性问题 461
20.4判定性过程 462
20.5什么是复杂性类 462
20.6复杂性类的类型 462
20.7归约 464
20.8关于复杂性类的问题集 466
第21章 其他主题 469
21.1引言 469
21.2位编程的技巧 469
21.3其他编程问题 474
参考文献 481