第一部分 算法和构件块 2
第1章 算法分析 2
1.1 什么是算法分析 2
1.2 算法运行时间的实例 5
1.3 连续子序列最大和的问题 6
1.3.1 简单的O（n3）算法 7
1.3.2 改进的O（N2）算法 8
1.3.3 线性算法 9
1.4 一般的大O规则 11
1.5 对数 14
1.6 静态查找问题 15
1.6.1 顺序查找 15
1.6.2 二分搜索 16
1.6.3 插值查找 18
1.7 算法分析的检查 18
1.8 大O分析的局限性 19
小结 20
关键概念 20
常见错误 21
网上资源 21
习题 21
参考文献 26
第2章 集合类API 27
2.1 引言 27
2.2 迭代器模式 28
2.2.1 基本的迭代器设计 29
2.2.2 基于继承的迭代器和工厂方法 30
2.3 集合类API：容器和迭代器 32
2.3.1 Collection接口 32
2.3.2 Iterator接口 35
2.4 泛型算法 36
2.4.1 Comparator函数对象 37
2.4.2 Collections类 37
2.4.3 二分搜索 39
2.4.4 排序 40
2.5 List接口 40
2.5.1 ListIterator接口 41
2.5.2 LinkedList类 42
2.6 栈和队列 44
2.6.1 栈 44
2.6.2 栈与计算机语言 45
2.6.3 队列 46
2.6.4 集合类API中的栈和队列 46
2.7 集合 47
2.7.1 TreeSet类 48
2.7.2 HashSet类 48
2.8 映射 52
2.9 优先级队列 55
小结 57
关键概念 57
常见错误 58
网上资源 58
习题 59
参考文献 61
第3章 递归 62
3.1 什么是递归 62
3.2 背景：数学归纳法证明 63
3.3 基本的递归 65
3.3.1 以任何数制打印数 66
3.3.2 为什么可行 67
3.3.3 原理解析 68
3.3.4 太多的递归可能是危险的 69
3.3.5 树的预习 70
3.3.6 其他实例 71
3.4 数值应用 74
3.4.1 模运算 74
3.4.2 模的幂运算 75
3.4.3 最大公因子和乘法逆元素 76
3.4.4 RSA密码系统 78
3.5 分治算法 79
3.5.1 连续子序列最大和的问题 80
3.5.2 对一个基本的分治情况的分析 82
3.5.3 分治算法运行时间的通用上界 84
3.6 动态规划 86
3.7 回溯 89
小结 92
关键概念 92
常见错误 93
网上资源 93
习题 94
参考文献 96
第4章 排序算法 97
4.1 排序为什么重要 97
4.2 预备知识 98
4.3 插入排序及其他简单排序算法的分析 98
4.4 谢尔排序 101
4.5 归并排序 103
4.5.1 有序数组的线性时间合并 103
4.5.2 归并排序算法 105
4.6 快速排序 106
4.6.1 快速排序算法 107
4.6.2 快速排序的分析 108
4.6.3 挑选中心点 111
4.6.4 一种划分策略 112
4.6.5 键等于中心点 113
4.6.6 三个元素的中值划分 114
4.6.7 小规模数组 114
4.6.8 Java快速排序程序 115
4.7 快速选择 117
4.8 排序的下界 118
小结 119
关键概念 119
常见错误 120
网上资源 120
习题 120
参考文献 123
第5章 随机化 124
5.1 为什么需要随机数 124
5.2 随机数生成器 125
5.3 非均匀分布随机数 129
5.4 产生随机排列 130
5.5 随机化算法 131
5.6 随机化素数检验 133
小结 135
关键概念 135
常见错误 136
网上资源 136
习题 136
参考文献 138
第二部分 应用 140
第6章 娱乐和游戏 140
6.1 单词搜索迷宫 140
6.1.1 理论 140
6.1.2 Java实现 142
6.2 Tic-Tac-Toe游戏 146
6.2.1 α-β剪枝 146
6.2.2 置换表 148
6.2.3 计算机象棋 151
小结 152
关键概念 152
常见错误 152
网上资源 152
习题 153
参考文献 154
第7章 栈和编译器 155
7.1 平衡符号检查器 155
7.1.1 基本算法 155
7.1.2 实现 156
7.2 简单计算器 163
7.2.1 后缀机 164
7.2.2 中缀到后缀的转化 165
7.2.3 实现 166
7.2.4 表达式树 172
小结 173
关键概念 173
常见错误 174
网上资源 174
习题 174
参考文献 175
第8章 实用程序 176
8.1 文件压缩 176
8.1.1 前缀编码 177
8.1.2 赫夫曼算法 178
8.1.3 实现 180
8.2 交叉引用生成器 191
8.2.1 基本思想 191
8.2.2 Java实现 191
小结 194
关键概念 194
常见错误 195
网上资源 195
习题 195
参考文献 197
第9章 模拟 198
9.1 约瑟夫问题 198
9.1.1 简单实现方案 199
9.1.2 更高效的算法 200
9.2 事件驱动模拟 202
9.2.1 基本思路 202
9.2.2 实例：调制解调器银行的模拟 203
小结 209
关键概念 209
常见错误 209
网上资源 209
习题 209
第10章 图和路径 211
10.1 图的定义 211
10.2 非加权的最短路径问题 221
10.2.1 理论 221
10.2.2 Java实现 223
10.3 非负权值的最短路径算法 224
10.3.1 理论：Dijkstra算法 224
10.3.2 Java实现 227
10.4 含负权值的最短路径问题 228
10.4.1 理论 228
10.4.2 Java实现 229
10.5 无环图的路径问题 230
10.5.1 拓扑排序 230
10.5.2 无环图最短路径算法的理论 232
10.5.3 Java实现 233
10.5.4 应用：关键路径分析 234
小结 236
关键概念 236
常见错误 237
网上资源 237
习题 238
参考文献 240
第三部分 实现 242
第11章 内部类和ArrayList的实现 242
11.1 迭代器与嵌套类 242
11.2 迭代器和内部类 244
11.3 AbstractCollection类 246
11.4 StringBuilder 249
11.5 使用迭代器的ArrayList的实现 250
小结 254
关键概念 254
常见错误 254
网上资源 254
习题 255
第12章 栈和队列 257
12.1 动态数组的实现 257
12.1.1 栈 257
12.1.2 队列 260
12.2 链表实现 265
12.2.1 栈 265
12.2.2 队列 267
12.3 两种实现方式的比较 270
12.4 java.util.Stack类 270
12.5 双向队列 271
小结 271
关键概念 272
常见错误 272
网上资源 272
习题 272
第13章 链表 273
13.1 基本思想 273
13.1.1 头结点 274
13.1.2 迭代器类 275
13.2 Java实现 276
13.3 双向链表和循环链表 281
13.4 有序链表 283
13.5 集合类API中LinkedList类的实现 284
小结 292
关键概念 292
常见错误 293
网上资源 293
习题 293
第14章 树 296
14.1 普通的树 296
14.1.1 定义 296
14.1.2 实现 297
14.1.3 应用：文件系统 298
14.2 二叉树 301
14.3 递归和树 306
14.4 树的遍历：迭代器类 307
14.4.1 后序遍历 310
14.4.2 中序遍历 313
14.4.3 前序遍历 314
14.4.4 层次遍历 316
小结 317
关键概念 317
常见错误 318
网上资源 318
习题 318
第15章 二叉查找树 321
15.1 基本思想 321
15.1.1 操作 322
15.1.2 Java实现 323
15.2 顺序统计量 329
15.3 二叉查找树操作的分析 332
15.4 AVL树 335
15.4.1 性质 335
15.4.2 单旋转 337
15.4.3 双旋转 339
15.4.4 AVL插入小结 341
15.5 红黑树 341
15.5.1 自下而上的插入 342
15.5.2 自上而下的红黑树 344
15.5.3 Java实现 345
15.5.4 自上而下的删除 350
15.6 AA树 352
15.6.1 插入 353
15.6.2 删除 354
15.6.3 Java实现 355
15.7 集合类API中TreeSet类和TreeMap类的实现 358
15.8 B树 371
小结 376
关键概念 376
常见错误 377
网上资源 377
习题 378
参考文献 379
第16章 散列表 382
16.1 基本概念 382
16.2 散列函数 383
16.3 线性探测法 385
16.3.1 线性探测法的直观分析 386
16.3.2 实际上所发生的：初始聚类 386
16.3.3 find操作的分析 387
16.4 二次探测法 388
16.4.1 Java实现 392
16.4.2 二次探测法的分析 398
16.5 分别链接散列 399
16.6 散列表与二叉查找树 399
16.7 散列表的应用 400
小结 400
关键概念 400
常见错误 401
网上资源 401
习题 401
参考文献 403
第17章 优先级队列：二叉堆 404
17.1 基本概念 404
17.1.1 结构性 405
17.1.2 堆的有序性 406
17.1.3 允许的操作 406
17.2 基本操作的实现 408
17.2.1 插入 408
17.2.2 deleteMin操作 410
17.3 buildHeap操作：线性时间的堆构造 411
17.4 高级操作：decreaseKey和merge 414
17.5 内排序：堆排序 414
17.6 外排序 416
17.6.1 为什么需要新的算法 417
17.6.2 外排序模型 417
17.6.3 简单算法 417
17.6.4 多路归并 418
17.6.5 多阶段归并 419
17.6.6 置换选择法 420
小结 421
关键概念 422
常见错误 422
网上资源 422
习题 422
参考文献 425
第四部分 高级数据结构 428
第18章 伸展树 428
18.1 自调整和均摊法的分析 428
18.1.1 均摊法时间限度 429
18.1.2 简单的自调整策略（并不管用） 429
18.2 基本的自底向上的伸展树 430
18.3 基本的伸展树操作 432
18.4 自底向上伸展的分析 432
18.5 自顶向下的伸展树 436
18.6 自顶向下伸展树的实现 439
18.7 伸展树与其他搜索树的比较 442
小结 442
关键概念 443
常见错误 443
网上资源 443
习题 443
参考文献 444
第19章 归并优先级队列 445
19.1 斜堆 445
19.1.1 归并是基本操作 445
19.1.2 满足堆有序性的树的简化归并 446
19.1.3 斜堆：一个简单的修改 446
19.1.4 斜堆的分析 447
19.2 偶堆 448
19.2.1 偶堆操作 449
19.2.2 偶堆的实现 450
19.2.3 应用：Dijkstra最短加权路径算法 455
小结 457
关键概念 457
常见错误 457
网上资源 457
习题 457
参考文献 458
第20章 不相交集类 459
20.1 等价关系 459
20.2 动态等价及应用 459
20.2.1 应用：生成迷宫 460
20.2.2 应用：最小生成树 462
20.2.3 应用：最近的共同祖先问题 463
20.3 快速查找算法 466
20.4 快速并算法 466
20.4.1 智能并算法 468
20.4.2 路径压缩 469
20.5 Java实现 470
20.6 按秩并和路径压缩的最坏情况 471
小结 476
关键概念 477
常见错误 478
网上资源 478
习题 478
参考文献 479
附录A 运算符 481
附录B 位运算符 482