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 递归简论 6
1.4 Java中的一般对象 9
1.4.1 IntCell类 10
1.4.2 MemoryCell类 12
1.4.3实现一般的findMax方法 13
1.5异常 14
1.6.2 StringTokenizer对象 17
1.6输入和输出 17
1.6.1基本的流操作 17
1.6.3 顺序文件 18
1.7代码的组织 20
1.7.1包 20
1.7.2 MyInteger类 21
1.7.3关于效率的考虑 21
小结 22
练习 22
参考文献 24
第2章 算法分析 25
2.1数学基础 25
2.2模型 27
2.3要分析的问题 27
2.4 运行时间计算 29
2.4.1一个简单的例子 30
2.4.2一般法则 30
2.4.3最大子序列和问题的解 32
2.4.4运行时间中的对数 37
2.4.5检验你的分析 40
2.4.6分析结果的准确性 41
小结 41
练习 42
参考文献 46
第3章 表、栈和队列 47
3.1抽象数据类型（ADT） 47
3.2表ADT 47
3.2.1表的简单数组实现 48
3.2.2链表 48
3.2.3程序设计细节 49
3.2.4 链表 54
3.2.5循环链表 54
3.2.6例子 55
3.2.7链表的游标实现 59
3.3栈ADT 64
3.3.1栈模型 64
3.3.2栈的实现 64
3.3.3 应用 69
3.4队列ADT 75
3.4.1队列模型 75
3.4.2队列的数组实现 75
3.4.3队列的应用 79
小结 80
练习 80
4.1预备知识 85
第4章 树 85
4.1.1树的实现 86
4.1.2树的遍历及应用 87
4.2二叉树 89
4.2.1实现 90
4.2.2一个例子：表达式树 90
4.3查找树ADT——二叉查找树 93
4.3.1 find 95
4.3.2 findMin和findMax 95
4.3.3 insert 96
4.3.4 remove 97
4.3.5平均情形分析 99
4.4 AVL树 101
4.4.1单旋转 102
4.4.2双旋转 105
4.5伸展树 110
4.5.1一个简单的想法（不能直接使用） 111
4.5.2展开 112
4.6树的遍历 117
4.7 B树 118
小结 122
练习 123
参考文献 128
第5章 散列 131
5.1一般想法 131
5.2散列函数 131
5.3 分离链接法 133
5.4开放定址法 136
5.4.1线性探测法 137
5.4.2平方探测法 138
5.4.3双散列法 143
5.5再散列 144
5.6 可扩散列 145
小结 148
练习 149
参考文献 152
第6章 优先队列（堆） 155
6.1模型 155
6.2一些简单的实现 156
6.3二叉堆 156
6.3.1结构性质 156
6.3.2堆序性质 157
6.3.3基本的堆操作 158
6.3.4其他的堆操作 162
6.4优先队列的应用 164
6.4.1选择问题 165
6.4.2事件模拟 166
6.5 d－堆 167
6.6左式堆 167
6.6.1左式堆性质 167
6.6.2左式堆操作 168
6.7斜堆 173
6.8 二项队列 175
6.8.1二项队列结构 175
6.8.2 项队列操作 176
6.8.3二项队列实现 178
小结 182
练习 183
参考文献 187
7.2.1算法 189
7.2插入排序 189
第7章 排序 189
7.1预备知识 189
7.2.2插入排序的分析 190
7.3一些简单排序算法的下界 190
7.4希尔排序 191
7.5堆排序 194
7.6 归并排序 197
7.7快速排序 202
7.7.1选取枢纽元 202
7.7.2分割策略 204
7.7.3 小数组 206
7.7.4实际的快速排序例程 206
7.7.5快速排序的分析 208
7.7.6选择问题的线性期望时间算法 210
7.8排序算法的一般下界 212
7.9桶式排序 214
7.10外部排序 214
7.10.1为什么需要新算法 214
7.10.2外部排序模型 214
7.10.3简单算法 215
7.10.4多路合并 216
7.10.5多相合并 217
7.10.6替换选择 217
小结 218
练习 219
参考文献 223
第8章 不相交集ADT 227
8.1等价关系 227
8.2动态等价性问题 227
8.3基本数据结构 229
8.4灵巧求并算法 232
8.5路径压缩 233
8.6按秩求并和路径压缩的最坏情形 235
8.7一个应用 240
小结 242
练习 242
参考文献 243
第9章 图论算法 245
9.1若干定义 245
9.2拓扑排序 247
9.3最短路径算法 250
9.3.1无权最短路径 251
9.3.2 Dijkstra算法 254
9.3.3具有负边值的图 259
9.3.4无圈图 260
9.3.5所有顶点对最短路径 262
9.4网络流问题 262
9.5最小生成树 266
9.5.1 Prim算法 267
9.5.2 Kruskal算法 269
9.6深度优先搜索的应用 271
9.6.1无向图 271
9.6.2双连通性 272
9.6.3欧拉回路 275
9.6.4有向图 278
9.6.5查找强分支 279
9.7 NP完全性介绍 281
9.7.1难与易 281
9.7.2 NP类 282
9.7.3 NP完全问题 283
小结 284
练习 285
参考文献 291
第10章 算法设计技巧 295
10.1贪婪算法 295
10.1.1一个简单的调度问题 296
10.1.2哈夫曼编码 298
10.1.3近似装箱问题 302
10.2分治算法 309
10.2.1分治算法的运行时间 309
10.2.2最近点问题 311
10.2.3选择问题 314
10.2.4一些算术问题的理论改进 317
10.3.1用表代替递归 320
10.3动态规划 320
10.3.2矩阵乘法的顺序安排 322
10.3.3最优二叉查找树 325
10.3.4所有点对最短路径 327
10.4随机化算法 329
10.4.1随机数发生器 330
10.4.2跳跃表 333
10.4.3素性测试 335
10.5 溯算法 337
10.5.1 收费公路重建问题 338
10.5.2博弈 341
小结 347
练习 347
参考文献 353
11.1一个无关的智力问题 359
第11章 摊还分析 359
11.2二项队列 360
11.3斜堆 363
11.4斐波那契堆 365
11.4.1切除左式堆中的节点 366
11.4.2二项队列的懒惰合并 368
11.4.3斐波那契堆操作 370
11.4.4 时间界的证明 371
11.5伸展树 373
小结 376
练习 376
参考文献 377
第12章 高级数据结构及其实现 379
12.1自顶向下伸展树 379
12.2红黑树 383
12.2.1自底向上插入 385
12.2.2自顶向下红黑树 386
12.2.3 自顶向下删除 390
12.3确定性跳跃表 391
12.4 AA树 396
12.5 treap树 401
12.6 k-d树 404
12.7配对堆 406
小结 411
练习 411
参考文献 414
附录A 一些库例程 417
附录B Collections类库 429
索引 445