第0章 引言

第1章 Java类

1.1 对象与类

1.2 在Java类中使用方法

1.3 定义Java类

1.3.1 方法定义

1.3.2 实参与形参

1.3.3 传递实参

1.3.4 Name类的定义

1.3.5 构造函数

1.3.6 toString方法

1.3.7 调用其他方法的方法

1.3.8 返回所属类实例的方法

1.3.9 静态域与静态方法

1.3.10 方法的重载

1.4 枚举类

1.5 包

本章小结

练习

项目设计

第2章 从已有类创建新类

2.1 合成

2.1.1 通用类型

2.1.2 适配器

2.2 继承

2.2.1 从构造函数中调用构造函数

2.2.2 基类的私有域与私有方法

2.2.3 受保护的访问

2.2.4 方法的覆盖与重载

2.2.5 多重继承

2.3 类型兼容性与基类

2.3.1 Object类

2.3.2 抽象类与抽象方法

2.4 多态性

本章小结

练习

项目设计

第3章 类的设计

3.1 封装

3.2 方法的说明

3.3 接口

3.3.1 编写接口

3.3.2 实现接口

3.3.3 作为数据类型的接口

3.3.4 接口的通用类型

3.3.5 Comparable接口

3.3.6 扩展接口

3.3.7 接口与抽象类

3.3.8 符号常量

3.4 类的选择

3.4.1 类的确定

3.4.2 CRC卡片

3.5 类的复用

本章小结

练习

项目设计

第4章 线性表

4.1 ADT线性表说明

4.2 使用ADT线性表

4.3 像使用自动售货机一样使用线性表

4.4 Java类库：List接口

本章小结

练习

项目设计

第5章 用数组实现线性表

5.1 使用定长数组实现ADT线性表

5.1.1 类比

5.1.2 Java实现

5.2 使用动态扩展数组实现ADT线性表

5.2.1 扩展数组

5.2.2 线性表的新实现

5.3 Java类库：ArrayList与Vector类

5.4 用数组实现ADT线性表的优缺点

本章小结

练习

项目设计

第6章 用链表实现线性表

6.1 链表

6.1.1 在表头添加来创建链表

6.1.2 在表末添加来创建链表

6.1.3 在不同位置添加来创建链表

6.2 使用链表实现ADT线性表

6.2.1 私有类Node

6.2.2 数据域与构造函数

6.2.3 选择要实现的核心方法组

6.2.4 在线性表的末端插入元素

6.2.5 在线性表的指定位置插入元素

6.2.6 私有方法getNodeAt

6.2.7 断言与isEmpty方法

6.2.8 display方法

6.3 测试不完整的实现

本章小结

练习

项目设计

第7章 完成线性表的链表实现

7.1 从链表中删除一个元素

7.2 完成ADT线性表的链表实现

7.2.1 方法remove

7.2.2 方法replace

7.2.3 方法getEntry

7.2.4 方法contains

7.2.5 其他方法

7.3 使用具有设置与获取方法的Node类

7.4 表尾引用

7.5 用链表实现ADT线性表的优缺点

7.6 Java类库：LinkedList类

本章小结

练习

项目设计

第8章 迭代器

8.1 什么是迭代器

8.2 Iterator接口

8.3 独立类迭代器

8.4 内部类迭代器

8.4.1 基于链表实现

8.4.2 基于数组实现

8.5 迭代器方法为何在自己的类中

8.6 ListIterator接口

8.7 基于数组实现ListIterator接口

8.8 Java类库：Iterable接口

8.8.1 Iterable与for-each循环

8.8.2 重温List接口

本章小结

练习

项目设计

第9章 算法的效率

9.1 动机

9.2 度量算法的效率

9.3 形式化

9.4 效率的图形表示

9.5 ADT线性表不同实现的效率

9.5.1 基于数组实现

9.5.2 基于链表实现

9.5.3 比较上述实现

本章小结

练习

项目设计

第10章 递归

