Java程序设计与数据结构（第2版国外计算机科学经典教材）

第1章 概述
1.1 集合
1.1.1 集合的分类
1.1.2 关于集合的操作
1.2 抽象数据类型
1.3 算法分析
1.3.1 简单性和清晰度
1.3.2 空间效率
1.3.3 时间效率
1.4 算法类型
1.4.1 贪婪算法
1.4.2 分治算法
1.4.3 回溯算法
1.5 软件开发过程
1.5.1 复杂性
1.5.2 脆弱性
1.5.3 可扩展性
1.5.4 互连性
1.6 面向对象程序设计简介
1.6.1 过程式程序设计
1.6.2 函数式程序设计
1.6.3 面向对象程序设计(00P)
1.6.4 面向对象程序设计的直观概括
1.7 软件开发生命周期
1.8 本书的软件开发方法
1.8.1 需求
1.8.2 分析
1.8.3 设计
1.8.4 实现
1.9 分析和设计阶段的测试
1.10 测试代码
1.10.1 单元、集成和验收测试
1.10.2 测试内容
1.10.3 如何设计测试数据
1.11 正确性的证明
1.12 软件开发过程的其他方面
1.12.1 编码约定
1.12.2 前置条件和后置条件
1.13 层次系统的开发
第2章 面向对象程序设计和基本的输入输出功能
2.1 简介
2.2 类和对象
2.2.1 示例：字符串对象
2.2.2 示例：终端输出
2.2.3 对象、类和计算机内存
2.2.4 对象的3个特征
2.2.5 客户端和服务器
2.3 Employee类
2.3.1 用户需求
2.3.2 类模板的结构
2.3.3 Employee类的设计和实现
2.3.4 构造函数和异常
2.3.5 this的使用
2.3.6 取值方法、赋值方法和toString方法
2.3.7 测试等同性
2.3.8 比较及接口Comparable.
2.3.9 复制对象及接口Cloneable
2.3.10 对象序列化
2.3.11 finalize和dispose方法
2.3.12 使用对象时一些有用的提示
2.4 继承和多态
2.5 实现一个简单的图形层次结构
2.5.1 实现Shape类
2.5.2 实现Circle类
2.5.3 构造函数和super保留字
2.5.4 其他方法和super保留字
2.5.5 实现Rectangle类
2.5.6 保护型(protected)变量和方法
2.5.7 实现、扩展、重写和终结
2.6 图形类的使用
2.6.1 查找合适的方法
2.6.2 图形数组
2.7 将图形作为参数和返回值
2.7.1 示例：输入Retangle，输出Circle
2.7.2 示例：输入任意图形，输出Circle
2.7.3 示例：输入任意图形，输出任意图形
2.8 面向对象系统的分解
2.8.1 确定类
2.8.2 分配职责
2.8.3 确定数据属性
2.8.4 确定方法
2.8.5 类和对象模型之间的关系
2.9 基于字符的流输入、输出
2.9.1 介绍键盘读取器
2.9.2 扩展键盘读取器
2.9.3 文件读取器
2.9.4 格式化输出
2.9.5 使用支持类
第3章 基于GUI的Java应用程序
3.1 模型、视图、控制器模式
3.2 温度转换程序的代码
3.2.1 模型
3.2.2 视图
3.2.3 控制器
3.2.4 视图和控制器的完整代码
3.3 GridBagLayout类
3.4 EasyGridLayout类
3.5 IntegerField类和DoubleField类
3.6 弹出式消息
3.7 其他窗口组件
3.7.1 菜单和文本区
3.7.2 复选框和单选按钮
3.7.3 列表框
3.8 模式对话框的使用
3.9 多窗口应用程序
3.10 侦听器共享
3.11 方法一览表
第4章 复杂度
4.1 衡量算法的效率
4.1.1 测量算法的执行时间
4.1.2 对指令计数
4.1.3 用代数方法推导增长率
4.1.4 测量算法使用的内存
4.2 比较增长率
4.2.1 使用代数方法比较增长率
4.2.2 大O表示法
4.2.3 最佳、最差和平均性能
4.3 查找算法
4.3.1 数组的线性查找法
4.3.2 数组的二分查找法
4.4 排序算法
4.4.1 选择排序
4.4.2 冒泡排序
4.4.3 插入排序
4.5 案例分析：记录运行时间 以及对指令计数
4.5.1 要求
4.5.2 分析
4.5.3 Algorithms类的设计
4.5.4 Algorithms类的实现
4.5.5 AlgorithmProfiler类的 设计和实现
第5章 数组和链表
5.1 数组的特性
5.1.1 随机访问和连续地址内存
5.1.2 静态内存和动态内存
5.1.3 物理大小和逻辑大小
5.2 数组操作
5.2.1 增加数组的大小
5.2.2 减小数组大小
5.2.3 向数组中插入数据项
5.2.4 从数组中移除数据项
5.2.5 数组方法的测试程序
5.2.6 复杂度的权衡：查找和 修改数组
5.3 链表
5.3.1 单链表和双向链表
5.3.2 不连续地址内存和节点
5.3.3 定义单链节点类
5.3.4 使用单链节点类
5.4 单链表的操作
5.4.1 遍历
5.4.2 查找(对象或第i项)
5.4.3 替换(对象或第i项)
5.4.4 在首端插入
5.4.5 在尾端插入
5.4.6 在首端移除
5.4.7 在尾端移除
5.4.8 插入(对象或第i项)
5.4.9 移除(对象或第i项)
5.4.10 复杂度的权衡：时间、 空间和单链表
5.5 链表的各种变体
5.5.1 带有虚头节点的循环链表
5.5.2 双向链表
第6章 集合概述
6.1 简介
6.1.1 本书中集合的概述
6.1.2 Tiny集合
6.2 多种实现
6.3 集合和强制类型转换
6.4 集合和串行化
6.5 迭代器
6.5.1 迭代器的使用
6.5.2 实现Tiny和iterator方法
6.6 集合和集合视图
6.6.1 两个例子
6.6.2 Collection接口中的方法
6.6.3 ColleetionView方法的 实现(可选内容)
6.6.4 AbstractCollection 实现(可选内容)
6.7 集合的原型和专门版本
6.7.1 Tiny专门版本的概述 (可选内容)
6.7.2 Tiny接口的扩展(可选内容)
6.7.3 将Tiny方法分配给类 (可选内容)
6.7.4 编写代码的细节(可选内容)
6.8 本章向导
第7章 栈
7.1 栈概述
7.2 栈原型
7.3 栈的使用
7.4 栈原型的实现
7.4.1 数组实现
7.4.2 链表实现
7.4.3 两个实现的时间和空间分析
7.5 栈的3个应用
7.5.1 算术表达式求值
7.5.2 回溯算法
7.5.3 内存管理
7.6 专门版本的接口
7.7 专门版本的实现
7.8 案例分析：后缀表达式求值
7.8.1 要求
7.8.2 分析
7.8.3 设计
7.8.4 实现
第8章 队列
8.1 队列概述
8.2 队列的原型
8.3 队列原型的实现
8.3.1 链表实现
8.3.2 数组实现
8.3.3 两种实现的时间和空间分析
8.4 队列的两个应用
8.4.1 模拟
8.4.2 CPU循环调度
8.5 专门版本的接口
8.6 专门版本的实现
8.7 案例分析1：模拟超市结账流程
8.7.1 要求
8.7.2 分析
8.7.3 总体设计
8.7.4 MarketModel类的设计
8.7.5 MarkotModel类的实现
8.7.6 Cashier类的设计
8.7.7 Cashier类的实现
8.7.8 Customer类的设计
8.7.9 Customer类的实现
8.8 优先队列
8.9 案例分析2：急诊室调度
8.9.1 要求
8.9.2 分析
8.9.3 推荐界面
第9章 列表
9.1 列表概述
9.2 列表原型
9.3 列表的使用
9.4 列表原型的实现
9.4.1 静态数组实现
9.4.2 双向链表实现
9.4.3 两种实现的时间和空间分析
9.5 列表的3个应用
9.5.1 堆存储管理
9.5.2 对磁盘文件的组织
9.5.3 其他ADT实现
9.6 专门版本的接口
9.7 专门版本的实现
9.8 案例分析：维护任务列表(to-do列表)
9.8.1 要求
9.8.2 分析
9.8.3 设计
9.8.4 实现
第10章 递归、查找、排序和回溯
10.1 递归概述
10.1 实现递归
10.1.2 跟踪递归调用
10.1.3 编写递归方法的准则
10.1.4 递归方法的运行支持
10.1.5 两种递归方法的分析
10.1.6 两种递归方法的空间分析
10.2 递归和查找
10.2.1 数组的线性查找
10.2.2 数组的二分查找
10.3 递归和排序
10.3.1 快速捧序
10.3.2 归并排序
10.4 递归和回溯
10.5 采用递归的理由
10.5.1 消除递归
10.5.2 尾递归
10.6 案例分析1：迷宫解决方案
10.6.1 要求
10.6.2 分析
10.6.3 类
10.6.4 MazeView的实现
10.6.5 MazcModel的实现
10.7 递归下降及其编程语言
10.7.1 语法介绍
10.7.2 识别、解析和解释语言中的语句
10.7.3 词汇分析和扫描器
10.7.4 解析策略
10.8 案例分析2：递归下降解析器
10.8.1 要求
10.8.2 分析
10.8.3 推荐的用户界面
10.8.4 Parser的实现
第11章 树
11.1 树的概述
11.1.1 树的讨论
11.1.2 普通树和二叉树的正式定义
11.2 树的表示
11.2.1 链表表示
11.2.2 完全二叉树的数组表示：
11.3 二叉树的操作
11.3.1 二叉树的原型
11.3.2 BinaryTreePT的测试程序
11.3.3 BinaryTreePT类的实现
11.4 案例分析1：解析表达式树
11.4.1 要求
11.4.2 用户界面
11.4.3 ExpressionTree类的分析和设计
11.4.4 Parser类的分析、设计和实现
11.5 普通树操作
11.5.1 树的接口
11.5.2 Treelterator接口
11.6 普通树类的实现(可选内容)
11.6.1 实现中的类职责
11.6.2 AbstractTree类的设计和实现
11.6.3 LinkedTree类的设计和实现
11.6.4 树迭代器的设计和实现
11.7 案例分析2：技能数据库
11.7.1 要求
11.7.2 分析
11.7.3 模型类的设计和实现
11.7.4 视图类的设计和实现
第12章 特殊树
12.1 堆
12.1.1 二叉树的形状
12.1.2 可比对象
12.1.3 Heap接口
12.1.4 Heap实现
12.1.5 堆排序的实现
12.1.6 add方法和pop方法的实现
12.1.7 分析堆排序
12.1.8 迭代器的实现
12.1.9 使用堆实现优先队列
12.2 二叉搜索树
12.2.1 排序集合抽象数据类型及其接口
12.2.2 排序集合抽象数据类型的实现
12.2.3 二分查找
12.2.4 二叉搜索树的实现
12.2.5 分析二叉搜索树
12.3 “更好的”二叉搜索树(可选内容)
12.3.1 2-3树
12.3.2 AVL树
第13章 无序集合：集、映射和包
13.1 集、映射和包概述
13.1.1 集
13.1.2 映射
13.1.3 包
13.1.4 无序集合的迭代器
13.1.5 一个简短的例子
13.2 实现的考虑事项
13.2.1 散列
13.2.2 散列链表方法的分析
13.2.3 其他散列策略
13.3 映射原型类
13.3.1 HashMapPT类的接口
13.3.2 HashMapPT类的设计
13.4 集原型类
13.4.1 HashSetPT类的接口
13.4.2 设计和实现
13.5 包原型类
13.5.1 HashBagPT类的接口
13.5.2 设计和实现
13.6 Java集合框架中的Map类和Set类
13.6.1 映射
13.6.2 Set接口
13.7 将Bag ADT添加到集合框架
13.7.1 Bag接口
13.7.2 Bag实现
13.8 案例分析1：文件索引系统
13.8.1 要求
13.8.2 分析
13.8.3 设计和实现
13.9 案例分析2：信贷批准系统
13.9.1 要求
13.9.2 分析
13.9.3 类
13.9.4 设计和实现
第14章 图
14.1 概述
14.2 术语
14.3 图的表示
14.3.1 邻接矩阵
14.3.2 邻接表
14.3.3 两种表示的分析
14.3.4 运行时间的进一步分析
14.4 图的遍历
14.4.1 连通图的一般遍历算法
14.4.2 深度优先遍历和广度优先遍历
14.4.3 图的分量
14.5 图中的树
14.5.1 生成树和生成森林
14.5.2 最小生成树
14.5.3 最小生成树算法
14.6 拓扑排序
14.7 最短路径问题
14.7.1 Diikstra算法
14.7.2 初始化
14.7.3 计算
14.7.4 分析
14.8 图原型
14.8.1 使用图原型的例子
14.8.2 LinkedGraphPT类
14.8.3 LinkedVertexPT类
14.8.4 LinkedEdgePT类
14.9 一个专门的图实现(可选内容)
14.9.1 Graph接口
14.9.2 权值
14.9.3 实现
14：9.4 关于性能的提示
14.10 案例分析：测试图的算法
14.10.1 要求
14.10.2 分析
14.10.3 GraphDemoViCW类
14.10.4 GraphDemoModel类
第15章 多线程、网络和客户端/服务器编程
15.1 线程和进程
15.1.1 线程
15.1.2 休眠线程
15.1.3 生产者、消费者和同步
15.2 网络、服务器和客户端
15.2.1 IP地址
15.2.2 端口、服务器和客户端
15.2.3 套接字和一个日期/时间客户端程序
15.2.4 服务器套接字和一个日期/时间服务器端程序
15.2.5 客户端和服务器端之间的双向会话
15.2.6 使服务器处理多个客户端”
15.2.7 使用服务器守护进程
15.2.8 使用客户端处理器
15.2.9 模型、视图、控制器模式
15.3 案例分析：校园电话目录
15.3.1 要求
15.3.2 分析
15.3.3 设计
15.3.4 实现
附录A Java语言特性回顾
A.1 保留字
A.2 数据类型
A.3 变量、作用域和生命周期
A.4 表达式
A.5 控制语句
A.5.1 复合语句
A.5.2 if和if-else语句
A.5.3 while和do-while语句
A.5.4 for语句
A.5.5 switch语句
A.6 混合模式运算和强制类型转换
A.7 字符串
A.8 数组
A.9 方法和参数
A.10 引用类型
A.11 包装器类
A.12 类
A.13 接口
A.14 适配器
A.15 异常
A.16 程序包
A.17 文本文件
附录B 层次结构、接口及类
B.1 层次结构
B.2 接口
B.3 类
附录C 安装指令
C.1 使用JDK
C.2 使用JGrasp
术语表