描述
开 本: 16开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787111567288丛书名: 计算机科学丛书
内容简介
本书是一本数据结构的教材，Java语言与数据结构两条知识主线贯穿始终，这两条主线既相互独立又相互支撑。本书介绍了计算机编程中使用的数据结构和算法，包括29章，每章涉及一个ADT或其不同实现的规格说明和用法；书中贯穿9个Java插曲，涉及Java的高级特性。本书主要讲述了组织数据、设计类、包、栈、递归、排序、队列、双端队列、优先队列、线性表、有序表、查找、字典、散列、树、二叉查找树、堆、平衡查找树、图等内容，并对算法的效率进行了分析。本书非常适合作为大学本科生数据结构课程的教材，也可作为计算机研究与开发人员的参考书。
目 录
目 录
Data Structures and Abstractions with Java, Fourth Edition
出版者的话
译者序
前言
引言 组织数据 1
序言 设计类 3
P.1 封装 3
P.2 说明方法 5
P.2.1 注释 5
P.2.2 前置条件和后置条件 5
P.2.3 断言 6
P.3 Java接口 7
P.3.1 写一个接口 8
P.3.2 实现一个接口 9
P.3.3 接口作为数据类型 11
P.3.4 派生一个接口 12
P.3.5 接口内命名常量 13
P.4 选择类 14
P.4.1 标识类 15
P.4.2 CRC卡 15
P.4.3 统一建模语言 16
P.5 重用类 17
第1章 包 22
1.1 什么是包 22
1.2 说明一个包 23
1.3 使用ADT包 30
1.4 像使用自动贩卖机一样使用ADT 33
1.5 ADT集合 34
1.6 Java类库：接口Set 35
Java插曲1 泛型 39
第2章 使用数组实现包 43
2.1 使用固定大小的数组实现ADT包 43
2.1.1 类比 43
2.1.2 一组核心方法 44
2.1.3 实现核心方法 45
2.1.4 让实现安全 51
2.1.5 测试核心方法 54
2.1.6 实现更多的方法 56
2.1.7 删除项的方法 58
2.2 使用可变大小的数组实现ADT包 65
2.2.1 可变大小数组 65
2.2.2 包的新实现 68
2.3 使用数组实现ADT包的优缺点 70
Java插曲2 异常 75
第3章 使用链式数据实现包 82
3.1 链式数据 82
3.2 ADT包的链式实现 84
3.2.1 私有类Node 84
3.2.2 类LinkedBag的框架 85
3.2.3 定义一些核心方法 86
3.2.4 测试核心方法 89
3.2.5 方法getFrequencyOf 90
3.2.6 方法contains 91
3.3 从链中删除一项 92
3.4 有设置和获取方法的类Node 96
3.5 使用链实现ADT包的优缺点 98
第4章 算法的效率 102
4.1 动机 102
4.2 测量算法的效率 103
4.2.1 计数基本操作 105
4.2.2 、差和平均情形 106
4.3 大O表示 107
4.4 描述效率 110
4.5 实现ADT包的效率 113
4.5.1 基于数组的实现 113
4.5.2 链式实现 114
4.5.3 两种实现的比较 115
第5章 栈 121
5.1 ADT栈的规格说明 121
5.2 使用栈来处理代数表达式 125
5.2.1 问题求解：检查中缀代数表达式中平衡的分隔符 125
5.2.2 问题求解：将中缀代数表达式转换为后缀表达式 129
5.2.3 问题求解：计算后缀表达式的值 133
5.2.4 问题求解：计算中缀表达式的值 134
5.3 程序栈 136
5.4 Java类库：类Stack 137
第6章 栈的实现 142
6.1 链式实现 142
6.2 基于数组的实现 144
6.3 基于向量的实现 148
6.3.1 Java类库：类Vector 148
6.3.2 使用向量实现ADT栈 149
第7章 递归 154
7.1 什么是递归 154
7.2 跟踪递归方法 158
7.3 返回一个值的递归方法 160
7.4 递归处理数组 162
7.5 递归处理链 165
7.6 递归方法的时间效率 166
7.6.1 countDown的时间效率 166
7.6.2 计算xn的时间效率 167
7.7 困难问题的简单求解方案 168
7.8 简单问题的低劣求解方案 172
7.9 尾递归 174
7.10 间接递归 176
7.11 使用栈来替代递归 177
Java插曲3 再谈泛型 185
第8章 排序简介 194
8.1 对数组进行排序的Java方法的组织 194
8.2 选择排序 195
8.2.1 迭代选择排序 196
8.2.2 递归选择排序 198
8.2.3 选择排序的效率 198
8.3 插入排序 199
8.3.1 迭代插入排序 199
8.3.2 递归插入排序 201
8.3.3 插入排序的效率 202
8.3.4 链式结点链的插入排序 203
8.4 希尔排序 205
8.4.1 算法 206
8.4.2 希尔排序的效率 207
8.5 算法比较 208
第9章 更快的排序方法 213
9.1 归并排序 213
9.1.1 归并数组 213
9.1.2 递归归并排序 214
9.1.3 归并排序的效率 216
9.1.4 迭代归并排序 217
9.1.5 Java类库中的归并排序 218
9.2 快速排序 218
9.2.1 快速排序的效率 219
9.2.2 创建划分 219
9.2.3 实现快速排序 221
9.2.4 Java类库中的快速排序 223
9.3 基数排序 223
9.3.1 基数排序的伪代码 225
9.3.2 基数排序的效率 225
9.4 算法比较 226
Java插曲4 再谈异常 231
第10章 队列、双端队列和优先队列 238
10.1 ADT队列 238
10.1.1 问题求解：模拟排队 241
10.1.2 问题求解：计算出售股票的资本收益 246
10.1.3 Java类库：接口Queue 248
10.2 ADT双端队列 249
10.2.1 问题求解：计算出售股票的资本收益 251
10.2.2 Java类库：接口Deque 252
10.2.3 Java类库：类ArrayDeque 253
10.3 ADT优先队列 254
10.3.1 问题求解：跟踪任务分配 255
10.3.2 Java类库：类PriorityQueue 257
第11章 队列、双端队列和优先队列的实现 262
11.1 队列的链式实现 262
11.2 基于数组实现队列 265
11.2.1 循环数组 266
11.2.2 带一个不用位置的循环数组 267
11.3 队列的循环链式实现 272
11.4 Java类库：类AbstractQueue 277
11.5 双端队列的双向链式实现 2
Data Structures and Abstractions with Java, Fourth Edition
出版者的话
译者序
前言
引言 组织数据 1
序言 设计类 3
P.1 封装 3
P.2 说明方法 5
P.2.1 注释 5
P.2.2 前置条件和后置条件 5
P.2.3 断言 6
P.3 Java接口 7
P.3.1 写一个接口 8
P.3.2 实现一个接口 9
P.3.3 接口作为数据类型 11
P.3.4 派生一个接口 12
P.3.5 接口内命名常量 13
P.4 选择类 14
P.4.1 标识类 15
P.4.2 CRC卡 15
P.4.3 统一建模语言 16
P.5 重用类 17
第1章 包 22
1.1 什么是包 22
1.2 说明一个包 23
1.3 使用ADT包 30
1.4 像使用自动贩卖机一样使用ADT 33
1.5 ADT集合 34
1.6 Java类库：接口Set 35
Java插曲1 泛型 39
第2章 使用数组实现包 43
2.1 使用固定大小的数组实现ADT包 43
2.1.1 类比 43
2.1.2 一组核心方法 44
2.1.3 实现核心方法 45
2.1.4 让实现安全 51
2.1.5 测试核心方法 54
2.1.6 实现更多的方法 56
2.1.7 删除项的方法 58
2.2 使用可变大小的数组实现ADT包 65
2.2.1 可变大小数组 65
2.2.2 包的新实现 68
2.3 使用数组实现ADT包的优缺点 70
Java插曲2 异常 75
第3章 使用链式数据实现包 82
3.1 链式数据 82
3.2 ADT包的链式实现 84
3.2.1 私有类Node 84
3.2.2 类LinkedBag的框架 85
3.2.3 定义一些核心方法 86
3.2.4 测试核心方法 89
3.2.5 方法getFrequencyOf 90
3.2.6 方法contains 91
3.3 从链中删除一项 92
3.4 有设置和获取方法的类Node 96
3.5 使用链实现ADT包的优缺点 98
第4章 算法的效率 102
4.1 动机 102
4.2 测量算法的效率 103
4.2.1 计数基本操作 105
4.2.2 、差和平均情形 106
4.3 大O表示 107
4.4 描述效率 110
4.5 实现ADT包的效率 113
4.5.1 基于数组的实现 113
4.5.2 链式实现 114
4.5.3 两种实现的比较 115
第5章 栈 121
5.1 ADT栈的规格说明 121
5.2 使用栈来处理代数表达式 125
5.2.1 问题求解：检查中缀代数表达式中平衡的分隔符 125
5.2.2 问题求解：将中缀代数表达式转换为后缀表达式 129
5.2.3 问题求解：计算后缀表达式的值 133
5.2.4 问题求解：计算中缀表达式的值 134
5.3 程序栈 136
5.4 Java类库：类Stack 137
第6章 栈的实现 142
6.1 链式实现 142
6.2 基于数组的实现 144
6.3 基于向量的实现 148
6.3.1 Java类库：类Vector 148
6.3.2 使用向量实现ADT栈 149
第7章 递归 154
7.1 什么是递归 154
7.2 跟踪递归方法 158
7.3 返回一个值的递归方法 160
7.4 递归处理数组 162
7.5 递归处理链 165
7.6 递归方法的时间效率 166
7.6.1 countDown的时间效率 166
7.6.2 计算xn的时间效率 167
7.7 困难问题的简单求解方案 168
7.8 简单问题的低劣求解方案 172
7.9 尾递归 174
7.10 间接递归 176
7.11 使用栈来替代递归 177
Java插曲3 再谈泛型 185
第8章 排序简介 194
8.1 对数组进行排序的Java方法的组织 194
8.2 选择排序 195
8.2.1 迭代选择排序 196
8.2.2 递归选择排序 198
8.2.3 选择排序的效率 198
8.3 插入排序 199
8.3.1 迭代插入排序 199
8.3.2 递归插入排序 201
8.3.3 插入排序的效率 202
8.3.4 链式结点链的插入排序 203
8.4 希尔排序 205
8.4.1 算法 206
8.4.2 希尔排序的效率 207
8.5 算法比较 208
第9章 更快的排序方法 213
9.1 归并排序 213
9.1.1 归并数组 213
9.1.2 递归归并排序 214
9.1.3 归并排序的效率 216
9.1.4 迭代归并排序 217
9.1.5 Java类库中的归并排序 218
9.2 快速排序 218
9.2.1 快速排序的效率 219
9.2.2 创建划分 219
9.2.3 实现快速排序 221
9.2.4 Java类库中的快速排序 223
9.3 基数排序 223
9.3.1 基数排序的伪代码 225
9.3.2 基数排序的效率 225
9.4 算法比较 226
Java插曲4 再谈异常 231
第10章 队列、双端队列和优先队列 238
10.1 ADT队列 238
10.1.1 问题求解：模拟排队 241
10.1.2 问题求解：计算出售股票的资本收益 246
10.1.3 Java类库：接口Queue 248
10.2 ADT双端队列 249
10.2.1 问题求解：计算出售股票的资本收益 251
10.2.2 Java类库：接口Deque 252
10.2.3 Java类库：类ArrayDeque 253
10.3 ADT优先队列 254
10.3.1 问题求解：跟踪任务分配 255
10.3.2 Java类库：类PriorityQueue 257
第11章 队列、双端队列和优先队列的实现 262
11.1 队列的链式实现 262
11.2 基于数组实现队列 265
11.2.1 循环数组 266
11.2.2 带一个不用位置的循环数组 267
11.3 队列的循环链式实现 272
11.4 Java类库：类AbstractQueue 277
11.5 双端队列的双向链式实现 2
前 言
前 言Data Structures and Abstractions with Java, Fourth Edition欢迎使用本书，本书可作为数据结构课程的教材，例如CS-2课程。
作者集30余年讲授本科生计算机科学课程的教学经验，时刻谨记师生的需求来写作本书。作者想让本书适合读者阅读，这样学生学得更容易，老师教得更有效果。模仿现实世界情形的一些例子作为新素材的背景，帮助学生理解抽象概念。使用很多简单的图来解释及阐述复杂的思想。
这次修订保留了之前版本中的章节题目及次序。读者会发现，我们特别强调不同数据结构的需求及实现的设计决策，同时新增加了对安全可靠程序设计惯例的介绍。
我们希望你乐于阅读本书。与之前的众多读者一样，你能学会（或讲授）数据结构，有效果且能坚持下去。
欢迎使用本书的师生联系我们。非常感谢您的意见、建议及校正。联系我们的方式如下：
E-mail: [email protected]或[email protected]: www.facebook.com/makingitrealTwitter: twitter.com/Frank_M_CarranoWebsite: frank-m-carrano.com/makingitreal本版的组织结构本书采用易于讲授及易于学习的方式来组织、排列各章内容，使得每次将注意力集中在一个概念上，也能让阅读题的次序更灵活，从而能清楚地区分抽象数据类型（ADT）的规格说明（specification）及其实现。为此，我们将内容分为29章。每章涉及ADT或其不同实现的规格说明及用法。你可以只讨论一种ADT的规格说明及其实现，也可以在考虑实现之前讨论多种ADT的规格说明及用法。本书的组织方式方便你按喜欢的次序选择章节学习。
本版的创新之处章节顺序及涉及的题目与前面的版本保持一致，根据读者的反馈，我们将有些资料从附录或在线形式移到书中的正文部分。基于读者的建议及我们自己的修订意愿，对本书做了修改。本版中的主要修改如下：
在引言之后和第1章之前新增加了一个序言，它主要讨论如何设计类。这些资料包含在前一版本的附录D中。
在全书必要的地方，新安排了从附录或章节中抽出的与Java相关的Java插曲。这样做，有效地区分了概念及Java本身的问题。这些Java插曲的题目如下所示，它们穿插在章间：
Java插曲1 泛型Java插曲2 异常Java插曲3 再谈泛型Java插曲4 再谈异常Java插曲5 迭代器Java插曲6 可变及不可变对象Java插曲7 继承和多态Java插曲8 再论泛型Java插曲9 克隆安全可靠的程序设计是第2章中的一个新话题，将在新增加的“安全说明”部分讨论，并体现在实现ADT的Java代码中。
在以栈的介绍开头的第5章中，大多数的ADT方法通过抛出异常来表示失败。当它不是集合（collection）中的数据值时方法仅返回null。
泛型的扩展部分讨论了泛型方法及有界类型。
不可变、可变及克隆对象在Java插曲中介绍，而不像前一版本那样放在在线的第30章中。
增加的“设计决策”部分继续介绍规格说明及实现具体ADT时的抉择，并提供选择的理由。
对图做了修改，结点或数组元素中都显示具体对象而不是仅显示值。
不再包含基于向量实现的ADT线性表和队列的内容，但留作程序设计项目。
程序清单中给出了行号。
Java代码遵从Java 8标准。
增补了一个测试用例库。
下面是各章节的较大修改：
第1章除包之外，还介绍了ADT集合（set）。
第2章介绍了安全可靠的程序设计方法。本章建议修改的代码已集成到后续各章的所有ADT的实现中。
第5和6章在ADT栈的规格说明及实现中用到了异常。
第8和9章用伪代码代替一些排序方法的Java代码。
第10和11章在ADT队列、双端队列及优先队列的规格说明和实现中用到了异常。
第11章不再包含基于向量实现ADT队列的内容，这些内容留作程序设计项目。
第12、13和14章在ADT线性表的规格说明及实现中用到了异常。
第13章修改了ADT线性表基于数组的实现，忽略了数组元素从下标0开始。不再包含基于向量实现ADT线性表的内容，但留作程序设计项目。
第15章仅涉及ADT线性表的迭代器。Java中迭代器的概念放在前面的Java插曲5中，而不是放在这一章中。
第20章不再包含基于向量实现ADT字典的内容，这些内容留作程序设计项目。
第23章定义了平衡二叉树，前一版放在第25章中。
第24章不再定义二叉链表结点的接口，类BinaryNode也不再实现这个接口。
如何学习本书本书讨论的内容涉及数据的不同组织方法，以便所给的应用程序能以高效的方式访问并处理数据。这些内容是你未来进一步学习计算机科学知识所不可或缺的，因为它们是创建复杂、可靠软件所必需的基础知识。不论你是对设计视频游戏感兴趣，还是对设计机器人控制手术的软件感兴趣，学习数据结构都是走向成功的必经之路。即使你现在没有学完本书的全部内容，在后面的学习中也还可能会遇到相关话题。我们希望你享受阅读本书的过程，希望本书能成为你未来课程学习的有用参考资料。
读过前言后，还应该读引言，从而可以快速了解本书要讨论哪些内容，
作者集30余年讲授本科生计算机科学课程的教学经验，时刻谨记师生的需求来写作本书。作者想让本书适合读者阅读，这样学生学得更容易，老师教得更有效果。模仿现实世界情形的一些例子作为新素材的背景，帮助学生理解抽象概念。使用很多简单的图来解释及阐述复杂的思想。
这次修订保留了之前版本中的章节题目及次序。读者会发现，我们特别强调不同数据结构的需求及实现的设计决策，同时新增加了对安全可靠程序设计惯例的介绍。
我们希望你乐于阅读本书。与之前的众多读者一样，你能学会（或讲授）数据结构，有效果且能坚持下去。
欢迎使用本书的师生联系我们。非常感谢您的意见、建议及校正。联系我们的方式如下：
E-mail: [email protected]或[email protected]: www.facebook.com/makingitrealTwitter: twitter.com/Frank_M_CarranoWebsite: frank-m-carrano.com/makingitreal本版的组织结构本书采用易于讲授及易于学习的方式来组织、排列各章内容，使得每次将注意力集中在一个概念上，也能让阅读题的次序更灵活，从而能清楚地区分抽象数据类型（ADT）的规格说明（specification）及其实现。为此，我们将内容分为29章。每章涉及ADT或其不同实现的规格说明及用法。你可以只讨论一种ADT的规格说明及其实现，也可以在考虑实现之前讨论多种ADT的规格说明及用法。本书的组织方式方便你按喜欢的次序选择章节学习。
本版的创新之处章节顺序及涉及的题目与前面的版本保持一致，根据读者的反馈，我们将有些资料从附录或在线形式移到书中的正文部分。基于读者的建议及我们自己的修订意愿，对本书做了修改。本版中的主要修改如下：
在引言之后和第1章之前新增加了一个序言，它主要讨论如何设计类。这些资料包含在前一版本的附录D中。
在全书必要的地方，新安排了从附录或章节中抽出的与Java相关的Java插曲。这样做，有效地区分了概念及Java本身的问题。这些Java插曲的题目如下所示，它们穿插在章间：
Java插曲1 泛型Java插曲2 异常Java插曲3 再谈泛型Java插曲4 再谈异常Java插曲5 迭代器Java插曲6 可变及不可变对象Java插曲7 继承和多态Java插曲8 再论泛型Java插曲9 克隆安全可靠的程序设计是第2章中的一个新话题，将在新增加的“安全说明”部分讨论，并体现在实现ADT的Java代码中。
在以栈的介绍开头的第5章中，大多数的ADT方法通过抛出异常来表示失败。当它不是集合（collection）中的数据值时方法仅返回null。
泛型的扩展部分讨论了泛型方法及有界类型。
不可变、可变及克隆对象在Java插曲中介绍，而不像前一版本那样放在在线的第30章中。
增加的“设计决策”部分继续介绍规格说明及实现具体ADT时的抉择，并提供选择的理由。
对图做了修改，结点或数组元素中都显示具体对象而不是仅显示值。
不再包含基于向量实现的ADT线性表和队列的内容，但留作程序设计项目。
程序清单中给出了行号。
Java代码遵从Java 8标准。
增补了一个测试用例库。
下面是各章节的较大修改：
第1章除包之外，还介绍了ADT集合（set）。
第2章介绍了安全可靠的程序设计方法。本章建议修改的代码已集成到后续各章的所有ADT的实现中。
第5和6章在ADT栈的规格说明及实现中用到了异常。
第8和9章用伪代码代替一些排序方法的Java代码。
第10和11章在ADT队列、双端队列及优先队列的规格说明和实现中用到了异常。
第11章不再包含基于向量实现ADT队列的内容，这些内容留作程序设计项目。
第12、13和14章在ADT线性表的规格说明及实现中用到了异常。
第13章修改了ADT线性表基于数组的实现，忽略了数组元素从下标0开始。不再包含基于向量实现ADT线性表的内容，但留作程序设计项目。
第15章仅涉及ADT线性表的迭代器。Java中迭代器的概念放在前面的Java插曲5中，而不是放在这一章中。
第20章不再包含基于向量实现ADT字典的内容，这些内容留作程序设计项目。
第23章定义了平衡二叉树，前一版放在第25章中。
第24章不再定义二叉链表结点的接口，类BinaryNode也不再实现这个接口。
如何学习本书本书讨论的内容涉及数据的不同组织方法，以便所给的应用程序能以高效的方式访问并处理数据。这些内容是你未来进一步学习计算机科学知识所不可或缺的，因为它们是创建复杂、可靠软件所必需的基础知识。不论你是对设计视频游戏感兴趣，还是对设计机器人控制手术的软件感兴趣，学习数据结构都是走向成功的必经之路。即使你现在没有学完本书的全部内容，在后面的学习中也还可能会遇到相关话题。我们希望你享受阅读本书的过程，希望本书能成为你未来课程学习的有用参考资料。
读过前言后，还应该读引言，从而可以快速了解本书要讨论哪些内容，
评论
还没有评论。