第1章 引论 1
1.1本书讨论的内容 1
1.2数学知识复习 2
1.2.1指数 2
1.2.2对数 2
1.2.3级数 3
1.2.4模运算 4
1.2.5证明的方法 4
1.3递归简论 5
1.4实现泛型特性构件pre-Java 5 8
1.4.1使用Object表示泛型 9
1.4.2基本类型的包装 9
1.4.3使用接口类型表示泛型 10
1.4.4数组类型的兼容性 10
1.5利用Java 5泛性实现泛型特性成分 12
1.5.1简单的泛型类和接口 12
1.5.2自动装箱／拆箱 12
1.5.3带有限制的通配符 13
1.5.4泛型static方法 14
1.5.5类型限界 15
1.5.6类型擦除 16
1.5.7对于泛型的限制 16
1.6函数对象 17
小结 19
练习 19
参考文献 20
第2章 算法分析 22
2.1数学基础 22
2.2模型 24
2.3要分析的问题 24
2.4运行时间计算 26
2.4.1一个简单的例子 26
2.4.2一般法则 27
2.4.3最大子序列和问题的求解 28
2.4.4运行时间中的对数 33
2.4.5检验你的分析 36
2.4.6分析结果的准确性 37
小结 38
练习 38
参考文献 42
第3章表、栈和队列 44
3.1抽象数据类型 44
3.2表ADT 44
3.2.1表的简单数组实现 45
3.2.2简单链表 45
3.3 Java Collections API中的表 46
3.3.1 Collection接口 46
3.3.2Iterator接口 47
3.3.3 List接口、ArrayList类和LinkedList类 48
3.3.4例：remove方法对LinkedList类的使用 50
3.3.5关于ListIterator接口 51
3.4 ArrayList类的实现 52
3.4.1基本类 52
3.4.2迭代器、Java嵌套类和内部类 55
3.5 LinkedList类的实现 58
3.6栈ADT 64
3.6.1栈模型 64
3.6.2栈的实现 64
3.6.3应用 65
3.7队列ADT 70
3.7.1队列模型 70
3.7.2队列的数组实现 71
3.7.3队列的应用 72
小结 73
练习 73
第4章树 77
4.1预备知识 77
4.1.1树的实现 78
4.1.2树的遍历及应用 78
4.2二叉树 82
4.2.1实现 82
4.2.2例子：表达式树 82
4.3查找树ADT——二叉查找树 84
4.3.1 contains方法 86
4.3.2 findMin方法和findMax方法 87
4.3.3 insert方法 88
4.3.4 remove方法 89
4.3.5平均情况分析 90
4.4 AVL树 92
4.4.1单旋转 94
4.4.2双旋转 96
4.5伸展树 100
4.5.1一个简单的想法（不能直接使用） 101
4.5.2展开 102
4.6树的遍历 106
4.7 B树 108
4.8标准库中的集合与映射 111
4.8.1关于Set接口 112
4.8.2关于Map接口 112
4.8.3 TreeSet类和TreeMap类的实现 112
4.8.4使用多个映射的例 113
小结 118
练习 118
参考文献 123
第5章 散列 126
5.1一般想法 126
5.2散列函数 126
5.3分离链接法 128
5.4不用链表的散列表 132
5.4.1线性探测法 132
5.4.2平方探测法 133
5.4.3双散列 138
5.5再散列 139
5.6标准库中的散列表 141
5.7可扩散列 142
小结 144
练习 145
参考文献 148
第6章 优先队列（堆） 150
6.1模型 150
6.2一些简单的实现 151
6.3二叉堆 151
6.3.1结构性质 151
6.3.2堆序性质 153
6.3.3基本的堆操作 153
6.3.4其他的堆操作 155
6.4优先队列的应用 159
6.4.1选择问题 159
6.4.2事件模拟 160
6.5 d-堆 161
6.6左式堆 162
6.6.1左式堆性质 162
6.6.2左式堆操作 163
6.7斜堆 168
6.8二项队列 169
6.8.1二项队列结构 170
6.8.2二项队列操作 170
6.8.3二项队列的实现 172
6.9标准库中的优先队列 177
小结 177
练习 177
参考文献 181
第7章 排序 183
7.1预备知识 183
7.2插入排序 183
7.2.1算法 183
7.2.2插入排序的分析 184
7.3一些简单排序算法的下界 184
7.4希尔排序 185
7.5堆排序 188
7.6归并排序 191
7.7快速排序 195
7.7.1选取枢纽元 197
7.7.2分割策略 197
7.7.3小数组 199
7.7.4实际的快速排序例程 199
7.7.5快速排序的分析 200
7.7.6选择问题的线性期望时间算法 203
7.8排序算法的一般下界 205
7.9桶式排序 207
7.10外部排序 207
7.10.1为什么需要一些新的算法 207
7.10.2外部排序模型 207
7.10.3简单算法 208
7.10.4多路合并 209
7.10.5多相合并 210
7.10.6替换选择 210
小结 211
练习题 212
参考文献 216
第8章 不相交集类 219
8.1等价关系 219
8.2动态等价性问题 219
8.3基本数据结构 221
8.4灵巧求并算法 223
8.5路径压缩 225
8.6路径压缩和按秩求并的最坏情形 227
8.7一个应用 231
小结 233
练习题 233
参考文献 234
第9章 图论算法 237
9.1若干定义 237
9.2拓扑排序 239
9.3最短路径算法 241
9.3.1无权最短路径 242
9.3.2 Dijkstra算法 246
9.3.3具有负边值的图 250
9.3.4无圈图 251
9.3.5所有点对最短路径 253
9.3.6最短路径的例子 253
9.4网络流问题 255
9.5最小生成树 258
9.5.1 Prim算法 259
9.5.2 Kruskal算法 260
9.6深度优先搜索的应用 262
9.6.1无向图 262
9.6.2双连通性 263
9.6.3欧拉回路 266
9.6.4有向图 268
9.6.5查找强分支 269
9.7 NP-完全性介绍 270
9.7.1难与易 270
9.7.2 NP类 271
9.7.3 NP完全问题 272
小结 273
练习 273
参考文献 279
第10章 算法设计技巧 282
10.1贪婪算法 282
10.1.1一个简单的调度问题 282
10.1.2哈夫曼编码 284
10.1.3近似装箱问题 287
10.2分治算法 293
10.2.1分治算法的运行时间 293
10.2.2最近点问题 295
10.2.3选择问题 297
10.2.4一些算术问题的理论改进 300
10.3动态规划 303
10.3.1用一个表代替递归 303
10.3.2矩阵乘法的顺序安排 305
10.3.3最优二叉查找树 306
10.3.4所有点对最短路径 309
10.4随机化算法 311
10.4.1随机数发生器 312
10.4.2跳跃表 315
10.4.3素性测试 316
10.5回溯算法 319
10.5.1收费公路重建问题 319
10.5.2博弈 322
小结 328
练习 328
参考文献 335
第11章 摊还分析 339
11.1一个无关的智力问题 339
11.2二项队列 340
11.3斜堆 343
11.4斐波那契堆 345
11.4.1切除左式堆中的节点 345
11.4.2二项队列的懒惰合并 347
11.4.3斐波那契堆操作 348
11.4.4时间界的证明 349
11.5伸展树 351
小结 353
练习 354
参考文献 355
第12章 高级数据结构及其实现 356
12.1自顶向下伸展树 356
12.2红黑树 362
12.2.1自底向上的插入 362
12.2.2自顶向下红黑树 363
12.2.3自顶向下的删除 367
12.3确定性跳跃表 368
12.4 AA树 373
12.5 treap树 378
12.6 k-d树 381
12.7配对堆 383
小结 389
练习 389
参考文献 391
索引 394