译  者  序
数据结构与算法分析是计算机专业十分重要的一门基础课， 计算机科学各个领域及各种应用软件都要使用相关的数据结构和算法。
当面临一个新的设计问题时， 设计者需要选择适当的数据结构， 并设计出满足一定时间和空间限制的有效算法。本书作者把数据结构和算法分析有机地结合在一本教材中， 有助于读者根据问题的性质选择合理的数据结构， 并对算法的时间、 空间复杂性进行必要的控制。
 本书采用当前流行的面向对象的C++程序设计语言来描述数据结构和算法， 因为C++语言是程序员最广泛使用的语言。因此， 程序员可以把本书中的许多算法直接应用于将来的实际项目中。尽管数据结构和算法在设计本质上还是很底层的东西， 并不像大型软件工程项目开发那样， 对面向对象方法具有直接的依赖性， 因此有人会认为并不需要采用高层次的面向对象技术来描述底层算法。 但是采用C++语言能更好地体现抽象数据类型的概念， 从而更本质地描述数据结构和算法。为了使本书清晰易懂， 作者有意回避了C++的某些重要特性。
本书正文包括五大部分的内容， 第一部分是准备工作， 介绍了一些基本概念和术语， 以及基础数学知识。在本书的改版中， 作者加强了面向对象的讨论， 特别是增加了设计模式的相关内容， 例如享元、 访问者、 组合和策略等设计模式。设计模式像模板那样描述了一种解决方案的框架及具体实践， 又有类似于数据结构的代价和收益， 需要根据不同应用场景做出权衡。
 第二部分介绍了最基本的数据结构， 依次为线性表（包括栈和队列）、 二叉树和树。对每种数据结构的讲解都从其数学特性入手， 先介绍抽象数据类型， 然后再讨论不同的存储方法， 并且研究不同存储方法的可能算法。值得赞赏的是， 作者结合算法分析来讨论各种存储方法和算法的利弊， 摒弃那些不适宜的方法， 这样就调动了读者的思维， 使其可以从中学到考虑问题的方法。这种“授人以渔”的策略使读者在今后设计和应用数据结构时能全面地考虑各种因素， 选择最佳方案。
