第1章 概述 1
1.1 集合 1
1.1.1 集合的分类 1
目录 1
1.1.2 关于集合的操作 2
1.2 抽象数据类型 3
1.3 算法分析 4
1.3.1 简单性和清晰度 4
1.3.2 空间效率 4
1.3.3 时间效率 4
1.4 算法类型 5
1.4.2 分治算法 6
1.4.3 回溯算法 6
1.4.1 贪婪算法 6
1.5 软件开发过程 7
1.5.1 复杂性 7
1.5.2 脆弱性 7
1.5.3 可扩展性 8
1.5.4 互连性 8
1.6 面向对象程序设计简介 8
1.6.1 过程式程序设计 8
1.6.2 函数式程序设计 8
1.6.3 面向对象程序设计（OOP） 9
1.6.4 面向对象程序设计的直观概括 9
1.7 软件开发生命周期 10
1.8 本书的软件开发方法 11
1.9 分析和设计阶段的测试 12
1.8.4 实现 12
1.8.2 分析 12
1.8.3 设计 12
1.8.1 需求 12
1.10 测试代码 13
1.10.1 单元、集成和验收测试 13
1.10.2 测试内容 13
1.10.3 如何设计测试数据 14
1.11 正确性的证明 15
1.12 软件开发过程的其他方面 15
1.12.1 编码约定 15
1.12.2 前置条件和后置条件 16
1.13 层次系统的开发 17
2.1 简介 20
第2章 面向对象程序设计和基本的输入输出功能 20
2.2 类和对象 21
2.2.1 示例：字符串对象 21
2.2.2 示例：终端输出 22
2.2.3 对象、类和计算机内存 22
2.2.4 对象的3个特征 23
2.2.5 客户端和服务器 23
2.3 Employee类 23
2.3.1 用户需求 23
2.3.2 类模板的结构 26
2.3.3 Employee类的设计和实现 27
2.3.4 构造函数和异常 28
2.3.5 this的使用 30
2.3.6 取值方法、赋值方法和toString方法 30
2.3.7 测试等同性 32
2.3.8 比较及接口Comparable 33
2.3.9 复制对象及接口Cloneable 34
2.3.10 对象序列化 35
2.3.11 finalize和dispose方法 36
2.3.12 使用对象时一些有用的提示 37
2.4 继承和多态 37
2.5 实现一个简单的图形层次结构 38
2.5.1 实现Shape类 38
2.5.2 实现Circle类 39
2.5.3 构造函数和super保留字 40
2.5.4 其他方法和super保留字 41
2.5.5 实现Rectangle类 41
2.5.6 保护型（protected）变量和方法 42
2.6 图形类的使用 43
2.5.7 实现、扩展、重写和终结 43
2.6.1 查找合适的方法 44
2.6.2 图形数组 45
2.7 将图形作为参数和返回值 47
2.7.1 示例：输入Retangle，输出Circle 47
2.7.2 示例：输入任意图形，输出Circle 48
2.7.3 示例：输入任意图形，输出任意图形 48
2.8 面向对象系统的分解 49
2.8.1 确定类 50
2.8.2 分配职责 51
2.8.3 确定数据属性 51
2.8.4 确定方法 52
2.8.5 类和对象模型之间的关系 52
2.9 基于字符的流输入、输出 53
2.9.1 介绍键盘读取器 54
2.9.2 扩展键盘读取器 56
2.9.3 文件读取器 57
2.9.4 格式化输出 59
2.9.5 使用支持类 62
第3章 基于GUI的Java应用程序 64
3.1 模型-视图-控制器模式 64
3.2 温度转换程序的代码 65
3.2.1 模型 65
3.2.2 视图 66
3.2.3 控制器 67
3.2.4 视图和控制器的完整代码 68
3.3 GridBagLayout类 70
3.4 EasyGridLayout类 72
3.5 IntegerField类和DoubleField类 74
3.6 弹出式消息 75
3.7 其他窗口组件 77
3.7.1 菜单和文本区 78
3.7.2 复选框和单选按钮 80
3.7.3 列表框 83
3.8 模式对话框的使用 88
3.9 多窗口应用程序 93
3.10 侦听器共享 96
3.11 方法一览表 98
第4章 复杂度 107
4.1 衡量算法的效率 107
4.1.1 测量算法的执行时间 107
4.1.2 对指令计数 109
4.1.3 用代数方法推导增长率 111
4.2 比较增长率 112
4.2.1 使用代数方法比较增长率 112
4.1.4 测量算法使用的内存 112
4.2.2 大O表示法 114
4.2.3 最佳、最差和平均性能 115
4.3 查找算法 116
4.3.1 数组的线性查找法 116
4.3.2 数组的二分查找法 117
4.4 排序算法 119
4.4.1 选择排序 119
4.4.2 冒泡排序 120
4.4.3 插入排序 121
4.5 案例分析：记录运行时间以及对指令计数 122
4.5.1 要求 122
4.5.4 Algorithms类的实现 123
4.5.2 分析 123
4.5.3 Algorithms类的设计 123
4.5.5 AlgorithmProfiler类的设计和实现 125
第5章 数组和链表 130
5.1 数组的特性 130
5.1.1 随机访问和连续地址内存 130
5.1.2 静态内存和动态内存 131
5.1.3 物理大小和逻辑大小 132
5.2 数组操作 133
5.2.1 增加数组的大小 133
5.2.2 减小数组大小 134
5.2.3 向数组中插入数据项 134
5.2.4 从数组中移除数据项 135
5.2.6 复杂度的权衡：查找和修改数组 136
5.2.5 数组方法的测试程序 136
5.3 链表 137
5.3.1 单链表和双向链表 137
5.3.2 不连续地址内存和节点 138
5.3.3 定义单链节点类 139
5.3.4 使用单链节点类 140
5.4 单链表的操作 142
5.4.1 遍历 142
5.4.2 查找（对象或第i项） 143
5.4.3 替换（对象或第i项） 144
5.4.4 在首端插入 144
5.4.5 在尾端插入 145
5.4.6 在首端移除 146
5.4.7 在尾端移除 147
5.4.8 插入（对象或第i项） 148
5.4.9 移除（对象或第i项） 149
5.4.10 复杂度的权衡：时间、空间和单链表 150
5.5 链表的各种变体 150
5.5.1 带有虚头节点的循环链表 150
5.5.2 双向链表 151
第6章 集合概述 155
6.1 简介 155
6.1.1 本书中集合的概述 156
6.1.2 Tiny集合 158
6.2 多种实现 158
6.3 集合和强制类型转换 159
6.4 集合和串行化 161
6.5.1 迭代器的使用 162
6.5 迭代器 162
6.5.2 实现Tiny和iterator方法 163
6.6 集合和集合视图 166
6.6.1 两个例子 167
6.6.2 Collection接口中的方法 168
6.6.3 collectionView方法的实现（可选内容） 169
6.6.4 AbstractCollection实现（可选内容） 170
6.7 集合的原型和专门版本 172
6.7.1 Tiny专门版本的概述（可选内容） 172
6.7.2 Tiny接口的扩展（可选内容） 173
6.7.3 将Tiny方法分配给类（可选内容） 174
6.7.4 编写代码的细节（可选内容） 175
6.8 本章向导 179
7.1 栈概述 182
第7章 栈 182
7.2 栈原型 183
7.3 栈的使用 184
7.4 栈原型的实现 186
7.4.1 数组实现 186
7.4.2 链表实现 188
7.4.3 两个实现的时间和空间分析 191
7.5 栈的3个应用 192
7.5.1 算术表达式求值 192
7.5.2 回溯算法 195
7.5.3 内存管理 196
7.6 专门版本的接口 200
7.7 专门版本的实现 201
7.8.1 要求 204
7.8 案例分析：后缀表达式求值 204
7.8.2 分析 205
7.8.3 设计 207
7.8.4 实现 210
第8章 队列 216
8.1 队列概述 216
8.2 队列的原型 217
8.3 队列原型的实现 219
8.3.1 链表实现 219
8.3.2 数组实现 220
8.3.3 两种实现的时间和空间分析 222
8.4 队列的两个应用 223
8.4.1 模拟 223
8.4.2 CPU循环调度 224
8.5 专门版本的接口 225
8.6 专门版本的实现 226
8.7 案例分析1：模拟超市结账流程 228
8.7.1 要求 228
8.7.2 分析 228
8.7.3 总体设计 230
8.7.4 MarketModel类的设计 230
8.7.5 MarketModel类的实现 231
8.7.6 Cashier类的设计 232
8.7.7 Cashier类的实现 233
8.7.8 Customer类的设计 234
8.7.9 Customer类的实现 234
8.8 优先队列 236
8.9.2 分析 237
8.9.1 要求 237
8.9 案例分析2：急诊室调度 237
8.9.3 推荐界面 238
第9章 列表 240
9.1 列表概述 240
9.2 列表原型 241
9.3 列表的使用 244
9.4 列表原型的实现 247
9.4.1 静态数组实现 247
9.4.2 双向链表实现 250
9.4.3 两种实现的时间和空间分析 256
9.5 列表的3个应用 258
9.5.1 堆存储管理 258
9.5.2 对磁盘文件的组织 259
9.5.3 其他ADT实现 260
9.6 专门版本的接口 261
9.7 专门版本的实现 263
9.8 案例分析：维护任务列表（to-do列表） 267
9.8.1 要求 268
9.8.2 分析 268
9.8.3 设计 269
9.8.4 实现 270
第10章 递归、查找、排序和回溯 279
10.1 递归概述 279
10.1.1 实现递归 280
10.1.2 跟踪递归调用 281
10.1.3 编写递归方法的准则 282
10.1.4 递归方法的运行支持 283
10.1.5 两种递归方法的分析 284
10.1.6 两种递归方法的空间分析 286
10.2 递归和查找 287
10.2.1 数组的线性查找 287
10.2.2 数组的二分查找 288
10.3 递归和排序 290
10.3.1 快速排序 291
10.3.2 归并排序 295
10.4 递归和回溯 299
10.5 采用递归的理由 301
10.5.1 消除递归 302
10.5.2 尾递归 303
10.6.1 要求 304
10.6.2 分析 304
10.6 案例分析1：迷宫解决方案 304
10.6.3 类 306
10.6.4 MazeView的实现 306
10.6.5 MazeModel的实现 308
10.7 递归下降及其编程语言 310
10.7.1 语法介绍 310
10.7.2 识别、解析和解释语言中的语句 312
10.7.3 词汇分析和扫描器 312
10.7.4 解析策略 313
10.8 案例分析2：递归下降解析器 313
10.8.1 要求 313
10.8.2 分析 314
10.8.3 推荐的用户界面 314
10.8.4 Parser的实现 315
11.1 树的概述 319
第11章 树 319
11.1.1 树的讨论 321
11.1.2 普通树和二叉树的正式定义 322
11.2 树的表示 322
11.2.1 链表表示 322
11.2.2 完全二叉树的数组表示 324
11.3 二叉树的操作 325
11.3.1 二叉树的原型 326
11.3.2 BinaryTreePT的测试程序 328
11.3.3 BinaryTreePT类的实现 330
11.4 案例分析1：解析表达式树 335
11.4.1 要求 335
11.4.2 用户界面 336
11.4.3 ExpressionTree类的分析和设计 336
11.4.4 Parser类的分析、设计和实现 337
11.5 普通树操作 339
11.5.1 树的接口 339
11.5.2 TreeIterator接口 342
11.6 普通树类的实现（可选内容） 345
11.6.1 实现中的类职责 345
11.6.2 AbstractTree类的设计和实现 346
11.6.3 LinkedTree类的设计和实现 349
11.6.4 树迭代器的设计和实现 351
11.7 案例分析2：技能数据库 353
11.7.1 要求 353
11.7.2 分析 354
11.7.3 模型类的设计和实现 355
11.7.4 视图类的设计和实现 358
12.1.1 二叉树的形状 361
第12章 特殊树 361
12.1 堆 361
12.1.2 可比对象 362
12.1.3 Heap接口 362
12.1.4 Heap实现 363
12.1.5 堆排序的实现 364
12.1.6 add方法和pop方法的实现 365
12.1.7 分析堆排序 367
12.1.8 迭代器的实现 367
12.1.9 使用堆实现优先队列 368
12.2 二叉搜索树 372
12.2.1 排序集合抽象数据类型及其接口 372
12.2.2 排序集合抽象数据类型的实现 373
12.2.3 二分查找 374
12.2.4 二叉搜索树的实现 375
12.2.5 分析二叉搜索树 378
12.3 “更好的”二叉搜索树（可选内容） 379
12.3.1 2-3树 379
12.3.2 AVL树 380
第13章 无序集合：集、映射和包 385
13.1 集、映射和包概述 385
13.1.1 集 385
13.1.2 映射 386
13.1.3 包 387
13.1.4 无序集合的迭代器 387
13.1.5 一个简短的例子 387
13.2 实现的考虑事项 389
13.2.1 散列 389
13.2.3 其他散列策略 390
13.2.2 散列链表方法的分析 390
13.3 映射原型类 391
13.3.1 HashMapPT类的接口 391
13.3.2 HashMapPT类的设计 392
13.4 集原型类 396
13.4.1 HashSetPT类的接口 396
13.4.2 设计和实现 397
13.5 包原型类 399
13.5.1 HashBagPT类的接口 399
13.5.2 设计和实现 400
13.6 Java集合框架中的Map类和Set类 401
13.6.1 映射 401
13.6.2 Set接口 404
13.7.1 Bag接口 405
13.7 将Bag ADT添加到集合框架 405
13.7.2 Bag实现 406
13.8 案例分析1：文件索引系统 409
13.8.1 要求 409
13.8.2 分析 409
13.8.3 设计和实现 410
13.9 案例分析2：信贷批准系统 417
13.9.1 要求 417
13.9.2 分析 417
13.9.3 类 417
13.9.4 设计和实现 418
第14章 图 426
14.1 概述 426
14.2 术语 427
14.3.1 邻接矩阵 429
14.3 图的表示 429
14.3.2 邻接表 430
14.3.3 两种表示的分析 431
14.3.4 运行时间的进一步分析 431
14.4 图的遍历 432
14.4.1 连通图的一般遍历算法 432
14.4.2 深度优先遍历和广度优先遍历 432
14.4.3 图的分量 434
14.5 图中的树 435
14.5.1 生成树和生成森林 435
14.5.2 最小生成树 435
14.5.3 最小生成树算法 435
14.6 拓扑排序 437
14.7.1 Dijkstra算法 438
14.7 最短路径问题 438
14.7.2 初始化 439
14.7.3 计算 439
14.7.4 分析 440
14.8 图原型 440
14.8.1 使用图原型的例子 440
14.8.2 LinkedGraphPT类 441
14.8.3 LinkedVertexPT类 448
14.8.4 LinkedEdgePT类 451
14.9 一个专门的图实现（可选内容） 453
14.9.1 Graph接口 454
14.9.2 权值 456
14.9.3 实现 457
14.9.4 关于性能的提示 460
14.10.1 要求 461
14.10.2 分析 461
14.10.3 GraphDemoView类 461
14.10 案例分析：测试图的算法 461
14.10.4 GraphDemoModel类 466
第15章 多线程、网络和客户端／服务器编程 470
15.1 线程和进程 470
15.1.1 线程 471
15.1.2 休眠线程 472
15.1.3 生产者、消费者和同步 474
15.2 网络、服务器和客户端 479
15.2.1 IP地址 479
15.2.3 套接字和一个日期／时间客户端程序 481
15.2.2 端口、服务器和客户端 481
15.2.4 服务器套接字和一个日期／时间服务器端程序 483
15.2.5 客户端和服务器端之间的双向会话 485
15.2.6 使服务器处理多个客户端 485
15.2.7 使用服务器守护进程 486
15.2.8 使用客户端处理器 489
15.2.9 模型-视图-控制器模式 491
15.3 案例分析：校园电话目录 491
15.3.1 要求 491
15.3.2 分析 492
15.3.3 设计 493
15.3.4 实现 493
A.1 保留字 499
A.2 数据类型 499
附录A Java语言特性回顾 499
A.3 变量、作用域和生命周期 501
A.4 表达式 502
A.5 控制语句 503
A.5.1 复合语句 503
A.5.2 if和if-else语句 503
A.5.3 while和do-while语句 504
A.5.4 for语句 504
A.5.5 switch语句 504
A.6 混合模式运算和强制类型转换 505
A.7 字符串 505
A.8 数组 507
A.9 方法和参数 508
A.10 引用类型 509
A.13 接口 510
A.11 包装器类 510
A.12 类 510
A.14 适配器 511
A.15 异常 511
A.16 程序包 512
A.17 文本文件 513
附录B 层次结构、接口及类 516
B.1 层次结构 516
B.2 接口 516
B.3 类 516
附录C 安装指令 518
C.1 使用JDK 518
C.2 使用JGrasp 519
术语表 520