绪言——致成长中的程序员们 1
一、为什么要使用C＋＋？ 1
第一部分 理论基础 1
二、为什么要使用STL？ 3
三、编程的一些规范 4
四、应当使用什么开发环境？ 7
第1章 数据结构导论 11
1.1 数据结构与算法 11
1.1.1 数据结构 11
1.1.2 算法 13
1.2 数据结构的抽象形式——抽象数据类型 13
1.2.1 抽象数据类型 13
1.2.2 应用程序编程接口（API） 14
1.3 C＋＋类和抽象数据类型 15
1.3.1 C＋＋类 15
1.2.3 维护程序和文档 15
1.3.2 继承性 16
1.3.3 多态性 17
1.3.4 泛型设计和模板 18
1.4 运算与算法 19
1.4.1 运算 19
1.4.2 算法 20
1.5 算法分析 21
1.5.1 时空性能 21
1.5.2 时间复杂度分析 21
1.5.3 空间复杂度分析 25
1.5.4 算法分析与代码优化调整 26
第2章 C＋＋语言概述 27
2.1 C＋＋语言的演化和标准化历程 27
2.2 C＋＋支持的程序设计风格 30
2.2.1 基于过程的程序设计 31
2.2.2 基于对象的程序设计 32
2.2.3 面向对象的程序设计 33
2.2.4 泛型程序设计 34
2.3 模块化程序设计 34
2.3.1 函数 34
2.3.2 类和封装机制 40
2.4 类的构造、析构和赋值 40
2.4.1 构造函数和析构函数 40
2.4.2 类的赋值 41
2.5 类层次结构——继承和多态 43
2.5.1 访问控制：public、private和protected继承 43
2.5.2 虚函数与多态 45
2.6 异常处理 46
2.6.1 异常处理的应用情况 46
2.6.2 异常处理基础知识 46
2.7 推荐的编程习惯和风格 48
2.6.3 其他错误处理技术 48
第3章 C＋＋模板编程入门 52
3.1 类模板 53
3.1.1 如何定义类模板 53
3.1.2 如何实现类模板的成员函数 53
3.1.3 如何使用类模板 55
3.2 函数模板 56
3.2.1 如何定义函数模板 56
3.3 模板实例化 57
3.2.2 如何使用函数模板 57
3.4 模板的特化 61
3.4.1 类模板的特化 61
3.4.2 函数模板的特化 65
3.5 模板参数 66
3.6 静态成员和变量 69
3.7 模板和friend 71
3.8.2 函数对象的使用 72
3.8.1 如何定义函数对象 72
3.8 函数对象（仿函数） 72
3.8.3 模板函数对象 73
3.8.4 标准库中的函数对象 73
第4章 泛型设计、STL库与数据结构 75
4.1 标准C＋＋与STL 76
4.1.1 模板——现代C＋＋风格的基础 76
4.1.2 STL的发展历程 77
4.1.3 STL与C＋＋标准程序库 78
4.1.4 STL的实现版本 80
4.1.5 准标准程序库：Boost库 81
4.1.6 泛型算法与STL的应用展示 83
4.2 泛型程序设计与多态 89
4.2.1 面向对象程序设计中的多态 89
4.2.2 泛型程序设计中的多态 90
4.2.3 GP与OOP的对比 91
4.3.1 STL库的设计：容器、算法与迭代器 93
4.3 泛型程序设计与STL 93
4.3.2 Accumulate函数示例 95
4.4 概念与模型 96
4.4.1 必要条件集合 96
4.4.2 示例：迭代器 97
4.5 关联类型与特性类 98
4.5.1 函数模板中需要的关联类型 98
4.5.2 类中的typedef嵌套 98
4.5.3 特性类的定义 99
4.5.4 部分特化 100
4.5.5 标签分派 101
4.6 STL中的核心concept：迭代器剖析 102
4.6.1 迭代器概述 102
4.6.2 迭代器与索引的比较 103
4.6.3 STL的迭代器分类 103
4.6.4 STL中迭代器种类的选择 109
4.7 STL的其他组件 111
4.7.1 STL的数据结构：容器 111
4.7.2 STL算法 113
4.7.3 函数对象 114
4.7.4 适配器 115
4.7.5 分配器 117
第二部分 基础数据结构 118
第5章 线性表 118
5.1 线性表概述 118
5.1.1 线性表基础知识 118
5.1.2 线性表类ADT 119
5.2 顺序存储结构——顺序表 120
5.2.1 顺序表的定义及特点 120
5.2.2 顺序表的遍历与查找 120
5.2.3 顺序表的其他操作 122
5.2.4 顺序表类ADT以及类定义 123
5.3 链式存储结构——链表 125
5.3.1 单链表 126
5.3.2 双向链表 128
5.3.3 循环链表 130
5.3.4 链表类ADT以及类定义 130
5.4 vector的基本操作及应用 133
5.4.1 vector迭代器 133
5.4.2 vector的基本操作 133
5.5 list的基本操作及应用 145
5.5.1 list迭代器 145
5.5.2 list的基本操作 145
5.6 slist的基本操作及应用 152
5.6.1 slist的迭代器 152
5.6.2 slist的基本操作 152
5.7 线性表的应用案例 154
5.7.1 稀疏多项式的加法和乘法 154
5.7.2 大整数加法 160
第6章 栈与队列 167
6.1 双端队列 167
6.1.1 deque概况 167
6.1.2 操作与应用 168
6.2 堆栈基础 169
6.2.1 堆栈的定义 169
6.2.2 堆栈ADT 170
6.3 栈的使用 171
6.3.1 进制转换 171
6.3.2 列车调度 172
6.4 表达式计算 174
6.4.1 中缀表达式转换为后缀表达式 174
6.4.2 后缀表达式的计算 178
6.4.3 测试 180
6.5.1 队列的定义 181
6.5 队列和优先队列 181
6.5.2 队列ADT 182
6.5.3 队列的实现 183
6.5.4 优先队列 184
6.6 使用队列 185
6.6.1 时间驱动的模拟 185
6.6.2 基数排序法 189
6.7 栈与队列的综合实例 192
6.7.1 农夫过河问题 192
6.7.2 深度优先搜索算法 195
6.7.3 广度优先搜索算法 197
第7章 递归 199
7.1 递归基础 199
7.1.1 递归的概念 199
7.1.2 使用递归的情况 200
7.2.2 问题的递归求解 202
7.2.1 问题的提出 202
7.2 汉诺塔问题 202
7.2.3 Hanoi类 205
7.3 迷宫问题 206
7.3.1 问题的提出 207
7.3.2 迷宫的回溯分析 207
7.3.3 Maze类 209
7.4 八皇后问题 212
7.4.1 问题的描述 212
7.4.2 八皇后问题的回溯分析 213
7.4.3 QueenChess类的设计 214
7.5 递归算法的评价 217
7.5.1 递归工作栈 217
7.5.2 递归算法的复杂度 218
7.5.3 递归与迭代的比较 219
8.1.1 序列容器与有序关联容器 221
8.1 树和二叉树基础知识 221
第8章 树和二叉树 221
8.1.2 广义树结构 222
8.1.3 二叉树的定义与性质 223
8.1.4 二叉树遍历算法 225
8.1.5 二叉树遍历算法的应用 226
8.2 二叉搜索树基础知识 228
8.2.1 二叉搜索树的定义 228
8.2.2 二叉搜索树的操作 229
8.2.3 二叉搜索树类ADT 230
8.2.4 二叉搜索树的结构 231
8.2.5 二叉搜索树的实现要点 232
8.2.6 二叉搜索树的迭代器 232
8.3 二叉树类算法的实现代码分析 233
8.3.1 二叉树类的声明与接口 233
8.3.2 二叉树的遍历操作实现 234
8.3.3 树遍历算法的应用 235
8.3.4 二叉树相关算法的测试程序 239
8.4 二叉搜索树类的实现代码分析 242
8.4.1 二叉搜索树节点和树类的声明 242
8.4.2 构造函数、析构函数和赋值运算符 245
8.4.3 二叉搜索树的查找与更新操作 247
8.4.4 二叉搜索树的测试程序 251
8.5 二叉搜索树应用案例 256
8.5.1 消除重复项 256
8.5.2 音像商店事务管理系统 258
第9章 图 266
9.1 图的抽象 267
9.1.1 图的描述 267
9.1.2 图的数据结构 270
9.2 图的算法 272
9.2.1 图搜索算法 272
9.2.2 拓扑排序 275
9.2.3 连通分量算法 277
9.2.4 最短路径问题 278
9.2.5 最小生成树问题 282
9.3 Boost图库介绍 285
9.3.1 STL中的泛型 285
9.3.2 BGL中的泛型 286
9.3.3 BGL中的图算法 287
9.3.4 BGL实现的数据结构 287
9.3.5 BGL的历史 288
9.4 图类的实现与应用 289
9.4.1 图的概念（Concepts） 289
9.4.2 图类的实现 293
9.4.3 图类应用示例 298
9.5 图算法的实现和应用 302
9.5.1 访问器 302
9.5.2 图遍历算法的应用 306
9.5.3 拓扑排序的应用 309
9.5.4 最短路径算法的应用 310
9.5.5 最小生成树算法的应用 314
9.6 图的建模与可视化——Graphviz软件与DOT语言 317
9.6.1 核心绘图引擎 318
9.6.2 图文件描述语言——DOT语言 319
9.6.3 Graphviz应用示例 322
第三部分 综合应用 329
第10章 综合应用案例 329
10.1 数据压缩——霍夫曼编码解码器的实现 329
10.1.1 数据压缩理论简介 329
10.1.2 Huffman树 330
10.1.3 需求分析 332
10.1.4 Huffman压缩类的接口与应用 335
10.1.5 Huffman压缩类的实现 339
10.1.6 Huffman解压缩 345
10.2.1 精确测定算法时间的困难 349
10.2 算法时间复杂度测度——算法计时器的实现 349
10.2.2 应用统计方法解决困难 350
10.2.3 完成自动分析的Timer类 353
10.2.4 应用Timer类测试STL sort算法时间性能 357
10.3 理论计算机科学家族谱的文档／视图模式——STL组件的综合应用 360
10.3.1 系统设计：“模型—视图—控制器”模式 360
10.3.2 数据关系建模与数据结构选择 362
10.3.3 从源数据文档到视图 364
10.3.4 完整的族谱视图程序以及运行示例 370
10.4 词典检索系统——数据结构选择对系统性能影响的示例 373
10.4.1 解决方案1：应用全排列的方法查找变位词 374
10.4.2 解决方案2：应用pair向量改进时间效率 377
10.4.3 解决方案3：使用映射改进空间效率 382
附录A Boost安装指南 386
附录B 随书所附光盘内容清单 391
附录C STL库容器类速查手册 392