本书是为数据结构入门课程而编写的教材。作者Frank Carrano在编写过程自始至终特别考虑到了Java与对象，为教师和学生提供了一种精心设计并经过教学实验的方式借助Java讲授ADT和对象。本书独特的设计将内容组织为相对较短的章。这种方式使学习更容易，并留出了教学的机动性。本书教给学生如何使用线性表、词典、栈、队列等等来组织数据。利用这些数据组织方式，学生们将学到算法设计的相关技术。

前 言 作者的话 欢迎大家阅读《数据结构与抽象(Java版)（第三版）》。这是一本针对数据结构入门课程（通常被称为CS-2）而编写的书， 它可以作为我写的另外一本书Imagine！Java的续篇。 无论是一名教师还是一位学生， 我想告诉你， 这本书的撰写是基于我执教本科计算机科学课程30余年的经验。我希望这本书具有很好的读者友好性， 使学生可以毫不费力地学， 教师可以事半功倍地教。为了达到这个目标， 你会发现学习材料是以小块——我称之为“小节”——的形式组织的， 这样易于消化学习内容， 促进学习。本书用大量模拟现实世界问题的例子作为新素材， 帮助学生更好地学习和掌握抽象概念。并使用大量简单的图表阐明、 厘清了复杂的思想。 我希望你喜欢读这本书。像很多已经读过此书的读者一样， 可以有效且不断地学习或者讲授数据结构。 致以亲切的问候 附言： 十分乐意与使用本书的教师和学生们保持联系。下面是我的几种联系方式： 我的Facebook： www.facebook.com/makingitreal 我的Twitter： twitter.com/Frank_M_Carrano 我的电子邮箱： carrano@acm.org 我的博客： frank-m-carrano.com/makingitreal 学生注意事项 本书所包含的主题涉及各种数据组织方法的处理， 可以使应用程序高效地访问和操作数据。这些主题是以后学习计算机科学的基础， 因为它们提供了创建复杂和可靠的软件所需要的基础知识。无论是对设计电子游戏感兴趣还是喜欢开发机器人控制手术的软件， 数据结构的学习对成功而言都至关重要。即使现在不打算学习本书中的所有主题， 以后也有可能会接触到它们。衷心希望大家喜欢阅读本书， 并希望它成为未来课程学习的有用参考工具。 在看完这个前言之后， 读者应该阅读一下引言。这样就可以快速地了解它的主要内容， 以及在开始学习前所需要了解的相关Java的知识。附录A到附录G回顾了Java的基础知识、 类、 继承、 异常、 文件和javadoc风格的注释。请注意, 在本书的最后还给出了Java的保留字、 基本数据类型、 运算符的优先级和Unicode字符的列表。 另外， 请一定要浏览此前言的剩余部分， 从而了解本书将对你的学习有帮助的特色之处。 组织结构 本书主题的组织、 顺序的安排和内容展开的幅度都更易于学习和教学。它使读者一次专注于一个概念， 为读者提供主题学习顺序的灵活性， 并清晰地区分抽象数据类型（ADT）的说明和具体实现。为了达到这些目标， 本书将内容组织成30章， 每章都由一些短小的编了号的小节组成， 每个小节讲解一个概念。每一章或是讲述一个ADT的说明， 或是讲述它的实现。读者可以选择在了解一个ADT的说明后紧接着学习它的实现， 也可以选择在考虑任何实现问题之前先探讨若干个ADT的说明和使用。本书的组织结构可以使读者方便地选择自己喜欢的主题顺序进行阅读。 内容一览表 下面的各章名称列表显示了本书内容的整体组成情况。下面将会更进一步地描述各个章节的主要内容。请注意， 第30章（英文版本）和附录是在线提供的内容在线章节请登录华信教育资源网(www.hxedu.com.cn)下载。。 第1章 袋子 第2章 用数组实现袋子 第3章 用链表实现袋子 第4章 算法的效率 第5章 栈 第6章 栈的实现 第7章 递归 第8章 排序引论 第9章 快速排序方法 第10章 队列、 双端队列和优先队列 第11章 队列、 双端队列和优先队列的实现 第12章 线性表 第13章 用数组实现线性表 第14章 用链表实现线性表 第15章 迭代器 第16章 有序表 第17章 继承及线性表 第18章 查找 第19章 词典 第20章 词典的实现 第21章 散列概述 第22章 用散列实现词典 第23章 树 第24章 树的实现 第25章 二叉查找树的实现 第26章 堆的实现 第27章 平衡查找树 第28章 图 第29章 图的实现 第30章 可变的、 不可变的和可复制的对象 附录 A.Java基础 B.Java类 C.由已有类创建新类 D.类的设计 E.异常处理 F.文件输入与输出 G.文档与程序设计风格 第3版的新内容 根据读者和审稿人的意见， 对部分素材进行了重新组织。很多学生对栈和队列已经相当熟悉了， 所以对这些数据组织方式的内容出现在这一版较靠前的章节中。而且， 重新组织以后， 学生可以更好地理解链接数据的难点。在链表中添加或者删除头节点是最简单的操作。在介绍袋子的过程中， 本书使用这些简单的链表操作来实现袋子。在袋子之后介绍的是栈， 栈是一个更加有用的组织方式， 它的一种实现也是基于相同的简单链表。队列的实现为讨论对链表尾节点进行添加和删除提供了机会。最后， 本书对线性表的处理中关注了对链表中间节点进行添加和删除的操作。 读者将注意到相对于前一版本， 算法的效率（包括提升动机）、 递归和排序等内容也出现在此版本的靠前章节中。为了保持对数据结构的关注， 将原来的前三章——Java类、 由已有类创建新类和类的设计移到了附录部分。现在引言之后直接就开始介绍第一个数据合集——袋子。不过， 对于在开始学习本书主题之前需要学习Java类的读者， 仍然可以在附录中找到原来这些章节的完整内容。 最后， 这一版增加了一些新的特色。本书以“问题解决”的形式展示了大量的例子。在这种方式下， 首先提出一个问题， 然后讨论它的解决方案并进行实现。偶尔会出现的“设计决策”会探讨一个解决方案的多种设计选择。这两个新的特色帮助学生思考程序设计的重要方面， 也让他们在特定的场景下思考概念。上一个版本中已有的注释、 编程小贴士和自测问题（含答案）在本版中均进行了保留。此外， 读者将发现Deque接口、 ArrayDeque类的介绍以及其他的项目实践题目。 下面是本书新内容的总结： ● 较早介绍抽象数据类型、 可变大小数组和链接数据。 ● 对链接数据的循序渐进的讲解。 ● 较早介绍算法效率、 栈、 递归、 排序和队列等内容。 ● 有需要较好的算法效率的动力。 ● 第1章至第3章——袋子、 用数组实现袋子和用链表实现袋子——介绍和实现ADT袋子。 ● 新元素包括问题解决和设计决策。 ● 第二版中出现在开头章节的对Java类的回顾内容现在移到了附录中。 ● 标准接口Deque和类ArrayDeque的涵盖。 ● 附加的实践项目。 ● 自测问题的答案出现在每章的最后而不是附录中。 促进学习的特色之处 首先， 每章一开始都给出了内容列表， 学生需要阅读的预备章节和附录列表， 以及本章知识的学习目标。其次， 贯穿本书还出现了如下所示的其他教学元素： 注 以楷体字印刷的段落对重要的思想进行描述或者总结， 且需要和上下文一起阅读。 编程小贴士 在相关之处给出的改进或者有助于编程的建议。 示例 阐明新概念的大量例子。 解决问题 以“解决问题”的形式给出的大型例子， 其中首先提出问题， 然后对其解决方案进行讨论、 设计和实现。 设计决策 在制定解决方案的时候， 为读者可能做出的设计选择进行探讨。“设计决策”这一元素列出这样的设计选项， 并给出为特定例子所做出的最终选择的依据。这些讨论经常出现在解决问题例子的上下文中。 自测问题答案 在每一章中都会提出一些自测问题， 融合在章节的文字中， 来巩固刚刚提出的概念。这些“自我检测”问题帮助读者理解这些知识， 因为回答这些问题需要停顿和反思。这些问题的答案在每一章的最后给出。练习题和实践项目 可以通过解决每一章最后的练习题和实践项目来进行更深入的实践。遗憾的是， 尽管不是课堂授课， 我们也不能给读者提供这些练习题和实践项目的答案。只有采用本书进行教学的教师才可从出版商那里获取选中的答案。如果需要获得这些练习题和实践项目的帮助， 读者需要联系你的指导老师。 教师和学生可使用的教辅资源 以下各项资源在出版商的网站pearsonhighered.com/carrano上都可以访问到： ● 本书中出现的Java代码 ● 本书出版以来已发现的所有印刷错误的链接 ● 其他的在线内容的链接， 下面将进行介绍 教师资源为获取本书的教辅资源， 可参阅本书目录后所附的“教辅申请表”——编者注。 以下访问受限的资源只提供给采用本书进行教学的教师。教师需要登录Pearson教师资源中心（访问pearsonhighered.com/carrano）来获取这些资源： ● PowerPoint授课幻灯片 ● 教师解决方案手册 ● 书中的图表 除此之外， 教师可以访问本书的同步网站来获取以下在线高级内容， 仍然可以通过pearsonhighered.com/carrano进行访问： ● 第30章 ● 术语表 ● 附录B、 附录C和附录D的练习题和实践项目 请联系你的Pearson销售代表来获取教师访问码。联系方式可以通过访问pearsonhighered.com/replocator进行查看。 学生资源相关文件也可登录华信教育资源网（www.hxedu.com.cn)下载。 以下资源学生可以通过登录本书同步网站（访问pearsonhighered.com/carrano）来获得： ● 第30章 ● 术语表 ● 附录B、 附录C和附录D的练习题和实践项目 学生必须使用书前面的访问卡来注册和进入同步网站。没有访问码的学生可以按照同步网站上列出的步骤来购买访问权限。 请注意Java类库可以通过访问download.oracle.com/javase/7/docs/api/来获得。 章节概述 本书的读者应当已经修完一门编程课程， 最好是Java编程。附录部分覆盖了假定读者要了解的Java基础知识。大家可以将附录作为复习内容， 或者作为从其他编程语言向Java过渡的基础。这本书本身就以引言开头， 为我们将要学习的数据组织做好了铺垫。 ● 第1章至第3章： 介绍袋子这种抽象数据类型（ADT）。通过将这部分内容划分为几个章节， 清晰明了地将袋子的说明、 使用和实现区分开来。例如， 第1章详细说明袋子并提供了若干使用的例子。第2章涵盖了基于数组和向量的具体实现， 而第3章则介绍了链表并使用链表对袋子类进行定义。 同样， 在整本书中， 当讨论多种多样的其他类型的ADT的时候， 也将它们的说明和实现进行了分离。读者可以选择先学习对ADT进行说明和使用的章节， 以后再学习具体实现的章节； 也可以选择按照书中的顺序， 在学习说明和使用之后马上实现这些ADT。各章预备知识的列表将在这个前言的后面部分给出， 以帮助大家规划自己学习整本书的路线。 第2章不仅仅是简单地实现ADT袋子， 也展示了如何通过在开始只关注核心方法来实现一个类的方法。在实现类的时候， 一种大有益处的常见做法是首先实现和测试核心方法， 以后再去定义其他的方法。 ● 第4章： 介绍了算法的复杂度。我们将这一主题融入到后面的章节中。 ● 第5章和第6章： 第5章讨论栈， 给出了栈的使用实例。第6章通过使用数组、 向量和链表来实现栈。 ● 第7章至第9章： 接下来， 介绍递归这种问题解决工具以及它和栈的关系。递归和算法的效率一样， 是一个在整本书中不断涉及的主题。例如， 在第8章和第9章讨论各种各样的排序技术和它们的相对复杂度时， 我们考虑这些算法的迭代版本， 也考虑其递归版本。 ● 第10章和第11章： 第10章讨论队列、 双端队列和优先队列， 第11章考虑它们的实现。在第11章中， 介绍了循环链表和双向链表。 ● 第12章、 第13章和第14章： 接下来的这三章介绍ADT线性表。我们在抽象层次上讨论了这种合集， 然后分别使用数组、 向量和链表对它进行了实现。 ● 第15章： 然后， 基于线性表的讲解讨论迭代器。这一章考虑和实现了Java的迭代器接口Iterator和ListIteraror。本章还介绍了Iterable接口。 ● 第16章和第17章： 第16章继续讨论线性表， 介绍了有序表， 关注有序表的两种可能的实现及其效率。第17章说明如何将线性表作为有序表的超类， 并且讨论了超类的一般设计。 ● 第18章： 在线性表和有序表的背景下， 考察查找数组和链表的一些策略。这些讨论是后续章节的坚实基础。 ● 第19章至第22章： 第19章涵盖了ADT词典的说明和使用。第20章介绍词典的基于链表的实现和基于数组的实现。第21章介绍散列， 而第22章则利用散列实现了词典。 ● 第23章至第27章： 第23章讨论了树及其可能的用法。在给出树的一些例子的同时， 本章介绍了二叉查找树和堆。第24章考虑二叉树和一般树的实现， 而第25章则关注二叉查找树的实现。第26章说明如何使用数组来实现堆。第27章介绍平衡查找树。这一章包括AVL树、 2-3树、 2-4树、 红黑树和B树。 ● 第28章至第29章： 接着讨论图， 并且着眼于它的几种应用和两种具体实现。 ● 第30章： 最后一章详细阐述可变对象和不可变对象的概念， 介绍了克隆。在数据是可变的情况下， 如果客户程序维护一个ADT内部数据的引用， 那么它就可以改变这个数据， 而不用使用类的公有方法。我们考虑对客户程序如此操作进行预防的步骤。 ● 附录A至附录G： 附录提供关于Java的补充知识。如前所述， 附录A回顾了到类之前（不包括类）的基础知识。不过， 该附录也涵盖了Scanner类、 枚举类型、 装箱和拆箱以及for-each循环。附录B讨论Java类， 附录C进一步扩展这一主题， 着眼于组合和继承， 附录D关注类的设计。附录E涵盖异常处理， 附录F讨论文件。附录G考虑程序设计风格和注释， 介绍了javadoc注释风格并且定义了我们在本书中所使用的标签。 致谢 在此， 衷心地感谢下列审稿人员。正因为他们认真阅读了上一版本， 提出了中肯的意见和建议， 才使本书的质量和水平得到极大地提高。 Steven Andrianoff—St. Bonaventure University Brent Baas—LeTourneau University Timothy Henry—University of Rhode Island Ken Martin—University of North Florida Bill Siever—Northwest Missouri State University Lydia Sinapova—Simpson College Lubomir Stanchev—Indiana University Judy Walters—North Central College Xiaohui Yuan—University of North Texas 特别感谢在这本书漫长的修订过程中支持我的搭档们。我的编辑Tracy Dunkelberger给予我持续不断的热情、 鼓励、 智慧和指导。Melinda Haggerty和Allison Michael使审阅工作井井有条。Stephanie Sellinge见证了本书及其增补内容的发展。与我长期合作的文字编辑Rebecca Pepper， 确保我的表述清晰无误， 语法正确。Jeff Holcomb、 Bob Engelhardt和Louise Capulli 指导了这本书的出版。每当我需要他们的时候， 这支队伍一直与我携手同行。非常感谢他们！ 对前面诸位的感谢并不能削减我对许多其他帮助者的感激之情。再次感谢本书前两个版本的审稿人： 第二版的审稿人： Harold Anderson—Marist College Razvan Andonie—Central Washington University Tom Blough—Rensselaer Polytechnic Institute Chris Brooks—University of San Francisco Adrienne Decker—University at Buffalo, SUNY Henry Etlinger—Rochester Institute of Technology Derek Harter—Texas A＆M University Timothy Henry—University of Rhode Island Robert Holloway—University of Wisconsin, Madison Charles Hoot—Oklahoma City University Teresa Leyk—Texas A＆M University Robert McGlinn—Southern Illinois University, Carbondale Edward Medvid—Marymount University Charles Metzler—City College of San Francisco Daniel Zeng—University of Arizona 第一版的审稿人： David Boyd—Valdosta State University Dennis Brylow—Purdue University Michael Croswell—Industry trainer/consultant Matthew Dickerson—Middlebury College Robert Holloway—University of Wisconsin, Madison John Motil—California State University, Northridge Bina Ramamurthy—University at Buffalo, SUNY David Surma—Valparaiso University 还要感谢很多其他为旧版本提供帮助的人。他们是Alan Apt,James Blanding, Lianne Dunn, Mike Giacobbe, Toni Holm, Charles Hoot, Brian Jepson, Rose Kernan, ChristiannaLee, Patrick Lindner, John Lovell, Vince O’Brien, Patty Roy, Walt Savitch, Ben Schomp, HeatherScott, Carole Snyder, Chirag Thakkar, Camille Trentacoste, Nate Walker, and Xiaohong Zhu。 最后， 我想感谢我的家人和朋友——Doug, Ted, Vandee, Nancy, Sue, Tom, Maybeth, Marge和Lorraine——给了我一个远离电脑的生活。 感谢大家， 感谢你们的专业支持和鼓励。Frank M. Carrano 各章的预备知识 本书的每一章和每一个附录都假定读者已经在前期学习了一些知识。下面的表格列出了这些预备知识， 其中的数字代表了章节的编号， 字母指明了参考的附录。读者可以根据这些信息来规划自己的学习路径。 引 言 如果稍稍留意周围的人或事， 就会意识到人们可能采取不同的组织方式去处理日常的事务。例如， 今天早晨去商店买东西， 在收银结算时将到付费队伍的最后面去排队。大家自觉地按照时间先后的顺序排队， 排在最前面的人肯定第一个享受结算服务且最早离开队伍。最终， 将轮到你排到队伍的最前面， 付费后拿着装有所购买物品的袋子心满意足地离开。这时， 购物袋里的物品是没有什么顺序之分的， 有些还可能是相同的商品。 看到放在书桌上的一摞书或者一叠纸了吗？对这样的一摞东西（即栈）， 我们很容易查看或者取走放在最上面的物品， 也很容易继续在最上面添加新的物品。一摞东西中的物品也是按照时间先后的顺序组织的， 即最后添加的物品放在最上面， 而最先添加的物品放在最下面。 再看看放在桌上的那张事务处理列表吧。对你而言， 这张表中每一项书写的位置或许重要或许不重要。但是， 还是有可能在写的时候考虑过是按照事务的重要程度排列， 还是按照它们的字母顺序来排列。其实， 书写的顺序是你自己确定的， 事务处理列表只不过列出了所有待处理的事务条目而已。 字典是单词和它们的定义根据字母顺序组织的列表。我们往往需要查找某个单词， 查看它的定义。如果字典是纸质印刷的， 这种按照字母顺序的组织方式将有助于快速地找到单词。如果字典是计算机化的， 虽然表面上看不到它内部按字母顺序的组织方式， 但是该方式仍然提高了检索单词的速度。 既然提到了计算机， 那么就让我们看一下文件的组织方式——它们被组织到文件夹或目录中， 即每个文件夹包含若干其他的文件夹或文件。这种类型的组织方式是层次型的。如果对此组织方式画一张图的话， 可以看到它与家族树或公司的内部部门图有相似之处。确实， 这些数据的组织方式是相似的， 称为树。 最后， 注意一下为周末出游所设计的路线图。这张含有道路和城镇信息的图指示了如何从一个地方到达另一个地方， 往往其中有多条可选的线路。例如， 有一条路线可能是距离较短的， 而另一条可能是更快到达的。这种路线图具有的数据组织方式称为图。 除了前面这些日常例子之外， 计算机程序也需要组织其数据。也就是说， 程序可以使用列表、 栈、 字典等数据组织方式。这些数据组织方式被表示为多个抽象数据类型。一个抽象数据类型（Abstract Data Type， ADT）是一份规格说明书， 描述了一个数据集及其数据上的操作， 即每个ADT详细说明该存储什么样的数据， 以及对这些数据要进行哪些操作。不过， ADT并没有明确说明如何存储数据或者如何实现操作， 因此对这些ADT的讨论可以不依赖于任何程序设计语言。相对ADT而言， 一个数据结构是某个ADT在一种程序设计语言中的实现。 一个合集（collection）是更广的术语， 是指一个包含一组对象的ADT。一些合集允许重复的项， 而另一些不允许。一些合集按照某种顺序组织它们的内容， 而另一些则无序地组织。一个容器（container）是实现合集的一个类。大家以后可能看到， 有些人对术语“容器”和“合集”会不加区别地进行使用。 我们可以创建一个ADT袋子（bag)， 它由一个允许重复元素的无序合集构成， 很像是一个食品杂货袋， 一个午餐袋或者是一个装满薯片的袋子。假设从薯片袋子中取出一片薯片， 这时你不会知道这片薯片是何时放进袋子中的， 也不可能知道袋子中是否还有一片与刚取出的薯片形状完全相同的薯片。但是， 实际上并不需要关心这些。如果确实在意， 就不会将薯片存放在一个袋子中。 袋子不会将其内容排序， 但是有时候需要对物品进行排序的。各种各样的ADT使用不同的方式对它们所包含的元素进行排序。例如， ADT线性表（list）将它所含的项简单地进行编号。因此， 一个线性表有第一项、 第二项， 以此类推。尽管可以向线性表的末尾添加项， 实际上也可以在线性表开头或者线性表的某两项之间插入项。这么做会导致新项之后的项的重新编号。此外， 可以在线性表中删除某特定位置的项。因此， 线性表中项的位置并不一定表明它被添加的时间。请注意， 线性表并不决定项的存放位置， 而是由编程人员决定。 相比之下， ADT栈（stack）和队列（queue）则以时间顺序来组织它们的项。当从栈中删除一项时候， 所删除的是最近被添加的那一项。当删除队列中的一项的时候， 所删除的是最早被添加进队列中的那一项。因此， 栈就像一摞书。可以取走最上面的书或者将另一本书添加到这摞书的最上面。而队列就像是人排队的队伍， 人们从队首离开， 从队尾加入。 如果项是可比的， 一些ADT中的条目始终保持有序的状态。例如， 字符串可以按照字母顺序进行组织。当向ADT有序表（sorted list)中添加一项的时候， ADT决定要把该项放入哪个位置。不能像对待ADT线性表那样为待添加项指定一个位置。 ADT字典（dictionary）包含成对的项， 这一点非常像一本包含单词及其定义的语言类字典。在这个例子中， 单词充当的是关键字的角色， 它可以定位词条的位置。一些字典会将词条排序， 另一些则不会。 ADT树（tree）根据某种层次结构来组织它的条目。例如， 在家族树中， 人们与他们的孩子和父母相联系。ADT二叉查找树（binary search tree）使用层次化的有序结构， 这使得定位其中的条目更加简单。 ADT图（graph）是ADT树的一般化。ADT图关注的是条目之间的关系， 而非层次化的组织。例如， 一张路线图是一个显示了城镇间道路和距离的图。 本书向大家介绍如何使用和实现这些数据组织方式。在开始学习之前， 需要了解Java。附录A回顾了Java中的基本语句。附录B讨论类和方法的基本构造。可以选择简单浏览这些材料， 或是认真阅读， 也可以在需要的时候进行查看。附录C和附录D介绍Java的内容， 有可能某些部分或者全部的内容对你而言是全新的。附录C涵盖了技术性内容， 包括组合和继承， 其目的是为了从已有的类构建新的类。附录D讨论如何设计类， 定义方法和编写Java接口。使用接口和书写说明方法的注释对描述ADT至关重要。附录E介绍如何处理异常， 附录F展示了对外部文件的读写， 附录G则概述了如何书写适合javadoc的注释本书共有7个附录（附录A至附录G）。为减少本书的印制成本， 已将其附录的电子版上载至华信教育资源网（http://www.hxedu.com.cn）， 有兴趣的读者可免费下载——编者注。

