《数据结构与面向对象程式设计（C++版）（第4版）》是2012年清华大学出版社出版的图书，作者是Michael Main、Walter Savitch。
基本介绍
- 书名：数据结构与面向对象程式设计（C++版）（第4版）
- 作者：Michael Main、Walter Savitch
- 译者：金名 等
- ISBN：9787302278818
- 定价：89元
- 出版社：清华大学出版社
- 出版时间：2012-4-17
- 装帧：平装
图书简介
本书是为计算机科学专业的第二门课程编写的，在美国很多大学中称之为CS2。本书的重点是规範说明、设计和实现，以及基本数据类型的使用，这些内容都将在第二学期的课程中介绍。而且，本书还介绍了很多重要的编程技术，提供了有关抽象技术、面向对象程式设计、算法的大O时间分析以及排序等内容。
本书假设学生已经完成了“计算机科学导论”和“程式设计”课程的学习，但本书也包括了在第一门课中没有完全涵盖的内容（如递归和指针）。本书使用的是C++语言，但对C++类的介绍是从零开始的，因此，对于那些以C而不是以C++作为程式设计入门语言的学生来说，本书也是适用的。根据笔者的经验，这类学生需要对C++输入和输出技术（参见附录F），以及C++参数类型（参见第2章）有所了解。当C程式设计师克服了有关输入/输出和参数的障碍后，就能领略C++的类和面向对象特性。需要指出的是，根据学生不同的知识背景，本书有多种不同的学习方案。对于那些有较强套用背景的学生来说，可以有选择地学习本书的内容。
本书假设学生已经完成了“计算机科学导论”和“程式设计”课程的学习，但本书也包括了在第一门课中没有完全涵盖的内容（如递归和指针）。本书使用的是C++语言，但对C++类的介绍是从零开始的，因此，对于那些以C而不是以C++作为程式设计入门语言的学生来说，本书也是适用的。根据笔者的经验，这类学生需要对C++输入和输出技术（参见附录F），以及C++参数类型（参见第2章）有所了解。当C程式设计师克服了有关输入/输出和参数的障碍后，就能领略C++的类和面向对象特性。需要指出的是，根据学生不同的知识背景，本书有多种不同的学习方案。对于那些有较强套用背景的学生来说，可以有选择地学习本书的内容。
前言
本书是为计算机科学专业的第二门课程编写的，在美国很多大学中称之为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库中的散列表。
每种数据类型的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章）。
目录
第1章 软体开发的阶段 1
1.1 规範说明、设计与实现 2
1.1.1 概念设计：问题分解 3
1.1.2 前置条件与后置条件 4
1.1.3 使用由其他程式设计师提供的
函式 6
1.1.4 有关ANSI/ISO C++
标準的实现问题 8
1.1.5 本节自测练习 11
1.2 运行时间分析 12
1.2.1 台阶计数问题 12
1.2.2 大O表示法 16
1.2.3 C++函式的时间分析 17
1.2.4 最坏情况、平均情况以及
最好情况下的时间分析 19
1.2.5 本节自测练习 19
1.3 测试与调试 20
1.3.1 选择测试数据 20
1.3.2 边界值 20
1.3.3 完全代码测试 21
1.3.4 调试 21
1.3.5 本节自测练习 22
1.4 本章小结 22
本章自测练习参考答案 23
第2章 抽象数据类型与C++类 25
2.1 类与成员 25
2.1.1 编程示例：节流阀类
throttle 25
2.1.2 使用类 29
2.1.3 throttle类的演示小程式 30
2.1.4 实现成员函式 31
2.1.5 可以调用其他成员的
成员函式 34
2.1.6 本节自测练习 34
2.2 构造函式 35
2.2.1 throttle类的构造函式 35
2.2.2 修订throttle类的成员
函式 37
2.2.3 内联成员函式 38
2.2.4 本节自测练习 39
2.3 使用名称空间、头档案与
实现档案 39
2.3.1 创建名称空间 40
2.3.2 头档案 40
2.3.3 实现档案 44
2.3.4 使用名称空间里的数据项 46
2.3.5 本节自测练习 48
2.4 类与参数 49
2.4.1 编程示例：point类 49
2.4.2 参数默认值 52
2.4.3 参数 53
2.4.4 当函式的返回值的数据
类型为类时 58
2.4.5 本节自测练习 59
2.5 操作符重载 60
2.5.1 二元比较操作符重载 60
2.5.2 二元算术操作符重载 61
2.5.3 输入输出操作符重载 62
2.5.4 友元函式 64
2.5.5 point类汇总 66
2.5.6 操作符重载小结 68
2.5.7 本节自测练习 69
2.6 标準模板库与pair类 69
2.7 本章小结 70
本章自测练习参考答案 71
编程项目 73
第3章 容器类 81
3.1 bag类 81
3.1.1 bag类的规範说明 81
3.1.2 bag类的文档说明 88
3.1.3 bag类的演示程式 91
3.1.4 bag类的设计 93
3.1.5 类的不变式 94
3.1.6 bag类的实现 95
3.1.7 bag类的集成 101
3.1.8 bag类的测试 104
3.1.9 bag类的分析 105
3.1.10 本节自测练习 106
3.2 编程项目：sequence类 107
3.2.1 sequence类的规範说明 107
3.2.2 sequence类的文档说明 111
3.2.3 sequence类的设计 113
3.2.4 sequence类的伪代码实现 114
3.2.5 本节自测练习 116
3.3 互动式测试程式 116
本节自测练习 121
3.4 STL中的multiset类及其叠代器 122
3.4.1 multiset模板类 122
3.4.2 multiset类的一些成员 123
3.4.3 叠代器与[...)模式 123
3.4.4 测试叠代器的相等性 126
3.4.5 multiset类的其他操作符 126
3.4.6 不合法的叠代器 126
3.4.7 本节自测练习 128
3.5 本章小结 128
本章自测练习参考答案 128
编程项目 131
第4章 指针与动态数组 138
4.1 指针与动态记忆体 138
4.1.1 指针变数 139
4.1.2 指针与赋值操作符一起
使用 140
4.1.3 动态变数与new操作符 142
4.1.4 使用new操作符为
动态数组分配记忆体 143
4.1.5 记忆体堆与bad_alloc
异常 144
4.1.6 delete操作符 145
4.1.7 本节自测练习 147
4.2 把指针与数组作为参数 147
4.2.1 以指针作为值参数 147
4.2.2 数组参数 149
4.2.3 以指针或数组作为常量
参数 150
4.2.4 以指针作为引用参数 152
4.2.5 本节自测练习 153
4.3 具有动态数组的bag类 156
4.3.1 指针成员变数 156
4.3.2 成员函式按需分配记忆体 157
4.3.3 值语义 161
4.3.4 析构函式 163
4.3.5 修订后的bag类定义 164
4.3.6 修订后的bag类实现 165
4.3.7 修订后的bag类集成 170
4.3.8 本节自测练习 172
4.4 有关动态类的说明 172
4.4.1 4条规则 173
4.4.2 複製构造函式的特殊
重要性 173
4.4.3 本节自测练习 174
4.5 STL的string类与编程项目 174
4.5.1 以null结尾的字元串 174
4.5.2 初始化字元串变数 175
4.5.3 空字元串 175
4.5.4 读写字元串变数 175
4.5.5 strcpy函式 176
4.5.6 strcat函式 177
4.5.7 strlen函式 177
4.5.8 strcmp函式 178
4.5.9 string类的规範说明 178
4.5.10 string类的构造函式 180
4.5.11 重载operator[ ] 181
4.5.12 其他重载成员 181
4.5.13 string类的其他操作 182
4.5.14 string类的设计 182
4.5.15 string类的实现 183
4.5.16 string类的演示程式 185
4.5.17 串联输出操作符 186
4.5.18 声明常量对象 187
4.5.19 由构造函式产生的类型
转换 187
4.5.20 在表达式中使用
已重载的操作符 187
4.5.21 本章设计的string类与C++
库的string类 188
4.5.22 本节自测练习 188
4.6 编程项目：polynomial类 188
4.7 本章小结 191
本章自测练习参考答案 192
编程项目 194
第5章 鍊表 196
5.1 鍊表的基本节点类 196
5.1.1 为节点声明类 196
5.1.2 在鍊表节点中使用
typedef语句 197
5.1.3 头指针和尾指针 197
5.1.4 空指针NULL 198
5.1.5 头指针或尾指针为NULL
的含义 199
5.1.6 节点类构造函式 199
5.1.7 节点类成员函式 200
5.1.8 成员选择操作符 201
5.1.9 本节自测练习 204
5.2 鍊表工具包 205
5.2.1 鍊表工具包的头档案 205
5.2.2 计算鍊表的长度 206
5.2.3 鍊表的参数 209
5.2.4 在鍊表头插入新节点 210
5.2.5 在非鍊表头的其他位置
插入新节点 212
5.2.6 在鍊表中查找节点 215
5.2.7 根据节点的位置在鍊表中
寻找节点 217
5.2.8 鍊表複製 218
5.2.9 在鍊表头删除节点 221
5.2.10 在非鍊表头删除节点 222
5.2.11 清空鍊表 223
5.2.12 鍊表工具包的集成 224
5.2.13 使用鍊表工具包 228
5.2.14 本节自测练习 228
5.3 用鍊表实现bag类 229
5.3.1 第3个bag类的规範
说明 229
5.3.2 第3个bag类的类定义 230
5.3.3 如何使bag类的value_
type与节点类的value_
type相匹配 233
5.3.4 在类中使用动态记忆体
应遵循的规则 234
5.3.5 第3个bag类的实现 234
5.3.6 第3个bag类的集成 241
5.3.7 本节自测练习 244
5.4 编程项目：用鍊表实现
sequence类 244
5.4.1 关于修订后的sequence
类的设计建议 245
5.4.2 关于修订后的sequence
类的值语义 246
5.4.3 本节自测练习 246
5.5 动态数组、鍊表与双向鍊表 246
5.5.1 做出抉择 248
5.5.2 本节自测练习 249
5.6 标準模板库的vector、list和
deque类 249
本节测试练习 252
5.7 本章小结 252
本章自测练习参考答案 252
编程项目 257
第6章 用模板、叠代器和STL
进行软体开发 261
6.1 模板函式 261
6.1.1 模板函式的语法 263
6.1.2 使用模板函式 263
6.1.3 交换两个值的模板函式 265
6.1.4 模板函式的参数匹配 266
6.1.5 在数组中查找最大项
的模板函式 267
6.1.6 在已排序数组中插入一个
数据项的模板函式 268
6.1.7 本节自测练习 270
6.2 模板类 270
6.2.1 模板类的语法 270
6.2.2 进一步了解模板类实现
档案 277
6.2.3 模板类成员函式的参数
匹配 278
6.2.4 使用模板类 278
6.2.5 详细讨论上一个演示
程式 281
6.2.6 本节自测练习 282
6.3 STL算法与叠代器的使用 282
6.3.1 STL算法 282
6.3.2 标準叠代器的类型 283
6.3.3 数组的叠代器 285
6.3.4 本节自测习题 285
6.4 节点模板类 286
6.4.1 返回引用类型的函式 287
6.4.2 将引用返回值複製到
别处时会发生什幺 288
6.4.3 这里成员函式data
需要两个版本 288
6.4.4 新节点类的头档案和实现
档案 289
6.4.5 本节自测练习 297
6.5 鍊表的叠代器 297
6.5.1 节点叠代器 297
6.5.2 从std::iterator派生
而来的节点叠代器 299
6.5.3 节点叠代器的私有
成员变数 300
6.5.4 节点叠代器的构造函式 300
6.5.5 节点叠代器的*操作符 300
6.5.6 节点叠代器两个版本
的 ++ 操作符 300
6.5.7 节点叠代器的相等和不相
等比较 302
6.5.8 常量集合的叠代器 302
6.5.9 本节自测练习 304
6.6 含叠代器的鍊表版bag模板类 305
6.6.1 如何为容器类提供
叠代器 305
6.6.2 bag类叠代器 306
6.6.3 将叠代器定义在bag
类中的原因 307
6.6.4 本节自测练习 314
6.7 本章小结与5个bag类的小结 314
本章自测练习答案 315
编程项目 318
第7章 栈 320
7.1 STL的stack类 320
7.1.1 标準库的stack类 321
7.1.2 编程示例：翻转单词 322
7.1.3 本节自测练习 323
7.2 栈的套用 323
7.2.1 编程示例：括弧的匹配 323
7.2.2 编程示例：算术表达
式求值 325
7.2.3 算术表达式求值的
规範说明 326
7.2.4 算术表达式求值的设计 326
7.2.5 算术表达式求值的实现 331
7.2.6 计算器程式使用的函式 332
7.2.7 算术表达式求值的
测试与分析 332
7.2.8 算术表达式求值的改进 333
7.2.9 本节自测练习 333
7.3 stack类的实现 334
7.3.1 栈的数组实现 334
7.3.2 栈的鍊表实现 337
7.3.3 Koenig查找 341
7.3.4 本节自测练习 341
7.4 更複杂的栈套用 342
7.4.1 后缀表达式求值 342
7.4.2 将中缀表示法转换成后
缀表示法 344
7.4.3 在中缀表达式中使用
优先权规则 346
7.4.4 中缀转换为后缀的
正确性 348
7.4.5 本节自测练习 349
7.5 本章小结 349
本章自测练习答案 350
编程项目 351
第8章 伫列 356
8.1 STL伫列 356
8.1.1 标準库的伫列类 357
8.1.2 伫列的使用 358
8.1.3 本节自测练习 359
8.2 伫列的套用 359
8.2.1 编程示例：识别回文 359
8.2.2 本节自测练习 361
8.2.3 编程示例：洗车模拟
程式 362
8.2.4 洗车模拟程式的
规範说明 362
8.2.5 洗车模拟程式的设计 362
8.2.6 实现洗车类 365
8.2.7 实现模拟函式 371
8.2.8 本节自测练习 372
8.3 伫列类的实现 373
8.3.1 伫列的数组实现 373
8.3.2 有关伫列中环形数组实现
的讨论 377
8.3.3 伫列的鍊表实现 379
8.3.4 实现细节 380
8.3.5 本节自测练习 384
8.4 实现STL的双端伫列 384
8.4.1 为双端伫列的value_type
项调用析构函式和构造
函式 387
8.4.2 栈和伫列的其他变体 388
8.4.3 本节自测练习 388
8.5 栈、伫列和优先伫列类的引用
返回值 388
8.6 本章小结 389
本章自测练习答案 389
编程项目 390
第9章 递归思想 394
9.1 递归函式 394
9.1.1 递归思想的第一个例子 394
9.1.2 跟蹤递归调用 396
9.1.3 编程示例：write_vertical
的一个扩展 397
9.1.4 深入分析递归 398
9.1.5 成功递归函式的一般
形式 401
9.1.6 本节自测练习 402
9.2 递归的研究：分形和迷宫 402
9.2.1 编程示例：产生随机
分形 403
9.2.2 产生随机分形的函式及其
规範说明 404
9.2.3 分形函式的设计和实现 405
9.2.4 如何显示随机分形 407
9.2.5 编程示例：穿越迷宫 407
9.2.6 穿越迷宫函式的规範
说明 408
9.2.7 穿越迷宫函式的设计 409
9.2.8 穿越迷宫函式的实现 410
9.2.9 运用回溯穷举搜寻的
递归模式 412
9.2.10 编程示例：玩具熊游戏 413
9.2.11 本节自测练习 414
9.3 推导递归 415
9.3.1 如何确保没有无限递归 417
9.3.2 归纳推导递归函式的
正确性 419
9.3.3 本节自测练习 419
9.4 本章小结 420
本章自测练习答案 420
编程项目 422
第10章 树 427
10.1 树的简介 427
10.1.1 二叉树 427
10.1.2 二叉分类树 430
10.1.3 一般树 430
10.1.4 本节自测练习 431
10.2 树的表示法 431
10.2.1 完全二叉树的数组
表示法 432
10.2.2 使用节点类表示
二叉树 433
10.2.3 本节自测练习 434
10.3 二叉树节点类 435
10.3.1 编程示例：猜测动物
程式 439
10.3.2 猜测动物程式的
设计与实现 440
10.3.3 猜测动物程式的
改进 448
10.3.4 本节自测练习 448
10.4 树的遍历 449
10.4.1 二叉树的遍历 449
10.4.2 从树的节点中输出
数据 453
10.4.3 遍历中的问题 454
10.4.4 函式作为参数 454
10.4.5 apply函式的一个
模板版本 456
10.4.6 使apply模板函式
更具有通用性 457
10.4.7 树遍历的模板函式 458
10.4.8 本节自测练习 465
10.5 二叉查找树 466
10.5.1 二叉查找树存储机制 466
10.5.2 第6个bag类的定义 470
10.5.3 第6个bag类的某些
简单函式的实现 470
10.5.4 计算某个元素在二叉
查找树中出现的次数 471
10.5.5 添加一个新元素到二叉
查找树中 472
10.5.6 从二叉查找树中删除
某个元素 473
10.5.7 二叉查找树的组合
操作符 475
10.5.8 时间分析和叠代器 477
10.5.9 本节自测练习 478
10.6 本章小结 478
本章自测练习答案 479
编程项目 482
第11章 平衡树 487
11.1 堆 487
11.1.1 堆的存储规则 487
11.1.2 使用堆结构实现的
优先伫列 488
11.1.3 插入新项 488
11.1.4 删除项 489
11.2 STL优先伫列与堆算法 491
本节自测练习 492
11.3 B树 492
11.3.1 非平衡树的问题 493
11.3.2 B树的规则 493
11.3.3 B树的一个示例 495
11.3.4 用B树实现set类 495
11.3.5 在B树中查找项 499
11.3.6 在B树中插入项 501
11.3.7 B树的鬆散插入操作 501
11.3.8 修正子节点多余项
的私有成员函式 503
11.3.9 回到成员函式
Insert 504
11.3.10 採用自顶向下方法
设计 505
11.3.11 从B树中删除项 505
11.3.12 B树的鬆散删除
操作 506
11.3.13 解决子节点项短缺
问题的私有成员
函式 508
11.3.14 从B树中删除最大
的项 510
11.3.15 外部B树 512
11.3.16 本节自测练习 512
11.4 树、日誌和时间分析 513
11.4.1 二叉查找树的时间
分析 513
11.4.2 堆的时间分析 514
11.4.3 对数运算 515
11.4.4 对数级算法 516
11.4.5 本节自测练习 516
11.5 STL的map类和
multimap类 517
11.6 本章小结 518
本章自测练习答案 518
编程项目 521
第12章 查找 523
12.1 顺序查找和二叉查找 523
12.1.1 顺序查找 523
12.1.2 顺序查找的分析 523
12.1.3 二叉查找 525
12.1.4 二叉查找的设计 526
12.1.5 二叉查找的分析 528
12.1.6 标準库的查找函式 531
12.1.7 用于有序区间的函式 531
12.1.8 用于无序区间的函式 532
12.1.9 STL的search函式 533
12.1.10 本节自测练习 534
12.2 开地址散列 534
12.2.1 散列简介 534
12.2.2 表类的声明 536
12.2.3 表类的设计 538
12.2.4 表ADT的实现 541
12.2.5 选择散列函式来
减少冲突 547
12.2.6 再散列减少聚类 547
12.2.7 本节自测练习 548
12.3 链式散列 549
本节自测练习 551
12.4 散列的时间分析 551
12.4.1 散列表的装填因子 551
12.4.2 本节自测练习 553
12.5 程式设计：使用STL向量的
表类 553
12.5.1 新表类 553
12.5.2 在新表类中使用向量 554
12.5.3 常量模板参数 554
12.5.4 函式模板参数 554
12.5.5 实现新表类 555
12.5.6 本节自测练习 556
12.6 TR1库扩展中的散列表 556
12.7 本章小结 557
本章自测练习答案 557
编程项目 561
第13章 排序 563
13.1 二次排序算法 563
13.1.1 选择排序的规範说明 563
13.1.2 选择排序的设计 563
13.1.3 选择排序的实现 565
13.1.4 选择排序的效率分析 567
13.1.5 插入排序 569
13.1.6 插入排序的效率分析 571
13.1.7 本节自测练习 573
13.2 递归排序算法 574
13.2.1 使用递归的分治法 574
13.2.2 归併排序 576
13.2.3 归併函式 577
13.2.4 动态记忆体在归併排序中
的套用 581
13.2.5 归併排序的效率分析 582
13.2.6 档案的归併排序 583
13.2.7 快速排序 584
13.2.8 partition函式 585
13.2.9 快速排序的效率分析 588
13.2.10 为快速排序选择一个
好的基準元素 589
13.2.11 本节自测练习 589
13.3 使用堆的O(n log n)算法 590
13.3.1 堆排序 590
13.3.2 构建堆 595
13.3.3 向下重排 596
13.3.4 堆排序的效率分析 597
13.3.5 本节自测练习 598
13.4 STL的排序与二叉查找 598
13.4.1 原始C标準库函式
qsort 598
13.4.2 STL的排序函式 599
13.4.3 STL的堆排序 600
13.4.4 STL的二叉查找函式 600
13.4.5 用于STL排序函式
的比较参数 601
13.4.6 使用叠代器编写一个
自己的排序函式 601
13.5 本章小结 602
本章自测练习答案 603
编程项目 605
第14章 派生类与继承 610
14.1 派生类 610
14.1.1 如何声明派生类 612
14.1.2 派生类的自动构造
函式 613
14.1.3 使用派生类 614
14.1.4 派生类的自动赋值
操作符 615
14.1.5 派生类的自动析构
函式 616
14.1.6 覆盖继承的成员函式 616
14.1.7 本节自测练习 617
14.2 仿真生态系统 618
14.2.1 实现部分生物对象层次 618
14.2.2 organism类 618
14.2.3 animal类：具有新私有
成员变数的派生类 621
14.2.4 如何为派生类提供
新构造函式 622
14.2.5 animal类的其他
成员函式 623
14.2.6 本节自测练习 627
14.2.7 herbivore类 628
14.2.8 池塘生态仿真程式 630
14.2.9 池塘生态系统的实现
细节 634
14.2.10 使用池塘模型 634
14.2.11 动态记忆体的使用 635
14.2.12 本节自测练习 636
14.3 虚拟成员函式和game类 636
14.3.1 game类简介 636
14.3.2 受保护的成员 640
14.3.3 虚拟成员函式 640
14.3.4 虚拟析构函式 641
14.3.5 game类的受保护
虚拟成员函式 641
14.3.6 实现Connect Four
游戏的派生类 642
14.3.7 connect4类的私有
成员变数 642
14.3.8 connect4类的构造
函式和restart函式 644
14.3.9 处理游戏状态的
三个函式 644
14.3.10 处理移动的三个函式 645
14.3.11 clone函式 646
14.3.12 编写派生自game
类的游戏 646
14.3.13 game类的play算法 647
14.3.14 本节自测练习 650
14.4 本章小结 650
进阶阅读 650
本章自测练习答案 651
编程项目 655
第15章 图 657
15.1 图的定义 657
15.1.1 无向图 657
15.1.2 有向图 660
15.1.3 图的更多术语 661
15.1.4 航线的例子 661
15.1.5 本节自测练习 662
15.2 图的实现 663
15.2.1 使用邻接矩阵表示图 663
15.2.2 使用二维数组
存储邻接矩阵 663
15.2.3 使用边列表表示图 664
15.2.4 使用边集表示图 665
15.2.5 哪种表示方法最好 665
15.2.6 编程示例：标籤图类 665
15.2.7 用于增加顶点和边
的成员函式 666
15.2.8 标籤图类——重载
下标操作符 667
15.2.9 下标操作符的常量
版本 668
15.2.10 标籤图类——函式
neighbors 668
15.2.11 标籤图类的实现 669
15.2.12 本节自测练习 674
15.3 图的遍历 674
15.3.1 深度优先搜寻 675
15.3.2 宽度优先搜寻 677
15.3.3 深度优先搜寻的实现 679
15.3.4 宽度优先搜寻的实现 680
15.3.5 本节自测练习 682
15.4 路径算法 683
15.4.1 判断某条路径是否
存在 683
15.4.2 具有加权边的图 683
15.4.3 最短距离算法 684
15.4.4 最短路径算法 691
15.4.5 本节自测练习 691
15.5 本章小结 692
本章自测练习答案 692
编程项目 693
附录 697
附录A ASCII字元集 697
附录B 大O表达式 698
附录C 操作符的优先顺序 700
附录D 命令行编译和连结 701
附录E 使用老式编译器 701
附录F C++的输入和输出 701
附录G 选择库函式 708
附录H 标準模板类简介 711
附录I 一些有用函式的工具包 720
附录J 基本风格指南 723
附录K 下载GNU编译器和软体 723
附录L 异常处理 724
第1章 软体开发的阶段 1
1.1 规範说明、设计与实现 2
1.1.1 概念设计：问题分解 3
1.1.2 前置条件与后置条件 4
1.1.3 使用由其他程式设计师提供的
函式 6
1.1.4 有关ANSI/ISO C++
标準的实现问题 8
1.1.5 本节自测练习 11
1.2 运行时间分析 12
1.2.1 台阶计数问题 12
1.2.2 大O表示法 16
1.2.3 C++函式的时间分析 17
1.2.4 最坏情况、平均情况以及
最好情况下的时间分析 19
1.2.5 本节自测练习 19
1.3 测试与调试 20
1.3.1 选择测试数据 20
1.3.2 边界值 20
1.3.3 完全代码测试 21
1.3.4 调试 21
1.3.5 本节自测练习 22
1.4 本章小结 22
本章自测练习参考答案 23
第2章 抽象数据类型与C++类 25
2.1 类与成员 25
2.1.1 编程示例：节流阀类
throttle 25
2.1.2 使用类 29
2.1.3 throttle类的演示小程式 30
2.1.4 实现成员函式 31
2.1.5 可以调用其他成员的
成员函式 34
2.1.6 本节自测练习 34
2.2 构造函式 35
2.2.1 throttle类的构造函式 35
2.2.2 修订throttle类的成员
函式 37
2.2.3 内联成员函式 38
2.2.4 本节自测练习 39
2.3 使用名称空间、头档案与
实现档案 39
2.3.1 创建名称空间 40
2.3.2 头档案 40
2.3.3 实现档案 44
2.3.4 使用名称空间里的数据项 46
2.3.5 本节自测练习 48
2.4 类与参数 49
2.4.1 编程示例：point类 49
2.4.2 参数默认值 52
2.4.3 参数 53
2.4.4 当函式的返回值的数据
类型为类时 58
2.4.5 本节自测练习 59
2.5 操作符重载 60
2.5.1 二元比较操作符重载 60
2.5.2 二元算术操作符重载 61
2.5.3 输入输出操作符重载 62
2.5.4 友元函式 64
2.5.5 point类汇总 66
2.5.6 操作符重载小结 68
2.5.7 本节自测练习 69
2.6 标準模板库与pair类 69
2.7 本章小结 70
本章自测练习参考答案 71
编程项目 73
第3章 容器类 81
3.1 bag类 81
3.1.1 bag类的规範说明 81
3.1.2 bag类的文档说明 88
3.1.3 bag类的演示程式 91
3.1.4 bag类的设计 93
3.1.5 类的不变式 94
3.1.6 bag类的实现 95
3.1.7 bag类的集成 101
3.1.8 bag类的测试 104
3.1.9 bag类的分析 105
3.1.10 本节自测练习 106
3.2 编程项目：sequence类 107
3.2.1 sequence类的规範说明 107
3.2.2 sequence类的文档说明 111
3.2.3 sequence类的设计 113
3.2.4 sequence类的伪代码实现 114
3.2.5 本节自测练习 116
3.3 互动式测试程式 116
本节自测练习 121
3.4 STL中的multiset类及其叠代器 122
3.4.1 multiset模板类 122
3.4.2 multiset类的一些成员 123
3.4.3 叠代器与[...)模式 123
3.4.4 测试叠代器的相等性 126
3.4.5 multiset类的其他操作符 126
3.4.6 不合法的叠代器 126
3.4.7 本节自测练习 128
3.5 本章小结 128
本章自测练习参考答案 128
编程项目 131
第4章 指针与动态数组 138
4.1 指针与动态记忆体 138
4.1.1 指针变数 139
4.1.2 指针与赋值操作符一起
使用 140
4.1.3 动态变数与new操作符 142
4.1.4 使用new操作符为
动态数组分配记忆体 143
4.1.5 记忆体堆与bad_alloc
异常 144
4.1.6 delete操作符 145
4.1.7 本节自测练习 147
4.2 把指针与数组作为参数 147
4.2.1 以指针作为值参数 147
4.2.2 数组参数 149
4.2.3 以指针或数组作为常量
参数 150
4.2.4 以指针作为引用参数 152
4.2.5 本节自测练习 153
4.3 具有动态数组的bag类 156
4.3.1 指针成员变数 156
4.3.2 成员函式按需分配记忆体 157
4.3.3 值语义 161
4.3.4 析构函式 163
4.3.5 修订后的bag类定义 164
4.3.6 修订后的bag类实现 165
4.3.7 修订后的bag类集成 170
4.3.8 本节自测练习 172
4.4 有关动态类的说明 172
4.4.1 4条规则 173
4.4.2 複製构造函式的特殊
重要性 173
4.4.3 本节自测练习 174
4.5 STL的string类与编程项目 174
4.5.1 以null结尾的字元串 174
4.5.2 初始化字元串变数 175
4.5.3 空字元串 175
4.5.4 读写字元串变数 175
4.5.5 strcpy函式 176
4.5.6 strcat函式 177
4.5.7 strlen函式 177
4.5.8 strcmp函式 178
4.5.9 string类的规範说明 178
4.5.10 string类的构造函式 180
4.5.11 重载operator[ ] 181
4.5.12 其他重载成员 181
4.5.13 string类的其他操作 182
4.5.14 string类的设计 182
4.5.15 string类的实现 183
4.5.16 string类的演示程式 185
4.5.17 串联输出操作符 186
4.5.18 声明常量对象 187
4.5.19 由构造函式产生的类型
转换 187
4.5.20 在表达式中使用
已重载的操作符 187
4.5.21 本章设计的string类与C++
库的string类 188
4.5.22 本节自测练习 188
4.6 编程项目：polynomial类 188
4.7 本章小结 191
本章自测练习参考答案 192
编程项目 194
第5章 鍊表 196
5.1 鍊表的基本节点类 196
5.1.1 为节点声明类 196
5.1.2 在鍊表节点中使用
typedef语句 197
5.1.3 头指针和尾指针 197
5.1.4 空指针NULL 198
5.1.5 头指针或尾指针为NULL
的含义 199
5.1.6 节点类构造函式 199
5.1.7 节点类成员函式 200
5.1.8 成员选择操作符 201
5.1.9 本节自测练习 204
5.2 鍊表工具包 205
5.2.1 鍊表工具包的头档案 205
5.2.2 计算鍊表的长度 206
5.2.3 鍊表的参数 209
5.2.4 在鍊表头插入新节点 210
5.2.5 在非鍊表头的其他位置
插入新节点 212
5.2.6 在鍊表中查找节点 215
5.2.7 根据节点的位置在鍊表中
寻找节点 217
5.2.8 鍊表複製 218
5.2.9 在鍊表头删除节点 221
5.2.10 在非鍊表头删除节点 222
5.2.11 清空鍊表 223
5.2.12 鍊表工具包的集成 224
5.2.13 使用鍊表工具包 228
5.2.14 本节自测练习 228
5.3 用鍊表实现bag类 229
5.3.1 第3个bag类的规範
说明 229
5.3.2 第3个bag类的类定义 230
5.3.3 如何使bag类的value_
type与节点类的value_
type相匹配 233
5.3.4 在类中使用动态记忆体
应遵循的规则 234
5.3.5 第3个bag类的实现 234
5.3.6 第3个bag类的集成 241
5.3.7 本节自测练习 244
5.4 编程项目：用鍊表实现
sequence类 244
5.4.1 关于修订后的sequence
类的设计建议 245
5.4.2 关于修订后的sequence
类的值语义 246
5.4.3 本节自测练习 246
5.5 动态数组、鍊表与双向鍊表 246
5.5.1 做出抉择 248
5.5.2 本节自测练习 249
5.6 标準模板库的vector、list和
deque类 249
本节测试练习 252
5.7 本章小结 252
本章自测练习参考答案 252
编程项目 257
第6章 用模板、叠代器和STL
进行软体开发 261
6.1 模板函式 261
6.1.1 模板函式的语法 263
6.1.2 使用模板函式 263
6.1.3 交换两个值的模板函式 265
6.1.4 模板函式的参数匹配 266
6.1.5 在数组中查找最大项
的模板函式 267
6.1.6 在已排序数组中插入一个
数据项的模板函式 268
6.1.7 本节自测练习 270
6.2 模板类 270
6.2.1 模板类的语法 270
6.2.2 进一步了解模板类实现
档案 277
6.2.3 模板类成员函式的参数
匹配 278
6.2.4 使用模板类 278
6.2.5 详细讨论上一个演示
程式 281
6.2.6 本节自测练习 282
6.3 STL算法与叠代器的使用 282
6.3.1 STL算法 282
6.3.2 标準叠代器的类型 283
6.3.3 数组的叠代器 285
6.3.4 本节自测习题 285
6.4 节点模板类 286
6.4.1 返回引用类型的函式 287
6.4.2 将引用返回值複製到
别处时会发生什幺 288
6.4.3 这里成员函式data
需要两个版本 288
6.4.4 新节点类的头档案和实现
档案 289
6.4.5 本节自测练习 297
6.5 鍊表的叠代器 297
6.5.1 节点叠代器 297
6.5.2 从std::iterator派生
而来的节点叠代器 299
6.5.3 节点叠代器的私有
成员变数 300
6.5.4 节点叠代器的构造函式 300
6.5.5 节点叠代器的*操作符 300
6.5.6 节点叠代器两个版本
的 ++ 操作符 300
6.5.7 节点叠代器的相等和不相
等比较 302
6.5.8 常量集合的叠代器 302
6.5.9 本节自测练习 304
6.6 含叠代器的鍊表版bag模板类 305
6.6.1 如何为容器类提供
叠代器 305
6.6.2 bag类叠代器 306
6.6.3 将叠代器定义在bag
类中的原因 307
6.6.4 本节自测练习 314
6.7 本章小结与5个bag类的小结 314
本章自测练习答案 315
编程项目 318
第7章 栈 320
7.1 STL的stack类 320
7.1.1 标準库的stack类 321
7.1.2 编程示例：翻转单词 322
7.1.3 本节自测练习 323
7.2 栈的套用 323
7.2.1 编程示例：括弧的匹配 323
7.2.2 编程示例：算术表达
式求值 325
7.2.3 算术表达式求值的
规範说明 326
7.2.4 算术表达式求值的设计 326
7.2.5 算术表达式求值的实现 331
7.2.6 计算器程式使用的函式 332
7.2.7 算术表达式求值的
测试与分析 332
7.2.8 算术表达式求值的改进 333
7.2.9 本节自测练习 333
7.3 stack类的实现 334
7.3.1 栈的数组实现 334
7.3.2 栈的鍊表实现 337
7.3.3 Koenig查找 341
7.3.4 本节自测练习 341
7.4 更複杂的栈套用 342
7.4.1 后缀表达式求值 342
7.4.2 将中缀表示法转换成后
缀表示法 344
7.4.3 在中缀表达式中使用
优先权规则 346
7.4.4 中缀转换为后缀的
正确性 348
7.4.5 本节自测练习 349
7.5 本章小结 349
本章自测练习答案 350
编程项目 351
第8章 伫列 356
8.1 STL伫列 356
8.1.1 标準库的伫列类 357
8.1.2 伫列的使用 358
8.1.3 本节自测练习 359
8.2 伫列的套用 359
8.2.1 编程示例：识别回文 359
8.2.2 本节自测练习 361
8.2.3 编程示例：洗车模拟
程式 362
8.2.4 洗车模拟程式的
规範说明 362
8.2.5 洗车模拟程式的设计 362
8.2.6 实现洗车类 365
8.2.7 实现模拟函式 371
8.2.8 本节自测练习 372
8.3 伫列类的实现 373
8.3.1 伫列的数组实现 373
8.3.2 有关伫列中环形数组实现
的讨论 377
8.3.3 伫列的鍊表实现 379
8.3.4 实现细节 380
8.3.5 本节自测练习 384
8.4 实现STL的双端伫列 384
8.4.1 为双端伫列的value_type
项调用析构函式和构造
函式 387
8.4.2 栈和伫列的其他变体 388
8.4.3 本节自测练习 388
8.5 栈、伫列和优先伫列类的引用
返回值 388
8.6 本章小结 389
本章自测练习答案 389
编程项目 390
第9章 递归思想 394
9.1 递归函式 394
9.1.1 递归思想的第一个例子 394
9.1.2 跟蹤递归调用 396
9.1.3 编程示例：write_vertical
的一个扩展 397
9.1.4 深入分析递归 398
9.1.5 成功递归函式的一般
形式 401
9.1.6 本节自测练习 402
9.2 递归的研究：分形和迷宫 402
9.2.1 编程示例：产生随机
分形 403
9.2.2 产生随机分形的函式及其
规範说明 404
9.2.3 分形函式的设计和实现 405
9.2.4 如何显示随机分形 407
9.2.5 编程示例：穿越迷宫 407
9.2.6 穿越迷宫函式的规範
说明 408
9.2.7 穿越迷宫函式的设计 409
9.2.8 穿越迷宫函式的实现 410
9.2.9 运用回溯穷举搜寻的
递归模式 412
9.2.10 编程示例：玩具熊游戏 413
9.2.11 本节自测练习 414
9.3 推导递归 415
9.3.1 如何确保没有无限递归 417
9.3.2 归纳推导递归函式的
正确性 419
9.3.3 本节自测练习 419
9.4 本章小结 420
本章自测练习答案 420
编程项目 422
第10章 树 427
10.1 树的简介 427
10.1.1 二叉树 427
10.1.2 二叉分类树 430
10.1.3 一般树 430
10.1.4 本节自测练习 431
10.2 树的表示法 431
10.2.1 完全二叉树的数组
表示法 432
10.2.2 使用节点类表示
二叉树 433
10.2.3 本节自测练习 434
10.3 二叉树节点类 435
10.3.1 编程示例：猜测动物
程式 439
10.3.2 猜测动物程式的
设计与实现 440
10.3.3 猜测动物程式的
改进 448
10.3.4 本节自测练习 448
10.4 树的遍历 449
10.4.1 二叉树的遍历 449
10.4.2 从树的节点中输出
数据 453
10.4.3 遍历中的问题 454
10.4.4 函式作为参数 454
10.4.5 apply函式的一个
模板版本 456
10.4.6 使apply模板函式
更具有通用性 457
10.4.7 树遍历的模板函式 458
10.4.8 本节自测练习 465
10.5 二叉查找树 466
10.5.1 二叉查找树存储机制 466
10.5.2 第6个bag类的定义 470
10.5.3 第6个bag类的某些
简单函式的实现 470
10.5.4 计算某个元素在二叉
查找树中出现的次数 471
10.5.5 添加一个新元素到二叉
查找树中 472
10.5.6 从二叉查找树中删除
某个元素 473
10.5.7 二叉查找树的组合
操作符 475
10.5.8 时间分析和叠代器 477
10.5.9 本节自测练习 478
10.6 本章小结 478
本章自测练习答案 479
编程项目 482
第11章 平衡树 487
11.1 堆 487
11.1.1 堆的存储规则 487
11.1.2 使用堆结构实现的
优先伫列 488
11.1.3 插入新项 488
11.1.4 删除项 489
11.2 STL优先伫列与堆算法 491
本节自测练习 492
11.3 B树 492
11.3.1 非平衡树的问题 493
11.3.2 B树的规则 493
11.3.3 B树的一个示例 495
11.3.4 用B树实现set类 495
11.3.5 在B树中查找项 499
11.3.6 在B树中插入项 501
11.3.7 B树的鬆散插入操作 501
11.3.8 修正子节点多余项
的私有成员函式 503
11.3.9 回到成员函式
Insert 504
11.3.10 採用自顶向下方法
设计 505
11.3.11 从B树中删除项 505
11.3.12 B树的鬆散删除
操作 506
11.3.13 解决子节点项短缺
问题的私有成员
函式 508
11.3.14 从B树中删除最大
的项 510
11.3.15 外部B树 512
11.3.16 本节自测练习 512
11.4 树、日誌和时间分析 513
11.4.1 二叉查找树的时间
分析 513
11.4.2 堆的时间分析 514
11.4.3 对数运算 515
11.4.4 对数级算法 516
11.4.5 本节自测练习 516
11.5 STL的map类和
multimap类 517
11.6 本章小结 518
本章自测练习答案 518
编程项目 521
第12章 查找 523
12.1 顺序查找和二叉查找 523
12.1.1 顺序查找 523
12.1.2 顺序查找的分析 523
12.1.3 二叉查找 525
12.1.4 二叉查找的设计 526
12.1.5 二叉查找的分析 528
12.1.6 标準库的查找函式 531
12.1.7 用于有序区间的函式 531
12.1.8 用于无序区间的函式 532
12.1.9 STL的search函式 533
12.1.10 本节自测练习 534
12.2 开地址散列 534
12.2.1 散列简介 534
12.2.2 表类的声明 536
12.2.3 表类的设计 538
12.2.4 表ADT的实现 541
12.2.5 选择散列函式来
减少冲突 547
12.2.6 再散列减少聚类 547
12.2.7 本节自测练习 548
12.3 链式散列 549
本节自测练习 551
12.4 散列的时间分析 551
12.4.1 散列表的装填因子 551
12.4.2 本节自测练习 553
12.5 程式设计：使用STL向量的
表类 553
12.5.1 新表类 553
12.5.2 在新表类中使用向量 554
12.5.3 常量模板参数 554
12.5.4 函式模板参数 554
12.5.5 实现新表类 555
12.5.6 本节自测练习 556
12.6 TR1库扩展中的散列表 556
12.7 本章小结 557
本章自测练习答案 557
编程项目 561
第13章 排序 563
13.1 二次排序算法 563
13.1.1 选择排序的规範说明 563
13.1.2 选择排序的设计 563
13.1.3 选择排序的实现 565
13.1.4 选择排序的效率分析 567
13.1.5 插入排序 569
13.1.6 插入排序的效率分析 571
13.1.7 本节自测练习 573
13.2 递归排序算法 574
13.2.1 使用递归的分治法 574
13.2.2 归併排序 576
13.2.3 归併函式 577
13.2.4 动态记忆体在归併排序中
的套用 581
13.2.5 归併排序的效率分析 582
13.2.6 档案的归併排序 583
13.2.7 快速排序 584
13.2.8 partition函式 585
13.2.9 快速排序的效率分析 588
13.2.10 为快速排序选择一个
好的基準元素 589
13.2.11 本节自测练习 589
13.3 使用堆的O(n log n)算法 590
13.3.1 堆排序 590
13.3.2 构建堆 595
13.3.3 向下重排 596
13.3.4 堆排序的效率分析 597
13.3.5 本节自测练习 598
13.4 STL的排序与二叉查找 598
13.4.1 原始C标準库函式
qsort 598
13.4.2 STL的排序函式 599
13.4.3 STL的堆排序 600
13.4.4 STL的二叉查找函式 600
13.4.5 用于STL排序函式
的比较参数 601
13.4.6 使用叠代器编写一个
自己的排序函式 601
13.5 本章小结 602
本章自测练习答案 603
编程项目 605
第14章 派生类与继承 610
14.1 派生类 610
14.1.1 如何声明派生类 612
14.1.2 派生类的自动构造
函式 613
14.1.3 使用派生类 614
14.1.4 派生类的自动赋值
操作符 615
14.1.5 派生类的自动析构
函式 616
14.1.6 覆盖继承的成员函式 616
14.1.7 本节自测练习 617
14.2 仿真生态系统 618
14.2.1 实现部分生物对象层次 618
14.2.2 organism类 618
14.2.3 animal类：具有新私有
成员变数的派生类 621
14.2.4 如何为派生类提供
新构造函式 622
14.2.5 animal类的其他
成员函式 623
14.2.6 本节自测练习 627
14.2.7 herbivore类 628
14.2.8 池塘生态仿真程式 630
14.2.9 池塘生态系统的实现
细节 634
14.2.10 使用池塘模型 634
14.2.11 动态记忆体的使用 635
14.2.12 本节自测练习 636
14.3 虚拟成员函式和game类 636
14.3.1 game类简介 636
14.3.2 受保护的成员 640
14.3.3 虚拟成员函式 640
14.3.4 虚拟析构函式 641
14.3.5 game类的受保护
虚拟成员函式 641
14.3.6 实现Connect Four
游戏的派生类 642
14.3.7 connect4类的私有
成员变数 642
14.3.8 connect4类的构造
函式和restart函式 644
14.3.9 处理游戏状态的
三个函式 644
14.3.10 处理移动的三个函式 645
14.3.11 clone函式 646
14.3.12 编写派生自game
类的游戏 646
14.3.13 game类的play算法 647
14.3.14 本节自测练习 650
14.4 本章小结 650
进阶阅读 650
本章自测练习答案 651
编程项目 655
第15章 图 657
15.1 图的定义 657
15.1.1 无向图 657
15.1.2 有向图 660
15.1.3 图的更多术语 661
15.1.4 航线的例子 661
15.1.5 本节自测练习 662
15.2 图的实现 663
15.2.1 使用邻接矩阵表示图 663
15.2.2 使用二维数组
存储邻接矩阵 663
15.2.3 使用边列表表示图 664
15.2.4 使用边集表示图 665
15.2.5 哪种表示方法最好 665
15.2.6 编程示例：标籤图类 665
15.2.7 用于增加顶点和边
的成员函式 666
15.2.8 标籤图类——重载
下标操作符 667
15.2.9 下标操作符的常量
版本 668
15.2.10 标籤图类——函式
neighbors 668
15.2.11 标籤图类的实现 669
15.2.12 本节自测练习 674
15.3 图的遍历 674
15.3.1 深度优先搜寻 675
15.3.2 宽度优先搜寻 677
15.3.3 深度优先搜寻的实现 679
15.3.4 宽度优先搜寻的实现 680
15.3.5 本节自测练习 682
15.4 路径算法 683
15.4.1 判断某条路径是否
存在 683
15.4.2 具有加权边的图 683
15.4.3 最短距离算法 684
15.4.4 最短路径算法 691
15.4.5 本节自测练习 691
15.5 本章小结 692
本章自测练习答案 692
编程项目 693
附录 697
附录A ASCII字元集 697
附录B 大O表达式 698
附录C 操作符的优先顺序 700
附录D 命令行编译和连结 701
附录E 使用老式编译器 701
附录F C++的输入和输出 701
附录G 选择库函式 708
附录H 标準模板类简介 711
附录I 一些有用函式的工具包 720
附录J 基本风格指南 723
附录K 下载GNU编译器和软体 723
附录L 异常处理 724