本书是介绍数据结构的经典教材，第5版增加了新的覆盖递归内容的一章，介绍语法、语言及回溯；还增加了设计决策、注、安全说明及编程技巧内容；在大部分章节中，本版侧重游戏、电子商务及财务的新练习和程序设计项目；同时调整了某些主题的次序，相关的主题集中介绍，内容连贯。


经典数据结构教材新版，以Java语言与数据结构两条知识主线贯穿始终

欢迎使用第5版，本书可作为数据结构课程的教材，例如CS-2课程。
作者集30余年讲授本科生计算机科学的教学经验，时刻谨记师生的需求来写作本书。作者想让本书适合读者阅读，这样学生学得更容易，老师教得更有效果。为此，本书将资料分为一个个的小部分—我们称之为“段”，这样容易理解且方便学习。模仿现实世界情形的一些例子作为新素材的背景，帮助学生理解抽象概念。使用很多简单的图来解释及阐述复杂的思想。
这次修订重点关注各种数据结构的规范说明和实现的设计决策，并强调安全可靠的程序设计实践。
本书的组织结构
本书本着让教学和学习更容易的宗旨来组织、排列及划分所讨论的主题，主要包括：
每次将读者的注意力集中在一个概念上。
为读者提供灵活的阅读次序。
明确区分抽象数据类型（ADT）的规范说明及其实现。
将Java的相关内容独立为Java插曲，读者可以根据需要选择阅读。
为此，我们将内容分为30章，每章由带编号且每次只涉及一个概念的小段组成。每章涉及ADT的规范说明及用法或者其实现方式。你可以选择学习一种ADT的规范说明，然后研究其实现方式，也可以在考虑实现问题之前学习几种ADT的规范说明及用法。本书的组织方式方便你按喜欢的次序选择阅读章节。
我们使用Java插曲来介绍与Java相关的内容，从而明确地将涉及数据结构的内容与Java的具体问题区分开来。这些插曲根据需要穿插在本书的章节之间。不过，我们的关注点是数据结构而不是Java。从后面的目录中你可以看到这些插曲的标题，以及它们在章节之间的位置。
本版的新内容
第5版加强了第4版的内容，承袭了原有版本适合入门级学生的教学方法，保留了以前版本中的形式。根据读者的建议及我们自己的愿望，我们对本书做了全面修订，使内容更清晰和准确。本版中的主要修订如下：
增加了讨论更多递归内容的一章（第14章），介绍语法、语言及回溯。
继续介绍安全可靠的编程实践。
增加了新的设计决策、注、安全说明及程序设计技巧。
在大部分章节中，增加了侧重于游戏、电子商务及财务的新练习和程序设计项目。
调整了某些主题的次序。
完善了术语、描述和用词，以便于理解。
修改了插图，使之更容易阅读和理解。
将“自测题”改名为“学习问题”，并将答案移至网站中，鼓励小组一起讨论答案。
书中包含了关于Java类的附录，而不是将其放在网站中。
减少了书中的Java代码数量。
确保所有的Java代码兼容Java 9。
联系我们
欢迎使用本书的师生联系我们。非常感谢您的意见、建议及校正。我们的联系方式如下：
电子邮件：carrano@acm.org 或timhenry@acm.org
Twitter：twitter.com/makingCSreal
网站：www.makingCSreal.com 和 timothyhenry.net
Facebook：www.facebook.com/makingCSreal
如何学习本书
本书讨论的内容涉及数据的不同组织方法，以便所给的应用程序能以高效的方式访问并处理数据。这些内容是你未来进一步学习计算机科学知识所不可或缺的，因为它们是创建复杂、可靠的软件所必需的基础知识。不论你是对设计视频游戏感兴趣，还是对设计机器人控制手术的软件感兴趣，学习数据结构都是成功的必经之路。即使你现在不学完本书的全部内容，以后也可能遇到相关话题。我们希望你享受阅读本书的过程，希望本书能成为你未来课程学习的有用参考资料。
读过前言后，你应该读导论，从而快速了解本书要讨论哪些内容，以及开始学习之前你必须了解Java的哪些方面。序言中讨论了类的设计及Java接口的使用。本书从头至尾使用了接口。附录A、B和C讨论了javadoc注释、Java类和继承。Java插曲贯穿于书中，涵盖所需的Java高级特性。注意，在封二给出了Java保留字及运算符优先级，封三给出了基本数据类型及Unicode字符编码。
请一定要浏览前言的其他部分，了解有助于你学习的特点。
提高学习效率的特点
每章的开头是先修章节列表和读完本章要达成的学习目标。贯穿全书的其他教学要素如下：
注　重要的思想用突出显示的段落来表示或概括，意味着要与上下文一起阅读。
安全说明　这个特点介绍并突出显示进行安全可靠的程序设计的方方面面。
问题求解　大的示例以“问题求解”形式给出。提出问题，然后讨论、设计并实现解决方案。
设计决策　为了让读者明了制订一个方案时所做的设计选择，“设计决策”要素一一说明这样的选择，以及具体示例所做选择背后的关系。这些讨论常出现在“问题求解”部分。
示例　说明新概念的众多示例。
程序设计技巧　提出改善或方便程序设计的建议。
学习问题　每章都提出了学习问题，它们与正文混在一起，强化刚介绍的概念。学习问题有助于读者理解本书内容，因为回答它们需要深思。建议在查阅网站中给出的答案前，先和其他人讨论这些问题及其答案。
练习和程序设计项目　求解每章最后的练习和程序设计项目可获得更多的练习机会。很遗憾，我们不能为读者提供这些练习和程序设计项目的答案，只有采用本教材的教师可从出版商那里得到部分答案。要想获得这些练习和项目的帮助，请联系你的老师。
教师及学生资源
从出版商的网站pearsonhighered.com/carrano中，可得到下列资料：
本书中出现的Java代码。
本书出版后发现的印刷错误的链接。
下面描述的在线内容的链接。
关于配套网站资源，大部分需要访问码，访问码只有原英文版提供，中文版无法使用。
教师资源
采用本书的教师可访问pearsonhighered.com/carrano，登录Pearson的教师资源中心（Ins-t-ru-ctor Resource Center，IRC），得到下列受保护的资料：
教师指南。
PPT课件，附带用于所有图像的ADA兼容的描述文本。
教师答案手册。
实验手册和解决方案。
给教师的Java源代码。
书中的图。
测试用例库。
请联系Pearson销售代表获取教师访问码，从pearsonhighered.com/replocator可得到联系方式。
学生资源
登录出版商的网站pearsonhighered.com/carrano，可得到下列资料：
Java基础（补充材料1）。
文件输入输出（补充材料2）。
词汇表（补充材料3）。
学习问题答案（补充材料4）。
注意，从docs.oracle.com/javase/9/docs/api/可得到Java类库文档。
内容概要
本书的读者应当已经学完了程序设计课程，学习过Java就更好了。附录和在线补充材料涵盖了我们假定读者已经了解的Java的基本内容。可以使用这些资料来复习，或者作为从另一种程序设计语言转向Java的基础。
导论：首先为将要研究的数据组织做准备，看一些日常的例子。
序言：序言讨论了类的设计。我们讨论的主题包括前置条件、后置条件、断言、接口和统一建模语言（UML）。设计是我们要讲述的一个重要方面。
第1～3章：将包作为抽象数据类型（ADT）来介绍。明确地将包的规范说明、使用及实现分为几章来介绍。例如，第1章给出了包的规范说明，并提供了几个使用示例。这一章还介绍了ADT集合（set）。第2章涵盖了使用数组的实现方式，而第3章介绍了结点链表，并将其用在包的类定义中。
采用类似的方式，本书中在讨论其他各种ADT时也将规范说明与实现分开。可以选择先阅读ADT规范说明及用法的章节，之后再阅读实现ADT的章节；或者可以按章节出现的次序来阅读，学习了每个ADT的规范说明及用法之后马上学习它们的实现。前言后面的先修章节列表能帮助你制订本书的学习计划。
第2章不仅仅介绍了ADT包的简单实现，还介绍了首先关注核心方法的类的实现过程。当定义类时，先实现并测试这些核心方法，稍后再完成其他方法的定义，这种方式很有效。第2章还介绍了安全可靠的程序设计的概念，展示如何在代码中增加这层保护。
Java插曲1和Java插曲2：Java插曲1介绍了泛型，故我们可以将它用在第一个ADT（即包）中。这个插曲紧接在第1章之后。Java插曲2介绍了异常，它紧接在第2章之后。使用这些内容来实现ADT包。
第4章：本章介绍算法的效率和复杂度，这个话题在后面的章节中都有涉及。
第5和6章：第5章讨论栈，给出使用的示例。第6章使用数组、结点链表和向量来实现栈。
Java插曲3：该插曲展示程序员如何写新的异常类。为此，介绍了如何派生一个已有的异常类。该插曲还介绍了finally块。
第7和8章：第7章讨论队列、双端队列和优先队列，而第8章讨论它们的实现。第8章还介绍了循环链表及双向链表，用到了程序员定义的类EmptyQueueException。
第9章：接下来，介绍作为问题求解工具的递归，以及它与栈的关系。递归与算法效率也是贯穿全书一再讨论的话题。
第10～12章：接下来的三章介绍ADT线性表。抽象地讨论集合（collection），然后使用数组和结点链表来实现它。
Java插曲4和第13章：Java迭代器所涉及的内容是标准接口Iterator、Iterable和ListIterator。第13章则展示实现这些ADT线性表的迭代器方法，讨论并实现了Java迭代器接口Iterator和ListIterator。
第14章：这个新章节介绍了更多的递归内容，包括语言、语法和回溯。
Java插曲5：该插曲提供了所介绍的排序方法要用到的Java概念，介绍标准接口Comparable、泛型方法、限定的类型参数和通配符。
第15和16章：接下来的两章讨论不同的排序技术及与它们相关的复杂度。考虑这些算法的迭代及递归实现版本。
Java插曲6：该插曲讨论可变和不可变对象，这是与前几章关于排序的内容及下一章关于有序表的内容相关的话题。
第17和18章及Java插曲7：继续线性表的讨论，第17章介绍有序表，讨论两种可能的实现方法及它们的效率。第18章展示如何使用线性表作为有序表的超类（或父类），并讨论超类的一般设计原则。虽然继承是在附录C中概括的，但继承的相关内容（包括保护访问、抽象类及抽象方法）在第18章之前的Java插曲7中介绍。
第19章：接下来讨论使用数组或链表保存线性表或有序表的查找策略。这些讨论是后续章节的良好基础。
Java插曲8：开始下一章之前，快速学习该插曲中所涉及的多个泛型数据类型的内容是有必要的。
第20～23章：第20章讨论ADT字典的规范说明及使用。第21章介绍使用链表或数组实现字典。第22章介绍散列方法，而第23章使用散列来实现字典。
第24和25章：第24章讨论树及可能的应用。在树的几个应用示例中介绍二叉查找树及堆。第25章介绍二叉树和一般树的实现。
Java插曲9：Java插曲9讨论克隆。我们克隆一个数组、一个结点链表及一个二叉结点，还讨论了有序表的克隆。虽然这些内容很重要，但可作为选修内容，因为它们不是后续章节所必需的。
第26～28章：第26章重点讨论二叉查找树的实现。第27章展示如何使用数组来实现堆。第28章介绍平衡查找树，还介绍AVL树、2-3树、2-4树、红黑树及B树。
第29和30章：最后，我们讨论图，学习几个应用及两种实现方式。
附录A～附录C：附录中是Java内容的补充。如前所述，附录A涉及程序设计风格和注释，介绍了javadoc注释，定义了本书中使用的标签。附录B讨论了Java类，而附录C扩展了这个话题，讨论组成与继承。
先修章节
每一章和附录都假定读者肯定已经学习了之前的内容。下表列出这些先修章节，数字表示章号，字母表示附录，每个Java插曲编号前面冠以“JI”。读者可以用这些信息制订本书的学习计划。
章号 章名 先修章节
章号 章名 先修章节
序言 设计类 补充材料1，A，B，C
第1章 包 序言，C
Java插曲1 泛型 序言
第2章 使用数组实现包 序言，1
Java插曲2 异常 补充材料1，B，C
第3章 使用链式数据实现包 1，2，JI2
第4章 算法的效率 B，2，3
第5章 栈 序言，1，JI2
第6章 栈的实现 2，3，4，5
Java插曲3 再论异常 C，JI2
第7章 队列、双端队列和优先队列 序言，5
第8章 队列、双端队列和优先队列的实现 2，3，6，7
第9章 递归 B，2，3，4，5
第10章 线性表 导论，B，序言，JI2，1
第11章 使用数组实现线性表 序言，2，4，10
第12章 使用链式数据实现线性表 3，8，10，11
Java插曲4 迭代器 JI2，10
第13章 ADT线性表的迭代器 11，12，JI4
第14章 使用递归求解问题 5，9
Java插曲5 再论泛型 JI1
第15章 排序简介 3，4，9，JI5
第16章 更快的排序方法 4，9，JI5，15
Java插曲6 可变及不可变对象 C，10
第17章 有序表 4，9，10，12，JI6
Java插曲7 继承和多态 序言，C，6
第18章 继承和线性表 C，10，11，12，17，JI7
第19章 查找 4，9，10，11，12，17
Java插曲8 三论泛型 B，JI5
第20章 字典 10，JI4，13，19，JI8
第21章 字典的实现 3，4，10，11，12，JI4，19，20
第22章 散列简介 20，21
第23章 使用散列实现字典 4，11，12，JI4，20，21，22
第24章 树 5，9，12，JI4，19
第25章 树的实现 C，JI2，5，7，12，24
Java插曲9 克隆 JI5，JI6，17，25，B，C
第26章 二叉查找树的实现 C，9，20，24，25
第27章 堆的实现 2，11，24
第28章 平衡查找树 24，25，26
第29章 图 5，7，24
第30章 图的实现 5，7，10，JI4，13，20，24，29
附录A 文档和程序设计风格 Java的一些知识
附录B Java类 补充材料1
附录C 从其他类创建类 B
补充材料1 Java基础 程序设计语言知识
补充材料2 文件输入输出 序言，JI2，补充材料1

