数据结构与Java教程 (2008 年度畅销榜NO.2180 )

本书详细介绍了数据间的逻辑关系、存储方式和相关运算。帮助学生逐步学会分析和解决程序设计问题。举例说明了在问题求解过程中类和抽象数据类型的作用，论述了抽象数据类型的主要用途，并在许多实例和习题中使用了递归方法。
本书可作为计算机及其相关专业的本科生、研究生的教材，也可供程序开发人员自学。

第Ⅰ部分 问题求解方法
第1章 程序设计与软件工程基本原理 1
1.1 问题求解与软件工程 1
1.2 完成模块化设计 10
1.3 程序设计关键问题小结 15
第2章 递归：镜子 32
2.1 递归解决方案 32
2.2 事件计数 49
2.3 数组检索 55
2.4 组织数据 62
2.5 递归和效率 67
第3章 数据抽象：墙 76
3.1 抽象数据类型 76
3.2 规定ADT 80
3.3 实现ADT 90
第4章 链表 109
4.1 预备知识 109
4.2 链表程序设计 118
4.3 链表的变种 137
4.4 应用实例：维护库存清单 143
第5章 问题求解的递归方法 153
5.1 回溯 153
5.2 定义语言 157
5.3 递归与数学归纳的关系 167
第Ⅱ部分 用抽象数据类型求解问题
第6章 栈 177
6.1 抽象数据类型 177
6.2 栈ADT的简单应用 181
6.3 栈ADT的实现 185
6.4 应用：代数表达式 191
6.5 应用：检索问题 195
6.6　栈和递归之间的关系 204
第7章 队列 212
7.1 队列 212





7.2 队列ADT的简单应用 213
7.3 队列的实现 215
7.4 面向位置的ADT综述 225
7.5 应用：仿真 226
第8章 类关系 238
8.1 继承回顾 238
8.2 动态绑定和抽象类 246
8.3 ADT表和有序表回顾 254
8.4 面向对象方法的好处 262
第9章 算法效率与排序 267
9.1 算法效率的度量 267
9.2 排序算法及其效率 276
第10章 树 303
10.1 术语 303
10.2 二叉树ADT 309
10.3 二叉查找树 326
10.4 通用树 348
第11章 表格与优先级队列 357
11.1 表格ADT 357
11.2 优先级队列：表格的一种变体 371
第12章 表格的高级实现 389
12.1 平衡查找树 389
12.2 散列法 416
12.3 多重组织的数据 431
第13章 图 439
13.1 术语 439
13.2 图ADT 442
13.3 图的遍历 445
13.4 图的应用 449
第14章 外部方法 468
14.1 外部存储器简介 468
14.2 外部文件中的数据排序 470
14.3 外部表格 476
自测题答案 497

Java程序设计语言是Sun公司最重要的产品之一，经过多年的发展，现在已经真正成长为严谨、主流的开发语言，已经有越来越多的程序开发人员喜欢上这种简单易懂的面向对象语言，此外，Java程序设计语言在服务器及手机中的应用也是非常成功的。由于跨平台与网络功能将是未来软件的发展趋势，而Java在此方面具有得天独厚的优势，因此，我们在选择语言时，不得不考虑Java。正如Don Bailey所说的“我赞成作者使用Java来实现抽象数据类型的决定”。 本书以“墙和镜子”为主题，帮助读者澄清数据抽象（墙）与递归（镜子）这两个挑战性的概念：数据抽象将模块的实现细节同程序的其他部分相隔离，并将实现细节隐藏起来，非常像一堵墙把你同邻居隔开；递归是一种特殊的技术，通过解决类型完全相同的更小问题而解决大问题，非常像镜子中的影像随着每次反射而变得越来越小。本书通过揭示计算机科学家所用的方法和思维过程，帮助学生获得问题求解和程序设计的能力。 本书可以作为高等院校的计算机课程的教材，也可以在介绍数据结构或高级语言程序设计及其问题求解课程中结合使用本书。本书要求读者具备Java或其他语言的基础知识，或者有教师帮助他们通过附录A学习Java。 全书的翻译出版是集体工作的结晶。文家焱、刘伟杰、黄丽姬、柳赐佳、周莎莎、施晓东、施惠琼、蔡桂凌、施琳琼、陈华、柳晁锦、柳晁惠、施卓成、张琼雯、张庭辉、方杰等负责全书的翻译工作，柳小艳、孔颂燕、梁锦伦等负责全书的审校工作，施金庭、柳聿荫、施群肖和缪彩珠等负责全书的录入和排版工作。全书最后由施平安负责统稿。 在翻译过程中，我们对本书中出现的所有术语和难词难句都进行了仔细推敲和研究，然而疏漏和争议之处在所难免，望广大读者提出宝贵的意见。

