数据结构与算法分析(C++版)第二版
基本信息
- 原书名： Practice Introduction to Data Structures and Algorithm Analysis (C++ Edition) (2nd Edition)
- 原出版社： Prentice Hall
- 作者： 美 Clifford A. Shaffer
- 译者： 张铭译等
- 丛书名： 国外计算机科学教材系列
- 出版社：电子工业出版社
- ISBN：7505376462
- 上架时间：2002-7-4
- 出版日期：2002 年6月
- 页码：327
- 版次：1-1
- 所属分类：
计算机 > 计算机科学理论与基础知识 > 数据结构
教材 > 征订教材 > 高等理工
内容简介回到顶部↑
本书采用程序员最爱用的面向对象C++语言来描述数据结构和算法，并把数据结构原理和算法分析技术有机地结合在一起，系统介绍了各种类型的数据结构和排序、检索的各种方法。作者非常注意对每一种数据结构不同存储方法及有关算法进行分析比较。书中还引入了一些比较高级的数据结构与先进的算法分析技术，并介绍了可计算性理论的一般知识。本版的重要改进在于引入了参数化的模板，从而提高了算法中数据类型的通用性，支持高效的代码重用。本书概念清楚、逻辑性强、内容新颖，可作为大专院校计算机软件专业与计算机应用专业学生的教材和参考书，也可供计算机工程技术人员参考。
目录回到顶部↑
第一部分 预备知识
第1章 数据结构和算法
1.1 数据结构的原则
1.1.1 学习数据结构的必要性
1.1.2 代价与效益
1.2 抽象数据类型和数据结构
1.3 问题、算法和程序
1.4 深入学习导读
1.5 习题
第2章 数学预备知识
2.1 集合和关系
2.2 常用数学术语
2.3 对数
2.4 递归
2.5 级数求和与递归
2.6 数学证明方法
2.6.1 反证法
2.6.2 数学归纳法
2.7 评估
2.8 深入学习导读
第1章 数据结构和算法
1.1 数据结构的原则
1.1.1 学习数据结构的必要性
1.1.2 代价与效益
1.2 抽象数据类型和数据结构
1.3 问题、算法和程序
1.4 深入学习导读
1.5 习题
第2章 数学预备知识
2.1 集合和关系
2.2 常用数学术语
2.3 对数
2.4 递归
2.5 级数求和与递归
2.6 数学证明方法
2.6.1 反证法
2.6.2 数学归纳法
2.7 评估
2.8 深入学习导读
译者序回到顶部↑
数据结构与算法分析是一门计算机专业十分重要的基础课，计算机科学各领域及各种应用软件都要使用相关的数据结构和算法。当面临一个新的设计问题时，设计者需要选择适当的数据结构，并设计出满足一定时间和空间限制的有效算法。本书作者把数据结构和算法分析有机地揉合在一本教材中，有助于读者根据问题的性质选择合理的数据结构，并对时间空间复杂性进行必要的控制。
本书采用当前流行的面向对象的C++语言来描述数据结构和算法，因为C++语言是程序员最广泛使用的语言。因此，程序员可以把本书中的许多算法直接应用于将来的实际项目中。尽管数据结构和算法在设计本质上还是很底层的东西，并不像软件工程大型项目设计那样，对面向对象方法具有直接的依赖性，因此有人会认为并不需要采用面向对象的高级技术来描述底层的算法，但是采用C++语言能够更好地体现抽象数据类型的概念，从而更本质地描述数据结构和算法。为了使本书清晰易懂，作者有意回避了C++的某些重要特性。这个版本的重要改进是引入了参数化的模板，从而提高了算法中数据类型的通用性，支持高效的代码重用。本书包括四大部分内容，第一部分是准备工作，介绍了一些基本概念和术语，以及基本的数学知识。 第二部分介绍了最基本的数据结构，依次为线性表(包括栈和队列)、二叉树和树。对每种数据结构的讲解都从其数学特性入手，先介绍抽象数据类型，然后再讨论不同的存储方法，并且研究不同存储方法的可能算法。值得赞赏的是，作者结合算法分析来讨论各种存储方法和算法的利弊，摒弃那些不适宜的方法，这样就调动了读者思维，使其可从中学到考虑问题的方法。这种“授人以渔”的策略使读者在今后设计和应用数据结构时能够全面地考虑各种因素，并选择最佳方案。
作为最常用的算法，排序和检索历来是数据结构讨论的重点问题。这在第三部分的第9章和第10章中进行了详尽的讨论。排序算法最能体现算法分析的魅力，它的算法速度要求非常高： 其中内排序主要考虑的是怎样减少关键码之间的比较次数和记录交换次数，以提高排序速度；而外排序则考虑外存的特性，尽量减少访问操作，以提高排序速度。第8章证明了所有基于比较的排序算法的时间代价是Θ(nlogn)，这也是排序问题的时间代价。检索则考虑怎样提高检索速度，这往往与存储方法有关。书中介绍了几种高效的数据结构，如自组织线性表、散列表、B树和B+树等，都具有极好的检索性能。第四部分介绍了数据结构的应用与一些高级主题，其中包括图、跳跃表、广义表和稀疏矩阵等更复杂的线性表结构、还包括Trie结构、AVL树等复杂树结构，以及kd树、PR四分树等空间数据结构。另外，第四部分还简单介绍了求和、递归关系分析和均摊分析等高级算法分析技术，这些技术对于提高程序员的算法分析能力具有重要作用。
本书的前言及第1章至第7章由张铭翻译，第8章至第15章由刘晓丹翻译。另外，肖毅、柴雯、肖之屏、刘NFB35、赵培翔、李丽、王蜀安、张海东、刘振飞和李健等人也参加了本书的翻译工作，在此对他们的辛勤劳动表示感谢。由于水平有限，难免有不妥之处，欢迎批评指正。
本书采用当前流行的面向对象的C++语言来描述数据结构和算法，因为C++语言是程序员最广泛使用的语言。因此，程序员可以把本书中的许多算法直接应用于将来的实际项目中。尽管数据结构和算法在设计本质上还是很底层的东西，并不像软件工程大型项目设计那样，对面向对象方法具有直接的依赖性，因此有人会认为并不需要采用面向对象的高级技术来描述底层的算法，但是采用C++语言能够更好地体现抽象数据类型的概念，从而更本质地描述数据结构和算法。为了使本书清晰易懂，作者有意回避了C++的某些重要特性。这个版本的重要改进是引入了参数化的模板，从而提高了算法中数据类型的通用性，支持高效的代码重用。本书包括四大部分内容，第一部分是准备工作，介绍了一些基本概念和术语，以及基本的数学知识。 第二部分介绍了最基本的数据结构，依次为线性表(包括栈和队列)、二叉树和树。对每种数据结构的讲解都从其数学特性入手，先介绍抽象数据类型，然后再讨论不同的存储方法，并且研究不同存储方法的可能算法。值得赞赏的是，作者结合算法分析来讨论各种存储方法和算法的利弊，摒弃那些不适宜的方法，这样就调动了读者思维，使其可从中学到考虑问题的方法。这种“授人以渔”的策略使读者在今后设计和应用数据结构时能够全面地考虑各种因素，并选择最佳方案。
作为最常用的算法，排序和检索历来是数据结构讨论的重点问题。这在第三部分的第9章和第10章中进行了详尽的讨论。排序算法最能体现算法分析的魅力，它的算法速度要求非常高： 其中内排序主要考虑的是怎样减少关键码之间的比较次数和记录交换次数，以提高排序速度；而外排序则考虑外存的特性，尽量减少访问操作，以提高排序速度。第8章证明了所有基于比较的排序算法的时间代价是Θ(nlogn)，这也是排序问题的时间代价。检索则考虑怎样提高检索速度，这往往与存储方法有关。书中介绍了几种高效的数据结构，如自组织线性表、散列表、B树和B+树等，都具有极好的检索性能。第四部分介绍了数据结构的应用与一些高级主题，其中包括图、跳跃表、广义表和稀疏矩阵等更复杂的线性表结构、还包括Trie结构、AVL树等复杂树结构，以及kd树、PR四分树等空间数据结构。另外，第四部分还简单介绍了求和、递归关系分析和均摊分析等高级算法分析技术，这些技术对于提高程序员的算法分析能力具有重要作用。
本书的前言及第1章至第7章由张铭翻译，第8章至第15章由刘晓丹翻译。另外，肖毅、柴雯、肖之屏、刘NFB35、赵培翔、李丽、王蜀安、张海东、刘振飞和李健等人也参加了本书的翻译工作，在此对他们的辛勤劳动表示感谢。由于水平有限，难免有不妥之处，欢迎批评指正。
前言回到顶部↑
我们研究数据结构的目的是为了学会编写更高效的程序。既然现在的计算机速度一年比一年快，为什么还会需要高效率的程序呢？这是由于人类解决问题的雄心与能力是同步增长的。现代计算技术在计算能力和存储容量上的革命，仅仅提供了计算更复杂问题的有效工具，而程序的高效性要求永远也不会过时。
程序高效性的要求不会，也不应该与合理的设计和简明清晰的编码相矛盾。高效程序的设计基于良好的信息组织和优秀的算法，而不是基于“编程小伎俩”。如果一个程序员没有掌握程序设计简明清晰的基本原理，就不可能编写出有效的程序。反过来讲，简洁的程序需要合理的数据组织和清晰的算法。大多数计算机科学系的课程设置都已意识到，要培养良好的程序设计技能，首先应该强调基本的软件工程原理。因此，一旦程序员学会了程序设计和实现简明清晰的原理，下一步就应该学习有效的数据组织和算法，以提高程序的效率。
途径
本书描述了许多用于表示数据的技术。这些技术体现在以下的原则中：
1. 〖ZK(＃〗每一种数据结构和每一个算法都有其时间、空间的代价和效率。当面临一个新的设计问题时，设计者要透彻地掌握权衡时间、空间代价和算法有效性的方法，以适应问题的需要。这就要懂得算法分析的原理，而且还需要了解所使用的物理介质的特性(例如，数据存储在磁盘上与存储在主存中时，就有不同的考虑)。
2. 与代价和效率有关的是时空权衡。例如，人们通常增加空间代价来减少运行时间，反之亦然。程序员所面对的时空权衡问题普遍存在于软件设计和实现的各个阶段，因此必须把这个概念牢记在心。
3. 程序员应该充分了解一些现成的方法，以免进行不必要的重复开发工作。因此，学生们需要了解经常使用的数据结构和相关算法。
4. 数据结构服从于应用需求。学生们必须把分析应用需求放在第一位，然后再寻找一种与实际应用相匹配的数据结构。要做到这一点，需要应用上述三条原则。〖ZK)〗
教学建议
数据结构和算法设计的书籍往往囿于下面两种情形之一〖BFQ〗：〖BF〗一种是教材，一种是百科全书。有些书籍试图融合这两种编排，但通常是二者都没有组织好，而本书是作为教材来编写的。我相信了解那些用于选择或设计可解决问题的数据结构的基本原理十分重要，会比死记硬背书本内容重要得多。因此，本书中涵盖了大多数(但不是所有的)标准数据结构。为了阐述一些重要原理，也包括了某些并非广泛使用的数据结构。另外，本书中还介绍了一些相对较新但即将得到广泛应用的数据结构。
本书可作为本科生一个学期的教学内容，也可作为专业技术人员的自学教材。读者应该具备编程经验，最好学过相当于两个学期的结构化程序设计语言(如Pascal或C语言)，并且最好懂得一些C+ +的基本知识。早已熟悉递归的读者具有一定的优势。先修完一门好的离散数学课程对于数据结构的学习也大有裨益。第2章中给出了一些理解本书所必备的数学预备知识。读者遇到不熟悉的数学问题时，可以查阅这一章中的相关内容。
尽管本书应该一个学期完成，但书中超过了一个学期的内容，这样就可以为教师提供一些选择的余地。二年级学生的基本数据结构和算法分析背景不太多，可以给他们详细地讲解第1～12章的内容，再从第13章中选择一些专题来讲解，我就是这样来给二年级学生讲课的。背景知识更丰富的学生，可以先读第1章，跳过第2章中除“深入学习导读”之外的内容，简要地浏览第3章和第4章(请着重阅读4.1.3小节和4.2小节)，然后详细阅读其余的章节。另外，教师可以根据程序设计实习的需要，选择第13章中的某些专题内容。第13章是针对进行较大的程序设计练习而编写的。我建议所有选修数据结构的学生，都应该做一些高级树结构或其他较复杂的动态数据结构的上机实习，如第12章中的跳跃表或稀疏矩阵。所有这些数据结构都没有二叉检索树难，学完第5章的学生都有能力来实现它们。本书尽量合理地安排内容顺序。教师可以根据需要自由地重新组织内容。读者掌握了第1至第6章后，以下的内容就相对独立了。显然，外排序依赖于内排序和磁盘文件系统。Kruskal最小支撑树算法使用了6.2小节关于UNION/FIND的算法。9.2小节的自组织线性表谈到了8.3小节讨论的缓冲区置换技术。第14章的讨论基于本书的例题。15.2小节依赖于图论知识。一般情况下，大多数主题都只依赖于同一章中讨论过的内容。
关于C++
本书中所有示例程序都是用C++来编写的，但也并不想难倒那些对C++不熟悉的读者。在努力保持C++优点的同时，我尽量使示例程序简明、清晰。C++在本书中只是作为阐释数据结构的工具，而且实际上只用了C++的一个小子集。特别是书中用到了C++隐蔽实现细节的特性，如类(class)、私有成员(private class member)、构造函数(constructor)、析构函数(destructor)。这些特性支持着一个关键的概念，即体现于抽象数据类型(abstract data type)中的逻辑设计与体现于数据结构中的物理实现的分离。
为了使本书清晰易懂，我完全回避了C++的某些重要特性，并有意排除或尽量少用一些经验丰富的C++程序员常用的特性，如类的层次(class hierarchy)、继承(inheritance)和虚函数(virtual function)。运算符和函数的重载(overloading) 也很少使用。C的原始语义比C++所提供的一些类似功能要好一些。
当然，上述C++的特性在实际程序中是合理的设计基础，但是它们只能掩盖而并没有加强本书中所阐述的原理。例如，类的继承在避免重复编码和降低程序错误率方面很重要，但是从教育学的标准观点来看，类的继承在若干类中分散了数据元素的描述，从而使得程序更难理解。因此，在本书中，当类的继承对阐述观点有明显作用时才使用继承来定义类(例如第531小节)。但这并不意味着程序员都应该遵从类似的原则，避免代码重复和减少错误是很重要的目标，不要把本书中的示例程序直接复制到你自己的程序中，只把它们看做是对数据结构原理的阐释即可。我需要做出的最痛苦的选择是：在示例代码中是否使用模板(template)。写本书的第一版时，我决定不使用模板，这是因为考虑到它们的语义对于不熟悉C++语言的人来说掩盖了代码的含义。在随后的几年中，使用C+ +的计算机科学课程急剧地增加，我和编辑都感到现在的读者比从前的读者更熟悉模板的语义，因此本书在示例代码中大量地使用了模板。本书中的程序提供了有关数据结构原理的真实阐释，而不是完整实现了用于商用软件的标准数据结构。本书中的示例代码是为了清晰地阐述数据结构是怎样运作的，是对文字阐述的补充。不宜脱离相关的文字阐述而孤立地阅读或使用示例程序，因为大量的背景信息包含在文字阐述中，而不是在代码中。代码是对文字阐述的完善，反之则不然。这些例子中进行的参数检查，比起从事商业软件设计的程序员在编程中进行的参数检查要少得多。某些参数检查是以调用Assert的形式完成的，这是C库函数assert的改进函数。assert的输入是一个布尔表达式，一旦这个表达式的值为假 (false)，程序就立即终止。在实际程序中通常认为这种功能是不必要的，但是该功能对于理解一个数据结构怎样运作十分有用。
在示例程序中，我严格区分了“C++实现”和“伪码”。
标明“C++实现”的示例程序已在一个以上的编译器中真正编译过。“伪码”的示例通常具有与C++ G3〗+接近的语法，但是典型地包含一行以上的更高级描述。当我发现尽管并不十分精确但很简单的描述具有更好的教学效果时，就使用伪码。
几乎每一章都是以“深入学习导读”一节来结束的，这些小节并不是所在那一章的综合参考索引，而是为了通过这些导读书籍或文章给读者提供更广泛的信息和乐趣。有些情况下我也提供了某个知名计算机科学家的重要背景文章。
习题和项目设计
程序高效性的要求不会，也不应该与合理的设计和简明清晰的编码相矛盾。高效程序的设计基于良好的信息组织和优秀的算法，而不是基于“编程小伎俩”。如果一个程序员没有掌握程序设计简明清晰的基本原理，就不可能编写出有效的程序。反过来讲，简洁的程序需要合理的数据组织和清晰的算法。大多数计算机科学系的课程设置都已意识到，要培养良好的程序设计技能，首先应该强调基本的软件工程原理。因此，一旦程序员学会了程序设计和实现简明清晰的原理，下一步就应该学习有效的数据组织和算法，以提高程序的效率。
途径
本书描述了许多用于表示数据的技术。这些技术体现在以下的原则中：
1. 〖ZK(＃〗每一种数据结构和每一个算法都有其时间、空间的代价和效率。当面临一个新的设计问题时，设计者要透彻地掌握权衡时间、空间代价和算法有效性的方法，以适应问题的需要。这就要懂得算法分析的原理，而且还需要了解所使用的物理介质的特性(例如，数据存储在磁盘上与存储在主存中时，就有不同的考虑)。
2. 与代价和效率有关的是时空权衡。例如，人们通常增加空间代价来减少运行时间，反之亦然。程序员所面对的时空权衡问题普遍存在于软件设计和实现的各个阶段，因此必须把这个概念牢记在心。
3. 程序员应该充分了解一些现成的方法，以免进行不必要的重复开发工作。因此，学生们需要了解经常使用的数据结构和相关算法。
4. 数据结构服从于应用需求。学生们必须把分析应用需求放在第一位，然后再寻找一种与实际应用相匹配的数据结构。要做到这一点，需要应用上述三条原则。〖ZK)〗
教学建议
数据结构和算法设计的书籍往往囿于下面两种情形之一〖BFQ〗：〖BF〗一种是教材，一种是百科全书。有些书籍试图融合这两种编排，但通常是二者都没有组织好，而本书是作为教材来编写的。我相信了解那些用于选择或设计可解决问题的数据结构的基本原理十分重要，会比死记硬背书本内容重要得多。因此，本书中涵盖了大多数(但不是所有的)标准数据结构。为了阐述一些重要原理，也包括了某些并非广泛使用的数据结构。另外，本书中还介绍了一些相对较新但即将得到广泛应用的数据结构。
本书可作为本科生一个学期的教学内容，也可作为专业技术人员的自学教材。读者应该具备编程经验，最好学过相当于两个学期的结构化程序设计语言(如Pascal或C语言)，并且最好懂得一些C+ +的基本知识。早已熟悉递归的读者具有一定的优势。先修完一门好的离散数学课程对于数据结构的学习也大有裨益。第2章中给出了一些理解本书所必备的数学预备知识。读者遇到不熟悉的数学问题时，可以查阅这一章中的相关内容。
尽管本书应该一个学期完成，但书中超过了一个学期的内容，这样就可以为教师提供一些选择的余地。二年级学生的基本数据结构和算法分析背景不太多，可以给他们详细地讲解第1～12章的内容，再从第13章中选择一些专题来讲解，我就是这样来给二年级学生讲课的。背景知识更丰富的学生，可以先读第1章，跳过第2章中除“深入学习导读”之外的内容，简要地浏览第3章和第4章(请着重阅读4.1.3小节和4.2小节)，然后详细阅读其余的章节。另外，教师可以根据程序设计实习的需要，选择第13章中的某些专题内容。第13章是针对进行较大的程序设计练习而编写的。我建议所有选修数据结构的学生，都应该做一些高级树结构或其他较复杂的动态数据结构的上机实习，如第12章中的跳跃表或稀疏矩阵。所有这些数据结构都没有二叉检索树难，学完第5章的学生都有能力来实现它们。本书尽量合理地安排内容顺序。教师可以根据需要自由地重新组织内容。读者掌握了第1至第6章后，以下的内容就相对独立了。显然，外排序依赖于内排序和磁盘文件系统。Kruskal最小支撑树算法使用了6.2小节关于UNION/FIND的算法。9.2小节的自组织线性表谈到了8.3小节讨论的缓冲区置换技术。第14章的讨论基于本书的例题。15.2小节依赖于图论知识。一般情况下，大多数主题都只依赖于同一章中讨论过的内容。
关于C++
本书中所有示例程序都是用C++来编写的，但也并不想难倒那些对C++不熟悉的读者。在努力保持C++优点的同时，我尽量使示例程序简明、清晰。C++在本书中只是作为阐释数据结构的工具，而且实际上只用了C++的一个小子集。特别是书中用到了C++隐蔽实现细节的特性，如类(class)、私有成员(private class member)、构造函数(constructor)、析构函数(destructor)。这些特性支持着一个关键的概念，即体现于抽象数据类型(abstract data type)中的逻辑设计与体现于数据结构中的物理实现的分离。
为了使本书清晰易懂，我完全回避了C++的某些重要特性，并有意排除或尽量少用一些经验丰富的C++程序员常用的特性，如类的层次(class hierarchy)、继承(inheritance)和虚函数(virtual function)。运算符和函数的重载(overloading) 也很少使用。C的原始语义比C++所提供的一些类似功能要好一些。
当然，上述C++的特性在实际程序中是合理的设计基础，但是它们只能掩盖而并没有加强本书中所阐述的原理。例如，类的继承在避免重复编码和降低程序错误率方面很重要，但是从教育学的标准观点来看，类的继承在若干类中分散了数据元素的描述，从而使得程序更难理解。因此，在本书中，当类的继承对阐述观点有明显作用时才使用继承来定义类(例如第531小节)。但这并不意味着程序员都应该遵从类似的原则，避免代码重复和减少错误是很重要的目标，不要把本书中的示例程序直接复制到你自己的程序中，只把它们看做是对数据结构原理的阐释即可。我需要做出的最痛苦的选择是：在示例代码中是否使用模板(template)。写本书的第一版时，我决定不使用模板，这是因为考虑到它们的语义对于不熟悉C++语言的人来说掩盖了代码的含义。在随后的几年中，使用C+ +的计算机科学课程急剧地增加，我和编辑都感到现在的读者比从前的读者更熟悉模板的语义，因此本书在示例代码中大量地使用了模板。本书中的程序提供了有关数据结构原理的真实阐释，而不是完整实现了用于商用软件的标准数据结构。本书中的示例代码是为了清晰地阐述数据结构是怎样运作的，是对文字阐述的补充。不宜脱离相关的文字阐述而孤立地阅读或使用示例程序，因为大量的背景信息包含在文字阐述中，而不是在代码中。代码是对文字阐述的完善，反之则不然。这些例子中进行的参数检查，比起从事商业软件设计的程序员在编程中进行的参数检查要少得多。某些参数检查是以调用Assert的形式完成的，这是C库函数assert的改进函数。assert的输入是一个布尔表达式，一旦这个表达式的值为假 (false)，程序就立即终止。在实际程序中通常认为这种功能是不必要的，但是该功能对于理解一个数据结构怎样运作十分有用。
在示例程序中，我严格区分了“C++实现”和“伪码”。
标明“C++实现”的示例程序已在一个以上的编译器中真正编译过。“伪码”的示例通常具有与C++ G3〗+接近的语法，但是典型地包含一行以上的更高级描述。当我发现尽管并不十分精确但很简单的描述具有更好的教学效果时，就使用伪码。
几乎每一章都是以“深入学习导读”一节来结束的，这些小节并不是所在那一章的综合参考索引，而是为了通过这些导读书籍或文章给读者提供更广泛的信息和乐趣。有些情况下我也提供了某个知名计算机科学家的重要背景文章。
习题和项目设计
加载中...