致谢
衷心感谢以下审稿人认真阅读第4版，直言不讳地提出意见和建议，从而大大改进了我们的工作：
Prakash Duraisamy—迈阿密大学
David Gries—康奈尔大学
Hakam Alomari—迈阿密大学
Jack Pope—北亨内平社区学院
Anna Rafferty—卡尔顿大学

特别感谢Pearson教育集团在本书漫长的修订期间对我们的支持和帮助：执行项目经理Tracy Johnson、项目管理助理Meghan Jacoby、管理内容制作人Scott Disanno和内容制作人Lora Friedenthal。长期合作的文字编辑Rebecca Pepper确保本书清楚、正确，且语言无误。非常感谢大家！
除了前面提到的人之外，还要感谢其他许多人提供的帮助。Tim Henry为本版制作了PPT课件。俄克拉荷马城市大学的Charles Hoot教授编写了实验手册，阿克伦大学的Kathy Liszka教授编写了测试问题集，Joe Erickson和Jesse Grabowski提供了很多程序设计项目的答案。再次感谢本书之前版本的审稿人。
第4版审稿人：
Tony Allevato—弗吉尼亚理工学院暨州立大学
Mary Boelk—马凯特大学
Suzanne Buchele—西南大学
Kevin Buffardi—弗吉尼亚理工学院暨州立大学
Jose Cordova—路易斯安那门罗大学
Greg Gagne—威斯敏斯特学院
Victoria Hilford—休斯敦大学
Jim Huggins—凯特林大学
Shamim Kahn—哥伦布州立大学
Kathy Liszka—阿克伦大学
Eli Tilevich—弗吉尼亚理工学院暨州立大学
Jianhua Yang—哥伦布州立大学
Michelle Zhu—南伊利诺伊大学
第3版审稿人：
Steven Andrianoff—圣文德大学
Brent Baas—拉托诺大学
Timothy Henry—新英格兰理工学院
Ken Martin—北佛罗里达大学
Bill Siever—西北密苏里州立大学
Lydia Sinapova—辛普森学院
Lubomir Stanchev—印第安纳大学
Judy Walters—中北学院
Xiaohui Yuan—北得克萨斯大学
第2版审稿人：
Harold Anderson—曼利斯特学院
Razvan Andonie—华盛顿中心大学
Tom Blough—伦斯勒理工学院
Chris Brooks—旧金山大学
Adrienne Decker—纽约州立大学布法罗分校
Henry Etlinger—罗切斯特理工学院
Derek Harter—得克萨斯A&M大学
Timothy Henry—新英格兰理工学院
Robert Holloway—威斯康星大学麦迪逊分校
Charles Hoot—俄克拉荷马城市大学
Teresa Leyk—得克萨斯A&M大学
Robert McGlinn—南伊利诺伊大学卡本代尔校区
Edward Medvid—玛丽蒙特大学
Charles Metzler—旧金山城市学院
Daniel Zeng—亚利桑那大学
第1版审稿人：
David Boyd—瓦尔多斯塔州立大学
Dennis Brylow—普渡大学
Michael Croswell—产业培训师/顾问
Matthew Dickerson—明德学院
Robert Holloway—威斯康星大学麦迪逊分校
John Motil—加州州立大学北岭分校
Bina Ramamurthy—纽约州立大学布法罗分校
David Surma—瓦尔帕莱索大学

