本书是为计算机科学专业的第二门课程编写的，在美国很多大学中称之为CS2。本书的重点是规范说明、设计和实现，以及基本数据类型的使用，这些内容都将在第二学期的课程中介绍。而且，本书还介绍了很多重要的编程技术，提供了有关抽象技术、面向对象程序设计、算法的大O时间分析以及排序等内容。

本书假设学生已经完成了“计算机科学导论”和“程序设计”课程的学习，但本书也包括了在第一门课中没有完全涵盖的内容（如递归和指针）。本书使用的是C++语言，但对C++类的介绍是从零开始的，因此，对于那些以C而不是以C++作为程序设计入门语言的学生来说，本书也是适用的。根据笔者的经验，这类学生需要对C++输入和输出技术（参见附录F），以及C++参数类型（参见第2章）有所了解。当C程序员克服了有关输入/输出和参数的障碍后，就能领略C++的类和面向对象特性。需要指出的是，根据学生不同的知识背景，本书有多种不同的学习方案。对于那些有较强应用背景的学生来说，可以有选择地学习本书的内容。

本版新增内容

C++标准模板库（Standard Template Library，STL）在我们的课程中起着更大的作用了，在本书中增加了精心挑选的素材给予介绍。对我们来说，重要的是让我们的学生既能理解如何在应用程序中使用STL类，也能掌握实现这些类（或类似类）的途径。基于这种思考，本版进行了以下修改：

* 新增了2.6节，利用pair类对标准模板库进行早期介绍。我们在学生还没有完全理解模板之前，就向他们介绍STL。

* 在3.4节提前介绍multiset类和STL迭代器。这是介绍这些内容的好地方，因为学生刚刚明白了如何实现他们自己的第一个集合类（即bag类），该类是基于multiset类的。

* 在4.5节继续介绍STL的string类，在这里很适合学生用动态数组来实现自己的string类。

* 新增5.6节，对3个类似的STL类：vector、list和deque进行比较。此时，学生有足够的知识来理解典型的vector和list类实现。

* 在6.3节首次介绍STL算法，在11.2节和13.4节进行了扩展介绍。

* 新增8.4节，介绍了联合使用动态数组和指针，实现STL的deque类的细节。

* 在12.6节讨论了TR1库中的散列表。

大多数章节增加了很多新编程项目，你还可以关注本书的配套网站了解我们开发的新项目：www.cs.colorado.edu/~main/dsoc.html。

每种数据类型的5个介绍步骤

总体来说，第4版继续介绍如下的经典数据结构：集合、包（或多集）、序列表、有序列表（利用“小于”操作符排序）、栈、队列、表和图。此外，还补充介绍了一些数据结构，比如优先队列。上述每种数据结构都将按照如下固定的模式来进行介绍。

第1步：抽象地理解数据结构。在这一层上，学生从概念和图形的层面上，得到对数据结构及其操作的理解。例如，学生可以可视化一个栈及其压入和弹出元素的操作。简单的应用程序更容易理解，而且可以手工完成，比如使用栈来颠倒一个单词的字母顺序。

第2步：把数据结构的规范说明编写成一个C++类。在这一步中，学生明白和理解如何为实现数据类型的C++类编写规范说明。该规范说明包括构造函数、公用成员函数的原型，以及其他公用属性（比如一个用于确定栈的最大尺寸的基本常量）。每个成员函数的原型都给出了前置条件和后置条件，完整地描述了该函数的行为。在这一层很重要的是，让学生明白规范说明与任何实现技术无关。事实上，相同的规范说明可以用于描述相同数据类型的多种不同实现。

第3步：使用数据类型。有了规范说明，学生就可以编写小型的应用程序或演示程序，来展示所使用的数据结构。这些应用程序只是基于数据类型的规范说明，还没有涉及实现。

第4步：选择适当的数据结构，并继续设计和实现数据类型。在对数据类型有了一个好的抽象理解之后，就可以选择一个恰当的数据结构，比如固定大小的数组、动态数组、节点链表或节点二叉树。对于很多数据类型来说，最初的设计和实现会选择简单的方式，比如固定大小的数组。随后，我们将用更复杂的基本结构来重新设计和重新实现相同的数据结构。

