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

致谢
诚挚感谢仔细阅读前一版，并给出有效改善本书的评论、注释及建议的各位：
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——南伊利诺伊大学
特别感谢Pearson教育集团在本书漫长的修订期间对我们的支持：责任编辑Tracy Dunkelberger、程序经理Carole Snyder、程序管理团队主管Scott Disanno及项目经理Bob Engelhardt对我们的项目倾注了大量心血。长期合作的文字编辑Rebecca Pepper确保本书清楚、正确，且语言无误。非常感谢大家！
还要感谢很多人对我们的帮助。Steve Armstrong为本书的这一版本及之前的版本制作了PPT讲稿。俄克拉荷马城市大学（奥城大学）的Charles Hoot教授编写了实验手册。阿克伦大学的Kathy Liszka教授编写了新的测试问题集，Jesse Grabowski提供了很多程序设计项目的答案。再次感谢他们对本书之前版本的审阅。
审阅第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、James Blanding、Lianne Dunn、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、Maybeth、Marge及Lorraine给了我们远离计算机时的生活。谢谢你们每一个人，谢谢你们的专业和勇气。

Frank M. Carrano
Timothy M. Henry

计算机\数据结构

[美]弗兰克 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图形关系、传感器网络。

辛运帏 饶一梅 译：暂无简介

终于完成了这本如砖一样厚重的大部头书的翻译。一年多以前，当这本书摆上案头时，深知任务艰巨的同时，也期待着能探究书的内容。此时此刻，我可以告诉读者，这本书非常值得阅读。这本书最大的特点在于内容丰富但不冗杂，Java语言与数据结构两条知识主线贯穿始终。这两条主线既相互独立，又相互支撑。
作者对全书内容的组织及章节的安排颇费心思。将Java语言本身的内容集中起来，其中基本内容的介绍放在附录中，更深层次的内容以“Java插曲”的形式在适当的地方介绍。比如，附录A介绍了程序中离不开的注释该如何写；附录B和附录C介绍了语言的基本框架，包括构成语言重要成分的各个语句的语法、类及方法的定义等；附录E介绍了文件的输入/输出功能。而像泛型、异常、迭代器、可变对象及不可变对象、继承与多态及克隆等内容，都分主题放在各个Java插曲中。熟悉这些内容的读者可以略过它们，或者有选择地阅读。这些主题比较独立，可以单独学习，也可以在涉及相关内容时作为参考。读者学习各部分内容时可以集中精力，减轻学习的难度，也避免了顾此失彼。
全书介绍了包、栈、队列、线性表、字典、树、堆及图等数据结构。每种数据结构一般都在连续的两三章中介绍。前一章专门介绍与每种结构相关的ADT的规格说明，包括数据属性及相关操作。使用具体实例说明这些操作的含义及操作的结果，帮助读者理解其定义。定义的接口也与规格说明放在同一章中，这一章的内容基本上不涉及实现的细节。接下来的一章或两章着重介绍所讨论的ADT的实现过程，并对每种实现进行效率分析。对有些重要且应用广泛的数据结构，例如栈，还给出了问题求解实例。
树和图是非常重要的数据结构，树又衍生出二叉树、查找树等结构。它们的概念与实现，既来源于树，又有别于树，所以单独成章、重点介绍。图是本书介绍的最后一种结构，除了像其他ADT一样介绍了基本操作的实现之外，还着重介绍了图的几个应用，包括遍历、拓扑排序及最短路径问题。各类算法的实现过程中，有很多是使用递归完成的。本书使用一整章的篇幅介绍了递归的概念，及如何编写递归程序。
数据的存储方式可分为两大类：一类使用数组，包括向量；另一类使用指针，即链式实现。本书对各种ADT均给出数组及链式的两种实现方式，并针对每种实现的适用性做了介绍和对比。
除此之外，本书还介绍了排序、查找、散列等概念及相应的实现过程。它们是常用的方法，也是数据结构课程的重要组成部分。针对数据的不同存储方式，适用的排序及查找方法及其实现过程不尽相同，本书也一一做了介绍。
算法的效率是重要的衡量指标，作者介绍了算法分析的大O表示。使用这些技术，对书中实现的每个算法都进行了效率分析。
作者还特别注重知识的衔接。在每章开始都列出学习本章时应该先学习哪些先修章节，这为读者画出了一个清晰的学习路线图。另外，Java语言是面向对象的语言，具有天生的继承特性。有些类及接口，除了在概念上具有相关性之外，实现时也具有继承的关系。
译者在翻译过程中尽可能保持原书的风格，包括排版格式。除了正文中的内容全部翻译外，也将伪语言描述的算法中的英文语句标注为注释，帮助读者理解这些伪语言。
本书非常适合作为大学本科数据结构课程的教材使用。书中内容图文并茂，讲解条理清晰。在内容介绍过程中，配合讲解的内容穿插相关的问题，要求读者回答，并在每章最后给出了参考答案，帮助读者自行检查对知识的掌握程度。每章最后都有数目不等的练习及项目，教师可选择使用。本书提供了大量的代码，并对代码进行了详细的介绍，这些代码对学生理解课程内容非常有益。有些未全部实现的类及方法作为课后练习及项目，要求学生完成，书中提供的这些代码成为必要的参考及基础。
在此，译者非常感谢机械工业出版社华章分社给我们提供的翻译机会。我们不仅学习了作者的编写思想，更感受到作者的敬业精神。书中反映出的作者的认真态度，使我们在翻译过程中不敢有丝毫的懈怠。译者还要特别感谢本书的策划编辑朱劼及责任编辑盛思源。翻译过程中，译者始终得到机械工业出版社华章分社温莉芳总经理、朱劼编辑的大力支持和全方位的帮助。责任编辑严格把关，与译者多次探讨重要概念、术语的确切含义及合适的用辞。正是编辑的认真，才让本书顺利地和读者见面。
本书由辛运帏、饶一梅共同翻译。翻译过程中，得到了南开大学计算机与控制工程学院多位老师的支持和帮助，恕我们不能一一列出他们的姓名，在此一并表示衷心的感谢。还要特别感谢国防科技大学计算机学院熊岳山教授、东南大学计算机学院姜浩教授、北京理工大学网络服务中心陈朔鹰主任，正是他们为译者提出的众多非常好的建议，帮助译者顺利完成本书的翻译。
虽然我们在翻译时非常认真努力地工作，期望能以尽量高的水平将本书呈现给读者，但限于译者的水平有限，很多地方并不能完全体现作者的原意，翻译过程中更是难免会有错误之处，敬请广大读者指正。您的任何意见和建议都是我们进一步完善本书的动力。
感谢尊敬的读者选择了本书。

