本书是数据结构案例教程，以软件重用为指导思想，以STL库中实现的数据结构(容器)为参照，重构了数据结构的视角和知识体系，并突出实战性和应用性。

本书具体内容安排如下：第一部分是理论基础，包括绪论和第1、2、3、4章，介绍数据结构和算法的基础知识，C++语言的关键特征以及支撑STL设计的核心理念和机制。第二部分是基础数据结构，从第5章到第9章，涵盖了基础的数据结构，并包含丰富的例子。第三部分(即第10章)是综合应用，包括4个大的案例，是对前面章节所讲的基础数据结构的综合应用。本书附带的光盘中包含经过主流C++编译器编译通过的所有程序的源代码及编译后生成的可执行程序和第三方软件。

本书将C++泛型编程知识与数据结构知识紧密地结合在了一起，是国内比较罕见的、有技术深度的、符合现代发展方向的优秀教材/教辅读物。

本书适合于在校信息科学与技术类学生作为课程设计指导用书，亦可随数据结构课程同步学习，也非常适合于工作中的程序员以更加实践化的角度温习和应用数据结构。

　　

　　

前    言

　　

　　信息技术正在渗透到人类社会生产、生活的各个方面，作为信息技术灵魂的软件，其规模持续膨胀，在社会的正常运行中扮演着日益重要的角色。而软件开发的节奏也越来越快，应对这一挑战的不二法门，在于重用(reuse)。从汇编语言、C语言，到C++、Java的流行，是基础设计方法重用程度的提高：从指令语句到函数，从对象到构件，支持重用的语言机制日渐成熟。从20世纪60年代到现在，软件工程持续演进，且引起大家的普遍重视，也是为了提高软件开发的重用性：能重用优秀的、以往开发好的可靠模块(库，构件)。使新开发的功能也能很好地模块化，是软件工程努力的一个重要目标。要成长为一个专业的程序员，在入门开始就对重用性和软件工程有清醒的认识，是很有必要的。

　　在软件开发领域中，从事数据库方向的人员，可以不甚了解硬件体系结构；从事计算机图形学的人员，可以不懂SQL语言；做处理器设计的人员，也可以不了解数据仓库。但是他们都必须要掌握数据结构和算法，因为这是程序的灵魂。各种基础的数据结构，是程序中的基础构件。在越来越重视重用性的今天，一种设计良好的、健壮的、高效的基础库的出现也是必然的。

　　C语言和它的标准库本身，只提供了数组和结构体这样的基础结构，及过程化的几种排序算法，远不能达到基本重用库的规模。标准C++语言却应时代呼声，产生了这样的可重用的数据结构库——在C++语言里被称作容器，也提供了大量普遍适用的算法。C++标准库的重要组成部分：标准模板库(Standard Template Library，STL)则提供了完整的               实现。

　　本书正是在这样的背景下，以软件重用为指导思想，以STL库中实现的数据结构(容器)为参照，重构了数据结构的视角和知识体系。与高校现行的数据结构教材相比，本书最大的特色，就是实战性强、应用性强。不得不看到，许多学生在学完数据结构这门课程后，懂得了二叉树、图结构的性质和应用，但在实际实践中，自己去实现这些结构时，却又勉为其难了。从应用的角度看，这样的教学不算是成功的。因此我们策划了一本新的案例教程——就是您手头上的这本书。

　　本书从STL出发，从各种数据结构的应用角度出发，给读者讲解这些结构和在C++标准库中的实现，而不纠缠于各种细节。对程序设计和软件开发而言，STL是程序员手中的金刚钻，可以节省大量时间，去做好“瓷器活儿”；对于编程技术而言，STL是智囊和武库器，与编程工作最有直接关系的数据结构和算法，STL都有实现，并且充分优化，效率最优。此外，STL的设计理念，更具有可学习与可借鉴性，STL中对象的耦合性低，重用性高，各种构件独立设计，又能够灵活地互相组合。从应用角度看，任何一位程序员都不该舍弃现成的工具和方案，来重新造一个轮子(那是违背时代潮流和软件工程原则的)。我们编写这本书，就是为搭建攀上巨人肩膀的阶梯。