由于本书使用的是C++类，对于某个数据类型的实现，将有多种可供选择的数据结构（比如数组、指针等）来作为类的私有成员变量。对于每个实现的类，我们强调应清楚理解私有成员变量与数据类型抽象表示之间的关联规则。我们要求每个学生应用简洁的语言写出这些规则（我们称之为抽象数据类型的不变式）。一旦不变式编写完毕后，就可以继续实现各种成员函数了。不变式有助于编写正确的函数，原因有两条：（1）当函数开始运行时，每个函数（构造函数除外）都知道不变式已为真；（2）当函数结束运行时，每个函数（析构函数除外）都要确保不变式为真。

第5步：分析实现。每个实现的分析包括正确性、灵活性（例如固定大小还是动态大小）以及各种操作的时间分析（使用大O表示法）。当同一种数据类型以多种不同的方式来实现时，学生就可以有很好的机会对它们进行分析。

本课程结束时，学生将学到什么

在本课程结束时，学生将可以彻底理解数据类型了。他们知道如何使用数据类型，如何以多种不同的方式来实现数据类型，知道不同实现方法的实际效果，可以使用大O表示法来分析出各种实现的效率，通过类的不变式来论证各种实现的正确性。

本课程对今后学习有持久重要影响的是，在本课程中学生亲身体验了各种规范说明、设计和实现的过程。本课程对提高学生效率分析和正确性论证的能力也有很重要的帮助。但最重要的一点是，本课程向学生揭示了类可以在很多情况下很容易地使用。学生不再需要从零开始编写代码。我们告诉学生，将来某一天，当他们考虑某个问题时，会突然发现大量工作可以用bag类、stack类、queue类或其他类来完成。这些工作根本不需要他们自己去做什么，他们只需把在本课程中编写的bag类、stack类、queue类或其他类拿出来用就可以，无需任何修改。更多的情况是，他们可以使用标准数据类型库（比如C++标准模板库）中各种熟悉的数据类型。事实上，本书中所介绍的数据类型是标准模板库中的精简版本，因此，当学生进一步学习真正的标准模板库时，他们就有了一个较为熟悉的基础知识。在这个基础上进行设计实现时，就知道哪种数据类型是他们最需要的了，他们也就成为了真正的程序员。

其他基础知识

在本课程中，除了介绍基本的数据结构知识外，还为进行“真正的程序设计”所需的其他知识打下基础，具体如下。

1. 面向对象程序设计

通过让学生深入理解C++类，为面向对象程序设计（Object-Oriented Programming，OOP）打下基础。在课程早期会介绍有关类的重要内容：成员函数的表示法，私有成员与公用成员的分离，构造函数的作用，以及操作符重载等。这些内容足以让学生顺利而兴奋地开始类的学习。

当首次使用动态内存（第4章）时，将进一步介绍类的更多重要特性。此时，需要介绍另外3个方面的内容：复制构造函数、重载后的赋值操作符和析构函数。通过第一次使用动态内存时来介绍OOP的这些内容，可以给学生一个有关动态内存的具体蓝图。动态内存是一种可以拿来使用但随后必须收回的资源。

从概念上来说，OOP最大的创新在于通过继承实现软件重用。当然，也可以在数据结构课程开始时就介绍继承（例如，把set类实现为bag类的一个子类）。但是，过早介绍会使得过多地关注太多新概念，影响对基本数据结构的理解。因此，在我们的课程中，将继承放在最后介绍。但对继承的概述（14.1节和14.2节）可以在理解了复制构造函数之后就进行。基于这种想法，一些教师可能希望在栈与队列之前讲解第14章。

另一种方式是，对于那些已经了解类的基本知识的学生，让他们早些开始进行继承项目（比如14.2节的生态系统或14.3节的游戏引擎），而其他学生则先学习类。

2. 模板

模板函数和模板类是标准模板库的一个重要部分，使得程序员可以很容易地修改容器类中的基本数据项的类型。模板类还可以在一个程序中使用某个类的多个不同实例。同样，在栈（第7章）之前学习和使用模板（第6章）很重要，因为对使用了两种栈的表达式求值是一个很重要的应用。

3. 迭代器

迭代器是标准模板库的另一个重要部分，使得程序员可以很容易地遍历容器对象中的数据项（比如set类或bag类中的元素）。这种迭代器可以是内部的（实现为容器类的成员函数），也可以是外部的（由一个单独的类来实现，该类是容器类的友元）。我们在讲述第一个容器类（3.2节的sequence类）时引入了内部迭代器。在第6章需要时，给bag类添加了一个内部迭代器。此时，还讨论了更复杂的外部迭代器，学生应该明白外部迭代器的优点。在本书中，迭代器为许多编程项目提供了一个很好的选择，例如，实现一个外部bag迭代器（第6章），或使用栈来实现二叉搜索树的内部迭代器（第10章）。

