本书采用程序员最广泛采用的面向对象C++语言来描述数据结构和算法,并把数据结构原理和算法分析技术有机地结合在一起,系统介绍了各种类型的数据结构及排序、检索的各种方法。作者非常注意对每一种数据结构的不同存储方法及有关算法进行分析比较。书中还引入了一些比较高级的数据结构与先进的算法分析技术,并介绍了可计算性理论的一般知识。书中分别给出了C++实现方法和伪码实现方法,便于读者根据情况选择。本书作者维护的网站上可下载相关代码、编程项目和辅助练习资料。

本书概念清楚，逻辑性强，内容新颖：? 本书作者是国际上数据结构和算法分析领域的权威，他出版的有关C、C++、Java等语言的数据结构的各个版本教材均已由各家出版社引进国内，得到了广大读者的认可。? 本书是作者多年教学实践经验的积淀，配套资源很丰富。作者维护的网站上可下载相关代码、编程项目和辅助练习资料。 ? 本书描述了许多表示数据的技术，并将数据结构和算法分析有机地结合在一本教材中， 有助于读者根据问题的性质选择合理的数据结构， 并对算法的时间、 空间复杂性进行必要的控制。? 本书采用当前流行的面向对象的C++程序设计语言来描述数据结构和算法，作者加强了面向对象的讨论， 特别是增加了设计模式的相关内容。

及第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带给我的欢乐， 可以让我从艰苦的工作中解脱出来。最后， 也是最重要的， 感谢这些年来选修数据结构的学生， 是他们使我知道了在数据结构课程中什么是重要的而什么应该忽略， 许多深入的问题也是他们提供的。这本书献给他们。

Cliff A.Shaffer在美国马里兰大学获得学士、硕士和博士学位，现在在Virginia Polytechnic理工学院计算机科学系担任教授，主要讲授问题求解、数据结构与算法分析、算法理论等课程，积累了丰富的教学经验，并出版了多部著作。

目 录
第一部分 预 备 知 识
第1章 数据结构和算法
1.1 数据结构的原则
1.2 抽象数据类型和数据结构
1.3 设计模式
1.4 问题、 算法和程序
1.5 深入学习导读
1.6 习题
第2章 数学预备知识
2.1 集合和关系
2.2 常用数学术语
2.3 对数
2.4 级数求和与递归
2.5 递归 目 录
第一部分 预 备 知 识
第1章 数据结构和算法
1.1 数据结构的原则
1.2 抽象数据类型和数据结构
1.3 设计模式
1.4 问题、 算法和程序
1.5 深入学习导读
1.6 习题
第2章 数学预备知识
2.1 集合和关系
2.2 常用数学术语
2.3 对数
2.4 级数求和与递归
2.5 递归
2.6 数学证明方法
2.7 估计
2.8 深入学习导读
2.9 习题
第3章 算法分析
3.1 概述
3.2 最佳、 最差和平均情况
3.3 换一台更快的计算机， 还是换一种更快的算法
3.4 渐近分析
3.5 程序运行时间的计算
3.6 问题的分析
3.7 容易混淆的概念
3.8 多参数问题
3.9 空间代价
3.10加速你的程序
3.11实证分析
3.12深入学习导读
3.13习题
3.14项目设计
第二部分 基本数据结构
第4章 线性表、 栈和队列
4.1 线性表
4.2 栈
4.3 队列
4.4 字典
4.5 深入学习导读
4.6 习题
4.7 项目设计
第5章 二叉树
5.1 定义及主要特性
5.2 遍历二叉树
5.3 二叉树的实现
5.4 二叉检索树
5.5 堆与优先队列
5.6 Huffman编码树
5.7 深入学习导读
5.8 习题
5.9 项目设计
第6章 树
6.1 树的定义与术语
6.2 父指针表示法
6.3 树的实现
6.4 K叉树
6.5 树的顺序表示法
6.6 深入学习导读
6.7 习题
6.8 项目设计
第三部分 排序与检索
第7章 内排序
7.1 排序术语及记号
7.2 三种代价为Θ(n2)的排序算法
7.3 Shell排序
7.4 归并排序
7.5 快速排序
7.6 堆排序
7.7 分配排序和基数排序
7.8 对各种排序算法的实验比较
7.9 排序问题的下限
7.10深入学习导读
7.11习题
7.12项目设计
第8章 文件管理和外排序
8.1 主存储器和辅助存储器
8.2 磁盘
8.3 缓冲区和缓冲池
8.4 程序员的文件视图
8.5 外排序
8.6 深入学习导读
8.7 习题
8.8 项目设计
第9章 检索
9.1 检索未排序和已排序的数组
9.2 自组织线性表
9.3 集合检索
9.4 散列方法
9.5 深入学习导读
9.6 习题
9.7 项目设计
第10章 索引技术
10.1 线性索引
10.2 ISAM
10.3 基于树的索引
10.4 2-3树
10.5 B树
10.6 深入学习导读
10.7 习题
10.8 项目设计
第四部分 高级数据结构
第11章 图
11.1 术语和表示法
11.2 图的实现
11.3 图的遍历
11.4 最短路径问题
11.5 最小支撑树
11.6 深入学习导读
11.7 习题
11.8 项目设计
第12章 线性表和数组高级技术
12.1 广义表
12.2 矩阵的表示方法
12.3 存储管理
12.4 深入学习导读
12.5 习题
12.6 项目设计
第13章 高级树结构
13.1 Trie结构
13.2 平衡树
13.3 空间数据结构
13.4 深入学习导读
13.5 习题
13.6 项目设计
第五部分 算 法 理 论
第14章 分析技术
14.1 求和技术
14.2 递归关系
14.3 均摊分析
14.4 深入学习导读
14.5 习题
14.6 项目设计
第15章 下限
15.1 下限证明介绍
15.2 线性表检索的下限
15.3 查找最大值
15.4 对抗性下限证明
15.5 状态空间下限证明
15.6 找到第i大元素
15.7 优化排序
15.8 深入学习导读
15.9 习题
15.10 项目设计
第16章 算法模式
16.1 动态规划
16.2 随机算法
16.3 数值算法
16.4 深入学习导读
16.5 习题
16.6 项目设计
第17章 计算的限制
17.1 归约
17.2 难解问题
17.3 不可解问题
17.4 深入学习导读
17.5 习题
17.6 项目设计
第六部分 附 录
附录A 实用函数
参考文献
词汇表