目录：

第1章 基 础 .............................................. .. ....................................................1
1..1 基础编程模型 .......................................................................... 4
1..1..1 Java程序的基本结构 .................................. 4
1..1..2原始数据类型与表达式 .......................... 6
1..1..3 语句..................................................................................8
1..1..4 简便记法 ....................................................................9
L1..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
L4..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