10.1 何谓递归

10.2 跟踪递归方法

10.3 有返回值的递归方法

10.4 递归处理数组

10.5 递归处理链表

10.6 递归方法的时间效率

10.6.1 countDown的时间效率

10.6.2 计算xn的时间效率

10.7 困难问题的简单解法

10.8 简单问题的拙劣解法

10.9 尾递归

10.10 协同递归

本章小结

练习

项目设计

第11章 排序入门

11.1 组织用于数组排序的Java方法

11.2 选择排序

11.2.1 迭代选择排序

11.2.2 递归选择排序

11.2.3 选择排序的效率

11.3 插入排序

11.3.1 迭代插入排序

11.3.2 递归插入排序

11.3.3 插入排序的效率

11.3.4 链表的插入排序

11.4 希尔排序

11.4.1 Java代码

11.4.2 希尔排序的效率

11.5 算法比较

本章小结

练习

项目设计

第12章 快速排序算法

12.1 归并排序

12.1.1 数组的归并

12.1.2 递归归并排序

12.1.3 归并排序的效率

12.1.4 迭代归并排序

12.1.5 Java类库中的归并排序

12.2 快速排序

12.2.1 快速排序的效率

12.2.2 创建划分

12.2.3 快速排序的Java代码

12.2.4 Java类库中的快速排序

12.3 基数排序

12.3.1 基数排序的伪代码

12.3.2 基数排序的效率

12.4 算法比较

本章小结

练习

项目设计

第13章 有序表

13.1 ADT有序表的说明

13.2 链表实现

13.2.1 add方法

13.2.2 链表实现的效率

13.3 使用ADT线性表的实现

本章小结

练习

项目设计

第14章 继承与线性表

14.1 使用继承实现有序表

14.2 设计一个基类

14.3 有序表的一种高效实现

本章小结

练习

项目设计

第15章 可变对象、不可变对象与可克隆对象

15.1 可变对象与不可变对象

15.1.1 创建只读类

15.1.2 同伴类

15.2 可克隆对象

15.2.1 克隆数组

15.2.2 克隆链表

15.2.3 克隆体的有序表

本章小结

练习

项目设计

第16章 查找

16.1 问题描述

16.2 查找无序数组

16.2.1 迭代顺序查找无序数组

16.2.2 递归顺序查找无序数组

16.2.3 顺序查找数组的效率

16.3 查找有序数组

16.3.1 顺序查找有序数组

16.3.2 折半查找有序数组

16.3.3 Java类库：binarySearch方法

16.3.4 折半查找数组的效率

16.4 查找无序链表

16.4.1 迭代顺序查找无序链表

16.4.2 递归顺序查找无序链表

16.4.3 顺序查找链表的效率

16.5 查找有序链表

16.5.1 顺序查找有序链表

16.5.2 折半查找有序链表

16.6 查找方法的选择

本章小结

练习

项目设计

第17章 词典

17.1 ADT词典的说明

17.1.1 Java接口

17.1.2 迭代器

17.2 使用ADT词典

17.2.1 电话号码簿

17.2.2 词频

17.2.3 词的索引

17.3 Java类库：Map接口

本章小结

练习

项目设计

第18章 词典的实现

18.1 基于数组的实现

18.1.1 基于数组的无序词典

18.1.2 基于数组的有序词典

18.2 基于向量的实现

18.3 基于链表的实现

18.3.1 基于链表的无序词典

18.3.2 基于链表的有序词典

本章小结

练习

项目设计

第19章 散列概述

19.1 什么是散列

19.2 散列函数

19.2.1 计算散列码

19.2.2 将散列码压缩为散列表的索引

19.3 处理冲突

19.3.1 线性探测开放定址

19.3.2 二次探测开放定址

19.3.3 双散列开放定址

19.3.4 开放定址的潜在问题

19.3.5 链地址

本章小结

练习

项目设计

第20章 用散列实现词典

20.1 效率

20.1.1 装填因子

