第1章 Java面向对象的程序设计 1
1.1 对象与封装 1
1.1.1 对象 1
1.1.2 生存期、状态和消息 2
1.1.3 对象的客户 2
1.1.4 接口与实现的分离 2
1.2 类 2
1.2.1 状态与行为 3
1.2.2 方法重载 4
1.2.3 对象创建、构造器及垃圾回收 4
1.2.4 方法调用 7
1.2.5 静态域和静态方法 7
1.2.6 对象引用 9
1.3 继承 9
1.3.1 超类与子类 9
1.3.2 继承域与特化域 11
1.3.3 构造器 11
1.3.4 创建对象 12
1.3.5 继承方法和特化方法 12
1.3.6 方法覆盖 13
1.4 类Object 13
1.4.1 方法equals 14
1.4.2 方法toString 15
1.4.3 方法clone 15
1.5 异常 16
1.5.1 异常消息的解释 16
1.5.2 特有的错误处理 18
1.5.3 抛出异常 22
1.5.4 捕获异常 23
1.5.5 异常类 27
1.6 输入与输出 28
1.6.1 终端驱动IO 28
1.6.2 基于文件的输入与输出 29
1.6.3 字符串分解 32
1.6.4 编写异常类 33
1.7 类包 34
1.7.1 Java包 34
1.7.2 组建包 35
1.7.3 名字冲突解析 38
1.8 访问控制 39
1.8.1 私有访问 39
1.8.2 包访问 39
1.8.3 受保护访问 39
1.8.4 公有访问 40
1.8.5 一个例子 40
1.9 多态性 40
1.9.1 多态引用 41
1.9.2 提升类层次 42
1.9.3 降低类层次 42
1.9.4 instanceof操作符 43
1.10 抽象类 44
1.10.1 抽象类Shape 44
1.10.2 抽象类的性质 44
1.11 游乐园的例子 45
1.12 接口 47
1.12.1 Java接口结构 47
1.12.2 实现接口 47
1.12.3 接口作为类型 48
1.12.4 对接口的需求 48
1.12.5 扩展接口 49
1.13 通用性 49
1.13.1 把java.util.ArrayList用于集合 50
1.13.2 java.util.ArrayList的公有接口 51
1.13.3 通用类的实现 52
1.13.4 通用接口的实现 52
1.13.5 静态模板方法 54
1.14 总结 56
1.15 练习 58
1.16 程序设计问题 59
第2章 数据结构概观 62
2.1 什么是数据结构 62
2.2 我们学习什么数据结构 62
2.3 什么是抽象数据类型 64
2.4 OOP和Java在数据结构有什么优势 65
2.5 如何选择正确的数据结构 67
第3章 算法的效率 69
3.1 多项式的算术运算：一个具体例子 69
3.2 基本操作 70
3.3 输入规模 72
3.4 函数的渐近增长 72
3.5 阶与大0 73
3.5.1 典型运行时间的阶 75
3.5.2 多变元的阶 77
3.5.3 阶的相对顺序 77
3.5.4 阶的算术运算 78
3.6 最坏情况与平均情况 78
3.7 总结 80
3.8 练习 81
第4章 无序列表 84
4.1 无序列表的性质 84
4.2 顺序搜索 85
4.2.1 平均情况分析 86
4.2.2 基于搜索模式的数据重排列 87
4.3 类List 88
4.4 使用List的类ExpenseList 89
4.4.1 类Expense的接口 89
4.4.2 类Expense 90
4.4.3 类ExpenseList的接口 91
4.4.4 类ExpenseList的实现 92
4.4.5 对象的相等与搜索 94
4.5 链表 96
4.5.1 节点的定义 97
4.5.2 插入操作 98
4.5.3 删除操作 99
4.5.4 访问操作 100
4.5.5 循环链表 100
4.6 类LinkedList 102
4.7 类List的实现 106
4.8 总结 107
4.9 练习 108
4.10 程序设计问题 109
第5章 有序列表 112
5.1 介绍 112
5.2 二分搜索 113
5.2.1 分成两半 113
5.2.2 算法 114
5.3 排序：接口java.lang.Comparable 115
5.4 类OrderedList 117
5.5 合并有序列表 119
5.6 使用OrderedList的列表归并 123
5.6.1 Merger：一个实用类 123
5.6.2 归并类 125
5.7 类OrderedList的实现 126
5.8 总结 128
5.9 练习 129
5.10 程序设计问题 131
第6章 队列 133
6.1 队列的性质 133
6.2 UNIX打印队列 134
6.3 类Queue 135
6.4 使用Queue的类PrintQueue 136
6.5 类Queue的实现 139
6.5.1 设计1：使用基于数组的存储 139
6.5.2 设计2：使用LinkedList 141
6.6 总结 142
6.7 练习 143
6.8 程序设计问题 144
第7章 栈 146
7.1 栈的性质 146
7.2 栈的应用 147
7.2.1 括号匹配 147
7.2.2 后缀表达式求值 147
7.2.3 中缀表达式到后缀表达式的转换 149
7.3 类Stack 149
7.4 后缀表达式求值包 150
7.4.1 类PostfixEvaluator 150
7.4.2 类StatusKeeper 152
7.4.3 类StackKeeper 152
7.4.4 类PostfixEvaluator的实现 154
7.5 类Stack的实现 155
7.5.1 设计1：使用数组列表进行存储 156
7.5.2 设计2：使用链表进行存储 156
7.6 总结 157
7.7 练习 157
7.8 程序设计问题 159
第8章 递归 161
8.1 递归定义 161
8.1.1 列表 161
8.1.2 有序列表 162
8.1.3 阶乘函数 163
8.1.4 斐波那契数列 163
8.2 递归程序与退回 164
8.2.1 计算阶乘 164
8.2.2 计算斐波那契数列 166
8.2.3 关于链表的递归 166
8.3 对数组的递归：二分搜索 168
8.4 汉诺塔：一个应用 168
8.4.1 递归定义 169
8.4.2 递归程序 170
8.5 递归与栈 171
8.6 递归的缺点 171
8.7 尾递归 172
8.8 总结 174
8.9 练习 174
8.10 程序设计问题 175
第9章 二叉树和普通树 178
9.1 二叉树的性质 178
9.1.1 组件 178
9.1.2 节点位置代表的意义 179
9.1.3 结构 180
9.1.4 递归定义 181
9.2 二叉树的遍历 182
9.3 类BinaryTree 184
9.4 二叉树的存储与重构 186
9.4.1 二叉树的署名 187
9.4.2 从二叉树的署名构建二叉树 188
9.5 赫夫曼编码 190
9.5.1 统计编码与字典编码 190
9.5.2 算法 190
9.5.3 平均代码长度和前缀性质 191
9.5.4 使用BinaryTree的类Huffman 192
9.6 类BinaryTree的实现 196
9.7 基于栈的遍历 198
9.7.1 二叉树的中序遍历 198
9.7.2 类Visitor 200
9.8 普通树 200
9.8.1 例子：大学中的组织层次 200
9.8.2 例子：UNIX文件系统 200
9.8.3 实现中的空间问题 201
9.8.4 与二叉树的对应关系 202
9.8.5 普通树的署名 203
9.9 总结 204
9.10 练习 205
9.11 程序设计问题 207
第10章 二叉查找树和AVL树 210
10.1 比较树 210
10.1.1 使用比较树的搜索时间 211
10.1.2 比较树的高度 212
10.2 二叉查找树的性质 213
10.3 二叉查找树的操作 214
10.3.1 搜索操作 214
10.3.2 插入操作 215
10.3.3 删除操作 215
10.4 类BinarySearchTree 217
10.5 使用类BinarySearchTree 218
10.5.1 例子：树排序 218
10.5.2 例子：计数关键字 219
10.6 类BinarySearchTree的实现 220
10.6.1 搜索操作的实现 220
10.6.2 插入操作的实现 220
10.6.3 删除操作的实现 221
10.6.4 便利方法与遍历 223
10.7 AVL树 223
10.7.1 AVL树结构 224
10.7.2 搜索、插入和删除操作概述 225
10.7.3 旋转操作 225
10.7.4 插入操作 226
10.7.5 删除操作 227
10.7.6 AVL树操作的运行时间 231
10.7.7 AVL插入和删除：一般化 231
10.8 二分搜索：平均比较次数 234
10.9 总结 236
10.10 练习 236
10.11 程序设计问题 239
第11章 堆 241
11.1 作为优先队列的堆 241
11.2 堆的性质 242
11.3 堆的操作 242
11.3.1 插入操作 243
11.3.2 删除操作 243
11.3.3 运行时间分析 244
11.4 类Heap 244
11.5 使用堆的优先调度 245
11.5.1 纵览 245
11.5.2 使用堆的调度包 246
11.6 使用类Heap的排序 250
11.7 类Heap的实现 251
11.7.1 数组存储 251
11.7.2 使用ArrayList的实现 253
11.8 可更新堆 254
11.8.1 设计一个可更新堆 254
11.8.2 堆项的句柄 255
11.8.3 共享句柄数组 255
11.8.4 在堆中封装句柄 255
11.8.5 循环使用空闲句柄空间 256
11.9 总结 256
11.10 练习 257
11.11 程序设计问题 258
第12章 散列表 260
12.1 动机 260
12.2 散列 261
12.3 冲突解决方案 262
12.3.1 线性探查法 262
12.3.2 二次探查法 263
12.3.3 链表法 264
12.3.4 运行时间比较 265
12.4 类java.util.HashMap 265
12.4.1 表和负载因子 266
12.4.2 项的存储 267
12.4.3 添加项 267
12.4.4 再散列过程 269
12.4.5 搜索操作 270
12.5 二次探查法：探查位置的重复 270
12.6 总结 271
12.7 练习 271
12.8 程序设计问题 272
第13章 排序 273
13.1 插入排序 273
13.2 用分治法排序 275
13.2.1 快速排序 276
13.2.2 归并排序 280
13.3 堆排序 281
13.3.1 以线性时间构建堆 281
13.3.2 排序堆 283
13.4 基数排序 283
13.5 实现：类Quicksort 285
13.6 构建堆：线性运行时间 287
13.7 总结 288
13.8 练习 288
13.9 程序设计问题 290
第14章 图I：算法 292
14.1 使用图模拟关系 292
14.1.1 无向图 292
14.1.2 有向图 293
14.1.3 加权图 295
14.2 图的表示 295
14.3 图的遍历 297
14.3.1 无向图的深度优先搜索 297
14.3.2 无向图的广度优先搜索 298
14.3.3 遍历驱动器 299
14.3.4 有向图的遍历 300
14.4 有向图的拓扑排序 301
14.4.1 偏序和全序 301
14.4.2 拓扑编号 302
14.4.3 使用深度优先搜索的拓扑排序 302
14.4.4 使用广度优先搜索的拓扑排序 304
14.5 无向图的连通分支 305
14.6 加权有向图中的最短路径 306
14.7 总结 311
14.8 练习 311
第15章 图Ⅱ：实现 314
15.1 有向图类：DirGraph 314
15.1.1 顶点编号 315
15.1.2 类Neighbor 316
15.1.3 运用类DirGraph 317
15.2 无向图类：UndirGraph 317
15.3 深度优先搜索类：DFS 319
15.3.1 设计与接口 319
15.3.2 类Visitor 320
15.3.3 DFS的实现 321
15.4 拓扑排序类：DFSTopsort 322
15.4.1 TopVisitor：扩展类Visitor 322
15.4.2 DFSTopsort的实现 322
15.5 连通分支类：DFSConncomp 323
15.5.1 ConnVisitor：扩展类Visitor 323
15.5.2 DFSConncomp的实现 324
15.6 最短路径类：ShortestPaths 324
15.6.1 WeightedNeighbor：扩展类Neighbor 325
15.6.2 ShortestPaths的实现 325
15.7 图的实现 328
15.7.1 DirGraph的实现 328
15.7.2 类UndirGraph的实现 331
15.7.3 加权图的实现 331
15.8 总结 332
15.9 程序设计问题 332
索引 335