数据结构与抽象 Java语言描述（原书第4版） 内容简介

本书是一本数据结构的教材，Java语言与数据结构两条知识主线贯穿始终，这两条主线既相互独立又相互支撑。本书介绍了计算机编程中使用的数据结构和算法，包括29章，每章涉及一个ADT或其不同实现的规格说明和用法；书中贯穿9个Java插曲，涉及Java的高级特性。本书主要讲述了组织数据、设计类、包、栈、递归、排序、队列、双端队列、优先队列、线性表、有序表、查找、字典、散列、树、二叉查找树、堆、平衡查找树、图等内容，并对算法的效率进行了分析。本书非常适合作为大学本科生数据结构课程的教材，也可作为计算机研究与开发人员的参考书。

数据结构与抽象 Java语言描述（原书第4版） 目录

出版者的话

译者序

前言

引言组织数据

序言设计类

P.1封装

P.2说明方法

P.2.1注释

P.2.2前置条件和后置条件

P.2.3断言

P.3Java接口

P.3.1写一个接口

P.3.2实现一个接口

P.3.3接口作为数据类型

P.3.4派生一个接口

P.3.5接口内命名常量

P.4选择类

P.4.1标识类

P.4.2CRC卡

P.4.3统一建模语言

P.5重用类

第1章包

1.1什么是包

1.2说明一个包

1.3使用ADT包

1.4像使用自动贩卖机一样使用ADT

1.5ADT集合

1.6Java类库：接口set

Java插曲1泛型

第2章使用数组实现包

2.1使用固定大小的数组实现ADT包

2.1.1类比

2.1.2一组核心方法

2.1.3实现核心方法

2.1.4让实现安全

2.1.5测试核心方法

2.1.6实现更多的方法

2.1.7删除项的方法

2.2使用可变大小的数组实现ADT包

2.2.1可变大小数组

2.2.2包的新实现

2.3使用数组实现ADT包的优缺点

Java插曲2异常

第3章使用链式数据实现包

3.1链式数据

3.2ADT包的链式实现

3.2.1私有类Node

3.2.2类LinkedBag的框架

3.2.3定义一些核心方法

3.2.4测试核心方法

3.2.5方法getFrequencyOf

3.2.6方法contalns

3.3从链中删除一项

3.4有设置和获取方法的类Node

3.5使用链实现ADT包的优缺点

第4章算法的效率

4.1动机

4.2测量算法的效率

4.2.1计数基本操作

4.2.2最优、最差和平均情形

4.3大O表示

4.4描述效率

4.5实现ADT包的效率

4.5.1基于数组的实现

4.5.2链式实现

4.5.3两种实现的比较

第5章栈

5.1ADT栈的规格说明

5.2使用栈来处理代数表达式

5.2.1问题求解：检查中缀代数表达式中平衡的分隔符

5.2.2问题求解：将中缀代数表达式转换为后缀表达式

5.2.3问题求解：计算后缀表达式的值

5.2.4问题求解：计算中缀表达式的值

5.3程序栈

5.4Java类库：类stack

第6章栈的实现

6.1链式实现

6.2基于数组的实现

6.3基于向量的实现

6.3.1Java类库：类Vector

6.3.2使用向量实现ADT栈

第7章递归

7.1什么是递归

7.2跟踪递归方法

7.3返回一个值的递归方法

7.4递归处理数组

7.5递归处理链

7.6递归方法的时间效率

7.6.1countDown的时间效率

7.6.2计算xn的时间效率

7.7困难问题的简单求解方案

7.8简单问题的低劣求解方案

7.9尾递归

7.10间接递归

7.11使用栈来替代递归

Java插曲3再谈泛型

第8章排序简介

8.1对数组进行排序的Java方法的组织

8.2选择排序

8.2.1迭代选择排序

8.2.2递归选择排序

8.2.3选择排序的效率

8.3插入排序

8.3.1迭代插入排序

8.3.2递归插入排序

8.3.3插入排序的效率

8.3.4链式结点链的插入排序

8.4希尔排序

8.4.1算法

8.4.2希尔排序的效率

8.5算法比较

第9章更快的排序方法

9.1归并排序

9.1.1归并数组

9.1.2递归归并排序

9.1.3归并排序的效率

9.1.4迭代归并排序

9.1.5Java类库中的归并排序

9.2快速排序

9.2.1快速排序的效率

9.2.2创建划分

9.2.3实现快速排序

9.2.4Java类库中的快速排序

9.3基数排序

9.3.1基数排序的伪代码

9.3.2基数排序的效率

9.4算法比较

Java插曲4再谈异常

第10章队列、双端队列和优先队列

10.1ADT队列

10.1.1问题求解：模拟排队

10.1.2问题求解：计算出售股票的资本收益

10.1.3Java类库：接口Queue

10.2ADT双端队列

10.2.1问题求解：计算出售股票的资本收益

10.2.2Java类库：接口Deque

10.2.3Java类库：类ArrayDeque

10.3ADT优先队列

10.3.1问题求解：跟踪任务分配

10.3.2Java类库：类PriorityQueue

第11章队列、双端队列和优先队列的实现

11.1队列的链式实现

11.2基于数组实现队列