还要感谢在前几版写作过程中帮助过我们的很多人。他们是：Alan Apt，Steve Armstrong，James Blanding，Lianne Dunn，Bob Englehardt，Mike Giacobbe，Toni Holm，Charles Hoot，Brian Jepson，Rose Kernan，Christianna Lee，Patrick Lindner，John Lovell，Vince O’Brien，Patty Roy，Walt Savitch，Ben Schomp，Heather Scott，Carole Snyder，Chirag Thakkar，Camille Trentacoste，Nate Walker，Xiaohong Zhu。
最后，感谢我们的家人和朋友Doug、Joanne、Tita、Bobby、Ted、Nancy、Sue、Tom、Bob、Maybeth、Marge和Lorraine给了我们远离计算机时的生活。
谢谢你们每一个人，谢谢你们的专业和鼓励。

Frank M. Carrano
Timothy M. Henry

计算机\数据结构

本书是数据结构的经典教材，内容涵盖线性结构、层次结构、图等数据结构，排序、查找等重要方法，以及算法的评估和迭代/递归实现方式等，并采用Java语言基于数组和链表实现了各种ADT。本书的组织方式独特，语言简洁，示例丰富，程序规范，习题多样。

本书新特色
新增加了一章讨论递归，介绍语法、语言及回溯。
增加了新的设计决策、注、安全说明及编程技巧。
在大部分章节中，增加了侧重游戏、电子商务及财务的练习和程序设计项目。
调整了某些主题的次序，相关的主题集中介绍，内容连贯。
修改了插图，使之更容易阅读和理解。
将“自测题”改名为“学习问题”，并将答案移至网站中，鼓励小组一起讨论答案。
书中包含了关于Java类的附录，而不是将其放在网站中。

作者简介
弗兰克·M. 卡拉诺（Frank M. Carrano） 是美国罗得岛大学计算机科学系荣誉退休教授，1969年获得美国锡拉丘兹大学计算机科学专业博士学位。他的研究兴趣包括数据结构、计算机科学教育、社会问题的计算处理和数值计算。Carrano教授撰写了多本著名的计算机科学高年级本科生教科书。
蒂莫西·M. 亨利（Timothy M. Henry） 是美国新英格兰理工学院计算机科学系副教授，1986年获得美国欧道明大学计算机科学专业硕士学位，2001年获得美国罗得岛大学应用数学专业博士学位，自2000年以来一直保有美国PMI的项目管理专家（Project Management Professional，PMP）认证资格。他教授的课程有数据结构与抽象、编程语言基础、操作系统与网络、计算机系统基础、计算机科学项目、文件系统取证等，研究领域涉及计算机和数学取证、交互式3D图形关系、传感器网络。

设　计　类
先修章节：补充材料1、附录A、附录B、附录C
面向对象程序设计体现了三个设计概念：封装、继承和多态。如果不熟悉继承和多态，请参看附录A、B和C。这里我们讨论封装，这是设计类的过程中隐藏实现细节的一种方式。我们强调，在方法实现之前规范说明它应该有什么行为是重要的，在程序中将规范说明作为注释也是重要的。
我们介绍Java接口，这是将类行为的声明与其实现分开的一种方式。最后，介绍用于标识特定解决方案所需的类的一些初级技术。
封装
如果你想学习驾驶，那么对汽车的哪些描述对你最有用？显然不是描述它的发动机的工作过程。当你想学习驾驶时，这样的细节不是必要的。事实上，可以以你的方式获知这些细节。如果你想学习驾驶汽车，最有用的汽车描述是下面这样的特点：
如果你将脚踩在油门踏板上，汽车将开得更快。
如果你将脚踩在制动踏板上，汽车将慢下来并最终停止。
如果你将方向盘向右转，汽车将右转。
如果你将方向盘向左转，汽车将左转。
就像你不需要告诉想开车的人发动机是如何工作的一样，你也不需要告诉使用一款软件的人Java实现的全部细节。同样，假定你为另一位程序员写了一个用在程序中的软件组件，你应该告诉其他的程序员如何使用它，而不是与程序员分享如何写软件的细节。
封装（encapsulation）是面向对象程序设计的设计原则之一。“封装”这个词听上去好像是把东西放进胶囊，这个想象确实是正确的。封装隐藏了“胶囊”里的细节。由于这个原
因，封装常常被称为信息隐藏（information hiding）。但不是所有的事情都应该隐藏。在汽车里，有些东西是可见的—像是踏板和方向盘—而其他的则藏在引擎盖下面。换句话说，汽车是封装的，这样，隐藏了细节，只有驾车所需的控制是可见的，如图P-1所示。类似地，你应该封装Java代码，让细节隐藏，而只有必需的控制是可见的。