作为最常用的算法， 排序和检索历来是数据结构讨论的重点问题。这在第三部分的第7章~第10章中进行了详尽的讨论。排序算法最能体现算法分析的魅力， 它的算法速度要求非常高： 其中内排序主要考虑的是怎样减少关键码之间的比较次数和记录交换次数， 以提高排序速度； 而外排序则考虑外存的特性， 尽量减少访问操作， 以提高排序速度。第7章证明了所有基于比较的排序算法的时间代价是O(nlogn)， 这也是排序问题的时间代价。检索则考虑怎样提高检索速度， 这往往与存储方法有关。书中介绍了几种高效的数据结构， 如自组织线性表、 散列表、 B树和B+树等， 都具有极好的检索性能。
第四部分介绍了数据结构的应用与一些高级主题， 其中包括图、 跳跃表、 广义表和稀疏矩阵等更复杂的线性表结构， 还包括了Trie结构、 AVL树等复杂树结构， 以及k-d树、 PR四分树等空间数据结构。
本书第三版从第14~17章以较大的篇幅增写了第五部分， 从而加强算法分析方面的内容。这一部分首先介绍了求和、 递归关系分析和均摊分析等算法分析技术， 这些技术对于提高程序员的算法分析能力具有重要作用。然后讨论算法和状态空间下限的概念与实例， 并介绍了对抗性下限证明方法。本书系统地介绍了重要算法模式， 包括动态规划、 随机算法和变换， 并介绍了傅里叶变换等数值算法。最后讨论了计算复杂性理论中的难解问题， 利用归约把各种问题的难度联系起来。
本书的前言及第1~10章由张铭翻译， 第11~17章由刘晓丹翻译。另外， 肖之屏、 刘智冲、 方译萌、 王子琪、 王晟、 盛达魁、 刘金宝、 贺一骏、 桂欢等人也参加了本书的翻译工作， 在此对他们的辛勤劳动表示感谢。由于水平有限， 难免有不妥之处， 欢迎读者批评指正。
前    言
人们研究数据结构的目的， 是为了学会编写效率更高的程序。现在的计算机速度一年比一年快， 为什么还需要高效率的程序呢？这是由于人类解决问题的雄心与能力是同步增长的。现代计算技术在计算能力和存储容量上的革命， 仅仅提供了解决更复杂问题的有效工具， 而对程序高效率的要求永远也不会过时。
程序高效率的要求不会也不应该与合理的设计和简明清晰的编码相矛盾。高效率程序的设计基于良好的信息组织和优秀的算法， 而不是基于“编程小伎俩”。一名程序员如果没有掌握设计简明清晰程序的基本原理， 就不可能编写出有效的程序。反过来说， 对开发代价和可维护性的考虑不应该作为性能不高的借口。设计中的通用性（generality in design）应该在不牺牲性能的情况下达到， 但前提是设计人员知道如何去衡量性能， 并且把性能作为设计和实现不可分割的一部分。大多数计算机科学系的课程设置都意识到要培养良好的程序设计技能， 首先应该强调基本的软件工程原理。因此， 一旦程序员学会了设计和实现简明清晰程序的原理， 下一步就应该学习有效的数据组织和算法， 以提高程序的效率。
途径： 本书描述了许多表示数据的技术。这些技术包括以下原则： 
1. 每一种数据结构和每一个算法都有其时间、 空间的代价和效率。当面临一个新的设计问题时， 设计者要透彻地掌握权衡时间、 空间代价和算法有效性的方法， 以适应问题的需要。这就需要懂得算法分析原理， 而且还需要了解所使用的物理介质的特性(例如， 当数据存储在磁盘上与存储在主存中， 就有不同的考虑)。
2. 与代价和效率有关的是时空权衡。例如， 人们通常增加空间代价来减少运行时间， 或者反之。程序员所面对的时空权衡问题普遍存在于软件设计和实现的各个阶段， 因此这个概念必须牢记于心。
3. 程序员应该充分了解一些现成的方法， 以免做不必要的重复开发工作。因此， 学生们需要了解经常使用的数据结构和相关算法， 以及程序中常见的设计模式。
4. 数据结构服从于应用需求。学生们必须把分析应用需求放在第一位， 然后再寻找一个与实际应用相匹配的数据结构。要做到这一点， 需要应用上述三条原则。
笔者讲授数据结构多年， 发现设计在课程中起到了非常重要的作用。本教材的几个版本中逐步增加了设计模式和接口。本书第一版完全没有提到设计模式。第二版有一些篇幅讲解了几个设计模式的例子， 并且介绍了字典ADT和比较器类。编写本书第三版的基本数据结构和算法时， 都直接介绍了一些相关的设计模式。
教学建议： 数据结构和算法设计的书籍往往囿于下面这两种情形之一： 一种是教材， 一种是百科全书。有的书籍试图融合这两种编排， 但通常是二者都没有组织好。本书是作为教材来编写的。我相信， 了解如何选择或设计解决问题的高效数据结构的基本原理是十分重要的， 这比死记硬背书本内容要重要得多。因此， 我在本书中涵盖了大多数、 但不是全部的标准数据结构。为了阐述一些重要原理， 也包括了某些并非广泛使用的数据结构。另外， 还介绍了一些相对较新、 但即将得到广泛应用的数据结构。
在本科教学体系中， 本书适用于低年级（二年级或三年级）的高级数据结构课程或者高年级的算法课程。第三版中加入了很多新的素材。通常， 这本书被用来讲授一些超过常规一年级的CS2课程， 也可作为基础数据结构的介绍。读者应该已有两个学期的基本编程经验， 并具备一些C++基础技能。对已经熟悉部分内容的读者会有一些优势。数据结构的学生如果先学完离散数学课程， 也颇有益处。不过， 第2章还是给出了比较完整的数学预备知识， 这些知识对理解本书的内容还是很有必要的。读者如果在阅读中遇到不熟悉的知识， 可以回头看看相应的章节。
大二学生掌握的基本数据结构和算法分析的背景知识(相对于从传统CS2课程中获得的基础知识)并不太多， 可以对他们详细地讲解第1～11章的内容， 再从第13章选择一些专题来讲解， 我就是这样来给二年级学生讲课的。背景知识更丰富的学生， 可以先阅读第1章， 跳过第2章中除参考书目之外的内容， 简要地浏览第3章和第4章， 然后详细阅读第5~12章。另外， 教师可以根据程序设计实习的需要， 选择第13章以后的某些专题内容。高年级的算法课程可以着重讲解第11章和第14~17章。
第13章是针对大型程序设计练习而编写的。我建议所有选修数据结构的学生， 都应该做一些高级树结构或其他较复杂的动态数据结构的上机实习， 例如第12章中的跳跃表(skip list)或稀疏矩阵。所有这些数据结构都不会比二叉检索树更难， 而且学完第5章的学生都有能力来实现它们。
我尽量合理地安排章节顺序。教师可以根据需要自由地重新组织内容。读者掌握了第1~6章后， 后续章节的内容就相对独立了。显然， 外排序依赖于内排序和磁盘文件系统。Kruskal最小支撑树算法使用了6.2节关于并查（UNION/FIND）的算法。9.2节的自组织线性表提到了8.3节讨论的缓冲区置换技术。第14章的讨论基于本书的例题。17.2节依赖于图论知识。在一般情况下， 大多数主题都只依赖于同一章中讨论的内容。
 几乎每一章都是以“深入学习导读”一节结束的。它并不是这一章的综合参考索引， 而是为了通过这些导读书籍或文章提供给读者更广泛的信息和乐趣。在有些情况下我还提供了作为计算机科学家应该知道的重要背景文章。