　　本书的一大特色，是对图结构库的处理，STL库涵盖了数据结构中所有的线性结构和树结构(以map和set方式)，但并没有覆盖图部分。为此，我们引入了与STL设计风格完全一致同时具有工业强度、开放源码的Boost Graph Library(BGL)图库，BGL库在C++标准化委员会中，是具有半官方地位的优秀库。这部分的内容，在国内现已发行的同类图书中，尚为解见。读者通过阅读本书第9章，相信必有耳目一新的感觉。

　　本书的另一特色是对编程规范自始至终的强调与遵守，通过严格的规范约束，塑造职业作风。规范本身与语言已经融为一体，在职业程序员圈子里，已经形成一种默认的规则。希望读者对这些规范也能有足够的重视。

　　本书的结构包括三个部分。第一部分：理论基础，即绪论和第1、2、3、4章，讲解数据结构和算法的基础知识、C++语言的关键特征以及支撑STL设计的核心理念和机制。绪论部分给出了针对全书提纲挈领的分析，对于有C++面向对象经验的读者，我们也建议仔细阅读第3、4章，因为泛型设计作为现代C++的设计方式，与经典的面向对象设计有很大的不同。第二部分：基础数据结构，从第5章到第9章，涵盖了基础的数据结构，并包含丰富的例子。第三部分：综合应用(第10章)，由4个大的案例构成，是对前面章节所讲的基础结构的综合应用。

　　本书附带的光盘中包含有经过主流C++编译器编译通过的所有程序的源代码、已编译的可执行文件和第三方软件。

　　本书适合于在校信息科学与技术类学生作为课程设计指导用书，亦可随数据结构课程同步学习，以增强实践能力，也非常适合于工作中的程序员以更加实践化的角度温习和应用数据结构。

　　作为预备知识，学习者应具有一定的C/C++程序设计的基础。但为了降低读者的门槛，在第一部分中，我们择要讲解了C++语言特征，重点讲述了泛型设计。囿于本书的定位和篇幅，不可能十分详细地介绍C++，读者对该语言方面的问题，建议参考本书最后参考文献给出的C++教程类的世界级经典教材。

　　本书的3位主要作者都是有丰富实践经验且工作在一线的程序员，在本书编写过程中，尽力向读者介绍编程语言的最新进展和成果，并从学习者的学习曲线考虑，合理组织，降低学习曲线的陡峭度。

　　李光元负责编写本书的第2章、第6章、第7章内容，吴春芳负责编写本书的第5章内容(清华大学出版社的宋延清负责编写本书的第3章内容)，李建学负责第1章、第4章、第8至第10章内容及全书的统稿工作，其他章节及程序开发由余健、韩阳、黄晓燕、贾音、郭刚、张永宝、李享、陈凯共同完成。

　　在写作过程中，作者们反复斟酌，从章节顺序到程序变量命名、注释文档，都做了精心的安排。

　　尽管本书经过了反复的讨论和推敲，但限于水平，难免有诸多不妥之处，希望读者批评指正，以便再版时改进。可以发电子邮件到ChiensyueLee@gmail.com与作者联系。

　　

　　

　　

　　编  者

　　

目    录

　　

第一部分  理论基础

　　

绪言  ——致成长中的程序员们 1

一、为什么要使用C++? 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.2.3  维护程序和文档 15

1.3  C++类和抽象数据类型 15

1.3.1  C++类 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.6.3  其他错误处理技术 48

2.7  推荐的编程习惯和风格 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.2.2  如何使用函数模板 57

3.3  模板实例化 57

3.4  模板的特化 61

3.4.1  类模板的特化 61

3.4.2  函数模板的特化 65

3.5  模板参数 66

3.6  静态成员和变量 69

3.7  模板和friend 71

3.8  函数对象(仿函数) 72

3.8.1  如何定义函数对象 72

3.8.2  函数对象的使用 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  泛型程序设计与STL 93

4.3.1  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

　　

　　

第二部分  基础数据结构

　　

第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  队列和优先队列 181

6.5.1  队列的定义 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  汉诺塔问题 202

7.2.1  问题的提出 202

7.2.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章  树和二叉树 221

8.1  树和二叉树基础知识 221

8.1.1  序列容器与有序关联容器 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

　　

　　

第三部分  综合应用

　　

第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  算法时间复杂度测度——算法

 计时器的实现 349

10.2.1  精确测定算法时间

的困难 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