第1章 基础 1
1.1基础编程模型 4
1.1.1 Java程序的基本结构 4
1.1.2原始数据类型与表达式 6
1.1.3语句 8
1.1.4简便记法 9
1.1.5数组 10
1.1.6静态方法 12
1.1.7 API 16
1.1.8字符串 20
1.1.9输入输出 21
1.1.10二分查找 28
1.1.11展望 30
1.2数据抽象 38
1.2.1使用抽象数据类型 38
1.2.2抽象数据类型举例 45
1.2.3抽象数据类型的实现 52
1.2.4更多抽象数据类型的实现 55
1.2.5数据类型的设计 60
1.3背包、队列和栈 74
1.3.1 API 74
1.3.2集合类数据类型的实现 81
1.3.3链表 89
1.3.4综述 98
1.4算法分析 108
1.4.1科学方法 108
1.4.2观察 108
1.4.3数学模型 112
1.4.4增长数量级的分类 117
1.4.5设计更快的算法 118
1.4.6倍率实验 121
1.4.7注意事项 123
1.4.8处理对于输入的依赖 124
1.4.9内存 126
1.4.10展望 129
1.5案例研究：union-find算法 136
1.5.1动态连通性 136
1.5.2实现 140
1.5.3展望 148
第2章 排序 152
2.1初级排序算法 153
2.1.1游戏规则 153
2.1.2选择排序 155
2.1.3插入排序 157
2.1.4排序算法的可视化 159
2.1.5比较两种排序算法 159
2.1.6希尔排序 162
2.2归并排序 170
2.2.1原地归并的抽象方法 170
2.2.2自顶向下的归并排序 171
2.2.3自底向上的归并排序 175
2.2.4排序算法的复杂度 177
2.3快速排序 182
2.3.1基本算法 182
2.3.2性能特点 185
2.3.3算法改进 187
2.4优先队列 195
2.4.1 API 195
2.4.2初级实现 197
2.4.3堆的定义 198
2.4.4堆的算法 199
2.4.5堆排序 205
2.5应用 214
2.5.1将各种数据排序 214
2.5.2我应该使用哪种排序算法 218
2.5.3问题的归约 219
2.5.4排序应用一览 221
第3章 查找 227
3.1符号表 228
3.1.1 API 228
3.1.2有序符号表 230
3.1.3用例举例 233
3.1.4无序链表中的顺序查找 235
3.1.5有序数组中的二分查找 238
3.1.6对二分查找的分析 242
3.1.7预览 244
3.2二叉查找树 250
3.2.1基本实现 250
3.2.2分析 255
3.2.3有序性相关的方法与删除操作 257
3.3平衡查找树 269
3.3.1 2-3查找树 269
3.3.2红黑二叉查找树 275
3.3.3实现 280
3.3.4删除操作 282
3.3.5红黑树的性质 284
3.4散列表 293
3.4.1散列函数 293
3.4.2基于拉链法的散列表 297
3.4.3基于线性探测法的散列表 300
3.4.4调整数组大小 304
3.4.5内存使用 306
3.5应用 312
3.5.1我应该使用符号表的哪种实现 312
3.5.2集合的API 313
3.5.3字典类用例 315
3.5.4索引类用例 318
3.5.5稀疏向量 322
第4章图 329
4.1无向图 331
4.1.1术语表 331
4.1.2表示无向图的数据类型 333
4.1.3深度优先搜索 338
4.1.4寻找路径 342
4.1.5广度优先搜索 344
4.1.6连通分量 349
4.1.7符号图 352
4.1.8总结 358
4.2有向图 364
4.2.1术语 364
4.2.2有向图的数据类型 365
4.2.3有向图中的可达性 367
4.2.4环和有向无环图 369
4.2.5有向图中的强连通性 378
4.2.6总结 385
4.3最小生成树 390
4.3.1原理 391
4.3.2加权无向图的数据类型 393
4.3.3最小生成树的API和测试用例 396
4.3.4 Prim算法 398
4.3.5 Prim算法的即时实现 401
4.3.6 Kruskal算法 404
4.3.7展望 407
4.4最短路径 412
4.4.1最短路径的性质 413
4.4.2加权有向图的数据结构 414
4.4.3最短路径算法的理论基础 420
4.4.4 Dijkstra算法 421
4.4.5无环加权有向图中的最短路径算法 425
4.4.6一般加权有向图中的最短路径问题 433
4.4.7展望 445
第5章 字符串 451
5.1字符串排序 455
5.1.1键索引计数法 455
5.1.2低位优先的字符串排序 458
5.1.3高位优先的字符串排序 461
5.1.4三向字符串快速排序 467
5.1.5字符串排序算法的选择 470
5.2单词查找树 474
5.2.1单词查找树 475
5.2.2单词查找树的性质 483
5.2.3三向单词查找树 485
5.2.4三向单词查找树的性质 487
5.2.5应该使用字符串符号表的哪种实现 489
5.3子字符串查找 493
5.3.1历史简介 493
5.3.2暴力子字将串查找算法 494
5.3.3 Knuth-Morris-Pratt子字符串查找算法 496
5.3.4 Boyer-Moore字符串查找算法 502
5.3.5 Rabin-Karp指纹字符串查找算法 505
5.3.6总结 509
5.4正则表达式 514
5.4.1使用正则表达式描述模式 514
5.4.2缩略写法 516
5.4.3正则表达式的实际应用 517
5.4.4非确定有限状态自动机 518
5.4.5模拟NFA的运行 520
5.4.6构造与正则表达式对应的NFA 522
5.5数据压缩 529
5.5.1游戏规则 529
5.5.2读写二进制数据 530
5.5.3局限 533
5.5.4热身运动：基因组 534
5.5.5游程编码 537
5.5.6霍夫曼压缩 540
第6章 背景 558
索引 611