本书是为数据结构入门课程而编写的教材。作者Frank Carrano在编写过程自始至终特别考虑到了Java与对象，为教师和学生提供了一种精心设计并经过教学实验的方式借助Java讲授ADT和对象。本书独特的设计将内容组织为相对较短的章。这种方式使学习更容易，并留出了教学的机动性。本书教给学生如何使用线性表、词典、栈、队列等等来组织数据。利用这些数据组织方式，学生们将学到算法设计的相关技术。
本书在编写过程中特别考虑到了面向对象程序设计(OOP)的思想与Java语言的特性。它不是从基于另一种程序设计语言的数据结构教材简单地"改编"而来的，因此在数据结构的实现上更加"地道"地运用了Java语言，并且自始至终强调以面向对象的方式来思考、分析和解决问题。
张引，浙江大学计算机科学与技术学院副教授，1999年于浙江大学计算机系取得计算机应用博士学位并留校工作至今。主要研究领域为图形图像、模式识别、数据分析与挖掘、知识表达与发现。
Frank M.Carrano是美国罗得岛大学计算机科学系的荣誉退休教授，于1969年获得美国锡拉丘兹大学计算机科学专业博士学位。他的兴趣包括数据结构、计算机科学教育、社会问题的计算处理和数值计算。Carrano教授对计算机科学高年级本科课程的设计和交付特别感兴趣，曾撰写了多本著名的计算机科学专业的本科教材。
目 录
第1章 袋子
袋子
袋子的行为
袋子的规格说明
接口
ADT袋子的使用
像使用自动售货机一样使用ADT
Java类库： 接口Set
第2章 使用数组实现袋子
使用固定大小的数组实现ADT袋子
一个类比
一组核心方法
核心方法的实现
核心方法的测试
更多方法的实现
删除物品的方法
使用可变大小的数组实现ADT袋子
调整数组的大小
袋子的一种新的实现
使用数组实现ADT袋子的优缺点
第3章 使用链表实现袋子
链表
通过添加节点到表头来创建链表
ADT袋子的链表实现
私有的类Node
类LinkedBag的概要
一些核心方法的定义
核心方法的测试
方法getFrequencyOf
方法contains
从链表中删除物品
方法remove和clear
具有方法set和get的类Node
使用链表实现ADT袋子的优缺点
第4章 算法的效率
动机
算法效率的度量
基本操作次数的统计
最好、 最坏和平均情况
大O表示法
程序结构的复杂度
效率的图形化表示
ADT袋子不同实现的效率
基于数组的实现
基于链表的实现
两种实现方法的比较
第5章 栈
ADT栈的规格说明
利用栈处理代数表达式
应用问题： 中缀代数表达式中括号平衡的
检查
应用问题： 中缀表达式向后缀表达式的
转换
应用问题： 后缀表达式的求值
应用问题： 中缀表达式的求值
程序栈
Java类库： 类Stack
第6章 栈的实现
基于链表的实现
基于数组的实现
基于向量的实现
Java类库： Vector类
使用向量实现ADT栈
第7章 递归
什么是递归
跟踪一个递归方法
有返回值的递归方法
递归地处理一个数组
递归地处理一个链表
递归方法的时间效率
countDown的时间效率
计算xn的时间效率
一个复杂问题的简单解决方案
一个简单问题的拙劣解决方案
尾递归
间接递归
使用栈代替递归
第8章 排序引论
组织Java对数组排序的方法
选择排序
迭代选择排序
递归选择排序
选择排序的效率
插入排序
迭代插入排序
递归插入排序
插入排序的效率
链表的插入排序
希尔排序
Java代码
希尔排序的效率
算法比较
第9章 快速排序方法
归并排序
数组的归并
递归的归并排序
归并排序的效率
迭代的归并排序
Java类库中的归并排序
快速排序
快速排序的效率
创建划分
快速排序的Java代码
Java类库中的快速排序
基数排序
基数排序的伪代码
基数排序的效率
算法比较
第10章 队列、 双端队列和优先队列
ADT队列
解决问题： 模拟排队
解决问题： 计算出售股票时的资本
增益（一）
Java类库： 接口Queue
ADT双端队列
解决问题： 计算出售股票时的资本
增益（二）
Java类库： 接口Deque
Java类库： ArrayDeque类
ADT优先队列
解决问题： 跟踪你的作业
Java类库： 类PriorityQueue
第11章 队列、 双端队列和优先队列的
实现
基于链表队列的实现
基于数组队列的实现
循环数组
有一个未使用存储单元的循环数组
基于向量队列的实现
基于循环链表队列的实现
由两部分构成的循环链表
Java类库： 类AbstractQueue
基于双向链表双端队列的实现
实现优先队列的可用方法
第12章 线性表
ADT线性表的规格说明
使用ADT线性表
Java类库： List接口
Jave类库： ArraryList类
第13章 用数组实现线性表
用数组实现ADT线性表
一个类比
Java实现
用数组实现ADT线性表的效率
用Vector实现ADT线性表
第14章 用链表实现线性表
操作链表节点
在多种位置加入节点
在多种位置删除节点
私有方法getNodeAt
开始实现
数据域和构造函数
在列表结尾加入
在列表给定位置加入
方法isEmpty和toArray
测试核心方法
继续实现
一个更好的实现
尾引用
用链表实现ADT列表的效率
Java类库： 类LinkedList
第15章 迭代器
迭代器是什么
Iterator接口
使用Iterator接口
独立类迭代器
内部类迭代器
基于链表实现
基于数组实现
为什么迭代器方法在它们自己的
类中
ListIterator接口
使用ListIterator接口
ListIterator接口基于数组的实现
内部类
Java类库： Iterable接口
Iterable和for-each循环
修改版接口List
第16章 有序表
ADT有序表的规格说明
使用ADT有序表
链表实现
方法add
链表实现的效率
使用ADT线性表的实现
效率问题
第17章 继承及线性表
使用继承实现有序表
设计一个基类
创建一个抽象基类
有序表的一种高效实现
方法add
第18章 查找
问题引入
查找无序数组
无序数组的迭代式顺序查找
无序数组的递归式顺序查找
顺序查找数组的效率
查找有序数组
有序数组的顺序查找
有序数组的二分查找
Java类库： 方法binarySearch
二分查找数组的效率
查找无序链表
无序链表的迭代式顺序查找
无序链表的递归式顺序查找
顺序查找链表的效率
查找有序链表
有序链表的顺序查找
二分查找有序链表
查找方法的选择
第19章 词典
ADT词典规格说明
Java接口
迭代器
使用ADT词典
问题解决： 电话号码本
问题解决： 词频
问题解决： 词的索引
Java类库： Map接口
第20章 词典的实现
基于数组的实现
一个无序数组词典
一个有序数组词典
基于向量的实例
链式实例
一个无序链式词典
一个有序链式词典
第21章 散列概述
散列是什么
散列函数
计算散列码
将散列码压缩成散列表的索引
处理冲突
用线性探测实现开放定址
用二次探测实现开放定址
用双重散列实现开放定址
开放定址的潜在问题
链地址
第22章 用散列实现词典
散列的效率
容载分析
开放定址消耗分析
链地址消耗分析
再散列
不同冲突解决方案的对比
用散列实现词典的实例
散列表中的条目
数据域和构造函数
getValue， remove和add方法
迭代器
Java类库： HashMap类
Java类库： HashSet类
第23章 树
树的概念
层次化的数据组织
树的术语
树的遍历
遍历二叉树
一般树的遍历
树的Java接口
树的通用接口
二叉树的接口
二叉树的例子
表达式树
决策树
二叉查找树
堆
一般树的例子
语法分析树
游戏树
第24章 树的实现
二叉树的节点
节点的接口
二叉树节点的实现
ADT二叉树的实现
创建基本二叉树
privateSetTree方法
访问器与更改器方法
计算高度和节点数
遍历
表达式树的实现
一般树
一般树的节点
用二叉树表示一般树
第25章 二叉查找树的实现
开始
二叉查找树接口
重复的条目
开始类定义
查找和检索
遍历
添加条目
递归实现
迭代实现
删除条目
删除一个叶子节点的条目
删除节点有一个孩子的条目
删除节点有两个孩子的条目
删除为根的条目
递归实现
迭代实现
操作的效率
平衡的重要性
节点添加的顺序
ADT词典实现
第26章 堆的实现
再论ADT堆
用数组表示堆
插入条目
删除根
创建堆
堆排序
第27章 平衡查找树
AVL树
单旋转
双旋转
实现细节
2-3树
查找2-3树
添加条目至2-3树
添加时分裂节点
2-4树
添加条目至2-4树
比较AVL， 2-3和2-4树
红黑树
红黑树的性质
添加条目到红黑树
Java类库： TreeMap类
B树
第28章 图
一些示例和术语
公路线路图
航空线路图
迷宫
树
遍历
广度优先遍历
深度优先遍历
拓扑排序
路径
寻找路径
无权图的最短路径算法
加权图中的最短路径
ADT图的Java接口
第29章 图的实现
两种实现的概述
邻接矩阵
邻接表
顶点和边
类Vertex的规格说明
内部类Edge
实现Vertex类
ADT图的实现
基本操作
图算法在 线 部 分
第30章 可变的、 不可变的和可复制的对象（英文版本）
附录A Java基础
附录B Java类
附录C 从已有类创建新类
附录D 类的设计
附录E 异常处理
附录F 文件输入与输出
附录G 文档与程序设计风格
新书资讯