关于C++： 本书中的所有示例程序都是用C++编写的， 但是我并不想难倒那些对C++不熟悉的读者。在努力保持C++优点的同时， 使示例程序尽量简明、 清晰。C++在本书中只是作为阐释数据结构的工具。此外， 特别用到了C++隐蔽实现细节的特性， 例如类（class）、 私有类成员（private class member）、 构造函数（constructor）、 析构函数（destructor）。这些特性支持了一个关键概念： 体现于抽象数据类型（abstract data type）中的逻辑设计与体现于数据结构中的物理实现的分离。
 为了使得本书清晰易懂， 我回避了某些C++的最重要特性。书中有意排除或尽量少使用一些特性， 而这些特性是经验丰富的C++程序员经常使用的， 例如类的层次（class hierarchy）、 继承（inheritance）和虚函数（virtual function）， 运算符和函数的重载（operator and function overloading）也很少使用。在很多情况下， 更倾向于使用C的原始语义， 而不是C++所提供的一些类似功能。
当然上述C++的特性在实际程序中是合理的程序设计基础， 但是它们只能掩盖而不是加强本书所阐述的原理。例如， 对于程序员来说， 类的继承在避免重复编码和降低程序错误率方面是一个很重要的工具； 但是从教学的标准观点来看， 类的继承在若干类中分散了单个逻辑单元的描述， 从而使程序更难理解。因此， 仅当类的继承对阐述文章的观点有明显作用时， 我才使用它（见5.3.1节）。避免代码重复和减少错误是很重要的目标， 请不要把本书中的示例程序直接复制到自己的程序中， 而只是把它们看成是对数据结构原理的阐释。
一个痛苦的选择是， 作者要决定在示例代码中是否使用模板（template）。在编写本书的第一版时， 我决定不使用模板， 因为考虑到它们的语义对于不熟悉C++语言的人来说掩盖了代码的含义。在随后的几年中， 使用C++的计算机科学课程急剧地增加了， 因此我假设现在的读者比以前的读者更熟悉模板的语义。因此本书在示例代码中大量使用了模板。
本书中的C++程序提供了有关数据结构原理的真实阐释， 是对文字阐述的补充。不宜脱离相关文字阐述而孤立地阅读或使用示例程序， 因为大量的背景信息包含在文字阐述中， 而不是包含在代码中。代码是对文字阐述的完善， 而不是相反的作用。这不是一系列具有商业质量的类的实现。如果读者想寻找一些标准的数据结构的完整实现， 或者要在你的代码中使用这些数据结构， 那么应该在Internet上寻找。
例如， 这些例子中所做的参数检查， 比起商业软件要少得多， 因为这种检查将降低算法的清晰度。某些参数检查和约束检查（例如是否从一个空容器中删除值）是以调用Assert的形式完成的。Assert的输入是一个布尔表达式， 一旦这个表达式的值为假（false）， 程序就立即终止。函数遇到一个坏参数就终止程序， 这在真实程序中通常是不必要的， 但有益于理解一个数据结构是怎样工作的。在实际的程序应用中， C++异常处理机制（exception handling features）用来处理一些输入数据错误。然而， Assert提供了一种机制， 既有益于阐明一个数据结构的工作条件， 也有利于采用真正的异常处理机制来代替。请参看附录中的Assert实现。
 在示例程序中， 我严格区分了“C++实现”和“伪码”（pseudocode）。一个标明“C++实现”的示例程序在一个以上的编译器中被真正编译过。伪码的示例通常具有与C++接近的语法， 但是一般包含一行以上更高级的描述。当我发现简单的、 尽管并不十分精确的描述具有更好的教学效果时， 就使用伪码。