20.1.2 开放定址的开销

20.1.3 链地址的开销

20.2 再散列

20.3 处理冲突的各方案比较

20.4 使用散列的词典实现

20.4.1 散列表中的元素

20.4.2 数据域与构造函数

20.4.3 方法getValue、remove和add

20.4.4 迭代器

20.5 Java类库：类HashMap

本章小结

练习

项目设计

第21章 栈

21.1 ADT栈的说明

21.2 利用栈处理代数表达式

21.2.1 检查中缀代数表达式的括号是否平衡

21.2.2 将中缀表达式转化为后缀表达式

21.2.3 后缀表达式求值

21.2.4 中缀表达式求值

21.3 程序栈

21.4 使用栈代替递归

21.5 Java类库：类Stack

本章小结

练习

项目设计

第22章 栈的实现

22.1 基于链表的实现

22.2 基于数组的实现

22.3 基于向量的实现

本章小结

练习

项目设计

第23章 队列、双端队列与优先队列

23.1 ADT队列的描述

23.2 使用队列模拟排队

23.3 使用队列计算股份销售的资本收益

23.4 Java类库：Queue接口

23.5 ADT双端队列的描述

23.6 使用双端队列计算股份销售的资本收益

23.7 ADT优先队列的描述

23.8 使用优先队列跟踪委派任务

本章小结

练习

项目设计

第24章 队列、双端队列与优先队列的实现

24.1 基于链表的队列实现

24.2 基于数组的队列实现

24.2.1 循环数组

24.2.2 含有一个未用位置的循环数组

24.3 基于向量的队列实现

24.4 基于循环链表的队列实现

24.5 Java类库：AbstractQueue类

24.6 基于双向链表的双端队列实现

24.7 实现优先队列的可用方法

24.8 Java类库：PriorityQueue类

本章小结

练习

项目设计

第25章 树

25.1 树的概念

25.1.1 层次化的组织

25.1.2 树的术语

25.2 树的遍历

25.2.1 二叉树的遍历

25.2.2 树的遍历

25.3 树的Java接口

25.3.1 所有树的接口

25.3.2 二叉树的接口

25.4 二叉树举例

25.4.1 表达式树

25.4.2 决策树

25.4.3 二叉查找树

25.4.4 堆

25.5 树举例

25.5.1 语法分析树

25.5.2 博弈树

本章小结

练习

项目设计

第26章 树的实现

26.1 二叉树的结点

26.1.1 结点的接口

26.1.2 BinaryNode的实现

26.2 ADT二叉树的实现

26.2.1 创建基本二叉树

26.2.2 方法privateSetTree

26.2.3 访问者与修改者方法

26.2.4 计算高度与统计结点

26.2.5 遍历

26.3 表达式二叉树的实现

26.4 树

26.4.1 树的结点

26.4.2 用二叉树表示树

本章小结

练习

项目设计

第27章 二叉查找树的实现

27.1 预备知识

27.1.1 二叉查找树接口

27.1.2 重复元素

27.1.3 开始类定义

27.2 查找与检索

27.3 遍历

27.4 插入元素

27.4.1 递归实现

27.4.2 迭代实现

27.5 删除元素

27.5.1 删除叶子结点中的元素

27.5.2 删除有一个孩子的结点中的元素

27.5.3 删除有两个孩子的结点中的元素

27.5.4 删除根结点中的元素

27.5.5 递归实现

27.5.6 迭代实现

27.6 操作的效率

27.6.1 平衡的重要性

27.6.2 插入结点的顺序

27.7 ADT词典的实现

本章小结

练习

项目设计

第28章 堆的实现

28.1 再论ADT堆

28.2 用数组表示堆

28.3 插入元素

28.4 删除根

28.5 创建堆

28.6 堆排序

本章小结

练习

项目设计

第29章 平衡查找树

29.1 AVL树

29.1.1 单旋转

29.1.2 双旋转

29.1.3 实现细节

29.2 2-3树

