第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.11 AVL树 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 优先队列ADT 181
7.3 优先队列的应用 182
7.4 优先队列的实现 182
7.5 堆和二叉堆 183
7.6 二叉堆 184
7.7 优先队列（堆）的相关问题 190
第8章 并查集ADT 201
8.1 引言 201
8.2 等价关系和等价类 201
8.3 并查集ADT 202
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 散列表ADT 317
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.4 Robin-Karp字符串匹配算法 336
15.5 基于有限自动机的字符串匹配算法 337
15.6 KMP算法 338
15.7 Boyce-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