4. 递归

第一学期有时候会向学生介绍递归。但第一学期的很多示例是尾递归，其中，函数的最后一步是递归调用。这可能会给学生一个错误的印象，认为递归只不过是一个循环。鉴于此，在第二学期的课程中，尽量避免过早地使用尾递归。例如，链表中的遍历和其他操作都可以用尾递归来实现，但如果这样做，其结果是增强对递归的错误认识（当学生在操作含有成千上万个数据项的链表时，应忘记尾递归的链表操作，以免出现潜在的运行时栈溢出）。

因此，在第二学期的课程中，我们重点介绍的是使用除尾递归之外的其他递归解决方案。第9章就是遵循这种理念来介绍3个示例的。其中的两个示例（产生随机分形和穿越迷宫）对学生会有较大的触动。在我讲授的课堂上，先讲授递归（第9章），紧接着讲授树（第10章），因为在递归树算法中，递归是非常重用的。但是，对于那些希望更加强调递归的教师来说，可能会提前讲授递归，有的甚至提到第2章之前。

在学时比较充裕的课程中，可以学习高级树项目（第11章），分析递归树算法，解释一下保持树平衡的重要性。这两者都提高了最坏情况下的性能，避免出现潜在的运行时栈溢出。

5. 搜索和排序

第12章和第13章介绍了搜索和排序算法的基础知识。第12章回顾了有序数组的二叉搜索，许多学生之前已经见过这些内容了。第13章回顾了简单的二次排序方法，但该章的重点是快速算法：递归合并排序（最坏情况下的运行时间为O(n log n)）和Tony Hoare递归快速排序（平均运行时间为O(n log n)）以及基于树的堆排序（最坏情况下的运行时间为O(n log n)）。此外还对C++标准模板库的排序函数做了新的介绍。

高级项目

本书提供了很多项目，可以用更高级的类来实现，或者让那些在设计大型类方面有扎实基础的学生来完成。部分高级项目如下：

* 使用动态内存的polynomial类（4.6节）。

* 标准库迭代器，这是用于bag类的迭代器的最高级实现（6.3节～6.5节）。

* 用于二叉搜索树的迭代器（第10章的编程项目）。

* 用链表（第8章的项目）或堆（11.1节）实现的优先队列。

* 用B-树（11.3节）实现的set类。我们对这个项目进行了全面介绍，提供了足够的信息，以便学生无需参考其他教材，就可以实现该类。在我们的课程中，我们已经成功指导一些优先的学生独立完成该项目。

* 使用继承的项目，如14.2节的生态系统项目。

* 使用抽象类实现继承项目，比如14.3节的game基类（利用该类可以很容易地实现两玩家的游戏，比如Othello或connect 4）。

* 第15章的graph类以及相关的图算法。这是优先学生可能独立完成的另一个案例。

C++语言特性

C++是一种具有很多高级特性的复杂语言，在第二学期的课程中不会触及到这些内容。但本书将力求介绍所遇到的那些特性。在本书的第1版中，介绍了当年C++的两个特性：新的布尔数据类型（参见图2.1）和静态成员常量（参见3.1节）。关于静态成员变量的使用要求在1998年发布的标准中进行了修改，本书已经体现了这种修改（现在，常量的声明必须在类定义内部和外部同时进行）。1998标准的另一个主要新特性是名称空间的使用，在这本书第2版中也已经体现了。一些老式的编译器可能不支持这两种新特性。为此，我们给出了一些解决这些问题的辅助办法（参见附录E），以及一些有关下载和安装GNU g++编译器的帮助（参见附录K）。

章节安排的灵活性

本书在编写方式上给予了教师很大的选择空间，他们可以根据特定背景的学生调整教学内容，或者有选择地先讲授某些章节。本前言的最后给出了本书章节之间的相互关系。两个方框之间的连线表明上一个方框中的内容必须在下一个方框中的内容之前讲授。

这里给出了关于本书内容讲授次序的一些参考建议：

