数据结构与抽象（Java语言版） (2008 年度畅销榜NO.2625 )

本书是为数据结构入门课程（通常课号是CS-2）而编写的教材。作者Frank Carrano和Walter Savitch在编写过程自始至终特别考虑到了Java与对象，为教师和学生提供了一种精心设计并经过教学实验的方式借助Java讲授ADT和对象。本书独特的设计将内容组织为相对较短的章。这种方式使学习更容易，并留出了教学的机动性。本书教给学生如何使用线性表、词典、栈、队列等等来组织数据。利用这些数据组织方式，学生们将学到算法设计的相关技术。书中的“编程提示”给读者额外的编程建议；大量的插图使讲解更形象生动；自测题贯穿各章，书末还给出了答案。
本书适合作为数据结构的教学用书。

第1章 Java类

1.1 对象与类
1.2 在Java类中使用方法
1.2.1 引用与别名
1.2.2 实参与形参
1.3 定义Java类
1.3.1 方法定义
1.3.2 传递实参
1.3.3 Name类的定义
1.3.4 构造函数
1.3.5 toString方法
1.3.6 静态的域与方法
1.4 包

第2章 从已有类创建新类

2.1 合成
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 Java接口
3.3.1 编写接口
3.3.2 实现接口
3.3.3 作为数据类型的接口
3.3.4 接口实现中的类型转换
3.3.5 扩展接口
3.3.6 接口中的符号常量
3.3.7 接口与抽象类的比较
3.4 类的选择
3.4.1 类的确定
3.4.2 CRC卡片
3.5 类的复用

第4章 线性表

4.1 ADT线性表说明
4.2 使用ADT线性表
4.3 Java类库：List接口
4.4 使用线性表如同使用自动售货机

第5章 用数组实现线性表

5.1 使用定长数组实现ADT线性表
5.1.1 类比
5.1.2 Java实现
5.2 使用动态扩展数组实现ADT线性表
5.2.1 扩展数组
5.2.2 线性表新的实现
5.3 使用向量实现ADT线性表
5.4 用数组实现ADT线性表的优缺点
5.5 Java类库
5.5.1 ArrayList类
5.5.2 Serializable接口

第6章 用链表实现线性表

6.1 链表
6.1.1 创建一个链表
6.1.2 创建另一个链表
6.1.3 仍创建一个键表
6.2 Node类
6.3 使用链表实现ADT线性表
6.3.1 在线性表的末端插入元素
6.3.2 在线性表的指定位置插入元素
6.3.3 私有方法getNodeAt
6.3.4 方法remove
6.3.5 方法replace
6.3.6 方法getEntry
6.3.7 方法contains
6.3.8 其余方法
6.3.9 使用具有设置与获取方法的Node类
6.4 表尾引用
6.5 用链表实现ADT线性表的优缺点
6.6 Java类库：LinkedList类

第7章 迭代器

7.1 迭代器是什么
7.1.1 基本迭代器
7.1.2 对ADT进行修改的迭代器方法
7.2 内部迭代器的实现
7.3 将选代器本身实现为一个类
7.3.1 外部迭代器
7.3.2 内部类迭代器

第8章 Java的迭代器接口

8.1 Iterator接口
8.2 实现Iterator接口
8.2.1 基于链表实现
8.2.2 基于数组实现
8.3 ListIterator接口
8.4 基于数组实现ListIterator接口
8.5 Java类库：重温ArrayList和LinkedList

第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 计算的时间效率
10.7 困难问题的简单解法
10.8 简单问题的拙劣解法
10.9 尾递归
10.10 协同递归

第11章 排序入门

11.1 选择排序
11.1.1 迭代选择排序
11.1.2 递归选择排序
11.1.3 选择排序的效率
11.2 插入排序
11.2.1 迭代插入排序
11.2.2 递归插入排序
11.2.3 插入排序的效率
11.2.4 链表的插入排序
11.3 希尔排序
11.3.1 Java代码
11.3.2 希尔排序的效率
11.4 算法比较

第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.3 克隆体的有序表
15.4 克隆数组
15.5 克隆链表

第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.1.3 基于数组的有序词典
18.2 基于向量的实现
18.3 基于链表的实现
18.3.1 元素
18.3.2 基于链表的无序词典
18.3.3 基于链表的有序词典

第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 链地址
19.4 效率
19.4.1 装填因子
19.4.2 开放定址的开销
19.4.3 链地址的开销
19.5 再散列
19.6 处理冲突的各方案比较
19.7 使用散列的词典实现
19.7.1 散列表中的元素
19.7.2 数据域与构造函数
19.7.3 方法getValue、remove及add
19.7.4 迭代器
19.8 Java类库：类HashMap