图P-1　汽车的控制装置对司机是可见的，但它的内部工作机理是隐藏的
封装将数据和方法放到一个类中，而隐藏了使用类时不必需的实现细节。如果类的设计良好，使用它就不需要去理解它的实现。程序员可以在不知道代码细节的情况下使用类的方法。程序员只需要知道如何为方法提供相应的参数，让方法执行正确的动作。简单地说，程序员不必担心类定义的内部细节。使用封装软件来写更多软件的程序员，他的任务更简单。结果，软件生产得更快，错误也更少。
注：封装是面向对象程序设计的设计原则之一，它将数据和方法放到一个类中，故而隐藏了类实现的细节。程序员仅需要知道使用这个类的信息就足够了。设计良好的类，即使每个方法都隐藏了，也能使用。
抽象（abstraction）是一个要求你关注什么而不是如何的过程。当设计类时，执行的是数据抽象（data abstraction）。你关注你想做的，或关注数据，而不担心如何完成这些任务，及如何表示数据。抽象要求你将注意力集中于哪些数据和操作是重要的。当抽象某件事时，你要确定中心思想。例如，书的抽象就是书的简介，与之相对的是整本书。
当设计一个类时，不应该考虑任一个方法的实现，即不应该担心类的方法如何达成它的目标。将规范说明与实现分开，能让你专心于更少的细节，所以能让你的工作更容易，出错概率更低。详细的设计良好的规范说明，有助于让实现更易成功。
注：抽象的过程要求你关注什么而不是如何。
如果正确，封装将类定义分为两部分—接口（interface）和实现（implementation）。接口描述程序员使用这个类时必须要了解的一切事情。它包括类的公有方法的方法头，告诉程序员如何使用这些公有方法的注释，及类中公有定义的任何常量。接口部分应该是在你的程序中使用这个类时只需要了解接口。注意，使用某个类的程序称为类的客户（client）。
实现部分由所有的数据域及所有方法的定义组成，包括公有、私有及保护的。虽然执行客户程序时需要实现，但编写客户程序时应该不需要知道任何实现细节。图P-2说明了一个类的封装实现及客户接口。虽然实现对客户是隐藏的，但接口却是可见的，且为客户提供了与实现进行交互的规范机制。

图P-2　接口在隐藏的实现与客户之间提供了规范的交互机制
接口和实现在Java类的定义中是不分开的，它们合在一起。不过你可以随同你的类创建一个独立的Java接口。本序言后半部分的内容介绍如何写这样的接口，本书中还会再写几个。
学习问题1　接口如何区别于类的实现？
学习问题2　考虑一个不同于汽车的例子，用来说明封装。例子中的哪些部分对应于接口，哪些部分对应于实现？
规范说明方法
将类的目标及方法与其实现分开，对一个成功的软件项目来说至关重要。应该规范说明每个类及方法，而不关心它的实现。写这些描述能捕捉到你最初的想法，并开发它们，从而才能足够明确地实现它们。你写的描述应该作为注释放到程序中有用的地方。你不能在写了程序之后为了应付老师或老板才写注释。
注释
现在来看看为类的方法而写的注释。虽然各企业有自己的注释风格，但Java开发者有特定的应该遵从的注释风格。如果程序中含有这种风格的注释，则可以执行一个称为javadoc的实用程序，从而得到描述类的文档。这个文档告诉未来使用这些类的人们必须要了解的东西，但忽略了所有实现细节，包括所有的方法定义体。
程序javadoc提取类头、所有公有方法的头，及以特定形式写的注释。每个这样的注释必须出现在公有类定义或公有方法头的前面，且必须以/**开头，以*/结尾。注释中以符号@开头的特定的标签（tag）标识方法的不同方面。例如，使用@param标识参数，
@return标识返回值，而@throws表示方法抛出的异常。本序言中，在注释中会看到几个这样的标签示例。附录A详述了如何书写javadoc注释。
现在不再进一步讨论javadoc注释的规则，而讨论规范说明一个方法的重要方面。首先，你需要写一个简洁的语句来阐述方法的目的或任务。这个语句以动词开头，能让你避免冗长的文字，而那些文字真的是不需要的。
在思考方法的目的时，应该考虑它的输入参数，如果有，要描述它们。还需要描述方法的结果。是让它返回一个值、让它做些动作，还是让它改变参数的状态？在写这些描述时，应该时刻牢记以下理念。
前置条件和后置条件
前置条件（precondition）是一条条件语句，它在方法执行前必须为真。除非前置条件满足，否则不应该使用方法，也不能期待方法正确执行。前置条件可以与方法参数的描述相关。例如，计算x平方根的方法可以用x≥0作为前置条件。
后置条件（postcondition）是一条语句，当前置条件满足且完全执行方法后，它为真。对于一个值方法，后置条件将描述方法返回的值。对于一个void方法，后置条件描述所做的动作及对调用对象的任何修改。一般地，后置条件描述方法调用产生的所有影响。
考虑后置条件有助于弄清楚方法的目的。注意到，从前置条件到后置条件没有提到如何做，即我们将方法的规范说明与它的实现分离。
程序设计技巧：不能满足后置条件的方法，即使符合前置条件，也可以抛出异常。（关于异常的讨论见Java插曲2和Java插曲3。）
职责。前置条件的职责是保证必须满足特定条件。如果是信任的客户，比如同一个类中的另一个方法，负责在调用方法之前满足条件，则该方法不需要检查条件。另一方面，如果该方法负责满足条件，则客户不检查它们。明确声明谁必须检查一组给定条件，既提高了检查的概率，又避免了重复劳动。
例如，要规范说明前一段提到的求平方根方法，可以在方法头前面写如下的注释：

虽然我们在这个注释中将前置条件和后置条件一起写了出来，但是可以分别指明它们。
更安全的技术是让方法承担检查参数的职责。此例中，注释应该如下：

程序设计技巧：在方法头之前的注释中充分说明每个公有方法。对于确保方法能正确执行而必须满足的条件，要说明是由方法还是由客户来负责进行检查。以这种方式，既做了检查又不会重复检查。但在调试过程中，方法应该检查前置条件是否满足。
当使用继承和多态来重写超类中的方法时，子类中的方法可能会出现与超类中的方法不一致的问题。前置条件和后置条件可以帮助程序员避免这个问题。后置条件必须适用于子类中方法的所有版本。重写的方法可以添加到后置条件中—即它能做得更多—但不能做得更少。不过重写的方法不能增加其前置条件。换句话说，它不能比基类中的方法要求得更多。
学习问题3　假定类Square有一个数据域side及设置side值的方法setSide。这个方法的方法头和注释是什么？回答这个问题的时候要牢记前置条件和后置条件。
断言
断言（assertion）是一条关于程序逻辑的某些方法的事实语句。可以将它看作值为真的布尔表达式，或至少在某些点应该为真。例如，前置条件和后置条件是方法开始前及结束后关于条件的断言。如果有一个断言为假，则程序一定有错。
可以将断言作为注释放在代码中。例如，如果在方法定义的某些地方，你知道变量sum应该是正的，则可以写如下的注释：

