第1章 Java语言的面向对象编程 1
1.1 Java入门 1
1.1.1 变量的声明 1
1.1.2 运算符 3
1.1.3 选择语句 3
1.1.4 循环语句 4
1.1.5 异常处理 5
1.2 Java面向对象编程 6
1.2.1 封装 6
1.2.2 抽象数据类型 12
1.2.3 继承 13
1.2.4 多态性 16
1.3 输入和输出 19
1.3.2 行输入 21
1.3.1 输入、输出字节 21
1.3.3 标志输入：单词和数字 22
1.3.4 基本数据类型的输入和输出 22
1.3.5 对象的输入和输出 23
1.3.6 随机存取文件 24
1.4 Java和指针 24
1.5 java.util中的向量 28
1.6 数据结构和面向对象的编程 32
1.7 示例学习：随机存取文件 32
1.8 习题 39
1.9 编程作业 41
参考文献 42
第2章 复杂性分析 44
2.1 计算复杂性和渐近复杂性 44
2.2 大O表示法 44
2.3 大O表示法的性质 46
2.4 Ω和？表示法 47
2.5 可能出现的问题 48
2.6 复杂性示例 48
2.7 寻找渐近复杂性：示例 49
2.8 最好的、平均的和最坏的情况 51
2.9 平摊复杂性 53
2.10 NP完整性 56
2.11 习题 58
参考文献 60
第3章 链表 62
3.1 单向链表 62
3.1.1 插入 66
3.1.2 删除 67
3.1.3 查找 70
3.2 双向链表 72
3.3 循环链表 74
3.4 跳转表 75
3.5 自组织表 80
3.6 稀疏表 83
3.7 java.util的链表 85
3.7.1 LinkedList 85
3.7.2 ArrayList 89
3.8 结论 91
3.9 示例学习：图书馆 92
3.10 习题 99
3.11 编程作业 101
参考文献 103
第4章 堆栈和队列 105
4.1 堆栈 105
4.2 队列 111
4.3 优先级队列 117
4.4 示例学习：脱离迷宫 118
4.5 习题 122
4.6 编程作业 124
参考文献 125
第5章 递归 126
5.1 递归定义 126
5.2 方法调用和递归实现 128
5.3 剖析递归调用 129
5.4 尾递归 132
5.5 非尾递归 133
5.6 间接递归 137
5.7 嵌套递归 139
5.8 过分递归 139
5.9 回溯 142
5.11 示例学习：递归下降解释器 147
5.10 小结 147
5.12 习题 153
5.13 编程作业 155
参考文献 157
第6章 二叉树 158
6.1 树、二叉树和二叉查找树 158
6.2 二叉树实现 161
6.3 搜索二叉查找树 163
6.4 树的遍历 164
6.4.1 广度优先遍历 165
6.4.2 深度优先遍历 165
6.4.3 无堆栈深度优先遍历 171
6.5 插入 175
6.6 删除 178
6.6.1 归并删除法 179
6.6.2 复制删除法 181
6.7 树的平衡 183
6.7.1 DSW算法 185
6.7.2 AVL树 187
6.8 自调整树 191
6.8.1 自重构树 192
6.8.2 伸展树 192
6.9 堆 196
6.9.1 堆作为优先级队列 197
6.9.2 以堆的形式组织数组 199
6.10 波兰表示法和表达式树 202
6.11 示例学习：计算单词频率 206
6.12 习题 212
6.13 编程作业 214
参考文献 217
第7章 多分树 220
7.1 B树家族 220
7.1.1 B树 221
7.1.2 B树 229
7.1.3 B＋树 230
7.1.4 前缀B＋树 232
7.1.5 比特树 233
7.1.6 R树 235
7.1.7 2-4树 236
7.1.8 java.util中的树 248
7.2 检索树 257
7.3 结论 264
7.4 示例学习：拼写检查程序 264
7.5 习题 273
7.6 编程作业 274
参考文献 277
第8章 图 279
8.1 图的表示法 280
8.2 图的遍历 281
8.3 最短路径 284
8.4 圈检测 291
8.5 生成树 293
8.6 连通性 297
8.6.1 无向图的连通性 297
8.6.2 有向图的连通性 300
8.7 拓扑排序 302
8.8 网络 303
8.8.1 最大流 303
8.8.2 最小代价的最大流量 311
8.9 匹配 313
8.9.1 稳定匹配问题 318
8.9.2 分配问题 319
8.9.3 非二部图中的匹配 321
8.10 欧拉图和哈密顿图 322
8.10.1 欧拉图 322
8.10.2 哈密顿图 324
8.11 图的着色 329
8.12 图论中的NP完整性问题 331
8.12.1 团问题 331
8.12.2 3色问题 332
8.12.3 顶点覆盖问题 333
8.12.4 哈密顿回路问题 333
8.13 示例学习：典型代表问题 335
8.14 习题 336
8.15 编程作业 345
参考文献 346
第9章 排序 349
9.1 基本排序算法 350
9.1.1 插入排序 350
9.1.2 选择排序 352
9.1.3 冒泡排序 353
9.2 决策树 355
9.3 高效排序算法 357
9.3.1 Shell排序 357
9.3.2 堆排序 360
9.3.3 快速排序 363
9.3.4 归并排序 367
9.3.5 基数排序 370
9.4 java.util中的排序 373
9.5 总结 375
9.6 示例学习：多项式加法 376
9.7 习题 383
9.8 编程作业 384
参考文献 384
第10章 散列 387
10.1 散列函数 387
10.1.1 除法 387
10.1.2 折叠法 388
10.1.3 平方取中函数 388
10.1.4 提取方法 388
10.1.5 基数变换 388
10.2 冲突解决 389
10.2.1 开放定址法 389
10.2.2 链 393
10.2.3 桶定址法 394
10.3 删除 394
10.4 完全散列函数 395
10.4.1 Cichelli方法 396
10.4.2 FHCD算法 398
10.5 可扩展文件的散列函数 400
10.5.1 可扩展散列 400
10.5.2 线性散列 402
10.6 java.util中的散列 404
10.6.1 HashMap 404
10.6.2 HashSet 407
10.6.3 Hashtable 410
10.7 示例学习：桶散列 414
10.8 习题 421
10.9 编程作业 422
参考文献 423
11.1 数据压缩的条件 425
第11章 数据压缩 425
11.2 赫夫曼编码 426
11.3 顺串长度编码 436
11.4 Ziv-Lempel编码 437
11.5 示例学习：结合顺串长度编码的赫夫曼方法 439
11.6 习题 448
11.7 编程作业 448
参考文献 449
第12章 存储管理 451
12.1 顺序适配方法 451
12.2 非顺序适配算法 452
12.3 无用单元收集 459
12.3.1 标记和清除算法 459
12.3.2 复制方法 465
12.3.3 增量式无用单元收集 466
12.4 总结 471
12.5 示例学习：内置无用单元收集器 472
12.6 习题 473
12.7 编程作业 479
参考文献 481
第13章 字符串匹配 484
13.1 精确字符串匹配 484
13.1.1 直接匹配算法 484
13.1.2 Knuth-Morris-Pratt算法 486
13.1.3 Boyer-Moore算法 492
13.1.4 多路查找 500
13.1.5 面向位方法 501
13.1.6 词匹配集 504
13.1.7 正则表达式匹配 510
13.1.8 后缀检索树和树 513
13.1.9 后缀数组 517
13.2 近似字符串匹配 518
13.2.1 字符串相似度 519
13.2.2 k误配的字符串匹配 524
13.3 示例学习：最长公共子字符串 526
13.4 习题 533
13.5 编程作业 535
参考文献 535
附录A 大O的计算 537
A.1 谐波级数 537
A.2 函数lg（n！）的近似 537
A.3 快速排序平均情况的大O 538
A.4 随机二叉树中的平均路径长度 540
A.5 AVL树中的节点数量 541
附录B NP完整性 542
索引 554