* 典型课程。从第1～10章开始，如果学生已经具备C++类的基础知识，可以跳过第2章的部分内容。这其中的大多数章节可以在一周内讲授完，但第5章、第6章、第9章和第10章则可能需要多一些的时间。通常，我们是用13周的时间来讲授这些内容，包括考试时间以及讲授链表和树的时间。剩余时间可以用来讲授第11章或12.1节和第13章。

* 侧重面向对象程序设计的课程。如果学生在其他课程中已经学习了排序与搜索，那么就有时间来重点学习面向对象程序设计了。第1～4章可以详细讲授，然后介绍派生类（14.1节）。此时，可以让学生做一些有趣的OOP项目，比如14.2节的生态系统或14.3节的游戏。然后讲授基本的数据结构（第5～8章），把队列实现为一个派生类（14.3节），最后以第9章和第10章结束本课程，重点强调递归成员    函数。

* 快速课程。把第1～3章作为第一周的自学内容，从第4章开始讲授，这样在学期末会留出两三周的时间，于是学生可以在搜索、排序以及其他高级主题上投入更多的时间。

我们也曾经以更快的速度来讲授本课程，不讲授栈和队列（但把这些章节作为自学内容）。

* 提前讲授递归或提前讲授排序。前一到三周的时间用于讲授递归思想，然后阅读第1章和第9章的内容，可能还要补充递归项目的学习。

如果提前讲授递归，那么也就可以在介绍C++类之前，讲授二叉搜索（12.1节）和大部分的排序算法（第13章）。 

通过Internet获取教辅内容

在www.aw-bc.com/cssupport网站中，所有读者都可以访问如下内容：

* 源代码。本书中出现过的所有C++类、函数和程序。

* 勘误表。我们尽可能不犯错误，但有时候难免。在上述网站中给出了一个已经发现的错误列表，并随时按需更新。欢迎您贡献您所发现的错误。

下面内容只能提供给符合条件的教师：

* PPT

* 考试题

* 部分编程项目的参考答案

* 作业与实验练习

* 建议的教学大纲

致谢

当Walter教授在Colorado大学计算机系访问Michael教授时，开始了本书的写作。在Walter教授回到California大学工程与计算机科学系后，本作品才完成。我们非常感谢这些大学为我们提供条件，感谢那些优秀的学生，感谢那些志同道合的同事。

我们的学生给了我们特别重要的帮助，有将近5000个我们的学生阅读了本书的材料，提出建议，告诉我们他们是如何学习的。我们感谢那些在他们的课程中使用本书材料并提出反馈意见的审阅人和教师：Zachary Bergen、Cathy Bishop、Martin Burtscher、Gina Cherry、Courtney Comstock、Stephen Davies、Robert Fronhardt、John Gillett、Mike Hendricks、Ralph Hollingsworth、Yingdan Huang、Patrick Lynn、Ron McCarty、Shivakant Mishra、Evi Nemeth、Rick Osborne、Rachelle Reese和Nicholas Tran等。本书还请以下人员进行了审阅：Wolfgan W. Bein、Bill Hankley、Michael Milligan、Paul Nagin、Jeff Parker、Andrew L. Wright、John R. Rose和Evan Zweifel等。我们感谢这些同事的出色批评和鼓励。

感谢Lesley McDowell和Chris Schenk，他们在Colorado大学计算机系的每一天都是快乐和热情的。我们还要感谢AW出版社的编辑和工作人员。Heather McNally的工作激励着我们，与我们进行融洽的交流，使本作品出版的每一步都变得轻松惬意。在Colorado大学，Karin Dejamaer和Jessica Hector给予了友善的鼓励，我们感谢他们。我们感谢和欣赏Michael Hirsch的编辑工作，他总是有着过人的精力、热情和鼓舞。最后，我们原来的编辑Susan Hartman仍然继续给予我们支持、鼓励和指导，没有你，这本书不可能面世！

除了感谢以上这些人的工作和支持之外，我们还有感谢那些每天为我们提供快乐和鼓励的人。我们深切地感谢Holly Armold、Vanessa Crittenden、Meredith Boyles、Suzanne Church、Erika Civils、Lynne Conklin、Andrzej Ehrenfeucht、Paul Eisenbrey、Skip Ellis、John Kennedy、Rick Lowell、George Main、Mickey Main、Jesse Nuzzi、Ben Powell、Marga Powell、Megan Powell、Grzegorz Rozenberg、Hannah、Timothy和Janet等。

章节相互关系图如下所示：