这样的注释用来说明并不太明晰的某些逻辑。另外，断言为你指明调试期间需要精确检查的代码位置。
学习问题4　假定你有一个正整数数组。下列语句查找数组中的最大整数。下列循环中的if语句之后，应该写一个什么样的断言来当作注释？

断言语句（assert statement）。Java不仅仅能让你写个注释当断言，还能使用assert语句强制执行断言，如

如果保留字assert后面的布尔表达式为真，则语句什么也不做。如果它为假，则发生断言错误（assertion error），程序中断执行。显示如下的错误信息：

可以在assert语句后添加第二个表达式来进一步说明这条错误信息。第二个表达式必须表示一个值，而在错误信息中它是作为字符串显示的。例如，语句

当sum≤0时在错误信息中添加了sum的值。比如，错误信息可能是

默认情况下，程序执行时是禁用assert语句的。所以程序完成后可以将assert语句留在程序中，而不会浪费运行时间。当执行一个程序时，如果想让它们执行，就必须要启用assert语句。如何启用它们依赖于编程环境。
注：程序中的断言明示出必须为真的逻辑。在Java中，可以使用一条assert语句写一个断言。它的格式如下：

如果第一个表达式为假，则可选的第二个表达式的值将出现在错误信息中。
程序设计技巧：使用assert语句是发现程序逻辑错误的简单有效的方法。除了可用于这个目的之外，留在程序中的断言还能向修改或扩展程序的人阐明你的逻辑。记住，Java会忽略assert语句，除非程序的使用者指定了其他的选项。
程序设计技巧：调试时使用assert语句，能使方法强制满足前置条件。但是assert语句不能替代if语句。应该将assert语句作为程序设计的辅助手段，而不是程序逻辑的一部分。
Java接口
本序言前面的内容中，我们提到接口这个术语，当在你的程序中要使用某个类时，由接口告诉你必须要知道的所有东西。虽然一个Java类与实现它的接口合在一起，但是也可以写一个单独的接口。
Java接口（Java interface）是一个程序组件，它声明了一些公有方法，且能定义公有命名常量。这样的接口应该含有说明方法的注释，以便为实现它们的程序员提供必要的信息。有些接口描述了类中的所有公有方法，还有一些仅说明特定的方法。
当写一个类来定义接口中声明的方法时，称这个类实现（implement）了接口。实现接口的类必须定义接口中说明的每个方法的方法体。但是接口可能没有声明类中定义的每个方法。
你能写自己的接口，也能使用Java类库中定义的接口。当写一个Java接口时，可以将它放在它自己的文件中，即接口和实现接口的类在两个独立的文件中。
写一个接口
Java接口的开头很像是类的定义，不过要用保留字interface替代class，即接口的开头是如下语句：

而不是

接口可以含有任意多个公有方法头，每个方法头的后面是一个分号。接口不声明类的构造方法，也不能声明静态或终极方法。注意，接口中的方法默认是公有的，故在方法头中可以省略puclic。接口还可以定义任意多个公有命名常量。
示例。想象如圆、正方形或一块地这样的对象，它们既有周长又有面积。假定我们想让这种对象的类有一个返回数量值的访问方法。如果实现这些类的程序员不是同一个人，则他们可能会用不同的方式来说明这些方法。为确保定义这些方法的类有统一的格式，我们可以写一个接口，如程序清单P-1所示。这个接口为程序员提供了方法说明的简单概要。程序员应该不必去查看实现它们的类就能使用这些方法。
程序清单P-1　接口Measurable

将接口定义保存在一个与接口名同名的文件中，后面加上.java。例如，前面的接口在文件Measurable.java中。
程序设计技巧：Java接口是写注释的好地方，是用来说明每个方法的目的、参数、前置条件及后置条件的地方。用这种方式，可以在一个文件中说明一个类，而在另一个文件中实现它。
注：接口可以声明数据域，但它们必须是公有的。通常，类的数据域是私有的，故接口中的任何数据域表示的都应该是命名常量。所以它们应该是公有的、终极的及静态的。
注：接口中声明的方法不能是静态的，也不能是终极的。但是可以在实现接口的类中声明这样的方法。
示例。假定你最终想定义人名的类。最开始或许是定义如程序清单P-2所示的Java接口，为这个人名类说明方法。限于篇幅，我们只为最开始的两个方法添加了注释。这个接口提供了整个类中所需方法的规范说明。当实现附录B中程序清单B-1所示的如Name这样的类时可以使用它。另外，只看这个接口，就应该能为类写一个客户。
程序清单P-2　接口NameInterface

注意，方法giveLastNameTo的参数的数据类型是接口—NameInterface—而不是像Name这样的类。我们将在段P.19的开头来谈论接口作为数据类型的话题。现在，只需知道接口不应该限制实现它的类的名字。
注：命名一个接口
接口名，特别是Java中标准的接口名，常常以“able”结尾，例如Measurable。这样的结尾并不总能提供一个好名字，所以也常会使用“er”或是“Interface”作为结尾。与Java的异常以“Exception”为结尾一样，接口常以“Interface”为结尾。
实现一个接口
实现接口的任何类，必须要在类定义的开头使用implements子句进行说明。例如，如果类Circle实现了接口Measurable，它的开头就是下面这种形式的：

然后，类必须定义接口中声明的每个方法。本例中，类Circle必须至少实现方法getPerimeter和getArea。
如果写一个实现Measurable的类Square，这个类的开头应该是这样的：

且它至少应该定义方法getPerimeter和getArea。显然，这两个方法的定义不同于它们在类Circle中的定义。
图P-3展示的是Measurable、Circle、Square及它们的客户所在的文件。

图P-3　用于接口、实现接口的类及其客户的文件
注：写接口是类的设计人员向其他程序员规范说明方法的一种方式。实现接口是程序员确保类已经定义了某些方法的一种方式。
注：不同的类或许以不同的方式实现同一个接口。例如，可以有多个类实现接口Measurable，且为方法getPerimeter和getArea写各自的版本。
示例。想象用于如圆、球体和圆柱体等不同几何形状的类。其中的每一个几何体都有一个半径。我们可以定义下列接口，让类来实现它：

接口能知道已经定义了半径，所以为这个量声明设置方法和获取方法。但是，不能为半径声明数据域。实现接口的类来做这件事。
实现这个接口的类Circle如下所示：


类定义了一个私有数据域radius，且实现了接口Circular中声明的方法setRadius和getRadius。接口中不能含有像radius这样的数据域，因为它是私有的。
注：类中定义的方法个数可以超出它实现的接口中声明的方法个数。例如，类Circle定义了方法getArea，它没有包含在接口Circular中。
多个接口。类可以实现多个接口。如果想这样做，只需列出所有的接口名，并以逗号分隔即可。如果类从另一个类派生而来，则implements子句永远在extends子句的后面。所以可以写：

要想记住这个次序，只需记着保留字extends和implements在类头中以字母序出现即可。
实现多个接口的类必须定义接口中声明的每个方法。如果类实现的多个接口中出现了相同的方法头，则类中只需定义一个方法。
不能从多个基类派生一个类。这个限制避免了实现继承时可能出现的冲突。Java接口中含有方法的规范说明，但不去实现它们。类可以实现这些规范说明，而不管它们是出现在一个接口中还是出现在多个接口中。通过允许类实现多个接口这种机制，Java既实现了多重继承，又去掉了它可能引起的混乱。
学习问题5　写一个Java接口，规范定义学生类并声明其中的方法。
学习问题6　定义一个类，实现前一个问题中你写的接口。要包含数据域、构造方法及至少一个方法的定义。
接口作为数据类型
当声明变量、数据域或方法的参数时，可以将Java接口用作数据类型。例如，段P.15中的方法giveLastNameTo有一个类型为NameInterface的参数：

