本书从抽象思想、问题解决以及C编程语言使用的观点介绍了数据结构和算法。本书中包含了C的最新特性，任何地方都可以完全使用标准模板库（STL）。C允许程序员分开编写接口和实现，将它们保存在单独编译的文件中，并隐藏实现的具体细节。本书深入了一层：数据结构的接口和实现在本书的不同部分讨论。第一部分（对象和C）、第二部分（算法和构建块）、第三部分（应用程序）打基础，专门讨论各种基本概念并提供实践中的一些例子。第四部分（实现）介绍数据结构的实现。接口与实现的这种分离促进了抽象思想。将类接口放在实现之前编写与使用，这就迫使读者去思考各种数据结构的功能性和潜能（例如，在实现优先队列之前就使用它了）。特色：加入了C最新的发展，包含一个有关模型的新章节，并且从头到尾都使用了vector类。包含在恰当时使用了STL的修订材料。介绍高级使用C较重要的细节的同时，介绍了类和继承（这两者简化了最初的表示法）的一些新内容。阐述了数据结构的STL接口，并提供了STL实现，同时也提供了不使用STL的简化过的接口，这使得理解数据结构的基础知识更加简单，没有了STL的复杂性。包含大量的代码。这些都已被全面重写并测试过，可兼容当前各种各样的编译器。本书前言序言本书是为计算机科学专业的第2学期的课程而编写的，从典型的《数据结构》（CS-2，即计算机科学专业第2学期）开始直到高级的数据结构和算法分析。CS-2课程的内容经历过一段时间的演变。尽管多数人都同意这样的主题安排，但在具体的细节上还是有较大的分歧。获得一致认可的主题是软件开发的原则，最突出的是封装和信息隐藏的概念。理论上，所有的CS-2课程都倾向于包含运行时分析、递归、基本的排序方法和初等数据结构。许多大学还开设了高级课程，主题涉及到高级的数据结构、算法、运行时分析。本书中的材料设计同时考虑到这两种级别，因此读者不必再另外购买其他教科书。尽管如此，争论最激烈的还是CS-2中编程语言的选择以及其他几项必要的基本选择，包括：是否这么早就介绍面向对象的设计或基于对象的设计。对数学水平的要求。在实现数据结构及其使用之间达到恰当的平衡点，以及与所选语言相关的编程细节。笔者写本书的目的是，从抽象思维和问题求解的角度来介绍数据结构和算法。笔者试图覆盖所有与数据结构、分析及其C实现有关的重要内容，同时对那些理论上似乎很有意义但实际上很少使用的数据结构，则是避而远之。几乎不可能有哪本书能像本书一样在一门课程里讲述所有不同的数据结构，包括数据结构的使用。因此，笔者设计了本教材，以便让教师能够灵活地选择主题。教师需要在实践和理论之间寻求平衡，然后选择最适合课程需要的主题。正如此序言后面所讨论的那样，笔者对课本进行了细致的组织，尽可能地降低了各章之间的依赖性。统一的方法笔者的基本假设是基于任何语言的软件开发工具都有一个庞大的库，许多数据结构就是这些库的一部分。笔者预感到数据结构教学的重心将从实现转向使用。在本书中，笔者采用了一套独特的方法，将数据结构分成规范和实现，并充分利用已有的数据结构库，即标准模板库（StandardTemplateLibrary，STL）。在第二部分将会有一章（第7章）单独讲述适合大多数应用程序的STL子集。第二部分还讲述了基本的分析技术、递归和排序。第三部分介绍使用STL数据结构的应用程序。直到第四部分已经使用数据结构之后，才开始介绍STL的实现。因为STL是C的一部分（较早的编译器则使用本教材中的STL代码，请参阅稍后的"代码可用性"部分），学生可以使用现有的软件组件来设计大型项目。尽管本书中大量使用了STL，但本书并非针对STL的专著，也不是专门讲述STL实现的入门读物。本书的重点在于数据结构和基本的问题求解技术。当然，数据结构设计中使用的技术大都适用于STL的实现，因此在第四部分有几章介绍了STL的实现。然而，教师可以选择第四部分中较简单的实现，而不必讨论STL协议。第7章介绍了STL，这对理解第三部分的代码很有必要。笔者只是使用了一些基本的STL。许多教师更喜欢定义、实现，然后使用每个数据结构的传统方法。由于第三部分和第四部分中的材料之间并不存在依赖关系，因此可以利用本书轻松地教授传统方法。预备技能阅读本书的学生应该了解一门面向对象或面向过程的编程语言。必须了解编程语言的基本特征，包括基元数据类型、运算符、控制结构、函数（方法）、输入和输出（但并不需要了解数组和类）。已初步接触过C或Java的学生可能会觉得前两章的某些内容很简单。但其他部分所讲的C技术细节则相对比较深奥，在入门课程中可能不会讲到这些知识。学习了其他语言课程的学生应该从第1章开始学习，并且应该仔细研读。还应该查阅附录A，因为附录A中讨论了某些专属于C的语言问题。如果喜欢同时参阅一本C参考书，可以参考第1章中给出的推荐书目。离散数学方面的知识对学习本书很有帮助，但并非绝对必要。本书给出了几个数学证明，但对于更复杂的证明，则提示读者复习有关的数学知识。第8章以及第19～24章需要具备一定程度的数学技能。教师可以轻松地选择跳过数学证明，而只介绍证明结果。本书中所有的数学证明都被清晰地标出来了，并与本书正文部分分开。
鄂公网安备 42010302001612号 