第1章 面向对象编程 1
1.1 软件设计和开发 1
1.2 面向对象设计 2
1.3 抽象数据类型 3
1.4 Java接口 4
1.5 类和对象 5
1.6 修饰符 9
1.7 组合、聚合和继承 11
1.8 统一建模语言 14
1.9 多态 16
1.10 Javadoc 18
复习题 19
习题 19
复习题答案 21
习题答案 22
第2章 数组 30
2.1 数组特性 30
2.2 数组复制 32
2.3 java.util.Array类 33
2.4 顺序查找算法 35
2.5 折半查找算法 36
复习题 38
习题 39
复习题答案 44
习题答案 44
第3章 链接的数据结构 58
3.1 维护有序阵列 58
3.2 间接引用 59
3.3 链接的结点 62
3.4 将元素插入到链接列表 69
3.5 在列表头插入元素 72
3.6 从有序链接列表删除元素 74
3.7 嵌入类 75
复习题 77
习题 78
复习题答案 80
习题答案 80
第4章 Java集合框架 87
4.1 继承层次结构 87
4.2 Collection接口 88
4.3 HashSet类 90
4.4 泛型集合 92
4.5 泛型方法 94
4.6 泛型通配符 95
4.7 迭代器 96
4.8 TreeSet类 99
4.9 LinkedHashSet类 103
4.10 EnumSet类 103
4.11 List接口 105
4.12 ArrayList和Vector类 106
4.13 LinkedList类 107
4.14 ListIterator接口 108
4.15 Queue接口 108
4.16 PriorityQueue类 111
4.17 Deque接口和ArrayDeque类 112
4.18 Map接口及其实现类 114
4.19 Arrays类 117
4.20 Collections类 118
4.21 自动装箱 120
复习题 121
习题 122
复习题答案 123
习题答案 124
第5章 栈 127
5.1 栈操作 127
5.2 JCF Stack类 127
5.3 Stack接口 128
5.4 使用索引的实现 129
5.5 使用链接的实现 131
5.6 将公共代码抽象化 133
5.7 应用：RPN计算器 134
复习题 137
习题 137
复习题答案 140
习题答案 141
第6章 队列 147
6.1 队列操作 147
6.2 JCF Queue接口 147
6.3 简单的Queue接口 148
6.4 使用索引的实现：数组方式 149
6.5 使用索引的实现：双向链表 151
6.6 应用：客户—服务器系统 153
复习题 159
习题 159
复习题答案 161
习题答案 161
第7章 线性表 167
7.1 JCF List接口 167
7.2 范围视图操作sublist（） 168
7.3 线性表迭代器 170
7.4 其他线性表类型 174
7.5 应用：Josephus问题 178
7.6 应用：Polynomial类 180
复习题 185
习题 185
复习题答案 186
习题答案 187
第8章 哈希表 190
8.1 Java的Map接口 190
8.2 HashMap类 191
8.3 Java的哈希码 193
8.4 哈希表 194
8.5 哈希表的性能 196
8.6 冲突消解算法 197
8.7 独立链 201
8.8 应用 202
8.9 TreeMap类 205
复习题 206
习题 206
复习题答案 207
习题答案 208
第9章 递归 211
9.1 简单的递归函数 211
9.2 递归基础条件和递归部分 212
9.3 跟踪递归调用 214
9.4 递归折半查找算法 215
9.5 二项式系数 217
9.6 欧几里得算法 218
9.7 正确性的归纳证明 219
9.8 复杂性分析 220
9.9 动态规划 221
9.10 汉诺塔 222
9.11 互递归 224
复习题 227
习题 227
复习题答案 229
习题答案 229
第10章 树 239
10.1 树的定义 239
10.2 决策树 241
10.3 迁移图 242
10.4 有序树 244
10.5 遍历算法 245
复习题 247
习题 249
复习题答案 250
习题答案 251
第11章 二叉树 254
11.1 定义 254
11.2 二叉树的计数 255
11.3 满二叉树 256
11.4 相同、相等和同构 257
11.5 完全二叉树 259
11.6 二叉树遍历算法 261
11.7 表达式树 263
11.8 二叉树类BinaryTree 265
11.9 遍历算法的实现 271
11.10 森林 276
复习题 276
习题 277
复习题答案 279
习题答案 280
第12章 搜索树 287
12.1 多路搜索树 287
12.2 B-树 289
12.3 二叉搜索树 292
12.4 二叉搜索树的性能 293
12.5 AVL树 294
复习题 298
习题 298
复习题答案 299
习题答案 299
第13章 堆和优先级队列 303
13.1 堆 303
13.2 自然映射 303
13.3 堆的插入 304
13.4 堆的删除 305
13.5 优先级队列 306
13.6 JCF PriorityQueue类 306
复习题 308
习题 309
复习题答案 310
习题答案 310
第14章 排序 314
14.1 代码说明 314
14.2 Java的Arrays.sort（）方法 315
14.3 冒泡排序 316
14.4 选择排序 317
14.5 插入排序 318
14.6 SHELL排序 319
14.7 归并排序 320
14.8 快速排序 324
14.9 堆排序 327
14.10 比较排序的速度限制 331
14.11 基数排序 331
14.12 桶排序 333
复习题 336
习题 338
复习题答案 340
习题答案 342
第15章 图 352
15.1 简单图 352
15.2 图的术语 352
15.3 路径与回路 353
15.4 同构图 355
15.5 图的邻接矩阵 357
15.6 图的关联矩阵 358
15.7 图的邻接表 358
15.8 有向图 359
15.9 有向图的路径 361
15.10 加权有向图和加权图 362
15.11 欧拉路径和哈密顿回路 363
15.12 Dijkstra算法 364
15.13 图的遍历算法 368
复习题 373
习题 374
复习题答案 379
习题答案 380
附录A 基础数学知识 388
A.1 下取整与上取整函数 388
A.2 对数 388
A.3 渐进复杂性分类 389
A.4 第一数学归纳法原理 390
A.5 第二数学归纳法原理 391
A.6 等比级数 392
A.7 求和公式 393
A.8 调和数 393
A.9 Stirling公式 394
A.10 斐波那契数列 395
复习题 395
习题 396
复习题答案 396
习题答案 397