传给这个方法的任何实参，必须是实现NameInterface的类的对象。
为什么不将aName的类型声明为一个类（例如Name）呢？我们想让接口独立于实现它的类，因为实现一个接口的类可以有多个。使用NameInterface作为参数的类型，能保证方法的实参具有NameInterface中声明的所有方法。通常，如果数据类型是接口，你能保证方法的参数具有特定的方法，即接口中声明的那些方法。另一方面，参数只有那些方法。
要是一个类C的头不含有implements NameInterface短语，仍实现了接口中的方法，又会如何呢？那你不能将C的实例作为参数传给giveLastNameTo方法。
注：将接口当作变量的类型，这意味着，这个变量可以引用一个对象，它有一组方法且仅有这组方法。
注：接口类型是引用类型。
如下变量声明

使得myName成为一个引用变量。现在myName可以指向实现NameInterface的任意一个类的任意对象。故如果Name实现了NameInterface，且有

则myName.getFirst()返回指向字符串

[美]弗兰克·M. 卡拉诺（Frank M.Carrano）蒂莫西·M. 亨利（Timothy M. Henry） 著：弗兰克·M. 卡拉诺（Frank M. Carrano）是美国罗得岛大学计算机科学系荣誉退休教授，1969年获得美国锡拉丘兹大学计算机科学专业博士学位。他的研究兴趣包括数据结构、计算机科学教育、社会问题的计算处理和数值计算。Carrano教授撰写了多本著名的计算机科学高年级本科生教科书。
蒂莫西·M. 亨利（Timothy M. Henry）是美国新英格兰理工学院计算机科学系副教授，1986年获得美国欧道明大学计算机科学专业硕士学位，2001年获得美国罗得岛大学应用数学专业博士学位，自2000年以来一直保有美国PMI的项目管理专家（Project Management Professional，PMP）认证资格。他教授的课程有数据结构与抽象、编程语言基础、操作系统与网络、计算机系统基础、计算机科学项目、文件系统取证等，研究领域涉及计算机和数学取证、交互式3D图形关系、传感器网络。

时隔三年多，这本书又一次摆上案头。看着崭新的书，一方面敬佩原作者Frank M. Carrano和Timothy M. Henry严谨的治学态度和勤奋的工作精神，一方面也激励译者不能懈怠，要以更加认真的工作态度完成第5版的翻译工作。
一如既往，第5版也是个厚重的大部头。相比于第4版，主体内容没有太多的变化，仍然是Java语言与数据结构两条知识主线贯穿始终。本版的修订主要集中在三个方面。
第一方面，是章节次序做了调整，相关的主题集中介绍。这样，学习时内容连贯，也可以相互对比。比如，栈和队列都是受限的线性表，属于线性结构，通常情况下是依次介绍的。在第4版中，这两部分内容并不是连续的，其间还穿插介绍了递归和排序的内容。很明显，第5版的安排更加合理了。再比如，排序的方法比较多，按照效率来分，通常分为两大类，第5版中将排序方法也调整到了连续的章节中。
第二方面，是将递归的内容拆分为两章，先介绍基础知识，后介绍使用递归求解问题的方法。递归不是一个直观的概念，要想在程序中正确使用递归求解问题，深入理解概念是必不可少的环节。第5版加强了这些内容的介绍，帮助读者递归地思考问题，同时还介绍了递归程序的效率分析。
第三方面，是增加了侧重于游戏、电子商务及财务方面的新练习和程序设计项目。学习了数据结构的知识之后，可以通过练习和程序设计项目来检验学习的效果。第4版中，在每章的最后都有数量不等的练习题和程序设计题目，在此基础上，第5版又增加了结合实际应用的题目。以这些题目作为切入点，可以逐步过渡到大的应用项目的开发。
第5版中，语言更加准确简捷，给出的图更加清晰明确。读者可以选择按序学习各章的内容，也可以先学习ADT的部分，再学习各ADT的实现部分。作者对章节的安排方便了读者的学习过程。作为教师，讲授的次序也可以自主安排。
为了让读者对全书内容有个大致的了解，下面简略地介绍一下全书的内容。
全书介绍了包、栈、队列、线性表、字典、树、堆及图等数据结构。每种数据结构都在连续的两三章中介绍。前一章专门介绍与每种结构相关的ADT的规范说明，包括数据属性及相关操作。使用具体实例说明这些操作的含义及操作的结果，帮助读者理解其定义。定义的接口也与规范说明放在同一章中，这一章的内容基本上不涉及实现的细节。接下来的一章或两章中，着重介绍对所讨论ADT的实现过程，并对每种实现进行效率分析。对有些重要且应用广泛的数据结构，还给出了问题求解实例。
树和图是非常重要的数据结构，树又衍生出二叉树、查找树等结构。它们的概念与实现，既来源于树，又有别于树，所以单独成章、重点介绍。图是本书介绍的最后一种结构，除了像其他ADT一样介绍了基本操作的实现之外，还着重介绍了图的几个应用，包括遍历、拓扑排序及最短路径问题。各类算法的实现，有很多是使用递归完成的。本书使用两章的篇幅介绍了递归的概念，及如何编写递归程序。
数据的存储方式可分为两大类：一类使用数组，包括向量；另一类使用指针，即链式实现。本书对各个ADT均给出基于数组及基于链的两种实现方式，并针对每种实现的适用性做了介绍和对比。
除此之外，本书还介绍了排序、查找、散列等概念及相应的实现过程。它们是常用的方法，也是数据结构课程的重要组成部分。针对数据的不同存储方式，适用的排序和查找方法及其实现过程不尽相同，本书也一一做了介绍。
算法的效率是重要的衡量指标，作者介绍了算法分析的大O表示。书中实现的每个算法都使用这些技术进行了效率分析，特别介绍了递归方法的效率分析。
本书将Java语言的相关内容组织成插曲及附录，在插曲中介绍了泛型、异常、迭代器、可变对象及不可变对象、克隆等内容，在附录中介绍了Java的基本语法，以及编写Java程序时要注意的方面。同时还给出了词汇表，方便读者查询。附录中的内容属于Java语言的基本知识，插曲中的内容是更深入的部分。这些主题比较独立，熟悉这些内容的读者可以略过它们，也可以在涉及相关内容时作为参考而有选择地阅读。这样可以减轻读者的学习难度，也避免了顾此失彼。作者特别注重知识的衔接，在每章的最前面，列出学习本章时应该先学习哪些先修章节，这为读者画出了一个清晰的学习路线图。
译者在翻译过程中，尽可能地保持了原书的风格，包括排版格式。除了正文中的内容全部翻译外，也翻译了伪语言描述的算法中的英文语句，以帮助读者理解伪语言。
本书非常适合作为大学本科数据结构课程的教材使用。书中内容图文并茂，讲解条理清晰。在内容介绍过程中，配合讲解的内容穿插相关的问题并要求读者回答，帮助读者自行检查对知识的掌握程度。每章最后都有数目不等的练习及项目，教师可选择使用。本书提供了大量的代码，并对代码进行了详细的介绍，这些代码对学生理解课程内容非常有益。有些未全部实现的类及方法作为课后练习及项目，要求学生完成，书中提供的这些代码成为必要的参考及基础。
在此，非常感谢机械工业出版社华章分社给译者提供的翻译机会。在翻译过程中，译者不仅学习了作者的编写思想，更感受到作者的敬业精神。书中反映出的作者的认真态度，使译者在翻译过程中不敢有丝毫的懈怠。译者还要特别感谢朱劼、张梦玲等编辑。翻译过程中，译者始终得到机械工业出版社华章分社温莉芳副总经理、朱劼主任的大力支持和全方位的帮助。责任编辑严格把关，与译者多次探讨重要概念、术语的确切含义及合适的用辞。正是各位编辑的认真负责，才让本书顺利地和读者见面。
本书由辛运帏翻译。翻译过程中，得到了南开大学计算机学院多位老师的支持和帮助，包括徐敬东教授、刘晓光教授、王刚教授、杨巨峰教授等，由于篇幅所限，恕译者不能一一列出全部人的姓名，在此一并表示衷心的感谢。还要特别感谢国防科技大学计算机学院熊岳山教授、东南大学计算机学院姜浩教授、北京理工大学网络服务中心陈朔鹰主任，正是他们为译者提出的众多非常好的建议，帮助译者顺利完成了本书的翻译。
虽然译者在翻译时非常认真努力，期望以尽量高的水平将本书呈现给读者，但限于译者的水平，很多地方并不能完全体现作者的原意。第5版的翻译中也尽量改正了第4版翻译中的错误，但书中仍难免有错误之处，敬请广大读者指正。您的任何意见和建议都能帮助进一步完善本书。
感谢尊敬的读者选择了本书。

