内容简介

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

作者简介

Frank M.Carrano，是美国罗得岛大学（University of Rhode Island）计算机科学系荣誉退休教授，于1969年获得美国锡拉丘兹大学计算机科学专业博士学位。他的兴趣包括数据结构、计算机科学教育、社会问题的计算处理和数值计算。Carrano教授对计算机科学高年级本科课程的设计和交付特别感兴趣，曾撰写了多本的计算机科学高年级本科生教科书。

Timothy Henry，是美国罗得岛大学计算机科系副教授，1986年获得美国欧道明大学（Old Dominion University）计算机科学专业硕士学位，2001年获得美国罗得岛大学应用数学专业博士学位。从2000年至今一直保有美国PMI的项目管理专家（Project Management Professional，PMP）认证资格。他教授的课程有：数据结构与抽象、编程语言基础、操作系统与网络、计算机系统基础、计算机科学项目、文件系统取证等。研究的领域有：计算机和数学取证、交互式3D图形关系、传感器网络。

目录

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

感悟与笔记

• 抽象数据类型或ADT是数据集和数据上操作的规格说明。这个规格说明不- 指明如何保存数据或如何实现操作，它与任何程序设计语言无关。
• 当使用数据抽象来设计一个ADT时，关注想对数据做什么，而不用担心如- 何完成这些任务。即，忽略如何表示数据及如何操纵数据的细节。
• 程序设计语言中的ADT的表示封装了数据和操作。因此，具体的数据表示- 及方法实现都对客户隐藏。
• 集合是保存一组其他对象的对象。
• 包是无特殊次序的项的有限集合。
• 客户仅能使用ADT包中定义的操作来控制或访问包的项。
• 当向包中添加对象时，不能表明项在包中的位置。
• 可以从包中删除一个对象，或者按给定值，或者未指定。还可以从包中删除所有的对象。
• 包可以报告它是否含有给定的对象，还可以报告给定对象在包中出现的次数。
• 包可以告诉你它当前含有的对象数，能提供保存这些对象的数组。
• 集合（set）是一个不含有重复项的包。
• 对要讨论的类，要在实现它们之前使用类似CRC卡和UML这样的工具仔细说明方法。
• 设计了ADT草稿后，通过写使用ADT的伪代码，确认你理解了操作及它们的设计。
• 组织ADT规格说明的一种方式是写一个Java接口。
• 在定义类之前写一个测试它的程序，看看你是否完全理解并满意类中方法的规格说明。

会员免费下载

链接：https://pan.baidu.com/s/1VCj0R_er5KJ0tbKBhEGnDw

提取码： ****** 查看

￥69/年 开通VIP会员

成为本站VIP会员即可无限下载。 请先点击百度网盘，看资源是否还在，不在请点击链接通知站长补资源。

资源标签点击标签可查看对应分类的资源

Java数据结构与算法

资源推荐

免费 图解数据结构：使用Java

C++ 程序设计语言：第4部分 标准库（原书第4版）

C++编程思想（两卷合订本）

CSS世界

JavaScript DOM编程艺术（第2版）

C++ Primer Plus（第6版） 中文版

Vue.js快速入门

Java编程思想（第4版） [thinking in java]