第1章 Java综述 1
1.1 简介 2
1.2 Java程序结构 2
1.2.1 独立运行的程序和Applet 2
1.2.2 包 3
1.2.3 引入类和包 4
1.2.4 超类和子类 4
1.3 Java编译器和虚拟机 5
1.4 文档注释 6
1.5 数据类型 7
1.6 方法 8
1.6.1 参数 8
1.6.2 重载方法 9
1.7 异常 10
1.7.1 抛出一个异常 10
1.7.2 处理异常 11
1.8 自定义数据类型 12
1.8.1 Currency类 12
1.8.2 Currency的数据成员 13
1.8.3 Currency的方法成员 14
1.8.4 Currency的构造函数 14
1.8.5 创建Currency的实例 15
1.8.6 Currency的存取器（获取）方法 15
1.8.7 Currency的存取器（设置）方法 16
1.8.8 调用方法和访问数据成员 17
1.8.9 Currency的输出和算术方法 18
1.8.10 main方法 19
1.9 访问修饰符 21
1.10 继承和方法重写 21
1.11 重访Currency 23
1.12 定义一个异常类 25
1.13 泛型方法 26
1.13.1 Computable接口 26
1.13.2 泛型方法abc 27
1.13.3 java.lang.Comparable接口 28
1.13.4 Operable接口 28
1.13.5 Zero和CloneableObject接口 28
1.13.6 MyInteger封装类 29
1.13.7 使用数据类型和方法作为参数 29
1.14 垃圾收集 33
1.15 递归 33
1.15.1 递归函数 33
1.15.2 归纳 34
1.15.3 递归方法 35
1.16 测试和调试 39
1.16.1 什么是测试 39
1.16.2 设计测试数据 41
1.16.3 调试 43
1.17 参考资料和选择性读物 44
第2章 性能分析 45
2.1 什么是性能 45
2.2 空间复杂度 46
2.2.1 空间复杂度的组成 46
2.2.2 范例 49
2.3 时间复杂度 51
2.3.1 时间复杂度的组成 51
2.3.2 运算计数 52
2.3.3 最佳、最差和平均运算计数 56
2.3.4 步骤计数 61
第3章 渐近表示法 73
3.1 简介 73
3.2 渐近表示法 75
3.2.1 O表示法 75
3.2.2 Ω和Θ表示法 77
3.3 渐近数学（可选） 79
3.3.1 O表示法 79
3.3.2 Ω表示法 81
3.3.3 Θ表示法 82
3.3.4 o表示法 84
3.3.5 属性 84
3.4 复杂度分析范例 86
3.5 实用的复杂度 89
3.6 参考资料和选择性读物 91
第4章 性能测量 92
4.1 简介 92
4.2 选择实例规模 92
4.3 开发测试数据 93
4.4 建立试验 93
4.5 缓存管理 98
4.5.1 一个简单的计算机模型 98
4.5.2 遗漏缓存对运行时间的影响 99
4.5.3 矩阵乘法 99
4.6 参考资料和选择性读物 102
第5章 线性列表——数组表示形式 103
5.1 数据对象和结构 104
5.2 线性列表数据结构 105
5.2.1 抽象数据类型LinearList 105
5.2.2 LinearList接口 105
5.2.3 LinearListAsAbstractClass抽象类 106
5.3 数组表示形式 108
5.3.1 表示形式 108
5.3.2 改变一维数组的长度 109
5.3.3 类ArrayLinearList 110
5.3.4 ArrayLinearList的Iterator 114
5.4 矢量表示形式 121
5.5 在单个数组中的多个列表 124
5.6 性能测量 126
5.7 java.util.ArrayList类 128
5.8 参考资料和选择性读物 129
第6章 线性列表——链表表示 130
6.1 单向链表和链 131
6.1.1 表示形式 131
6.1.2 ChainNode类 132
6.1.3 Chain类 133
6.1.4 对ADT LinearList的扩展 137
6.1.5 ExtendedChain类 138
6.1.6 性能测量 139
6.2 循环列表和头节点 144
6.3 双向链表 146
6.4 链表术语表 147
6.5 应用 148
6.5.1 箱排序 148
6.5.2 基数排序 151
6.5.3 凸包 153
第7章 线性列表——模拟指针 158
7.1 需要模拟指针 158
7.2 模拟指针 159
7.3 内存管理 160
7.3.1 SimulatedSpace1类 161
7.3.2 SimulatedSpace2类 162
7.3.3 评价模拟内存管理 162
7.4 与垃圾收集比较 163
7.5 模拟链 164
7.5.1 SimulatedChain类 164
7.5.2 性能测量 165
7.6 内存管理链 167
7.7 应用程序——并查问题 168
7.7.1 等价类 168
7.7.2 应用程序 169
7.7.3 第一个并查解决方案 171
7.7.4 第二个并查解决方案 171
第8章 数组和矩阵 175
8.1 数组 175
8.1.1 抽象数据类型 175
8.1.2 对一个Java数组进行索引 176
8.1.3 行优先和列优先的映射 176
8.1.4 数组的数组表示形式 178
8.1.5 行优先和列优先的表示形式 178
8.1.6 不规则的二维数组 179
8.2 矩阵 180
8.2.1 定义和操作 180
8.2.2 Matrix类 182
8.3 特殊矩阵 186
8.3.1 定义和应用程序 186
8.3.2 对角线矩阵 188
8.3.3 三对角线矩阵 190
8.3.4 三角形矩阵 190
8.3.5 对称矩阵 191
8.4 稀疏矩阵 194
8.4.1 目的 194
8.4.2 使用单线性表的表示 195
8.4.3 使用多线性表的表示 202
8.4.4 性能测量 204
第9章 堆栈 208
9.1 定义和应用 208
9.2 抽象数据类型 210
9.3 数组表示 211
9.3.1 实现为子类 211
9.3.2 类arrayStack 213
9.3.3 性能测量 214
9.4 链式表示 217
9.4.1 类DerivedLinkedStack 217
9.4.2 类LinkedStack 217
9.4.3 性能测量 218
9.5 应用 219
9.5.1 括号匹配 219
9.5.2 汉诺塔 220
9.5.3 重排有轨电车 222
9.5.4 开关箱路由 227
9.5.5 离线等价类问题 229
9.5.6 迷宫中的老鼠 232
9.6 参考资料和选择性读物 241
第10章 队列 242
10.1 定义和应用 242
10.2 抽象数据类型 243
10.3 数组表示 244
10.3.1 表示方法 244
10.3.2 ArrayQueue类 246
10.4 链式表示 249
10.5 应用 252
10.5.1 有轨电车的重新安排 252
10.5.2 线路路由 254
10.5.3 图像组件编号 257
10.5.4 机械工厂模拟 260
10.6 参考资料和选择性读物 272
第11章 跳表和散列表 273
11.1 字典 273
11.2 抽象数据类型 275
11.3 线性表表示 276
11.4 跳表表示（可选） 278
11.4.1 理想情形 278
11.4.2 插入和删除 279
11.4.3 分配层级 280
11.4.4 类SkipNode 280
11.4.5 类SkipList 281
11.4.6 SkipList方法的复杂度 285
11.5 散列表表示 285
11.5.1 理想散列 285
11.5.2 散列函数和散列表 287
11.5.3 线性探查法 290
11.5.4 使用链表的散列 295
11.6 一个应用——文本压缩 300
11.6.1 LZW压缩 301
11.6.2 LZW压缩的实现 302
11.6.3 LZW解压缩 306
11.6.4 LZW解压缩的实现 306
11.6.5 性能评估 309
11.7 参考资料和选择性读物 311
第12章 二叉树和其他树 312
12.1 树 312
12.2 二叉树 315
12.3 二叉树的属性 316
习题 318
12.4 二叉树的表示 318
12.4.1 基于数组的表示 318
12.4.2 链接表示 319
12.5 常见的二叉树操作 320
12.6 二叉树遍历 320
12.7 ADT BinaryTree 325
12.8 类LinkedBinaryTree 326
12.9 应用 329
12.9.1 信号放大器的布置 329
12.9.2 并查（Union-Find）问题 334
12.10 参考资料和选择性读物 343
第13章 优先级队列 344
13.1 定义和应用 344
13.2 抽象数据类型 345
13.3 线性表 346
13.4 堆 347
13.4.1 定义 347
13.4.2 插入元素到最大堆 348
13.4.3 从最大堆中删除元素 348
13.4.4 最大堆的初始化 349
13.4.5 MaxHeap类 350
13.5 左倾树 354
13.5.1 基于高度和基于宽度的最小和最大左倾树 354
13.5.2 插入到最大HBLT 356
13.5.3 从最大HBLT中删除 356
13.5.4 合并两棵最大HBLT 356
13.5.5 初始化 358
13.5.6 MaxHBLT类 358
13.6 应用 362
13.6.1 堆排序 362
13.6.2 机器调度 363
13.6.3 哈夫曼编码 366
13.7 参考资料和选择性读物 371
第14章 比赛树 373
14.1 优胜树及其应用 373
14.2 抽象数据类型WinnerTree 377
14.3 优胜树的实现 377
14.3.1 表示 377
14.3.2 初始化一棵优胜树 378
14.3.3 重新进行比赛 378
14.3.4 类CompleteWinnerTree 378
14.4 失败树 379
14.5 应用 381
14.5.1 使用首次适应法的容器装包 381
14.5.2 使用下一适应法的容器装包 385
14.6 参考资料和选择性读物 388
第15章 二叉搜索树 389
15.1 定义 390
15.1.1 二叉搜索树 390
15.1.2 可索引二叉搜索树 391
15.2 抽象数据类型 392
15.3 二叉搜索树的操作及其实现 393
15.3.1 BinarySearchTree类 393
15.3.2 搜索 393
15.3.3 插入一个元素 394
15.3.4 删除一个元素 395
15.3.5 二叉搜索树的高度 397
15.4 有重复记录的二叉搜索树 399
15.5 索引的二叉搜索树 400
15.6 应用 401
15.6.1 柱状图 401
15.6.2 最优容器装包 404
15.6.3 交叉分配 406
第16章 平衡搜索树 413
16.1 AVL树 414
16.1.1 定义 414
16.1.2 AVL树的高度 415
16.1.3 AVL树的表示 415
16.1.4 AVL搜索树的搜索 415
16.1.5 AVL搜索树的插入 415
16.1.6 从AVL搜索树中删除 418
16.2 红黑树 421
16.2.1 定义 421
16.2.2 红黑树的表示 423
16.2.3 红黑树的搜索 423
16.2.4 红黑树的插入 423
16.2.5 从红黑树中删除 427
16.2.6 实现的考虑和复杂度 430
16.3 伸展树 432
16.3.1 引言 432
16.3.2 伸展操作 432
16.3.3 分摊复杂度 434
16.4 B-树 436
16.4.1 索引顺序存取法（ISAM） 436
16.4.2 m-叉搜索树 436
16.4.3 m叉排序B-树 438
16.4.4 B-树的高度 439
16.4.5 搜索B-树 439
16.4.6 插入元素到B-树 440
16.4.7 从B-树中删除 442
16.4.8 节点结构 445
16.5 参考资料和选择性读物 446
第17章 图 447
17.1 定义 447
17.2 应用和更多的定义 449
习题 451
17.3 属性 452
17.4 ADT Gaph 453
17.5 不带权值的图的表示 454
17.5.1 邻接矩阵 455
17.5.2 链式邻接表 456
17.5.3 数组邻接表 457
17.6 带权图的表示形式 458
17.7 类的实现 459
17.7.1 不同的类 459
17.7.2 邻接矩阵类 460
17.7.3 到类Chain的扩展 463
17.7.4 链表类 464
17.8 图的搜索方法 466
17.8.1 广度优先搜索 466
17.8.2 广度优先搜索的实现 468
17.8.3 Graph.bfs的复杂度分析 468
17.8.4 深度优先搜索 470
17.8.5 深度优先搜索的实现 471
17.8.6 Graph.dfs的复杂度分析 471
17.9 重访的应用 472
17.9.1 查找路径 472
17.9.2 连通图和连通分量 474
17.9.3 生成树 476
第18章 贪婪方法 479
18.1 最优化问题 479
18.2 贪婪方法 480
18.3 应用 483
18.3.1 集装箱装载 483
18.3.2 0/1背包问题 485
18.3.3 拓扑排序 487
18.3.4 二分覆盖 490
18.3.5 单源最短路径 493
18.3.6 最小生成树 497
18.4 参考资料和选择性读物 507
第19章 分而治之 508
19.1 方法 508
19.2 应用 515
19.2.1 缺陷棋盘 515
19.2.2 归并排序 517
19.2.3 快速排序 522
19.2.4 选择 528
19.2.5 最近顶点对 530
19.3 求解递归等式 538
19.4 复杂度下界 540
19.4.1 最小最大问题的下界 541
19.4.2 排序的下界 542
第20章 动态规划 544
20.1 方法 544
20.2 应用 546
20.2.1 0/1背包问题 546
20.2.2 矩阵乘法链 550
20.2.3 所有对最短路径 555
20.2.4 带负值的单源最短路径 558
20.2.5 不相交网子集 562
20.3 参考资料和选择性读物 568
第21章 回溯法 569
21.1 方法 569
21.2 应用 574
21.2.1 集装箱装载 574
21.2.2 0/1背包问题 581
21.2.3 最大集团 584
21.2.4 旅行售货员 587
21.2.5 电路板排列 589
第22章 分支限界法 595
22.1 方法 595
22.2 应用 598
22.2.1 集装箱装载 598
22.2.2 0/1背包问题 605
22.2.3 最大集团 607
22.2.4 旅行售货员 609
22.2.5 电路板排列 612