译者
2019年7月于南开津南园

出版者的话
译者序
前言
导论　组织数据 1
序言　设计类 3
封装 3
规范说明方法 5
注释 5
前置条件和后置条件 5
断言 6
Java接口 7
写一个接口 8
实现一个接口 9
接口作为数据类型 11
派生一个接口 12
接口内的命名常量 13
选择类 14
标识类 15
CRC卡 15
统一建模语言 16
重用类 18
练习 19
项目 19
第1章　包 22
什么是包 22
包的行为 23
规范说明一个包 23
一个接口 28
使用ADT包 30
像使用自动贩卖机一样使用ADT 33
ADT集合 34
Java类库：接口Set 35
本章小结 35
练习 36
项目 37
Java插曲1　泛型 40
泛型数据类型 40
接口中的泛型 40
泛型类 41
第2章　使用数组实现包 44
使用定长数组实现ADT包 44
模拟 44
一组核心方法 45
实现核心方法 46
让实现安全 52
测试核心方法 54
实现更多的方法 57
删除项的方法 59
使用变长数组实现ADT包 67
变长数组 67
包的新实现 69
使用数组实现ADT包的优缺点 71
本章小结 72
程序设计技巧 72
练习 73
项目 74
Java插曲2　异常 75
基础 75
处理异常 77
延缓处理：throws子句 77
现在处理：try-catch块 78
多个catch块 79
抛出异常 80
第3章　使用链式数据实现包 83
链式数据 83
添加到开头形成一个链表 84
ADT包的链式实现 85
私有类Node 85
类LinkedBag的框架 87
定义一些核心方法 88
测试核心方法 91
方法getFrequencyOf 92
方法contains 93
从链表中删除一项 94
方法remove和clear 95
有设置和获取方法的类Node 98
使用链表实现ADT包的优缺点 101
本章小结 101
程序设计技巧 101
练习 102
项目 102
第4章　算法的效率 104
动机 104
算法效率的衡量 105
统计基本操作 107
最优、最差和平均情况 109
大O表示 109
程序结构的复杂度 112
图示化效率 113
实现ADT包的效率 115
基于数组的实现 115
链式实现 117
两种实现的比较 118
本章小结 118
练习 118
项目 121
第5章　栈 123
ADT栈的规范说明 123
使用栈来处理代数表达式 127
问题求解：检查中缀代数表达式中平衡的分隔符 128
问题求解：将中缀表达式转换为后缀表达式 132
问题求解：计算后缀表达式的值 136
问题求解：计算中缀表达式的值 137
程序栈 139
Java类库：类Stack 140
本章小结 141
程序设计技巧 141
练习 141
项目 143
第6章　栈的实现 146
链式实现 146
基于数组的实现 149
基于向量的实现 152
Java类库：类Vector 153
使用Vector实现ADT栈 154
本章小结 155
练习 156
项目 156
Java插曲3　再论异常 158
程序员定义的异常类 158
继承和异常 162
finally块 163
第7章　队列、双端队列和优先队列 166
ADT队列 166
问题求解：模拟排队 169
问题求解：计算股票售出的资本收益 174
Java类库：接口Queue 177
ADT双端队列 177
问题求解：计算股票售出的资本收益 180
Java类库：接口Deque 181
Java类库：类ArrayDeque 182
ADT优先队列 183
问题求解：跟踪指派 184
Java类库：类PriorityQueue 185
本章小结 186
程序设计技巧 187
练习 187
项目 188
第8章　队列、双端队列和优先队列的实现 192
队列的链式实现 192
基于数组实现队列 196
循环数组 196
带一个未用元素的循环数组 198
队列的循环链式实现 203
两部分组成的循环链表 204
Java类库：类AbstractQueue 209
队列的双向链式实现 209
优先队列的可能实现方案 213
本章小结 213
程序设计技巧 214
练习 214
项目 215
第9章　递归 217
什么是递归 217
跟踪递归方法 221
返回一个值的递归方法 224
递归处理数组 226
递归处理链表 228
递归方法的时间效率 230
countDown的时间效率 230
计算xn的时间效率 231
尾递归 232
使用栈来替代递归 233
本章小结 234
程序设计技巧 234
练习 235
项目 237
第10章　线性表 240
ADT线性表的规范说明 240
使用ADT线性表 246
问题求解：使用大整数 250
Java类库：接口List 252
Java类库：类ArrayList 252
本章小结 253
练习 253
项目 254
第11章　使用数组实现线性表 257
使用数组实现ADT线性表 257
模拟 257
Java实现 259
使用数组实现ADT线性表的效率 266
本章小结 268
练习 268
项目 269
第12章　使用链式数据实现线性表 271
结点链表上的操作 271
在不同的位置添加结点 271
从不同的位置删除结点 275
私有方法getNodeAt 276
实现之初 277
数据域和构造方法 278
添加到线性表表尾 279
在线性表的给定位置添加 280
方法isEmpty和toArray 281
测试核心方法 283
继续实现 284
完善实现 286
尾引用 287
使用链表实现ADT线性表的效率 290
Java类库：类LinkedList 292
本章小结 292
练习 293
项目 294
Java插曲4　迭代器 296
什么是迭代器 296
接口Iterator 297
接口Iterable 298
使用接口Iterator 299
Iterable和for-each循环 302
接口ListIterator 303
再论接口List 306
使用接口ListIterator 306
第13章　ADT线性表的迭代器 309
实现迭代器的方法 309
独立类迭代器 309
内部类迭代器 312
链式实现 313
基于数组的实现 316
为什么迭代器方法在它自己的类中 319
基于数组实现接口ListIterator 320
内部类 322
本章小结 327
程序设计技巧 327
练习 327
项目 329
第14章　使用递归求解问题 331
困难问题的简单求解方案 331
简单问题的低劣求解方案 336
语言和语法 338
Java标识符语言 338
前缀表达式语言 339
前缀表达式的计算 342
间接递归 343
回溯 343
穿越迷宫 344
n皇后问题 345
本章小结 347
练习 348
项目 349
Java插曲5　再论泛型 352
接口Comparable 352
泛型方法 354
限定的类型参数 354
通配符 357
限定的通配符 357
第15章　排序简介 360
对数组进行排序的Java方法的组织 360
选择排序 361
迭代的选择排序 362
递归的选择排序 364
选择排序的效率 364
插入排序 365
迭代的插入排序 366
递归的插入排序 367
插入排序的效率 369
结点链表上的插入排序 369
希尔排序 372
算法 373
希尔排序的效率 374
算法比较 374
本章小结 375
程序设计技巧 375
练习 375
项目 377
第16章　更快的排序方法 379
归并排序 379
归并数组 379
递归的归并排序 380
归并排序的效率 382
迭代的归并排序 384
Java类库中的归并排序 384
快速排序 385
快速排序的效率 385
创建划分 386
实现快速排序 388
Java类库中的快速排序 390
基数排序 390
基数排序的伪代码 392
基数排序的效率 392
算法比较 393
本章小结 393
练习 394
项目 395
Java插曲6　可变及不可变对象 397
可变对象 397
不可变对象 398
创建只读类 399
伴生类 400
第17章　有序表 403
ADT有序表的规范说明 403
使用ADT有序表 406
链式实现 407
方法add 408
链式实现的效率 414
使用ADT线性表的实现 414
效率问题 417
本章小结 418
练习 419
项目 419
Java插曲7　继承和多态 421
继承的其他方面 421
何时使用继承 421
保护访问 422
抽象类和方法 422
接口与抽象类 424
多态 425
第18章　继承和线性表 430
使用继承实现有序表 430
设计一个基类 432
创建抽象基类 436
有序表的高效实现 439
方法add 439
本章小结 440
程序设计技巧 440
练习 440
项目 441
第19章　查找 443
问题 443
在无序数组中查找 443
无序数组中的迭代顺序查找 444
无序数组中的递归顺序查找 445
顺序查找数组的效率 446
在有序数组中查找 446
有序数组中的顺序查找 447
有序数组中的二分查找 447
Java类库：binarySearch方法 451
数组中二分查找的效率 451
在无序链表中查找 453
无序链表中的迭代顺序查找 453
无序链表中的递归顺序查找 453
链表中顺序查找的效率 454
在有序链表中查找 454
有序链表中的顺序查找 454
有序链表中的二分查找 455
查找方法的选择 455
本章小结 456
程序设计技巧 456
练习 456
项目 458
Java插曲8　三论泛型 460
多个泛型 460
第20章　字典 462
ADT字典的规范说明 462
Java接口 465
迭代器 466
使用ADT字典 468
问题求解：电话号码簿 468
问题求解：单词的频率 472
问题求解：单词的索引 475
Java类库：接口Map 478
本章小结 478
程序设计技巧 478
练习 479
项目 479
第21章　字典的实现 482
基于数组的实现 482
基于无序数组的字典 482
基于有序数组的字典 487
链式实现 491
无序链式字典 491
有序链式字典 492
本章小结 494
程序设计技巧 494
练习 494
项目 495
第22章　散列简介 496
什么是散列 496
散列函数 498
计算散列码 498
将散列码压缩为散列表的下标 501
解决冲突 502
开放地址的线性探查 502
开放地址的二次探查 507
开放地址的双散列 508
开放地址的潜在问题 510
拉链法 510
本章小结 513
练习 513
项目 514
第23章　使用散列实现字典 516
散列的效率 516
装填因子 516
开放地址法的代价 517
拉链法的代价 518
再散列 519
冲突解决机制的比较 520
使用散列实现字典 521
散列表中的项 521
数据域和构造方法 522
方法getValue、remove和add 523
迭代器 525
Java类库：类HashMap 526
Java类库：类HashSet 527
本章小结 527
练习 528
项目 528
第24章　树 531
树的概念 531
层次结构 531
树的术语 532
树的遍历 537
二叉树的遍历 537
一般树的遍历 538
用于树的Java接口 539
用于所有树的接口 539
用于二叉树的接口 540
二叉树示例 541
表达式树 541
决策树 543
二叉查找树 545
堆 547
一般树示例 548
解析树 549
游戏树 550
本章小结 550
练习 551
项目 553
第25章　树的实现 555
二叉树中的结点 555
二叉结点类 556
ADT二叉树的实现 557
创建基本二叉树 557
方法initializeTree 559
访问方法和赋值方法 561
计算高度和结点个数 562
遍历 563
表达式树的实现 567
一般树 568
用于一般树的结点 568
使用二叉树表示一般树 569
本章小结 570
程序设计技巧 570
练习 570
项目 572
Java插曲9　克隆 574
可克隆的对象 574
克隆一个数组 579
克隆一个链表 581
有序表的克隆 585
克隆一个二叉结点 587
第26章　二叉查找树的实现 589
入门知识 589
用于二叉查找树的接口 590
重复项 591
开始定义类 592
查找和获取 593
遍历 595
添加一项 595
递归实现 596
迭代实现 598
删除一项 600
删除叶结点中的项 600
删除仅有一个孩子的结点中的项 600
删除有两个孩子的结点中的项 601
删除根中的项 604
递归实现 604
迭代实现 607
操作效率 610
平衡的重要性 611
结点按什么次序添加 611
ADT字典的实现 612
本章小结 614
练习 615
项目 617
第27章　堆的实现 620
再论：ADT堆 620
使用数组表示堆 620
添加项 623
删除根 626
创建堆 628
堆排序 630
本章小结 633
练习 633
项目 634
第28章　平衡查找树 636
AVL树 636
单旋转 636
双旋转 639
实现细节 642
2-3树 646
在2-3树中进行查找 646
向2-3树中添加项 647
添加过程中结点的分裂 649
2-4树 650
向2-4树中添加项 650
AVL树、2-3树和2-4树的比较 652
红黑树 653
红黑树的特性 654
向红黑树中添加项 654
Java类库：类TreeMap 659
B树 659
本章小结 660
练习 660
项目 661
第29章　图 663
一些示例及术语 663
公路地图 663
航空公司的航线 665
迷宫 666
先修课程 666
树 667
遍历 667
广度优先遍历 668
深度优先遍历 669
拓扑序 670
路径 672
寻找路径 673
无权图中的最短路径 673
带权图中的最短路径 675
用于ADT图的Java接口 678
本章小结 681
练习 682
项目 684
第30章　图的实现 686
两个实现概述 686
邻接矩阵 686
邻接表 687
顶点和边 688
规范说明类Vertex 688
内部类Edge 690
类Vertex的实现 691
ADT图的实现 694
基本操作 694
图算法 697
本章小结 699
练习 699
项目 701
附录A　文档和程序设计风格 702
附录B　Java类 706
附录C　从其他类创建类 727
补充材料1　Java基础（在线）
补充材料2　文件输入输出（在线）
补充材料3　词汇表（在线）
补充材料4　学习问题答案（在线）