习题和项目设计： 只靠读书是不能学会灵活使用数据结构的。一定要编写实际的程序， 比较不同的数据结构技术来观察在一种给定的条件下哪一种数据结构更有效。
数据结构课程最重要的教学安排之一， 就是学生应该在什么时候开始学习使用指针和动态存储分配， 从而编程实现链表和树这样的数据结构。这也是学生们学习递归的时机。在教学体系中， 这是学生学习重大设计（significant design）的第一门课， 因为通常需要使用真实数据结构来引出重大设计练习。最后， 基于内存和基于硬盘的数据访问的本质区别， 必须要在编程实践中才能理解。基于以上原因， 一门数据结构课程没有大量的编程环节是不能成功的。在计算机系， 数据结构是课程计划中最难的一门编程课程。
学生还需要在解决问题中锻炼分析能力。本书提供了450个习题和编程项目， 希望读者能够好好利用它们。
与作者联系的方法及相关资料的获取： 本书难免有一些错误， 有些方面还有待进一步研究。非常欢迎读者指正， 并提出建设性意见。作者在Internet上的E-mail地址是shaffer@vt.edu， 也可以给以下的地址写信： 
    Cliff Shaffer
    Department of Computer Science
    Virginia Tech
    Blacksburg, VA 24061
本书的电子版和上课中使用的一些幻灯片材料， 可以从以下网站获取： 

http://www.cs.vt.edu/~shaffer/book.html示例代码也可以从上面的网站得到。弗吉尼亚技术学院二年级数据结构课程网页的URL为