译　者
2017年2月于南开园

出版者的话
译者序
前言
引言　组织数据　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　双端队列的双向链式实现　277
11.6　优先队列的可能实现方案　281
第12章　线性表　285
12.1　ADT线性表的规格说明　285
12.2　使用ADT线性表　291
12.3　Java类库：接口List　294
12.4　Java类库：类ArrayList　294
第13章　使用数组实现线性表　299
13.1　使用数组实现ADT线性表　299
13.1.1　类比　299
13.1.2　Java实现　301
13.1.3　使用数组实现ADT线性表的效率　308
第14章　使用链式数据实现线性表　313
14.1　链式结点链上的操作　313
14.1.1　在不同的位置添加结点　313
14.1.2　从不同的位置删除结点　316
14.1.3　私有方法getNodeAt　317
14.2　开始实现　318
14.2.1　数据域和构造方法　319
14.2.2　添加到线性表的表尾　320
14.2.3　在线性表的给定位置添加　321
14.2.4　方法isEmpty和toArray　322
14.2.5　测试核心方法　324
14.3　继续实现　325
14.4　细化实现　328
14.5　使用链实现ADT线性表的效率　331
14.6　Java类库：类LinkedList　333
Java插曲5　迭代器　338
第15章　ADT线性表的迭代器　351
15.1　实现迭代器的方法　351
15.2　独立类迭代器　351
15.3　内层类迭代器　354
15.3.1　链式实现　355
15.3.2　基于数组的实现　358
15.4　为什么迭代器方法在它自己的类中　360
15.5　基于数组实现接口ListIterator　362
Java插曲6　可变及不可变对象　372
第16章　有序表　378
16.1　ADT有序表的规格说明　378
16.2　链式实现　382
16.2.1　方法add　383
16.2.2　链式实现的效率　388
16.3　使用ADT线性表实现　388
Java插曲7　继承和多态　396
第17章　继承和线性表　405
17.1　使用继承实现有序表　405
17.2　设计一个基类　407
17.3　有序表的高效实现　413
第18章　查找　417
18.1　问题　417
18.2　在无序数组中查找　417
18.2.1　无序数组上的迭代顺序查找　418
18.2.2　无序数组上的递归顺序查找　418
18.2.3　顺序查找数组的效率　420
18.3　有序数组上的查找　420
18.3.1　有序数组上的顺序查找　420
18.3.2　有序数组上的二分查找　421
18.3.3　Java类库：方法binarySearch　424
18.3.4　数组上的二分查找的效率　425
18.4　无序链上的查找　426
18.4.1　无序链上的迭代顺序查找　426
18.4.2　无序链上的递归顺序查找　427
18.4.3　链上查找的效率　427
18.5　有序链上的查找　428
18.5.1　有序链上的顺序查找　428
18.5.2　有序链上的二分查找　428
18.6　查找方法的选择　429
Java插曲8　再论泛型　434
第19章　字典　436
19.1　ADT字典的规格说明　436
19.1.1　Java接口　439
19.1.2　迭代器　440
19.2　使用ADT字典　441
19.2.1　问题求解：电话号码簿　441
19.2.2　问题求解：字的频度　445
19.2.3　问题求解：字的词汇索引　448
19.3　Java类库：接口Map　451
第20章　字典的实现　455
20.1　基于数组的实现　455
20.1.1　基于数组的无序字典　455
20.1.2　基于数组的有序字典　459
20.2　链式实现　463
20.2.1　无序链式字典　464
20.2.2　有序链式字典　464
第21章　散列简介　470
21.1　什么是散列　470
21.2　散列函数　472
21.2.1　计算散列码　473
21.2.2　将散列码压缩为散列表的下标　475
21.3　解决冲突　476
21.3.1　开放地址的线性探查　476
21.3.2　开放地址的二次探查　480
21.3.3　开放地址的双散列　480
21.3.4　开放地址的潜在问题　482
21.3.5　拉链法　482
第22章　使用散列实现字典　488
22.1　散列的效率　488
22.1.1　装填因子　488
22.1.2　开放地址法的代价　489
22.1.3　拉链法的代价　490
22.2　再散列　491
22.3　冲突解决方案的比较　492
22.4　字典的散列实现　492
22.4.1　散列表中的项　492
22.4.2　数据域和构造方法　493
22.4.3　方法getValue、remove和add　495
22.4.4　迭代器　500
22.5　Java类库：类HashMap　501
22.6　Java类库：类HashSet　501
第23章　树　504
23.1　树的概念　504
23.1.1　层次结构　504
23.1.2　树的术语　505
23.2　树的遍历　509
23.2.1　二叉树的遍历　510
23.2.2　一般树的遍历　511
23.3　树的Java接口　512
23.3.1　所有树的接口　512
23.3.2　二叉树的接口　512
23.4　二叉树的示例　514
23.4.1　表达式树　514
23.4.2　决策树　515
23.4.3　二叉查找树　518
23.4.4　堆　520
23.5　一般树的示例　522
23.5.1　语法树　522
23.5.2　游戏树　523
第24章　树的实现　530
24.1　二叉树中的结点　530
24.2　ADT二叉树的实现　532
24.2.1　创建基本二叉树　532
24.2.2　方法privateSetTree　534
24.2.3　访问方法和赋值方法　536
24.2.4　计算高度和结点个数　536
24.2.5　遍历　537
24.3　表达式树的实现　541
24.4　一般树　543
24.5　使用二叉树表示一般树　543
Java插曲9　克隆　549
第25章　二叉查找树的实现　562
25.1　开始　562
25.1.1　二叉查找树的接口　563
25.1.2　重复项　564
25.1.3　开始定义类　565
25.2　查找和获取　566
25.3　遍历　567
25.4　添加一项　567
25.4.1　递归实现　568
25.4.2　迭代实现　571
25.5　删除一项　572
25.5.1　删除叶子结点中的项　573
25.5.2　删除仅有一个孩子的结点中的项　573
25.5.3　删除有两个孩子的结点中的项　574
25.5.4　删除根中的项　576
25.5.5　递归实现　576
25.5.6　迭代实现　579
25.6　操作效率　582
25.6.1　平衡的重要性　583
25.6.2　结点按什么次序添加　583
25.7　ADT字典的实现　584
第26章　堆的实现　594
26.1　再论：ADT堆　594
26.2　使用数组表示堆　594
26.3　添加项　597
26.4　删除根　599
26.5　创建堆　602
26.6　堆排序　603
第27章　平衡查找树　611
27.1　AVL树　611
27.1.1　单旋转　612
27.1.2　双旋转　614
27.1.3　实现细节　617
27.2　2-3树　620
27.2.1　在2-3树中进行查找　621
27.2.2　向2-3树中添加项　621
27.2.3　添加过程中分裂结点　623
27.3　2-4树　624
27.3.1　向2-4树中添加项　624
27.3.2　AVL树、2-3树和2-4树的比较　626
27.4　红黑树　626
27.4.1　红黑树的特性　627
27.4.2　向红黑树中添加项　628
27.4.3　Java类库：类TreeMap　632
27.5　B树　632
第28章　图　639
28.1　一些示例及术语　639
28.1.1　公路图　639
28.1.2　航空公司的航线　641
28.1.3　迷宫　642
28.1.4　先修课程　642
28.1.5　树　642
28.2　遍历　643
28.2.1　广度优先遍历　643
28.2.2　深度优先遍历　644
28.3　拓扑序　646
28.4　路径　648
28.4.1　寻找路径　648
28.4.2　无权图中的最短路径　648
28.4.3　带权图中的最短路径　651
28.5　ADT图的Java接口　654
第29章　图的实现　662
29.1　两个实现概述　662
29.1.1　邻接矩阵　662
29.1.2　邻接表　663
29.2　顶点和边　663
29.2.1　说明类Vertex　664
29.2.2　内部类Edge　666
29.2.3　类Vertex的实现　666
29.3　ADT图的实现　669
29.3.1　基本操作　669
29.3.2　图算法　672
附录A　文档和程序设计风格　678
附录B　Java基础（在线）　682
附录C　Java类（在线）　684
附录D　从其他类创建类　685
附录E　文件输入和输出（在线）　701
索引　702