Frank M. Carrano于1969年获得Syracuse大学的博士学位。多年来，Carrano教授一直致力于数据结构、数据抽象、计算机科学教育、社会信息处理以及数值计算领域的研究，他还非常重视计算机科学专业本科教材的设计和发行工作，目前已经编写并出版了数本知名的教材。 Janet J. Prichard分别于1986年和1995年获得Rhode Island大学的理学硕士学位和哲学博士学位，目前在Bryant 大学任助理教授。她的研究领域包括实时数据库、数据库查询语言、网络安全等。

本书源于Paul Helman和Robert Veroff编著的Intermediate Problem Solving and Data Structures: Walls and Mirrors一书（该书1986年由Benjamin/Cummings有限出版公司出版）。本书基于原书的组织结构和基本观点，从原著中选取一些技术、文本、插图及习题。Helman和Veroff教授引入了两个非常强大的类比：墙（wall）和镜子（mirror），这使我们更容易理解和学习计算机科学。 本书重点是数据抽象和其他问题求解工具。考虑到本科课程的多样性，本书覆盖了相当广泛的内容，以使其适合其他课程。例如，可以在介绍数据结构或高级语言程序设计及其问题求解课程中使用本书。本书目标是在数据抽象、面向对象程序设计和问题求解方法方面给学生打下坚实的基础。 致 学 生 已经有成千上万的学生阅读并学习过本书。“墙”和“镜子”表示贯穿于本书的两种基本的问题求解方法。数据抽象将模块的实现细节同程序的其他部分相分离，并将实现细节隐藏起来，非常像一堵墙把你同邻居隔开。递归是一种重复的技术，通过解决类型完全相同的更小的问题而解决大问题，非常像镜子中的影像随着每次反射而变得越来越小。 本书假定读者具备某些基本的Java知识。一些读者可能需要重温Java语言，甚至从头进行学习（参考附录A）。读者需要掌握if和switch选择结构；for、while和do循环结构；类、方法和参数；数组；字符串和文件。除了附录A外，本书还在第3章和第8章讨论Java类。我们还假设读者不具备第2章和第5章中论述的递归方法的使用经验。 方 法 本书详细说明了Java语言的优势和不足，同时继续采用对初级水平的学生容易理解的教学方法和材料。 背景知识 本书假设读者已具备Java或其他语言的基础知识，并有教师帮助他们通过附录A过渡到Java。除了该附录外，本书正式论述了Java类，包括类、继承、多态性、接口和包的基本概念。尽管本书介绍了这些内容以及抽象数据类型（ADT）的实现，但重点仍然是ADT，而不是Java。这些在面向对象程序设计的环境下介绍，但它假设未来的课程将详细讨论面向对象设计和软件工程，因此重点仍是数据抽象。 适应性 本书内容丰富。读者可以选择想学的内容，并按照自己的计划学习。各章的从属关系进一步说明了章节的学习顺序。 第Ⅰ部分中，各章可以根据学生的背景知识选择。其中有3章大篇幅地介绍了数据抽象和递归。数据抽象和递归都很重要，但到底应先讲哪部分却意见不一。尽管递归的章节在前，数据抽象的章节在后，但这一顺序可以调整。 第Ⅱ部分中，各章讲解顺序也可灵活处理。例如，可在介绍栈（第6章）之前或之后介绍类关系（第8章）；也可以在学完第5章后引入算法效率与排序（第9章）；可以在队列之前介绍树，或在表之前介绍图，或在学完表格后学习散列法、平衡二叉树和优先级队列（其他顺序亦可），也可在课程的早些时候学习外部方法（第14章），例如，在学完第9章中的归并排序后学习外部排序。 数据抽象 抽象数据类型的设计及应用是始终贯穿本书的问题求解方法。我们用几个实例说明了如何设计ADT，这是整个解决方案设计的一部分。我们首先用伪代码定义了所有ADT，然后在论述这些ADT的实现之前，在简单应用中使用。ADT与实现它的数据结构之间的差异仍然在整个讨论的最前面论述。本书一开始就解释了封装和Java类，并使学生明白Java类如何在ADT的客户程序中将已实现的数据结构隐藏起来。抽象数据类型包括：表、栈、队列、树、表格、堆和优先级队列，它们构成了课程的基础。 问题求解 本书强调了计算机科学家所用的方法和思维过程，帮助学生掌握问题求解和程序设计的能力。学习开发、分析和实现解决方案的方法同学习算法一样重要。 针对示例问题，提出解决方案的分析方法，在贯穿本书的解题方案设计过程中，使用了算法、数据结构以及递归逐步求精。 本书很早就介绍了Java引用和链表的处理，并在构建数据结构时使用了它们。本书还初步介绍了算法的数量级分析方法。这种方法先非正式地考虑，然后更量化地考虑基于数组和基于引用的数据结构的优缺点。各种方案的选择及实现是问题求解的核心课题。 最后研究程序设计风格、前置条件和后置条件的编档、辅助调试手段和循环不变量，它们都是实现和验证解决方案的重要手段。整本书都论述这些主题。 应用 本书围绕主题给出了一些典型应用。例如，折半检索、快速排序和归并排序算法是递归的重要应用，另外还介绍了数量级分析。在平衡二叉树搜索、散列法和文件索引这样一些课题中，又继续讨论搜索问题。在外部文件一节中还将再次讨论搜索和排序问题。 识别和计算代数表达式的算法，在递归环境下首先介绍，然后在栈的应用中再次讨论。其他应用包括：作为回溯法实例的八皇后问题、作为队列应用实例的事件驱动仿真，以及作为栈和队列应用实例的图搜索和遍历。 概 述 为便于学习和方便地剪裁内容以适应实际需要，本书进行了精心规划。 组织 本书内容分成两部分：第1章到第11章通常是一学期课程的核心，第1章或第2章可作为学生的复习材料。第11章到第14章的内容取决于这门课程在整个课程体系中的地位。 第Ⅰ部分是问题求解方法。第1章强调程序设计和软件工程的主要问题。下一章讨论递归，该章是为那些对递归这一重要课题不了解的学生准备的。递归地思考问题的能力是计算机科学家应具备的最有用的技能之一，对帮助人们更好地理解问题的性质通常具有重大的价值。这一章详尽地讨论递归，在第5章将再次深入地讨论。全书广泛使用递归，包括从简单的递归定义到语言识别、搜索、排序等算法。第3章详细论述数据抽象和抽象数据类型。讨论完ADT规范说明和用途后，本章讨论Java类、接口和异常，并用它们来实现ADT。第4章在讨论Java引用变量和链表时介绍了附加实现工具。 第Ⅱ部分是使用抽象数据类型进行问题求解。第Ⅱ部分继续研究数据抽象的用途。这一部分首先详细说明了栈、队列、二叉树、二叉查找树、表、堆和优先级队列等的基本抽象数据类型，然后用类实现它们。在实例中使用了抽象数据类型，并对它们的实现进行了比较。第8章通过进一步讨论继承、包、类与类之间的关系和迭代器，扩展了Java类的覆盖内容。第9章中，通过引入数量级分析和相应表示法，形式化地描述了前面讨论过的算法的效率。本章研究了几种查找和排序算法，包括递归的归并排序和快速排序的效率。 第Ⅱ部分还讨论一些高级课题。如平衡查找树（2-3、2-3-4、红黑和AVL树）和散列法，它们被当成表格的实现方式来研究的。我们对这些实现进行了分析，以确定各自支持的最优操作。最后讨论外部直接访问文件中的数据存储。修改了归并排序算法以便对数据排序，使用外部散列法和B-树索引对其进行搜索。这些搜索算法是内部散列法和2-3树的推广。 补充材料 本书读者可以在线（www.aw.com/cssupport）获得下列补充材料。 源代码：读者可以使用本书中出现的所有Java类、方法和程序 勘误表：我们努力做到不犯错误，但错误是难免的。诚邀读者指出更多的问题 某些教师可得到补充材料。请联系当地销售代理或发邮件aw.cse@aw.com 教师手册。该手册包含教学提示、示例教学大纲及所有习题的解答 习题库。包含大量多选题、判断题和简答题 PowerPoint讲义