http://ei.cs.vt.edu/～cs3114致谢： 本书得到了许多友人的帮助。我想特别感谢其中的几位， 他们对本书的出版贡献最大。对于没有被提及的朋友， 在此表示歉意。
弗吉尼亚技术学院在1994年秋季的学术休假中使得整个出书的事情成为可能， 我是从那时开始着手准备的。在编写这本书的第二版时， 系主任Dennis Kafura和Jack Carroll对本书给予了重要的精神支持。Mike Keenan、 Lenny Heath和Jeff Shaffer对本书最初版本的内容提供了有价值的意见。尤其是Lenny Heath多年来一直与我深入地讨论算法设计和分析的有关问题， 以及怎样把二者讲授给学生的方法。十分感谢Steve Edwards花了很多时间帮助我几次重写了第二版、 第三版的C++代码和Java代码， 并与我讨论程序设计的原则。Layne Watson提供了有关Mathematica软件的帮助， Bo Begole、 Philip Isenhour、 Jeff Nielsen和Craig Struble提供了一些技术上的帮助。感谢Bill McQuain、  Mark Abrams和Dennis Kafura回答了一些有关C++和Java的问题。
对于许多评阅了本书手稿的朋友， 本人欠情甚深。这些评阅者是： J.David Bezek (Evansville大学)， Douglas Campbell(Brigham Young大学)， Karen Davis (Cincinnati大学)， Vijay Kumar Garg(Texas-Austin大学)， Jim Miller(Kansas大学)， Bruce Maxim(Michigan-Dearborn大学)， Jeff Parker(Agile Networks/Harvard)， Dana Richards(George Mason大学)， Jack Tan(Houston大学)和Lixin Tao(Concordia大学)。要不是他们的热心帮助， 本书会出现更多技术上的错误， 内容也将更加浅显。
关于这本第二版的出版， 我想感谢下列评阅者： Gurdip Singh(Kansas州立大学)， Peter Allen (Columbia大学)， Robin Hill (Wyoming大学)， Norman Jacobson (California-Irvine大学)， Ben Keller (弗吉尼亚技术学院)和Ken Bosworth (Idaho州立大学)。另外， 我要感谢Neil Stewart和Frank J.Thesen对改进本书提出的意见和建议。
第三版的评阅者包括Randall Lechlitner(Houstin大学,  Clear Lake)和Brian C. Hipp(York技术学院)。感谢他们的建议。
Prentice Hall是本书第一版和第二版的出版方。没有出版社众多朋友的帮助， 不可能有本书的出版， 因为作者不可能自己印出书来。因此， 几年来我要感谢Kate Hargett、 Petra Rector、 Laura Steele和Alan Apt这几位编辑。感谢本书第二版的责任编辑Irwin Zucker， 还有本书C++版的责任编辑Kathleen Caren和Java版的责任编辑Ed DeFelippis， 他们在本书接近出版的最忙乱的日子里， 保持各个方面运作良好。感谢Bill Zobrist和Bruce Gregory使我着手此事。感谢Prentice Hall的Truly Donovan、 Linda Behrens和Phyllis Bregman在本书出版过程中给予的帮助。感谢Tracy Dunkelberger在交回版权给我时提供的帮助。可能还有许多没有被提及的Prentice Hall出版社的朋友， 他们也默默地提供了帮助。
本人非常感谢Dover出版社的Shelley Kronzek在第三版的出版过程中付出的一切。第三版中有许多扩展， 包括Java和C++代码， 以及一些改正。我相信这是迄今为止最好的一版。但是不知道学生会不会希望有一本免费的在线教材， 还是低价的印刷版本。最终， 我相信两个版本会提供更多的选择。编辑James Miller和设计经理Marie Zaczkiewicz为确保本书的高质量出版付出了辛勤的工作。
我十分感激Hanan Samet传授给我有关数据结构的知识。我从他那里学到了许多原理与知识， 当然本书中可能出现的错误并不是他的责任。感谢我的妻子Terry对我的爱与支持， 还有两个女儿Irena和Kate带给我的欢乐， 可以让我从艰苦的工作中解脱出来。最后， 也是最重要的， 感谢这些年来选修数据结构的学生， 是他们使我知道了在数据结构课程中什么是重要的而什么应该忽略， 许多深入的问题也是他们提供的。这本书献给他们。