29.2.1 2-3树的查找

29.2.2 往2-3树插入元素

29.2.3 插入期间分裂结点

29.3 2-4树

29.3.1 往2-4树插入元素

29.3.2 比较AVL树、2-3树和2-4树

29.4 红黑树

29.4.1 红黑树的特性

29.4.2 往红黑树插入元素

29.4.3 Java类库：类TreeMap

29.5 B树

本章小结

练习

项目设计

第30章 图

30.1 一些例子与术语

30.1.1 公路地图

30.1.2 航线

30.1.3 迷宫

30.1.4 先修课程

30.1.5 树

30.2 遍历

30.2.1 广度优先遍历

30.2.2 深度优先遍历

30.3 拓扑顺序

30.4 路径

30.4.1 寻找路径

30.4.2 无权图的最短路径

30.4.3 加权图的最短路径

30.5 ADT图的Java接口

本章小结

练习

项目设计

第31章 图的实现

31.1 两种实现的概述

31.1.1 邻接矩阵

31.1.2 邻接表

31.2 顶点与边

31.2.1 说明类Vertex

31.2.2 内部类Edge

31.2.3 实现Vertex类

31.3 ADT图的实现

31.3.1 基本操作

31.3.2 图的算法

本章小结

练习

项目设计

附录A Java基础

A.1 引言

A.1.1 应用程序和小程序

A.1.2 对象和类

A.1.3 第一个Java应用程序

A.2 Java基础

A.2.1 标识符

A.2.2 保留字

A.2.3 变量

A.2.4 基本类型

A.2.5 常量

A.2.6 赋值语句

A.2.7 赋值兼容性

A.2.8 类型转换

A.2.9 算术运算符和表达式

A.2.10 括号和优先规则

A.2.11 自增和自减运算符

A.2.12 特殊赋值运算符

A.2.13 符号常量

A.2.14 Math类

A.3 用键盘和屏幕进行简单的输入和输出

A.3.1 屏幕输出

A.3.2 用Scanner类进行键盘输入

A.4 if-else语句

A.4.1 布尔表达式

A.4.2 嵌套语句

A.4.3 多重if-else语句

A.4.4 条件运算符（可选）

A.5 switch语句

A.6 枚举

A.7 作用域

A.8 循环

A.8.1 while语句

A.8.2 for语句

A.8.3 do-while语句

A.8.4 关于循环的其他信息

A.9 String类

A.9.1 字符串中的字符

A.9.2 字符串的联接

A.9.3 String方法

A.10 StringBuilder类

A.11 使用Scanner抽取字符串的一部分

A.12 数组

A.12.1 数组形参和返回值

A.12.2 初始化数组

A.12.3 数组索引出界

A.12.4 对数组使用＝与＝＝

A.12.5 数组与for-each循环

A.12.6 多维数组

A.12 封装类

附录B 异常处理

B.1 基本的异常处理

B.2 Java类库的异常类

B.3 定义自己的异常类

B.4 复合catch代码块

B.5 finally代码块

B.6 抛出但不捕获异常的方法

B.7 不需要捕获的异常

附录C 文件输入与输出

C.1 概述

C.1.1 数据流

C.1.2 文件的优点

C.1.3 文件的类型

C.1.4 文件名

C.1.5 包java.io

C.2 使用PrintWriter写文本文件

C.3 读取文本文件

C.3.1 使用Scanner读取文本文件

C.3.2 使用BufferedReader读取文本文件

C.3.3 定义打开数据流的方法

C.4 二进制文件的I/O

C.4.1 使用DataOutputStream写二进制文件

C.4.2 使用DataInputStream读取二进制文件

C.5 File类

C.6 对象串行化

附录D 文档与程序设计风格

D.1 命名变量与类

D.2 缩排

D.3 注释

D.3.1 单行注释

D.3.2 注释块

D.3.3 何时写注释

D.3.4 Java文档注释

D.3.5 运行javadoc

附录E 自测题答案