第20章 栈

20.1 ADT栈的说明
20.2 利用栈处理代数表达式
20.2.1 检查中缀代数表达式中括号是否平衡
20.2.2 将中缀表达式转化为后缀表达式
20.2.3 后缀表达式求值
20.2.4 中缀表达式求值
20.3 程序栈
20.4 使用栈代替递归
20.5 Java类库：类Stack

第21章 栈的实现

21.1 基于链表的实现
21.2 基于数组的实现
21.3 基于向量的实现

第22章 队列、双端队列及优先队列

22.1 ADT队列的说明
22.2 使用队列模拟排队
22.3 使用队列计算股份销售的资本收益
22.4 ADT双端队列的说明
22.5 使用双端队列计算股份销售的资本收益
22.6 ADT优先队列的说明
22.7 使用优先队列计算股份销售的资本收益

第23章 队列、双端队列及优先队列的实现

23.1 基于链表实现队列
23.2 基于数组实现队列
23.2.1 循环数组
23.2.2 含有一个不用位置的循环数组
23.3 基于向量实现队列
23.4 基于循环链表实现队列
23.5 基于双向链表实现双端队列
23.6 实现优先队列可用方法

第24章 树

24.1 树的概念
24.1.1 层次化的组织
24.1.2 树的术语
24.2 树的遍历
24.2.1 二叉树的遍历
24.2.2 树的遍历
24.3 树的Java接口
24.3.1 所有树的接口
24.3.2 二叉树接口
24.4 二叉树举例
24.4.1 表达式树
24.4.2 决策树
24.4.3 二叉查找树
24.4.4 堆
24.5 树举例
24.5.1 语法分析树
24.5.2 博奕树

第25章 树的实现

25.1 二叉树的节点
25.1.1 节点的接口
25.1.2 BinaryNode的实现
25.2 ADT二叉树的实现
25.2.1 创建基本二叉树
25.2.2 方法privateSetTree
25.2.3 访问者与修改者方法
25.2.4 计算高度与统计节点
25.2.5 遍历
25.3 表达式二叉树的实现
25.4 树
25.4.1 树的节点
25.4.2 用二叉树表示树

第26章 二叉查找树的实现

26.1 预备知识
26.1.1 二叉查找树接口
26.1.2 相同的元素
26.1.3 开始类定义
26.2 查找与提取
26.3 遍历
26.4 插入元素
26.4.1 迭代实现
26.4.2 递归实现
26.5 删除元素
26.5.1 删除叶子节点中的元素
26.5.2 删除有一个孩子的节点中的元素
26.5.3 删除有两个孩子的节点中的元素
26.5.4 删除根节点中的元素
26.5.5 迭代实现
26.5.6 递归实现
26.6 操作的效率
26.6.1 平衡的重要性
26.6.2 插入节点的顺序
26.7 ADT词典的实现

第27章 堆的实现

27.1 再论ADT堆
27.2 用数组表示堆
27.3 插入兀素
27.4 删除根
27.5 创建堆
27.6 堆排序

第28章 平衡查找树

28.1 AVL树
28.1.1 单旋转
28.1.2 双旋转
28.1.3 实现细节
28.2 2－3树
28.2.1 2－3树的查找
28.2.2 向2－3树插入元素
28.2.3 插入期间分裂节点
28.3 2－4树
28.3.1 向2－4树插入元素
28.3.2 比较AVL树、2－3树及2－4树
28.4 红黑树
28.4.1 红黑树的特性
28.4.2 向红黑树插入元素
28.4.3 Java类库：类TreeMap
28.5 B树

第29章 图

29.1 一些例子与术语
29.1.1 公路地图
29.1.2 航线
29.1.3 迷宫
29.1.4 先修课程
29.1.5 树
29.2 遍历
29.2.1 广度优先遍历
29.2.2 深度优先遍历
29.3 拓扑顺序
29.4 路径
29.4.1 寻找路径
29.4.2 无权图中的最短路径
29.4.3 带权图中的最短路径
29.5 ADT图的Java接口

第30章 图的实现

30.1 两种实现的概述
30.1.1 邻接矩阵
30.1.2 邻接表
30.2 顶点与边
30.2.1 说明类Vertex
30.2.2 类Edge
30.2.3 实现类Vertex
30.3 ADT图的实现
30.3.1 基本操作
30.3.2 图的算法

附录A Java基础
附录B 异常处理
附录C 文件输入与输出
附录D 文档与程序设计风格
附录E 自测题答案