目 录 第1章 袋子 袋子 袋子的行为 袋子的规格说明 接口 ADT袋子的使用 像使用自动售货机一样使用ADT Java类库： 接口Set 第2章 使用数组实现袋子 使用固定大小的数组实现ADT袋子 一个类比 一组核心方法 核心方法的实现 核心方法的测试 更多方法的实现 删除物品的方法 使用可变大小的数组实现ADT袋子 调整数组的大小 袋子的一种新的实现 使用数组实现ADT袋子的优缺点 第3章 使用链表实现袋子 链表 通过添加节点到表头来创建链表 ADT袋子的链表实现 私有的类Node 类LinkedBag的概要 一些核心方法的定义 核心方法的测试 方法getFrequencyOf 方法contains 从链表中删除物品 方法remove和clear 具有方法set和get的类Node 使用链表实现ADT袋子的优缺点 第4章 算法的效率 动机 算法效率的度量 基本操作次数的统计 最好、 最坏和平均情况 大O表示法 程序结构的复杂度 效率的图形化表示 ADT袋子不同实现的效率 基于数组的实现 基于链表的实现 两种实现方法的比较 第5章 栈 ADT栈的规格说明 利用栈处理代数表达式 应用问题： 中缀代数表达式中括号平衡的 检查 应用问题： 中缀表达式向后缀表达式的 转换 应用问题： 后缀表达式的求值 应用问题： 中缀表达式的求值 程序栈 Java类库： 类Stack 第6章 栈的实现 基于链表的实现 基于数组的实现 基于向量的实现 Java类库： Vector类 使用向量实现ADT栈 第7章 递归 什么是递归 跟踪一个递归方法 有返回值的递归方法 递归地处理一个数组 递归地处理一个链表 递归方法的时间效率 countDown的时间效率 计算xn的时间效率 一个复杂问题的简单解决方案 一个简单问题的拙劣解决方案 尾递归 间接递归 使用栈代替递归 第8章 排序引论 组织Java对数组排序的方法 选择排序 迭代选择排序 递归选择排序 选择排序的效率 插入排序 迭代插入排序 递归插入排序 插入排序的效率 链表的插入排序 希尔排序 Java代码 希尔排序的效率 算法比较 第9章 快速排序方法 归并排序 数组的归并 递归的归并排序 归并排序的效率 迭代的归并排序 Java类库中的归并排序 快速排序 快速排序的效率 创建划分 快速排序的Java代码 Java类库中的快速排序 基数排序 基数排序的伪代码 基数排序的效率 算法比较 第10章 队列、 双端队列和优先队列 ADT队列 解决问题： 模拟排队 解决问题： 计算出售股票时的资本 增益（一） Java类库： 接口Queue ADT双端队列 解决问题： 计算出售股票时的资本 增益（二） Java类库： 接口Deque Java类库： ArrayDeque类 ADT优先队列 解决问题： 跟踪你的作业 Java类库： 类PriorityQueue 第11章 队列、 双端队列和优先队列的 实现 基于链表队列的实现 基于数组队列的实现 循环数组 有一个未使用存储单元的循环数组 基于向量队列的实现 基于循环链表队列的实现 由两部分构成的循环链表 Java类库： 类AbstractQueue 基于双向链表双端队列的实现 实现优先队列的可用方法 第12章 线性表 ADT线性表的规格说明 使用ADT线性表 Java类库： List接口 Jave类库： ArraryList类 第13章 用数组实现线性表 用数组实现ADT线性表 一个类比 Java实现 用数组实现ADT线性表的效率 用Vector实现ADT线性表 第14章 用链表实现线性表 操作链表节点 在多种位置加入节点 在多种位置删除节点 私有方法getNodeAt 开始实现 数据域和构造函数 在列表结尾加入 在列表给定位置加入 方法isEmpty和toArray 测试核心方法 继续实现 一个更好的实现 尾引用 用链表实现ADT列表的效率 Java类库： 类LinkedList 第15章 迭代器 迭代器是什么 Iterator接口 使用Iterator接口 独立类迭代器 内部类迭代器 基于链表实现 基于数组实现 为什么迭代器方法在它们自己的 类中 ListIterator接口 使用ListIterator接口 ListIterator接口基于数组的实现 内部类 Java类库： Iterable接口 Iterable和for-each循环 修改版接口List 第16章 有序表 ADT有序表的规格说明 使用ADT有序表 链表实现 方法add 链表实现的效率 使用ADT线性表的实现 效率问题 第17章 继承及线性表 使用继承实现有序表 设计一个基类 创建一个抽象基类 有序表的一种高效实现 方法add 第18章 查找 问题引入 查找无序数组 无序数组的迭代式顺序查找 无序数组的递归式顺序查找 顺序查找数组的效率 查找有序数组 有序数组的顺序查找 有序数组的二分查找 Java类库: 方法binarySearch 二分查找数组的效率 查找无序链表 无序链表的迭代式顺序查找 无序链表的递归式顺序查找 顺序查找链表的效率 查找有序链表 有序链表的顺序查找 二分查找有序链表 查找方法的选择 第19章 词典 ADT词典规格说明 Java接口 迭代器 使用ADT词典 问题解决： 电话号码本 问题解决： 词频 问题解决： 词的索引 Java类库： Map接口 第20章 词典的实现 基于数组的实现 一个无序数组词典 一个有序数组词典 基于向量的实例 链式实例 一个无序链式词典 一个有序链式词典 第21章 散列概述 散列是什么 散列函数 计算散列码 将散列码压缩成散列表的索引 处理冲突 用线性探测实现开放定址 用二次探测实现开放定址 用双重散列实现开放定址 开放定址的潜在问题 链地址 第22章 用散列实现词典 散列的效率 容载分析 开放定址消耗分析 链地址消耗分析 再散列 不同冲突解决方案的对比 用散列实现词典的实例 散列表中的条目 数据域和构造函数 getValue， remove和add方法 迭代器 Java类库： HashMap类 Java类库： HashSet类 第23章 树 树的概念 层次化的数据组织 树的术语 树的遍历 遍历二叉树 一般树的遍历 树的Java接口 树的通用接口 二叉树的接口 二叉树的例子 表达式树 决策树 二叉查找树 堆 一般树的例子 语法分析树 游戏树 第24章 树的实现 二叉树的节点 节点的接口 二叉树节点的实现 ADT二叉树的实现 创建基本二叉树 privateSetTree方法 访问器与更改器方法 计算高度和节点数 遍历 表达式树的实现 一般树 一般树的节点 用二叉树表示一般树 第25章 二叉查找树的实现 开始 二叉查找树接口 重复的条目 开始类定义 查找和检索 遍历 添加条目 递归实现 迭代实现 删除条目 删除一个叶子节点的条目 删除节点有一个孩子的条目 删除节点有两个孩子的条目 删除为根的条目 递归实现 迭代实现 操作的效率 平衡的重要性 节点添加的顺序 ADT词典实现 第26章 堆的实现 再论ADT堆 用数组表示堆 插入条目 删除根 创建堆 堆排序 第27章 平衡查找树 AVL树 单旋转 双旋转 实现细节 2-3树 查找2-3树 添加条目至2-3树 添加时分裂节点 2-4树 添加条目至2-4树 比较AVL， 2-3和2-4树 红黑树 红黑树的性质 添加条目到红黑树 Java类库： TreeMap类 B树 第28章 图 一些示例和术语 公路线路图 航空线路图 迷宫 树 遍历 广度优先遍历 深度优先遍历 拓扑排序 路径 寻找路径 无权图的最短路径算法 加权图中的最短路径 ADT图的Java接口 第29章 图的实现 两种实现的概述 邻接矩阵 邻接表 顶点和边 类Vertex的规格说明 内部类Edge 实现Vertex类 ADT图的实现 基本操作 图算法在 线 部 分 第30章 可变的、 不可变的和可复制的对象（英文版本） 附录A Java基础 附录B Java类 附录C 从已有类创建新类 附录D 类的设计 附录E 异常处理 附录F 文件输入与输出 附录G 文档与程序设计风格

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

http://www.hxedu.com.cn/hxedu/fg/book/bookinfo.html?code=G0276160