本书主要介绍了C++的基本知识、函数和库、字符串、流、集合、类的设计、递归、递归策略、回溯算法、算法分析、指针与数组、动态内存管理、效率与表示、线性结构、映射、树、图、继承、迭代的策略等内容。
本书是一本风格独特的C++语言教材，内容源自作者在斯坦福大学多年成功的教学实践。它突破了一般C++编程教材注重介绍C++语法特性的局限，不仅全面讲解了C++语言的基本概念，而且将重点放在深入剖析编程思路上，并以循序渐进的方式教授读者正确编写可行高效的C++程序。本书内容遵循ACM CS2013关于程序设计课程的要求，既适合做为高校计算机及相关专业学生的教材或教学参考书，也适合希望学习C++语言的初学者和中高级程序员使用。
本书特色
面向C++语言的初学者，从内容安排到讲授都遵循化繁为简、通俗易懂的特色，并安排大量案例，理论联系实际，使读者轻松进入C++编程的大门。
突出C++语言的特点，以面向对象概念和编程抽象为核心，使读者了解并掌握优秀软件开发人员应具备的编程思维与实践能力。
努力跨越传统的程序设计语法与算法策略之间的鸿沟，通过独具匠心的内容安排，将数据结构、算法的相关内容与语法基础巧妙结合，将众多经典、实用的算法策略传授给读者，为后续课程或读者的深入学习奠定基础。
前
埃里克 S. 罗伯茨
（Eric S. Roberts）
斯坦福大学教授，知名计算机教育家。1980年在哈佛大学获得博士学位，至今任教超过30年。 1990年加入斯坦福大学后，Roberts 教授长期从事斯坦福大学程序设计相关课程的教学，并编写过多部程序设计的优秀教材，多次获得斯坦福大学的教学奖项。与此同时，他积极活跃于ACM等组织，在计算机教学研究方面作了大量工作，作为联合主席完成了ACM CC2001的制定。他因其杰出贡献而获得ACM计算机教育杰出贡献奖。
后
李雁妮
西安电子科技大学软件学院教授，计算机软件与理论方向硕士生导师，计算机科学与技术博士生导师。主要研究方向为Web数据集成与挖掘、大数据分析算法、面向对象技术。
主要代表性成果及经历：近五年来以第一作者在其研究领域方向上的国际顶级期刊和会议上发表论文十余篇。作为项目负责人和项目主要成员，在研或完成了二十多项国家或横向合作项目。撰写两部C++程序设计教材，其中一部入选教育部“十一五”规划教材、普通高等教育精品教材。
致学生
在过去的十年里，计算领域正令人振奋地高速发展着。我们随身携带的网络设备运行速度越来越快，价格越来越便宜，功能也越来越强大。谷歌和维基百科等基于网络的服务给我们提供了大量触手可及的信息。社交网络把我们同世界各地的人联系起来。流媒体技术和更快速的硬件让我们能在任何时候下载所需的音乐和影像。
然而，这些技术并不是突然而至的，而是人们创造了它们。遗憾的是，具备必需的软件开发技能的人现在正供不应求。在硅谷的高科技中心，很多公司找不到能把技术设想转化为现实应用的工程师。各个公司正在极力招聘懂得开发及维护大型系统的人，即懂得数据表示、效率、安全性、正确性和模块化等问题的软件开发人员。
尽管本书不会教给你关于这些主题和计算机科学领域的所有知识，但它会给你一个良好的开始。在斯坦福大学，每年有超过1000名学生选择使用本教材上课。他们中的大部分人觉得在暑期实习或实际工作中仅仅学习本教材中的知识远远不够。更多的学生选择继续学习更深入的课程以使自己在这个高速发展的领域获得更多的机会。
本书的主题除了会在计算机行业中给你提供机会外，同时它也寄乐于学。你在本书中学到的算法和策略有一部分是最近十年发明的，其他的都存在了超过2000年——它们充分体现了人类的聪明才智和创造力。这些算法和策略还非常实用，它们会帮助你成为一个富有经验的程序员。
在你学习本书中的材料时，请牢记，编程总是需要通过实际操作来学习的。阅读一种算法技术并不代表你就能够把那个算法应用到实际中去。只有通过练习和尝试去解决问题的调试，你才能真正学到算法的精髓。编程有时候使人感觉很沮丧，但是当你找到最后一个错误并且看到你的程序正确运行时，会欣喜若狂，它足以回报你在编程这条道路上所付出的任何努力。
致教师
本教材适合作为典型的大学课程中第二门编程课程的教材。它涵盖了ACM的Curriculum 8报告中定义的传统CS2课程中的材料。因此它包含了CS102和CS103课程指定的绝大多数主题，CS102和CS103分别由“ACM/IEEE-CS联合计算机课程2001版”报告及“计算机科学课程2013版”草稿中的AL/基本数据结构及算法单元中的材料定义。
本教材采用的教学策略在斯坦福大学已大获成功。
1.数据结构的客户优先方法。传统的CS2课程由一系列基本数据结构组成。采用此模型，学生可同时学习如何使用一个特定的结构和如何实现它及理解它的性能特点。相比之下，本教材很早地展现了类的完整集合，让学生以客户的身份逐渐熟悉这些类。一旦学生透彻理解了这些内容，本书即开始展现它可能的实现范围和相关的计算特性。在斯坦福大学采用这种策略有助于学生轻松理解相关内容。自从做了这个改变，学生在需要使用集合类的考试中的分数也有了大幅度提高。
2.稍晚呈现那些需要详细了解底层机器的C++特性。尽管前两章给学生提供了C++中基本类型和控制结构的总览，但初始的部分刻意地区分了基本指针和数组等依赖于对底层机器架构理解的主题。虽然这些细节是CS2的基本部分，但也没有必要在课程刚开始的时候就给学生过大的负担。尽早介绍类的集合使得学生能够掌握几个其他同等重要的主题，包括集合类、递归、面向对象设计和算法分析，但是不需要同时纠结于它的底层细节。
3.一个方便易用的图形化可移植类库。使用C++作为教学语言的一个问题是标准类库不提供图形化功能。而本书自带了一个免费发布的开源类库—Standford C++类库，它提供了一种进行图形交互的简单且宜教宜学的方法。Standford C++类库还包括集合类的简化实现，它支持一个更逻辑化且更加有效的表示规则。
补充资源
对于学生
在Pearson网站（http://www.pearsonhighered.com/ericroberts/）上，读者可下载以下资源：
1.书中每个示例程序的源代码文件
2.运行示例的全彩PDF版本
3.复习题的答案
对于教师
在Pearson网站上，有资格的教师可下载以下资源：
1.书中每个示例程序的源代码文件
2.运行示例的全彩PDF版本
3.复习题的答案
4.编程习题的答案
5.每章的PowerPoint课件
Stanford C++类库
Stanford C++类库作为开源的开发项目可以免费获得。头文件、编译库和源代码可以通过GitHub (http://www.github.com/eric-roberts/StanfordCPPLib)或从作者的个人网站（http://cs.stanford.com/~eroberts/StanfordCPPLib）获得。
致谢
本教材有着有趣的发展历史，它在某些方面也反映了C++语言自身的进化。就像Bjarne Stroustrup的第1版C++是在C语言的基础上实现的，本书产生于我的另一本基于C语言的书——《C程序设计的抽象思维》，它由Pearson下属的AddisonWesley于1998年出版。十年前，我的斯坦福同事Julie Zelenski用C++语言更新了它，在那一年我们开始在一系列的概述课程中使用它。尽管修订的教材版本在开始时效果很好，但这些年来我们演变的系列概述课程表明它需要一个重新编写的教材版本，而这本书就是最终的产品。
我要感谢过去这些年在斯坦福的同事，首先要感谢Julie Zelenski在初始C++版本上的卓越贡献。我的同事Keith Schwarz、Jerry Cain、Stephen Cooper和Mehran Sahami 都对修订版做出了重要贡献。我还要向几届课程负责人和这些年我的学生表示感谢，他们都让本课程的教学变得更有激情。
另外，我还要向Marcia Horton、Tracy Johnson和Pearson团队的其他成员表达衷心的感谢，因为他们都对本书和它的旧版本的修订提供了大力支持。
最后，最衷心地感谢我的妻子Lauren Rusk，她又一次作为我的开发编辑发挥了她的魔力。Lauren梳理和润色了本书的文字。没有她，这本书不会成为现在这个样子。
埃里克S.罗伯茨
斯坦福大学
计算机\程序设计
本书是一本风格独特的C++语言教材，内容源自作者在斯坦福大学多年成功的教学实践。它突破了一般C++编程教材注重介绍C++语法特性的局限，不仅全面讲解了C++语言的基本概念，而且将重点放在深入剖析编程思路上，并以循序渐进的方式教授读者正确编写出可行高效的C++程序。本书内容遵循ACM CS2013关于程序设计课程的要求，既适合作为高校计算机及相关专业学生的教材或教学参考书，也适合希望学习C++语言的初学者和中高级程序员使用。
本书特色：
● 本书面向C++语言的初学者，从内容安排到讲授都遵循化繁为简、通俗易懂的特色，并安排大量案例，理论联系实际，使读者轻松进入C++编程的大门。
● 本书突出C++语言的特点，以面向对象概念和编程抽象为核心，使读者了解并掌握现代企业所需的优秀软件开发人员所需要的编程思维与实践能力。
● 本书努力跨越传统的程序设计语法与算法策略之间的鸿沟，通过独具匠心的内容安排，将数据结构、算法的相关内容与语法基础巧妙结合，将众多经典、实用的算法策略传授给读者，为后续课程或读者的深入学习奠定基础。
加34775、38074的封面
[美]埃里克 S. 罗伯茨（Eric S. Roberts） 著：
Eric S．Roberts是美国斯坦福大学计算机科学系教授，并担任系里主管教学事务的副主任，同时他还是工学院的Charles Simonyi讲席教授。他于1980年在哈佛大学应用数学系获得博士学位，并曾在DEC公司位于加州Palo Alto的系统研究中心做过5年的研究工作。作为一位获得高度评价的教育工作者，Roberts还因其在本科生教学中的杰出贡献获得了1993年的Bing Award奖。他的另一本备受赞誉的书《C语言的科学和艺术》已由机械工业出版社引进出版。
李雁妮 等译：暂无简介
本书是美国斯坦福大学计算机科学系C++编程课程多年来成功使用的优秀教材，我很荣幸能成为本书的译者。虽然在为时一年多的书稿翻译过程中，我倍感工作量的巨大与任务的艰辛，但却被本书严谨的结构、通俗精妙的语言以及丰富精巧的编程实例与习题等深深吸引，它驱动我尽最大努力翻译好这本优秀的C++编程教材，以此呈现给国内教授C++编程课程的高校教师和广大欲深入学习C++编程的大学生、研究生及专业的C++程序员。
本书突破了一般C++编程教材大多仅注重介绍C++语法特性的局限，以循序渐进的方式教授读者正确编写出可行高效的C++程序。本书内容不仅涵盖了2013版ACM和IEEE所规定的计算机科学学科在程序设计课程中所定义的内容，而且为了缩短或消除“C++语言”和“C++编程抽象”之间的鸿沟，在其示例和习题中还包含了基本的数据结构及算法课程中的相关内容。从易于读者掌握并尽快提高C++面向对象编程能力的角度，本书从第3章起便开始陆续介绍C++标准类库中的类，并以示例程序和若干编程模式示范总结了如何使用C++标准类库中的集合类、递归编程、面向对象程序设计和算法实现及分析等技术，同时提供了一个开源的、方便易用的图形化的可移植C++类库—Stanford C++类库。衷心祝愿广大读者能从这本优秀的C++编程教材中受益！
在本书翻译工作即将结束之时，衷心感谢机械工业出版社华章分社教材部朱劼女士，是她的努力才促成译者与华章公司在本书翻译上的合作。衷心感谢责任编辑缪杰对提高本书质量所做的大量细致的校对、修正等工作。
这里，要特别感谢王雅馨、黄一涵、刘磊、汪泰利、景祯彦等同学在本书译校过程中的辛勤付出。由于时间仓促且译者水平有限，译文中难免存在欠妥、纰漏与错误之处，恳请广大读者不吝赐教与指正。
李雁妮
2016年7月于西安电子科技大学
出版者的话
译者序
前言
第1章 C++概述1
1.1 你的第一个C++程序1
1.2 C++的历史2
1.2.1 面向对象范型2
1.2.2 C++的演化3
1.3 编译过程3
1.4 C++程序结构4
1.4.1 注释5
1.4.2 包含的库文件6
1.4.3函数原型6
1.4.4主程序7
1.4.5函数定义8
1.5 变量9
1.5.1 变量声明9
1.5.2命名规则10
1.5.3 局部变量和全局变量11
1.5.4 常量11
1.6 数据类型12
1.6.1 数据类型的概念12
1.6.2 整数类型13
1.6.3 浮点类型13
1.6.4 布尔类型14
1.6.5 字符14
1.6.6 字符串15
1.6.7 枚举类型16
1.6.8 复合类型17
1.7 表达式17
1.7.1 优先级和结合律18
1.7.2 表达式中的混合类型19
1.7.3整数除法和求余操作符19
1.7.4 类型转换20
1.7.5 赋值操作符20
1.7.6 自增和自减操作符21
1.7.7 布尔运算22
1.8 语句24
1.8.1 简单语句24
1.8.2 块24
1.8.3 if语句24
1.8.4 switch语句25
1.8.5while语句27
1.8.6 for语句29
本章小结31
复习题32
习题33
第2章 函数与库37
2.1 函数概念37
2.1.1 数学中的函数37
2.1.2 编程中的函数37
2.1.3 使用函数的优点38
2.1.4函数和算法38
2.2库39
2.3在C++中定义函数41
2.3.1函数原型41
2.3.2重载42
2.3.3默认形参数42
2.4函数调用机制43
2.4.1函数调用步骤43
2.4.2组合函数44
2.4.3追踪组合函数执行过程46
2.5引用参数49
2.6接口与实现52
2.6.1定义error库53
2.6.2导出数据类型54
2.6.3导出常量定义56
2.7接口设计原则58
2.7.1统一主题的重要性58
2.7.2简单性与信息隐藏原理59
2.7.3满足用户需求60
2.7.4通用工具的优势60
2.7.5库稳定性的价值60
2.8随机数库的设计61
2.8.1随机数与伪随机数61
2.8.2标准库中的伪随机数62
2.8.3选择正确的函数集63
2.8.4构建用户程序65
2.8.5随机数库的实现65
2.8.6初始化随机数种子69
2.9Stanford类库介绍73
2.9.1简单的输入和输出类库73
2.9.2Stanford类库中的图形处理程序74
本章小结77
复习题78
习题79
第3章 字符串类string85
3.1使用字符串作为抽象数据85
3.2字符串操作87
3.2.1操作符重载88
3.2.2从一个字符串中选取字符89
3.2.3字符串赋值90
3.2.4提取字符串中的子串90
3.2.5在一个字符串中进行搜索90
3.2.6循环遍历字符串中的所有字符91
3.2.7通过连接扩展字符串92
3.3
3.4修改字符串中的内容94
3.5遗留的C风格字符串95
3.6编写字符串应用程序95
3.6.1回文识别96
3.6.2将英语翻译成儿童黑话96
3.7strlib.h库99
本章小结100
复习题100
习题101
第4章 流类108
4.1格式化输出108
4.2格式化输入112
4.3数据文件113
4.3.1使用文件流114
4.3.2单个字符的输入/输出115
4.3.3面向行的输入/输出118
4.3.4格式化输入/输出119
4.3.5字符串流121
4.3.6一个用于控制台输入的更鲁棒的策略122
4.4类层次123
4.4.1生物层次123
4.4.2流类层次124
4.4.3在流层次中选择正确的层次126
4.5simpio.h和filelib.h库127
本章小结128
复习题128
习题129
第5章 集合类 133
5.1Vector类134
5.1.1指定Vector的基类型134
5.1.2声明Vector对象135
5.1.3Vector的操作135
5.1.4从Vector对象中选择元素136
5.1.5作为参数传递Vector对象137
5.1.6创建预先定义大小的Vector138
5.1.7Vector类的构造函数141
5.1.8Vector中的操作符142
5.1.9表示二维结构143
5.1.10Stanford类库中的Grid类143
5.2Stack类144
5.2.1Stack类结构145
5.2.2栈和小型计算器145
5.3Queue类148
5.3.1仿真和模型149
5.3.2排队模型149
5.3.3离散时间150
5.3.4仿真时间中的事件150
5.3.5实现仿真151
5.4Map类154
5.4.1Map类的结构154
5.4.2在一个应用中使用Map类156
5.4.3Map类作为关联数组157
5.5Set类158
5.5.1实现
5.5.2创建单词列表160
5.5.3Stanford类库中的Lexicon类161
5.6在集合上进行迭代162
5.6.1迭代顺序163
5.6.2再论儿童黑话164
5.6.3计算单词的频率165
本章小结167
复习题168
习题168
第6章 类的设计178
6.1 二维点的表示178
6.1.1 将Point定义为结构类型178
6.1.2 将Point定义为类179
6.1.3 接口与实现的分离182
6.2 操作符重载184
6.2.1 重载插入操作符184
6.2.2 判断两个点是否相等186
6.2.3 为Direction类型增加操作符189
6.3 有理数191
6.3.1 定义新类的机制192
6.3.2 采用用户的观点193
6.3.3 确定Rational类的私有实例变量193
6.3.4 为Rational类定义构造函数193
6.3.5 为Rational类定义方法194
6.3.6 实现Rational类196
6.4 token扫描器类的设计198
6.4.1 用户想从记号扫描器中得到什么199
6.4.2 tokenscanner.h接口200
6.4.3 实现TokenScanner类202
6.5 将程序封装成类205
本章小结207
复习题207
习题208
第7章 递归简介215
7.1 一个简单的递归例子215
7.2 阶乘函数217
7.2.1 fact的递归公式217
7.2.2 追踪递归过程218
7.2.3 递归的稳步跳跃221
7.3 斐波那契函数222
7.3.1 计算斐波那契数列项222
7.3.2 在递归实现中获得自信223
7.3.3 递归实现的效率224
7.3.4 递归不应被指责225
7.4 检测回文226
7.5 二分查找算法228
7.6 间接递归229
7.7 递归地思考230
7.7.1 保持全局的观点230
7.7.2 避免常见的错误231
本章小结232
复习题233
习题234
第8章 递归策略237
8.1 汉诺塔237
8.1.1 问题框架238
8.1.2 找到一种递归策略238
8.1.3 验证这个策略240
8.1.4 编码方案241
8.1.5 跟踪递归过程242
8.2 子集求和问题245
8.2.1 寻找一个递归解决方案246
8.2.2 包含/排除模式246
8.3 字符排列247
8.4 图的递归249
8.4.1 一个来自计算机艺术的实例250
8.4.2 分形252
本章小结254
复习题255
习题255
第9章 回溯算法264
9.1 迷宫的递归回溯264
9.1.1 右手法则264
9.1.2 寻找一种递归方法265
9.1.3 确定简单情况266
9.1.4 对迷宫问题的解决算法进行编码267
9.1.5 说服你自己那个方案可行269
9.2 回溯与游戏271
9.2.1 拿子游戏272
9.2.2 一个通用的双人游戏程序276
9.3 最小最大算法277
9.3.1 游戏树278
9.3.2 评价位置和走法278
9.3.3 限制递归搜索的深度280
9.3.4 实现最小最大算法280
本章小结282
复习题282
习题283
第10章 算法分析291
10.1 排序问题291
10.1.1 选择排序算法291
10.1.2 性能的经验评估292
10.1.3 分析选择排序算法的性能293
10.2 时间复杂度294
10.2.1 大O符号295
10.2.2 大O的标准简化295
10.2.3 选择排序算法的时间复杂度295
10.2.4 从代码中降低时间复杂度296
10.2.5 最坏情况以及平均情况下的复杂度297
10.2.6 大O符号的正式定义298
10.3 递归的终止300
10.3.1 分治策略的作用300
10.3.2 合并两个矢量301
10.3.3 归并排序算法301
10.3.4 归并排序的计算复杂度302
10.3.5 比较N2与N log2 N的性能304
10.4 标准的算法复杂度类别304
10.5 快速排序算法306
10.5.1 划分矢量308
10.5.2 快速排序算法的性能分析310
10.6 数学归纳法311
本章小结313
复习题314
习题315
第11章 指针和数组320
11.1 内存结构320
11.1.1 位、字节和字320
11.1.2 二进制和十六进制表示321
11.1.3 表示其他数据类型322
11.1.4 内存地址323
11.1.5 为变量分配内存325
11.2 指针326
11.2.1 把地址当作数值327
11.2.2 声明指针变量327
11.2.3 基本的指针运算328
11.2.4 指向结构和对象的指针330
11.2.5 关键字this331
11.2.6 特殊的指针NULL331
11.2.7 指针和引用调用332
11.3 数组334
11.3.1 声明数组334
11.3.2 数组元素的选择335
11.3.3 数组的静态初始化335
11.3.4 有效容量和分配容量336
11.3.5 指针和数组的关系336
11.4 指针运算338
11.4.1 数组索引和内存地址338
11.4.2 指针的自增自减运算339
11.4.3 C风格字符串339
11.4.4 指针运算和程序风格341
本章小结341
复习题342
习题344
第12章 动态内存管理347
12.1 动态分配和堆347
12.1.1 new操作符348
12.1.2 动态数组348
12.1.3 动态对象349
12.2 链表349
12.2.1 刚铎灯塔349
12.2.2 链表内的迭代352
12.2.3 递归和列表352
12.3 释放内存352
12.3.1 delete操作符352
12.3.2 释放内存策略353
12.3.3 析构函数354
12.4 定义CharStack类354
12.4.1 charstack.h接口355
12.4.2 选择字符栈的表示357
12.5 堆-栈图361
12.6 单元测试366
12.7 拷贝对象368
12.7.1 深拷贝和浅拷贝368
12.7.2 赋值和拷贝构造函数369
12.8 关键字const的使用371
12.8.1 常量定义371
12.8.2 常量引用调用372
12.8.3 const方法372
12.9 CharStack类的效率376
本章小结377
复习题378
习题379
第13章 效率和表示383
13.1 编辑文本的软件模式383
13.2 设计简单的文本编辑器384
13.2.1 编辑器命令384
13.2.2 EditorBuffer类的公有接口385
13.2.3 选择一种底层表示387
13.2.4 编写编辑器应用代码388
13.3 基于数组的类实现389
13.3.1 定义私有数据结构390
13.3.2 缓冲区操作的实现390
13.3.3 基于数组的编辑器的时间复杂度393
13.4 基于栈的类实现394
13.4.1 定义私有数据结构394
13.4.2 缓冲区操作的实现395
13.4.3 时间复杂度的比较397
13.5 基于列表的类实现397
13.5.1 链表缓冲区的插入操作400
13.5.2 链表缓冲区的删除操作402
13.5.3 链表表示法中光标的移动403
13.5.4 缓冲区实现的完善405
13.5.5 基于链表的缓冲区的时间复杂度407
13.5.6 双向链表408
13.5.7 时空权衡408
本章小结409
复习题409
习题410
第14章 线性结构414
14.1 模板414
14.2 栈的实现416
14.2.1 使用动态数组实现栈416
14.2.2 使用链表实现栈420
14.3 队列的实现426
14.3.1 基于数组的队列实现427
14.3.2 队列的链表表示433
14.4 实现矢量类437
14.5 集成原型和代码442
本章小结442
复习题443
习题444
第15章 映射446
15.1 使用矢量实现映射447
15.2 查找表449
15.3 哈希451
15.3.1 设计数据结构451
15.3.2 为字符串定义哈希函数452
15.3.3 实现哈希表454
15.3.4 跟踪哈希表的实现456
15.3.5 调整桶的数目457
15.4 实现HashMap类458
本章小结459
复习题460
习题461
第16章 树463
16.1 家谱463
16.1.1 用来描述树的术语463
16.1.2 树的递归特性464
16.1.3 用C++语言表示家谱464
16.2 二叉搜索树465
16.2.1 使用二叉搜索树的动机466
16.2.2 在二叉搜索树中寻找节点467
16.2.3 在二叉搜索树中插入一个新节点468
16.2.4 删除节点471
16.2.5 树的遍历472
16.3 平衡树473
16.3.1 平衡树策略474
16.3.2 可视化AVL算法475
16.3.3 单旋转476
16.3.4 双旋转478
16.3.5 实现AVL算法478
16.4 使用BST实现映射482
16.5 偏序数482
本章小结485
复习题485
习题487
第17章 集合494
17.1 集合作为一种数学抽象494
17.1.1 隶属关系494
17.1.2 集合运算495
17.1.3 集合恒等式496
17.2 集合接口的扩展497
17.3 集合的实现策略500
17.4 优化小整数的集合504
17.4.1 特征向量 504
17.4.2 压缩的位数组505
17.4.3 位操作符506
17.4.4 实现特征向量507
17.4.5 实现高级集合运算509
17.4.6 模板特化509
17.4.7 使用一种混合的实现509
本章小结510
复习题511
习题512
第18章 图514
18.1 图的结构514
18.1.1 有向图和无向图515
18.1.2 路径和回路516
18.1.3 连通性516
18.2 表示策略517
18.2.1 用邻接表表示连接关系517
18.2.2 用邻接矩阵表示连接关系518
18.2.3 用弧集合表示关系519
18.3 一种低层的图抽象520
18.4 图的遍历524
18.4.1 深度优先搜索524
18.4.2 广度优先搜索527
18.5 定义图类528
18.5.1 用类表示图、节点和弧528
18.5.2 用参数化的类实现图529
18.6 寻找最短路径538
18.7 搜索网页的算法542
18.7.1 谷歌的网页排名算法542
18.7.2 网页排名算法的一个简例543
本章小结544
复习题545
习题546
第19章 继承551
19.1 简单的继承551
19.1.1 指定模板类中的类型551
19.1.2 定义Employee类552
19.1.3 C++中子类的局限性554
19.2 图形对象的继承层次556
19.2.1 调用父类的构造函数561
19.2.2 将GObject类指针存储在矢量中563
19.3 表达式的类层次563
19.3.1 异常处理565
19.3.2 表达式结构566
19.3.3 表达式的递归定义566
19.3.4 二义性567
19.3.5 表达式树568
19.3.6 exp.h接口570
19.3.7 Expression子类的表示573
19.3.8 表达式图解573
19.3.9 方法的实现574
19.4 解析表达式577
19.4.1 语句解析和语法577
19.4.2 考虑运算的优先级578
19.4.3 递归下降语法分析器579
19.5 多重继承584
19.5.1 stream类库中的多重继承584
19.5.2 在GObject继承层次中添加GFillable类585
19.5.3 多重继承的危险性586
本章小结586
复习题587
习题589
第20章 迭代策略595
20.1使用迭代器595
20.1.1简单的迭代器例子595
20.1.2迭代器的层次结构597
20.2使用函数作为数据值598
20.2.1函数指针598
20.2.2简单的画图应用598
20.2.3声明函数指针600
20.2.4 实现plot函数600
20.2.5映射函数601
20.2.6实现映射函数603
20.2.7回调函数的限制603
20.3用函数封装数据604
20.3.1使用对象模拟闭包604
20.3.2函数对象的简单例子605
20.3.3向映射函数传递函数对象606
20.3.4编写以函数作为参数的函数607
20.4STL算法库607
20.5C++的函数式编程609
20.5.1 STL库
20.5.2 比较函数612
20.6 迭代器的实现612
20.6.1 为矢量类实现迭代器612
20.6.2 将指针作为迭代器616
20.6.3 typedef关键字617
20.6.4 为其他集合类实现迭代器618
本章小结618
复习题619
习题619
索引624
