译者序
前言
第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什么是运行时间分析4
1.9如何比较算法4
1.10什么是增长率4
1.11常用的增长率4
1.12分析的类型5
1.13渐近表示6
1.14大O表示法6
1.15Ω表示法7
1.16Θ表示法8
1.17重要说明9
1.18为什么称为渐近分析9
1.19渐近分析指南9
1.20渐近表示法的性质11
1.21常用的对数和累加公式11
1.22分治法主定理12
1.23分治法主定理的相关问题12
1.24问题规模减小和递归求解主定理13
1.25问题规模减小和递归求解主定理的变型13
1.26猜测和确认的方法14
1.27平摊分析15
1.28算法分析的相关问题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章链表34
3.1什么是链表34
3.2链表抽象数据类型34
3.3为什么要用链表35
3.4数组概述35
3.5链表、数组和动态数组的比较36
3.6单向链表36
3.7双向链表41
3.8循环链表46
3.9一种存储高效的双向链表51
3.10松散链表52
3.11链表的相关问题55
第4章栈72
4.1什么是栈72
4.2如何使用栈72
4.3栈抽象数据类型73
4.4异常73
4.5应用73
4.6实现73
4.7栈的各种实现方法比较77
4.8栈的相关问题78
第5章队列98
5.1什么是队列98
5.2如何使用队列98
5.3队列抽象数据类型99
5.4异常99
5.5应用99
5.6实现99
5.7队列的相关问题104
第6章树110
6.1什么是树110
6.2术语110
6.3二叉树111
6.4二叉树的遍历114
6.5通用树（N叉树）135
6.6线索（无栈或无队列结构）二叉树遍历141
6.7表达式树147
6.8异或树149
6.9二叉搜索树150
6.10平衡二叉搜索树164
6.11AVL树165
6.12树的其他形式178
6.12.1红黑树178
6.12.2伸展树179
6.12.3增强树179
6.12.4替罪羊树179
6.12.5区间树180
第7章优先队列和堆181
7.1什么是优先队列181
7.2优先队列ADT181
7.3优先队列的应用182
7.4优先队列的实现182
7.5堆和二叉堆183
7.6二叉堆184
7.7优先队列（堆）的相关问题190
第8章并查集ADT201
8.1引言201
8.2等价关系和等价类201
8.3并查集ADT202
8.4应用202
8.5并查集ADT实现中的权衡202
8.6快速UNION实现（慢FIND）203
8.7快速UNION实现（快速FIND）206
8.8路径压缩208
8.9小结209
8.10并查集的相关问题209
第9章图算法211
9.1引言211
9.2术语211
9.3图的应用214
9.4图的表示214
9.5图的遍历217
9.6拓扑排序225
9.7最短路径算法226
9.8最小生成树231
9.9图算法的相关问题235
第10章排序256
10.1什么是排序256
10.2为什么需要排序256
10.3排序的分类256
10.4其他分类方法257
10.5冒泡排序257
10.6选择排序258
10.7插入排序259
10.8希尔排序261
10.9归并排序262
10.10堆排序264
10.11快速排序264
10.12树排序266
10.13排序算法比较267
10.14线性排序算法267
10.15计数排序267
10.16桶排序268
10.17基数排序268
10.18拓扑排序269
10.19外部排序269
10.20排序的相关问题270
第11章查找279
11.1什么是查找279
11.2为什么需要查找279
11.3查找的类型279
11.4符号表和散列281
11.5字符串查找算法281
11.6查找的相关问题281
第12章选择算法(中位数)304
12.1什么是选择算法304
12.2基于排序的选择算法304
12.3基于划分的选择算法304
12.4线性选择算法——中位数的中位数算法305
12.5按照排序顺序查找K个最小元素305
12.6选择算法的相关问题305
第13章符号表314
13.1引言314
13.2什么是符号表314
13.3符号表的实现315
13.4符号表实现方法的比较315
第14章散列317
14.1什么是散列317
14.2为什么用散列317
14.3散列表ADT317
14.4散列的例子317
14.5散列的组成部分319
14.6散列表319
14.7散列函数319
14.8负载因子320
14.9冲突320
14.10冲突解决技术320
14.11分离链接法320
14.12开放定址法321
14.13冲突解决技术的比较322
14.14散列如何达到O(1)的时间复杂度322
14.15散列技术323
14.16不适用散列表的问题323
14.17布鲁姆过滤器323
14.18散列的相关问题325
第15章字符串算法335
15.1引言335
15.2字符串匹配算法335
15.3蛮力法336
15.4RobinKarp字符串匹配算法336
15.5基于有限自动机的字符串匹配算法337
15.6KMP算法338
15.7BoyceMoore算法342
15.8存储字符串的数据结构342
15.9字符串的散列表实现342
15.10字符串的二叉搜索树实现343
15.11键树343
15.12三叉搜索树345
15.13二叉搜索树、键树和三叉搜索树的比较349
15.14后缀树349
15.15字符串的相关问题353
第16章算法设计技术361
16.1引言361
16.2分类361
16.3按实现方法分类361
16.4按设计方法分类362
16.5其他分类法363
第17章贪婪算法364
17.1引言364
17.2贪婪策略的定义364
17.3贪婪算法的要素364
17.4贪婪算法的适用范围365
17.5贪婪算法的优缺点365
17.6贪婪算法的应用365
17.7贪婪思想365
17.8贪婪算法的相关问题368
第18章分治算法375
18.1引言375
18.2分治策略的定义375
18.3分治法的适用范围375
18.4分治法的图形化描述375
18.5分治思想376
18.6主定理377
18.7分治法的应用377
18.8分治法的相关问题378
第19章动态规划算法390
19.1引言390
19.2动态规划策略的定义390
19.3动态规划策略的性质390
19.4动态规划的适用范围390
19.5动态规划的实现方法391
19.6动态规划算法的例子391
19.7动态规划思想391
19.8动态规划的相关问题396
第20章复杂度类型425
20.1引言425
20.2多项式/指数时间425
20.3决策问题的定义426
20.4决策过程426
20.5复杂度类型的定义426
20.6复杂度类型426
20.7归约428
20.8复杂度类型的相关问题430
第21章杂谈433
21.1引言433
21.2位运算的使用433
21.2.1按位与操作433
21.2.2按位或操作434
21.2.3按位异或操作434
21.2.4按位左移操作434
21.2.5按位右移操作434
21.2.6按位补操作434
21.2.7检测第K位是否置位434
21.2.8第K位置位435
21.2.9第K位清零435
21.2.10切换第K位435
21.2.11切换值为1的最右位435
21.2.12隔离值为1的最右位435
21.2.13隔离值为0的最右位435
21.2.14检查某个数是否是2的幂436
21.2.15将某个数乘以2的幂436
21.2.16将某个数除以2的幂436
21.2.17找到给定操作数的模436
21.2.18反转二进制数436
21.2.19位值1的计数436
21.2.20创建末尾位为0的掩码437
21.2.21交换奇偶位438
21.2.22不使用除法来计算平均数438
21.3其他编程问题438
参考文献442