11.2.1循环数组

11.2.2带一个不用位置的循环数组

11.3队列的循环链式实现

11.4Java类库：类AbstractQueue

11.5双端队列的双向链式实现

11.6优先队列的町能实现方案

第12章线性表

12.1ADT线性表的规格说明

12.2使用ADT线性表

12.3Java类库：接口List

12.4Java类库：类ArrayList

第13章使用数组实现线性表

13.1使用数组实现ADT线性表

13.1.1类比

13.1.2Java实现

13.1.3使用数组实现ADT线性袁的效率

第14章使用链式数据实现线性表

14.1链式结点链上的操作

14.1.1在不同的位置添加结点

14.1.2从不同的位置删除鲒点

14.1.3私有方法getNodeAt

14.2开始实现

14.2.1数据域和构造方法

14.2.2添加到线性表的表尾

14.2.3在线性表的给定位置添加力，

14.2.4方法isEmpty和toArray

14.2.5测试核心方法

14.3继续实现

14.4细化实现

14.5使用链实现ADT线性表的效率

14.6Java类库：类LinkedList

Java插曲5迭代器

第15章ADT线性表的迭代器

15.1实现迭代器的方法

15.2独立类迭代器

15.3内层类迭代器

15.3.1链式实现

15.3.2基于教组的实现

15.4为什么迭代器方法在它自己的类中

15.5基于数组实现接门ListIterator

Java插曲6可变及不可变对象

第16章有序表

16.1ADT有序表的规格说明

16.2链式实现

16.2.1方法add

16.2.2链式实现的效率

16.3使用ADT线性表实现

Java插曲7继承和多态

第17章继承和线性表

17.1使用继承实现有序表

17.2设计一个基类

17.3有序表的高效实现

第18章查找

18.1问题

18.2在无序数组中查找

18.2.1无序数组上的迭代顺序查找

18.2.2无序数组上的递归顺序查找

18.2.3顺序查找数组的效率

18.3有序数组上的查找

18.3.1有序数组上的顺序查找

18.3.2有序数组上的二分查找

18.3.3Java类库：方法binarySearch

18.3.4数组上的二分查找的效率425

184无序链上的查找

18.4.1无序链上的迭代顺序查找

18.4.2无序链上的递归顺序查找

18.4.3链上查找的效率

18.5有序链上的查找

18.5.1有序链上的顺序查找

18.5.2有序链上的二分查找

18.6查找方法的选掸

Java插曲8再论泛型

第19章字典

19.1ADT字典的规格说明

19.1.1Java接口

19.1.2迭代器

19.2使用ADT字典

19.2.1问题求解：电话号码簿

19.2.2问题求解：字的频度

19.2.3问题求解：字的词汇索引

19.3Java类库：接口Hap

第20章字典的实现

20.1基于数组的实现

20.1.1基于数组的无序字典

20.1.2基于数组的有序字典

20.2链式实现

20.2.1无序链式字典

20.2.2有序链式字典

第21章散列简介

21.1什么是散列

21.2散列函数

21.2.1计算散列码

21.2.2将散列码压缩为散列表的下标

21.3解决冲突

21.3.1开放地址的线性探查

21.3.2开放地址的二次探查

21.3.3开放地址的双散列

21.3.4开放地址的潜在问题

21.3.5拉链法

第22章使用散列实现字典

22.1散列的效率

22.1.1装填因子

22.1.2开放地址法的代价

22.1.3拉链法的代价

22.2冉散列

22.3冲突解决方案的比较

22.4字典的散列实现

22.4.1散列表中的项

22.4.2数据域和构造方法

22.4.3方法getValue、remove和add

22.4.4迭代器

22.5Java类库：类HashMap

22.6Java类库：类HashSet

第23章树

23.1树的概念

23.1.1层次结构

23.1.2树的术语

23.2树的遍历

23.2.1二又树的遍历

23.2.2一般树的遍历

23.3树的Java接口

23.3.1所有树的接口

23.3.2二叉树的接口

23.4二叉树的示例

23.4.1表达式树

23.4.2决策树

23.4.3二叉查找树

23.4.4堆

23.5一般树的示例

23.5.1语法树

23.5.2游戏树

……

第24章树的实现

第25章二叉查找树的实现

第26章堆的实现

第27章平衡查找树

第28章图

第29章图的实现

附录A文档和程序设计风格

附录BJava基础（在线）

附录CJava类（在线）

附录D从其他类创建类

附录E文件输入和输出（在线）

索引

数据结构与抽象 Java语言描述（原书第4版） 精彩文摘

抽象(abstraction)是一个要求你关注什么而不是如何的过程。当设计类时，执行数据抽象(data abstraction)。你关注想做的或关注数据，而不担心如何完成这些任务及如何表示数据。抽象要求你将注意力集中于重要的数据和操作。当抽象某件事时，你要确定中心思想。例如，书的抽象就是书的简介，与之相对的是整本书。

当设计一个类时，不应该考虑任何方法的实现。即，不应该担心类的方法如何实现它的目标。将规格说明与实现分开，能让你专心于更少的细节，所以能让你的丁作更容易，出错概率更低。详细的、设计良好的规格说明，有助于让实现更易成功。