前     言

数据结构知识是计算机科学教育的一个基本组成部分，其他许多计算机科学领域都是构建在这个基础之上。对于想要从事实际的软件设计、实现、测试、维护工作的学生而言，掌握基本数据结构的知识是非常必要的。本书介绍的内容将会给从事以上工作的读者提供必要的知识。

本书突出了数据结构中三个重要方面。首先，强调了数据结构与它们的算法之间的联系，包括分析算法的复杂度。接着，依照当前的设计和实现范例，使用面向对象的方法来介绍数据结构。特别强调了有助于信息的封装与分解的信息隐藏原理。最后，本书的一个重要组成部分是数据结构的实现，它选择C++作为程序语言。

C++语言，作为C语言面向对象的后裔，在业界和学术界得到了广泛的应用，是一种非常优秀的程序语言。自然地，我们就选用C++来介绍数据结构。虽然人们也使用过Modula-2和Ada语言来讲授数据结构，但是传统上一直是使用Pascal来讲授数据结构。而且，由于C++语言在应用程序设计中的广泛使用以及这门语言面向对象的特性，使用它来讲授数据结构和算法课程(即使是入门级的课程)是非常合理的。

这本书适合作为教材，它包括旧的ACM(美国计算机协会)课程中CS2和CS7下所列的全部主题。同样，它也能满足新的ACM课程中CA202、CD202和CF204的大部分要求。

我们在大多数章节中都包括了一个实例分析，它阐明了一个完整的、使用特定算法和数据结构的环境为了说明所论述的主题的广泛应用范围，这些实例分析都是从计算机科学的不同领域中挑选出来，包括解释程序、符号计算和文件处理。

本书自始至终包含了简要的C++程序例子，举例说明数据结构在实践中的重要性。然而，理论分析同样也很重要，所以算法的介绍都结合了对算法效率的分析。

要特别留意关于递归的介绍，因为即使是最高明的学生在这个方面往往也会出现一些问题。经验表明，如果考虑运行时栈的话，就可以极好地说明递归的含义。当对一个递归函数进行跟踪的时候，我们不但在此章节里面显示出了栈的变化，而且在其他章节里同样也做到了这一点。比如说，如果我们不对系统在运行时栈上所做的工作进行解释的话，那么就算是一个短小的树遍历函数也可能难于理解。在讨论数据结构和算法的时候，脱离系统和纯理论的方法没有什么用处。

这本书讨论的重点是数据结构，而附带介绍其他一些主题仅仅是为了更好地理解数据结构。算法都是从数据结构的角度来进行讨论的，所以读者将无法找到各种算法的全面讨论，也无法找到完整介绍一个算法所需要的各方面的内容。然而，正如前面所提到过的，本书对递归的介绍具有一定的深度。另外，对算法的复杂度分析也比较详细。

第1~8章介绍了许多不同的数据结构以及使用这些数据结构的算法。并且分析了每一种算法的效率，同时给出了改进算法的建议。

●  第1章介绍了面向对象程序设计的基本原理，介绍了动态内存分配、指针的使用以及标准模板库(Standard Template Library，STL)。

● 第2章讲述了一些评价算法效率的方法。

● 第3章介绍了不同类型的链表，并且着重阐述了其指针实现。

● 第4章介绍了栈、队列及其应用。

● 第5章对递归进行了详细讨论。讨论了不同类型的递归，并对其中的一个递归调用进行了剖析。

● 第6章讨论了二叉树，包括二叉树的实现、遍历和搜索。在这一章中还介绍了平衡树。

● 第7章详细介绍了更一般化的树，比如森林、2-4树、B树。

● 第8章介绍图。

第9~12章给出了在前面的章节里所介绍的数据结构的不同应用，并强调了这些应用在数据结构方面的问题。

● 第9章详细介绍了排序，以及一些基础的和非基础的方法。

● 第10章讨论了散列(hashing)，它是搜索算法中最重要的主题之一。在强调数据结构使用的同时介绍了各种各样的技术。

● 第11章讨论了数据压缩算法和相应的数据结构。

● 第12章介绍了内存管理的多种方法和相应的数据结构。

● 附录A详细介绍了在第2章中提到的大O符号。

● 附录B介绍了标准模板库(STL)中的标准算法。

每一章都包含了对一些材料的讨论，并配以合适的图表和表格。除第2章外，所有的章节都包括一个实例分析，这个实例分析是该章所讨论的特性的一个范例。所有的实例分析都在PC上用Visual C++编译器测试过，只有von Koch snowflake除外，它是在PC上用Turbo C++测试的。每一章最后是一些不同难度的练习题。除了第2章之外，所有的章节都包括了课外作业以及最新的相关参考书籍。

第1~6章(2.9、3.4、6.4.3、6.7、6.8节除外)包含了构成任何数据结构课程基础的核心内容。这些章应该按照顺序来学习。其后的6章内容可以按照任意次序进行学习。一个学期的课程可以包括1~6章、第9章，以及10.1和10.2节。整本书可以在一个学年中学习。

本书中的文本示例程序的源代码可以通过WWW站点进行访问，站点地址为：http://www.mathcs.duq.edu/drozdek/DSinCpp。

第2版的改动

近年来C++最重要的发展就是引入标准模板库(STL)。STL是一个可重用组件的大集合，这些可重用组件是一些通用的(模板化)类和函数。它将程序员从实现许多标准的数据结构和算法的工作中解脱出来，从而大大地加快了程序设计进程。然而，只有很好地理解它们的函数和行为(这包括数据结构的复杂知识)，才能够合理地使用STL组件。本书的目的就是要向读者提供这样的知识。由于这个原因，本书中介绍的许多数据结构并没有或者并不局限于使用STL来实现。然而，由于关于如何使用STL的知识对于C++程序员来说是必不可少的，所以实例分析尽可能地使用了STL组件。通过这种方式，读者既可以获得关于数据结构机制的详细知识，也可以获得由STL提供的、将来可能要用到的代码实现知识。

因此，本书的一个新的特色就是通过以下形式介绍STL：

● 在1.7节对STL进行了概括性介绍

● 在1.8、3.7、3.8、4.4~4.6、7.1.8、7.1.9、9.4节介绍了与STL组件相关的数据结构和算法。

● 附录B

● 在实例分析中使用STL

其他一些加入到本书的新内容包括：在2.9节中的阻尼(amortized)分析，在8.9节中对匹配技术的分析，以及在8.9节和8.10节中对欧拉图和哈密顿图的讨论。

第1章重新编写了对C++的面向对象特性的讨论。还重新编写了1.4节中对指针的介绍和3.1~3.3节中对指针在链表中应用的介绍。第4章，对栈和队列的介绍也作了重大改动，并且包括了一个新的实例分析。同样，在整本书中都存在着许多小的改动。