国外计算机科学教材系列：数据结构与算法分析（C++版）（第3版）

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

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

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 递归
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 实用函数
参考文献
词汇表

人们研究数据结构的目的， 是为了学会编写效率更高的程序。现在的计算机速度一年比一年快， 为什么还需要高效率的程序呢？这是由于人类解决问题的雄心与能力是同步增长的。现代计算技术在计算能力和存储容量上的革命， 仅仅提供了解决更复杂问题的有效工具， 而对程序高效率的要求永远也不会过时。
程序高效率的要求不会也不应该与合理的设计和简明清晰的编码相矛盾。高效率程序的设计基于良好的信息组织和优秀的算法， 而不是基于“编程小伎俩”。一名程序员如果没有掌握设计简明清晰程序的基本原理， 就不可能编写出有效的程序。反过来说， 对开发代价和可维护性的考虑不应该作为性能不高的借口。设计中的通用性（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++的最重要特性。