本书保持了Liang博士系列丛书中一贯的标志性的教与学的哲学：以实例教，由实践学。通过使用他所提出的已经经过实践检验的“基础先行”的方法，Liang博士在本书中通过大量实例阐明了基本的C++特性，使得学生可以通过实践来更有效地进行学习。
在引入面向对象程序设计思想之前，Liang博士使用清晰简明的语言介绍了C++语言的基础知识和基本的程序设计技术，如循环、逐步求精等。这些概念都是使用简短且吸引人的实例来进行阐明的。他还在实例研究中给出了一些较大规模的实例，并附以整体的分析讨论和详细的逐行注解。
本书首先帮助学生循序渐进地学习所有必需和重要的基本概念，然后再进入到面向对象程序设计方法的学习，最终掌握构建具有异常处理和输入输出功能的有意义的应用程序的方法。贯穿全书的实例和练习都以问题求解为中心，力图培养学生开发可重用组件并用之创建实际项目的意识。
本书特点
●大量的表格和图示。
●较早地介绍编写程序的方法——从第2章开始，学生就能编写简短、有趣的游戏程序。
●使用UML描述类。
●大量的补充资料——安装和配置C++开发环境、IDE简明教程、补充的C++特性等，这些补充资料便于教师设计自己的课程内容。
无
十年来，Java语言的迅猛发展对C++形成了有力的冲击，但十年过去了，C++仍广泛用于工业界的软件开发和高等院校的教学，保持了其流行程序设计语言的地位。Java是开发图形用户界面、Internet应用程序和跨平台应用程序的理想语言，而C++则长于系统级编程（如开发操作系统和编译器）。可以预见，二者仍将会并存、互补。
现有的C++教材已经非常多了。本书区别于其他教材的特色是“基础先行方法”和撰写风格。基础先行方法是指，首先介绍基础的程序设计概念，诸如控制语句、循环、函数及数组，然后再介绍面向对象程序设计。本书的撰写风格可总结为两点：清晰和简明—使用简短且吸引人的例子清晰地阐述概念，而这种阐述是通过很多图表简明地呈现出来。
本书结构
教学方法
C++程序设计的教学方法多种多样。本书采用基础先行方法，首先逐步讲授所有必需和重要的基本概念，然后进入面向对象程序设计的学习，最后是如何利用面向对象方法构建具有错误处理、输入输出和复杂数据结构的有趣的应用程序。
就我个人的经验和我的很多同事的经验来看，程序设计的初学者想要取得成功，学习基础概念和基本程序设计方法（如循环、逐步求精方法等）是必须的。不具备过程式程序设计能力的学生是不可能学好面向对象程序设计方法的。讲授好基本数据类型、控制语句、函数和数组等概念，将为学生学习面向对象程序设计做好准备。
对于要求解的问题，基础先行方法总是先给出过程式的解决方案，然后再展示如何使用面向对象方法加以改进，这是对单纯面向对象程序设计教学的有益补充和强化。学生能学到何时使用，以及如何更有效地使用面向对象程序设计方法。
2005年之前的计算机科学教育大会（Computer Science Education，SIGCSE）上，对象早行（object-early）方法被广泛宣扬，基础先行方法的声音很微弱。目前这种状况已经发生了改变，一些对象早行方法的先前支持者承认遇到了挫折，对象早行方法失败了。本书的特点是基础先行和对象适行（object-right）—介绍基本程序设计方法之后，在恰当的时机引入面向对象程序设计。
程序设计不仅仅是语法、类或者对象那么简单，它的本质是问题求解。循环、函数和数组是解决实际问题的基本程序设计技术。从基本程序设计方法到面向对象程序设计，可抽象为很多层面，类只不过是其中之一。如何将这些层面中的思想应用于软件项目的设计与实现，是软件开发的关键。因此，本书最重要的目标有两个：一是教会学生利用这些抽象层面中的思想、方法求解问题；二是教会学生既能从宏观角度，又能从微观细节看待问题。全书的例子和练习都以问题求解为中心，试图培养学生开发可重用组件并用于创建实际项目的意识。
学习方法
程序设计课程与其他课程是完全不同的。学习一门程序设计课，应该从例子、练习中学习，甚至从错误中汲取知识。需要花很多时间编写程序，进行测试和调试。
对于程序设计的初学者，学习C++与学习任何其他高级程序设计语言没什么不同。基本要点是，在对实际问题设计程序式的解决方案，并利用分支语句、循环和函数将其转化为程序代码这一过程中掌握关键技巧。
一旦掌握了使用循环、函数和数组编写程序的基本技巧，就可以开始学习面向对象程序设计了。你将会学到如何使用类封装和类继承等机制开发面向对象软件。
教学方法学特点
本书作者撰写的系列丛书的共同特点是：以实例教，由实践学。基本的概念和方法都是通过实例来阐明，这样学生可以通过利用例子进行实验来学习。本书通过如下几个方面来帮助读者从大量资料中汲取尽可能多的知识：
目标 列出应该从当前章节中学到什么内容，这能帮助学生判断在完成一章的学习后是否达到了预期目标。
引言 以一个简单的概述作为一章的开始，使学生大致了解这一章会讲些什么内容。
实例 所有例子都是经过精心挑选的，描述方式也经过精心设计，易于学生参照进行实验，通过实例来讲授程序设计基本概念。本书给出了大量短小、简单且具有启发性的例子，来阐明重要的思想。
各章小结 回顾一章中学生必须理解和记忆的重要主题，以帮助他们强化这一章中所学的重要概念。
可选章节 包含非基础的，但是有价值的内容。教师可以讲授这些内容，也可以选择略过，或者稍后再进行讲授。可选章节会以“*”标记。
习题 每节后面都会有习题，帮助学生掌握自己的学习进度，评估学习效果。
程序设计练习 每节后面都会有一些程序设计练习题，使学生可以将学到的程序设计技巧应用于编程实践。程序设计练习按难易程度分为简单（无星号）、中等难度（*）、较为困难的（**）和有挑战性的（***）几个级别。如果说学习程序设计有什么诀窍的话，那就是实践，实践，再实践。为此，本书提供了非常多的程序设计练习。
交互式的自我测试 在本书的配套网站上提供了自我测试功能，学生可在线进行交互式的自我测试。网站提供了1 000多道多项选择题，均按章节组织。教师资源网站则有试卷生成功能，提供了更多的多项选择题。
注、提示和警告 这三类文字会贯穿全书，用来给出有价值的建议，以及对要点内容的提示。
注 给出相关主题的额外信息，强化重要概念。
提示 介绍良好的编程风格和习惯。
警告 帮助学生避免编程中易犯的错误。
章节相关性
下面的图表给出了各章之间的相关性。注意，第8章、第12章和第13章的讲授顺序可灵活掌握。
C++开发工具
可以使用Windows记事本或写字板等文本编辑器编辑C++程序，然后在控制台中通过命令行方式编译和运行程序。当然也可以使用C++开发工具，如Visual C++、Dev-C++和C++ Builder。这些工具都提供一个集成开发环境（integrated development environment，IDE），帮助用户快速开发C++程序。程序的编辑、编译、生成、运行和调试等功能都集成在一个图形用户界面内。有效地使用这些开发工具，可以极大地提高编程效率。第1章将介绍如何使用Visual C++和Dev-C++创建、编译和运行程序。配套网站提供了补充资料，其中详细介绍了Visual C++和C++ Builder的使用。
本书的所有程序都已在Visual C++、C++ Builder及GNU C++编译器中进行了测试。
配套网站
本书配套网站的网址是www.prenhall.com/liang或www.cs.armstrong.edu/liang/cpp，网站包含了如下内容：①习题答案；②编号为偶数的程序设计练习的参考解答；③本书所有例子的源代码；④按章节组织的交互式自我测试；⑤补充资料；⑥其他资源的链接；⑦勘误表。
补充资料
补充资料是本书内容的延伸，介绍了读者可能感兴趣的其他一些内容。下列补充资料都已放在配套网站上。
教师资源网站
教师资源网站网址为www.prenhall.com/liang，包含如下内容：
显示源码的PowerPoint幻灯片，能以彩色、高亮等方式区别显示不同语法结构，具有用户交互功能，可不脱离幻灯片运行程序。
试卷样例，一般每份试卷包含四个部分：
1. 多项选择题或简答题（大多数题目与配套网站的自我测试题不同）。
2. 程序查错。
3. 读程序写结果。
4. 程序设计。
所有程序设计练习题的参考解答，学生在配套网站只能得到偶数题目的解答。
基于Web的试卷生成工具。（教师可生成指定章节的测试题，题目出自一个有2 000多道题的数据库。）
在线测验。（学生可对每章进行在线测验，测验报告将会发送给教师。）
一些读者向作者索取教师资源网站中的资料。请大家理解这些资料仅供教师使用，因此，对此类请求不予答复。
致谢
我要感谢Ray Greenlaw及我在阿姆斯特朗大西洋州立大学的同事，他们给了我讲授C++程序设计相关课程的机会，并对本书的写作提供了大力支持。感谢我C++课程的学生们，他们帮我校对了本书的草稿。
特别要感谢下列审校者：
Dan Lipsa 阿姆斯特朗大西洋州立大学
Hui Liu 密苏里州立大学
Ronald Marsh 北达科他州立大学
Charles Nelson Rock Valley学院
Martha Sanchez 得克萨斯大学达拉斯分校
Kate Stewart 塔拉哈西社区学院
Margaret Tseng 蒙哥马利学院
Barbara Tulley 伊丽莎白镇学院
非常荣幸能与Prentice Hall公司合作。感谢Marcia Horton、Tracy Dunkelberger、Robin O誃rien、Christianna Lee、Carole Snyder、Mack Patterson、Vince O誃rien、Camille Trentacoste、Xiaohong Zhu、Rose Kernan和他们的同事们为这个项目的组织、实施和推进所做的工作，还要感谢Shelly Gerger-Knechtl的编辑工作和Scott Disanno的校对工作。
一如既往，我要感谢我的妻子Samantha，感谢她的爱、她的支持和鼓励。
Y. Daniel Liang
liang@armstrong.edu
www.cs.armstrong.edu/liang/cpp
本书保持了Liang博士系列丛书中一贯的标志性的教与学的哲学：以实例教，由实践学。通过使用他所提出的已经经过实践检验的“基础先行”的方法，Liang博士在本书中通过大量实例阐明了基本的C++特性，使得学生可以通过实践来更有效地进行学习。 在引入面向对象程序设计思想之前，Liang博士使用清晰简明的语言介绍了C++语言的基础知识和基本的程序设计技术，如循环、逐步求精等。这些概念都是使用简短且吸引人的实例来进行阐明的。他还在实例研究中给出了一些较大规模的实例，并附以整体的分析讨论和详细的逐行注解。 本书首先帮助学生循序渐进地学习所有必需和重要的基本概念，然后再进入到面向对象程序设计方法的学习，最终掌握构建具有异常处理和输入输出功能的有意义的应用程序的方法。贯穿全书的实例和练习都以问题求解为中心，力图培养学生开发可重用组件并用之创建实际项目的意识。 本书特点 ●大量的表格和图示。 ●较早地介绍编写程序的方法——从第2章开始，学生就能编写简短、有趣的游戏程序。 ●使用UML描述类。 ●大量的补充资料——安装和配置C++开发环境、IDE简明教程、补充的C++特性等，这些补充资料便于教师设计自己的课程内容。
Y. Daniel Liang：Y. Daniel Liang : Y. Daniel Liang 普度大学终身教授，阿姆斯特朗亚特兰大州立大学计算机科学系教授。他所编写的Java教程在美国大学Java课程中采用率最高，同时他还兼任Prentice Hall Java系列丛书编辑。
王刚 刘晓光 刘璟：暂无简介
设计高效稳定、具有专业水准的计算机软件，需要具备多方面的能力，例如，熟悉应用领域的相关知识，能合理地选择和设计各种数据结构和算法，精通软件工程相关知识和方法等。但无论如何，熟练的编程技巧仍是必备的基础能力。因为，无论多么丰富的领域知识，多么高效的数据结构和算法，多么良好的软件架构，最终都需要转化为计算机程序，才能被计算机所理解，进而指挥计算机按照人类的设想求解问题。在计算机发展的早期，人们必须通过在纸带上打孔的方式编写计算机程序。高级程序设计语言的出现，大大降低了人类与计算机沟通的难度。但计算机还未发展到能理解人类语言、动作、表情的程度，人们还是需要学习程序设计语言的语法和程序设计技巧，才能高效地与计算机沟通。C++是在C语言的基础上发展起来的，它继承了C语言的诸多优点。而面向对象程序设计特性的加入，又大大提高了程序开发、维护的效率。因此，十几年来，C++一直是使用最广泛的计算机高级程序设计语言之一。
本书的作者Y. Daniel Liang教授是国际知名的计算机教育家和专业书籍作家。多年来一直致力于教学方法的改革和教材的撰写，已与Prentice Hall公司合作出版了30余本计算机科学领域的专业书籍。这些书籍行销全世界，特别是Liang Java系列丛书，是最畅销的Java教材，被世界各地的高等院校广泛采用。本书是他在C++领域奉献给广大读者的最新力作。
本书分为三部分。第一部分介绍基础程序设计方法，包括基本数据类型和运算、分支语句、循环、函数、数组、指针和C字符串以及递归等内容。第二部分介绍面向对象程序设计方法，主要包括对象和类的基本概念、对象和类的深入内容、继承和多态、文件输入和输出、运算符重载及异常处理等内容。第三部分介绍了数据结构方面的基础知识，包括模板、链表、栈、队列、树、堆、优先队列、算法效率、排序算法、STL容器、STL算法等内容。
“基础先行方法”是本书区别于其他同类教材的最大特色。这种方法是指，并不在教学开始之初向学生介绍面向对象程序设计方法，而是首先介绍分支语句、循环、函数、数组等基础的程序设计方法，随后再引入面向对象程序设计方法。这种方法有利于学生循序渐进地掌握C++语言的程序设计技巧，已被国际计算机教育学届广泛接受。本书的另一特色是“清晰简明”的撰写风格，通过简短的、吸引人的例子来清晰地阐述概念，更容易提高学生学习的兴趣。
如果你还是个计算机程序设计的门外汉，本书可以将你引入这个广阔而引人入胜的领域；如果你对C++程序设计已经有所了解，本书也是一本很好的参考书籍。当然，如果你是一名计算机专业的在校学生，本书将是一本不可多得的高级语言程序设计课程的教材。
参与本书翻译工作的有王刚、刘晓光和刘，由王刚完成全书的审校工作。因时间仓促，翻译若有不妥之处，敬请读者批评指正。
译 者
2008年6月于南开
译者序
前言
第一部分 程序设计基础
第1章 计算机、程序和C++语言简介 2
1.1 引言 2
1.2 什么是计算机 2
1.2.1 CPU 3
1.2.2 内存 3
1.2.3 外存储设备 3
1.2.4 输入输出设备 4
1.2.5 通信设备 5
1.3 程序 5
1.4 操作系统 6
1.4.1 控制和监视系统活动 6
1.4.2 分配和指派系统资源 6
1.4.3 任务调度 7
*1.5 数制 7
1.5.1 二进制数与十进制数之间的转换 7
1.5.2 十六进制数与十进制数之间的
转换 8
1.5.3 二进制数与十六进制数之间的
转换 9
1.6 C++语言的历史 9
1.7 一个简单的C++程序 10
1.8 C++程序开发周期 11
*1.9 使用Visual C++开发C++程序 12
1.9.1 起步 12
1.9.2 创建项目 13
1.9.3 创建C++程序 14
1.9.4 编译C++程序 16
1.9.5 运行C++程序 16
*1.10 使用Dev-C++开发C++程序 17
1.10.1 起步 17
1.10.2 创建程序 17
1.10.3 编译C++程序 18
1.10.4 运行C++程序 19
*1.11 用Windows命令行方式开发C++
程序 20
*1.12 在UNIX平台上开发C++程序 21
小结 21
习题 22
程序设计练习 22
第2章 基本数据类型和运算 23
2.1 引言 23
2.2 编写简单的程序 23
2.3 从键盘读取输入 25
2.4 省略std::前缀 26
2.5 标识符 27
2.6 变量 27
2.7 赋值语句和赋值表达式 28
2.8 命名常量 29
2.9 数值数据类型及其运算 30
2.9.1 数值文字常量 31
2.9.2 数值运算符 32
2.9.3 算术表达式 33
2.9.4 简写运算符 34
2.10 数值类型转换 35
2.11 字符数据类型及其运算 37
2.11.1 转义序列表示特殊符号 37
2.11.2 char型和数值型之间的转换 38
2.12 实例研究 38
2.12.1 实例：计算贷款偿还金额 38
2.12.2 实例：计算给定金额的货币数量 40
2.12.3 实例：显示当前时间 42
2.13 程序设计风格和文档 43
2.13.1 适当的注释和注释风格 43
2.13.2 变量和常量的命名 43
2.13.3 恰当的缩进和空白 43
2.14 程序设计错误 43
2.14.1 语法错误 44
2.14.2 运行时错误 44
2.14.3 逻辑错误 44
2.15 调试 45
小结 45
习题 46
程序设计练习 48
第3章 分支语句 50
3.1 引言 50
3.2 bool类型 50
3.3 if语句 51
3.4 实例：猜生日 53
3.5 逻辑运算符 55
3.6 if . . . else语句 57
3.7 嵌套的if语句 58
3.8 实例：计算税款 60
3.9 实例：一个数学学习工具 62
3.10 switch语句 63
3.11 条件表达式 65
3.12 输出格式控制 65
3.13 运算符优先级和结合律 68
3.14 枚举类型 69
小结 71
习题 71
程序设计练习 75
第4章 循环 77
4.1 引言 77
4.2 while循环 77
4.2.1 实例：一个改进的数学学习工具 78
4.2.2 使用用户确认控制循环 80
4.2.3 使用哨兵值控制循环 80
4.3 do-while循环 81
4.4 for循环 82
4.5 使用哪种循环 84
4.6 嵌套的循环 85
4.7 实例研究 86
4.7.1 实例：求最大公约数 86
4.7.2 实例：计算销售额 87
4.7.3 实例：显示数字金字塔 89
*4.8 关键字break和continue 91
4.9 实例：输出素数 92
*4.10 简单文件输入输出 94
4.10.1 向一个文件写入数据 94
4.10.2 从一个文件读取数据 95
4.10.3 检测文件尾 96
小结 97
习题 97
程序设计练习 100
第5章 函数 105
5.1 引言 105
5.2 函数创建 105
5.3 函数调用 106
5.4 无返回值函数 108
5.5 按值方式传递参数 109
5.6 按引用方式传递参数 111
5.7 函数重载 113
5.8 函数原型 115
5.9 默认参数 116
5.10 实例研究：使用函数计算税款 117
5.11 在不同程序中重用函数 118
5.12 实例研究：生成随机字符 119
5.13 变量的作用域 121
5.13.1 for循环中变量的作用域 123
5.13.2 静态局部变量 123
5.14 数学函数 124
5.15 函数抽象和逐步求精 125
5.15.1 自顶向下设计 125
5.15.2 自顶向下或自底向上实现 127
5.15.3 实现细节 128
*5.16 内联函数 131
小结 132
习题 133
程序设计练习 136
第6章 数组 141
6.1 引言 141
6.2 数组基础 141
6.2.1 声明数组 141
6.2.2 数组下标变量 142
6.2.3 数组初始化语句 143
6.2.4 初始化字符数组 143
6.2.5 处理数组 144
6.2.6 实例：测试数组 145
6.2.7 实例：评定成绩等级 146
6.3 数组作为函数参数 147
6.4 数组作为函数返回值 149
6.5 搜索 151
6.5.1 顺序搜索方法 151
6.5.2 二分搜索方法 151
6.6 排序数组 153
6.6.1 选择排序 153
*6.6.2 插入排序 155
6.7 二维数组 156
6.7.1 声明二维数组 156
6.7.2 处理二维数组 157
6.7.3 二维数组作为函数参数 158
6.7.4 实例：评定多项选择测试的成绩 159
*6.7.5 实例：计算纳税额 160
*6.8 多维数组 162
6.8.1 实例：计算学生成绩 162
6.8.2 实例：猜生日 163
小结 164
习题 165
程序设计练习 166
第7章 指针和C字符串 171
7.1 引言 171
7.2 指针基础 171
7.3 用指针实现实参的引用传递 174
7.4 数组和指针 174
7.5 常量指针 176
7.6 指针作为函数返回值 177
7.7 动态内存分配 178
7.8 实例研究：统计每个字母的出现次数 180
7.9 字符和字符串 182
7.9.1 字符串函数 183
7.9.2 字符串存储和访问 184
7.9.3 读取字符串 185
7.9.4 C字符串函数 185
7.9.5 实例：获取子串 189
7.10 实例研究：检查回文串 189
小结 191
习题 191
程序设计练习 193
第8章 递归 196
8.1 引言 196
8.2 实例：阶乘 196
8.3 实例：斐波那契数列 198
8.4 用递归方法求解问题 200
8.5 递归辅助函数 201
8.5.1 选择排序 202
8.5.2 二分搜索 203
8.6 汉诺塔 204
8.7 递归与迭代 207
小结 207
习题 207
程序设计练习 209
第二部分 面向对象程序设计
第9章 对象和类 212
9.1 引言 212
9.2 声明类 212
9.3 构造函数 214
9.4 对象名 214
9.5 声明和实现分离 217
9.6 通过指针访问对象成员 219
9.7 在堆中创建动态对象 220
9.8 C++字符串类 220
9.8.1 构造一个字符串 220
9.8.2 追加字符串 221
9.8.3 字符串赋值 222
9.8.4 函数at、clear、erase和empty 222
9.8.5 函数length、size和capacity 222
9.8.6 字符串比较 222
9.8.7 获得子串 223
9.8.8 字符串搜索 223
9.8.9 字符串插入和替换 223
9.8.10 字符串运算符 223
9.9 数据域封装 224
9.10 变量作用域 226
9.11 this指针 227
9.12 对象作为函数参数 228
9.13 对象数组 230
9.14 类抽象和封装 232
9.15 实例研究：Loan类 232
9.16 构造函数初始化列表 235
小结 237
习题 238
程序设计练习 240
第10章 对象和类的更多内容 243
10.1 引言 243
10.2 不可变对象和不可变类 243
10.3 避免重复声明 245
10.4 实例成员和静态成员 246
10.5 析构函数 250
10.6 拷贝构造函数 252
10.7 自定义拷贝构造函数 254
10.8 友元函数和友元类 256
10.9 对象合成 257
10.10 实例研究：Course类 259
10.11 实例研究：StackOfIntegers类 261
10.12 C++向量类 263
小结 265
习题 265
程序设计练习 268
第11章 继承和多态 269
11.1 引言 269
11.2 基类和派生类 269
11.3 泛型程序设计 275
11.4 构造函数和析构函数 275
11.4.1 调用基类构造函数 275
11.4.2 构造函数链和析构函数链 276
11.5 函数重定义 277
11.6 多态和虚函数 278
11.7 关键字protected 280
11.8 抽象类和纯虚函数 281
11.9 动态类型转换 285
小结 286
习题 287
程序设计练习 291
第12章 文件输入输出 293
12.1 引言 293
12.2 文本输入输出 293
12.2.1 向文件中写入数据 293
12.2.2 从文件中读取数据 294
12.2.3 检测文件是否存在 295
12.2.4 检测文件末尾 296
12.3 格式化输出 297
12.4 成员函数：getline、get和put 297
12.5 fstream和文件打开模式 300
12.6 检测流状态 301
12.7 二进制输入输出 303
12.7.1 write函数 303
12.7.2 read函数 304
12.7.3 实例：二进制数组I/O 305
12.7.4 实例：二进制对象I/O 306
12.8 随机访问文件 309
12.9 更新文件 311
小结 312
习题 313
程序设计练习 313
第13章 运算符重载 315
13.1 引言 315
13.2 Rational类 315
13.3 运算符函数 320
13.4 简写运算符重载 321
13.5 [ ]运算符重载 322
13.6 一元运算符重载 323
13.7 ++和--运算符重载 323
13.8 和运算符重载 324
13.9 对象类型转换 325
13.10 新的Rational类 326
13.11 重载赋值运算符 332
小结 333
习题 333
程序设计练习 334
第14章 异常处理 335
14.1 引言 335
14.2 异常处理概述 335
14.3 异常处理机制的优点 337
14.4 异常类 338
14.5 自定义异常类 341
14.6 多重异常捕获 344
14.7 异常的传播 347
14.8 重抛出异常 349
14.9 异常规约 350
14.10 何时使用异常机制 350
小结 351
习题 351
程序设计练习 353
第三部分 数 据 结 构
第15章 模板 356
15.1 引言 356
15.2 模板基础 356
15.3 实例：一个通用排序函数 358
15.4 模板类 359
15.5 改进Stack类 364
小结 365
习题 366
程序设计练习 368
第16章 链表、栈和队列 369
16.1 引言 369
16.2 节点 369
16.3 链表类 371
16.4 实现LinkedList 373
16.4.1 实现addFirst(T element) 373
16.4.2 实现addLast(T element) 373
16.4.3 实现add(int index, T element) 374
16.4.4 实现removeFirst() 375
16.4.5 实现removeLast() 375
16.4.6 实现removeAt(int index) 377
16.5 链表的变形 382
16.6 使用链表类实现栈类 382
16.7 队列 383
*16.8 迭代器 385
小结 388
习题 388
程序设计练习 390
第17章 树、堆和优先队列 392
17.1 引言 392
17.2 二叉树 392
17.2.1 描述二叉树 392
17.2.2 访问二叉树中的节点 393
17.2.3 向二叉搜索树中插入数据元素 393
17.2.4 树的遍历 394
17.2.5 二叉树类 394
17.3 堆 399
17.3.1 堆的描述 399
17.3.2 堆的删除操作 399
17.3.3 堆的插入操作 400
17.3.4 Heap类 400
17.4 优先队列 403
小结 405
习题 406
程序设计练习 406
第18章 算法效率和排序 408
18.1 引言 408
18.2 评价算法效率 408
18.2.1 大O符号 409
18.2.2 实例：复杂性计算 409
18.2.3 分析二分搜索算法 411
18.2.4 分析选择排序算法 411
18.2.5 分析插入排序算法 412
18.2.6 分析汉诺塔算法 412
18.2.7 常见增长函数比较 412
18.3 起泡排序 413
18.4 归并排序 415
18.5 快速排序 418
18.6 堆排序 421
18.7 外排序 422
18.7.1 实现阶段I 423
18.7.2 实现阶段II 424
18.7.3 合并两个阶段 426
18.7.4 外排序分析 429
小结 429
习题 430
程序设计练习 431
第19章 STL容器 433
19.1 引言 433
19.2 STL基础 433
19.3 STL迭代器 437
19.3.1 迭代器类型 439
19.3.2 迭代器运算符 439
19.3.3 预定义的迭代器 441
19.3.4 istream_iterator和ostream_
iterator 442
19.4 顺序容器 443
19.4.1 顺序容器：vector 443
19.4.2 顺序容器：deque 445
19.4.3 顺序容器：list 446
19.5 关联容器 449
19.5.1 关联容器：set和multiset 449
19.5.2 关联容器：map和multimap 451
19.6 容器适配器 452
19.6.1 容器适配器：stack 452
19.6.2 容器适配器：queue 453
19.7 容器适配器：priority_queue 454
小结 454
习题 455
程序设计练习 457
第20章 STL算法 459
20.1 引言 459
20.2 算法类型 459
20.3 copy 461
20.4 fill和fill_n 462
20.5 generate和generate_n 463
20.6 remove、remove_if、remove_copy
和remove_copy_if 464
20.7 replace、replace_if、replace_copy
和replace_copy_if 466
20.8 find、find_if、find_end和
find_first_of 468
20.9 search和search_n 472
20.10 sort和binary_search 473
20.11 adjacent_find、merge和
inplace_merge 475
20.12 reverse和reverse_copy 476
20.13 rotate和rotate_copy 477
20.14 swap、iter_swap和swap_ranges 478
20.15 count和count_if 479
20.16 max_element和min_element 479
20.17 random_shuffle 480
20.18 for_each和transform 481
20.19 includes、set_union、set_
difference、set_intersection和set_symmetric_difference 481
20.20 accumulate、adjacent_difference、inner_product和partial_sum 484
小结 486
习题 487
程序设计练习 489
附录 491
附录A C++关键字 492
附录B ASCII字符集 493
附录C 运算符优先级表 494
附录D 位运算 495
