C++与数据结构（第3版）

前 言
    本书是北京市高等教育精品教材，编写者是优秀教学团队和北京市优秀教学团队“计算机公共课教学团队”的主要成员。教材的编写以*计算机基础课程教学指导委员会《计算机基础课程教学基本要求》中，有关理工类专业“算法基础与程序设计”课程要求为指导思想，结合教学改革实践，总结了精品课程和北京市精品课程“数据结构与算法设计”的建设经验，坚持以培养学生解决实践问题的能力为特色，以适应信息时代的人才培养模式。
 本书的写作特点
    数据结构是计算机算法设计的基础，在计算机科学中占有非常重要的地位。深入研究数据结构对构造完美算法结构和设计具有重要的作用。程序设计语言是实现算法的载体，语言只有满足算法实现的需求，才能被认识和掌握，数据结构只有通过程序语言才能在应用中发挥作用。因此，本书力求以算法为中介，使学习程序设计语言和学习数据结构共进。
    本书在介绍了 C++语言的程序设计方法的基础上，采用C++程序设计语言描述算法。C++是一种既支持面向过程程序设计，又支持面向对象程序设计的混合型语言，它独特的面向对象特征，可以为面向对象技术提供全面支持，是描述算法的一种较为理想的语言。采用面向对象程序设计语言描述施加与数据结构之上的算法，不仅有利于将面向对象技术相结合，也为上机实践提高高级语言程序设计水平提供了方便。
    本书是在对《C++与数据结构（第2 版）》进行精简和修改基础上完成的，共包括10章。第1 章是对数据结构和面向程序设计方法的概述。从第2 章到第4 章，是C++语言程序设计基础。主要内容是C++编程基础，精炼地介绍了数组与指针、函数、C++类及其对象的封装性、引用、友元和重载、继承与派生、多态性与虚函数、模板以及STL 的相关内容。从第5 章到第10 章，重点介绍典型的数据结构。主要内容包括：线性表、堆栈与队列、
树与二叉树、图、查找与散列结构、排序。全书每章都配有习题以及相应的程序例题和实验题目。
 本书的编排特点
    本书每章均安排有习题和实验训练题，可方便实践教学。
    对书中重要内容采用黑体标注。
    本书强调可读性。书中程序全部采用统一的设计风格。例如，类名和变量名的定义做到“望名知义”；采用缩进格式组织程序；对程序中的语句尽可能多地使用注释。
    本书包含大量的程序示例，给出了运行结果。凡是程序开头带有程序名编号的程序，都是可以直接在计算机中编译运行的程序。对于各章实验训练中的源代码，读者可扫描相应的二维码进行下载。
 教学支持
    本书的电子教案可以在讲课时用多媒体投影演示。教师不仅可以使用本教案，还可以方便地修改和重新组织其中的内容以适应自己的教学需要。使用本教案可以减少教师备课时编写教案的工作量，从而通过教学效果和效率。
    本书向使用本教材的教师免费提供电子教案和程序示例代码。需要的教师可以直接登录华信教育资源网免费注册下载。
    本书由高飞设计总体架构。第1，2 章由薛艳明编写，第3，4 章由白霞编写，第5，6，7 章由高飞编写，第8，9，10 章由聂青编写。全书由高飞、薛艳明统稿和定稿。在本书的编写过程中，北京理工大学信息与电子学院计算机教学团队中许多从事教学工作多年的同仁提出了许多宝贵的建议。电子工业出版社章海涛和袁玺编辑对本书的编写提出了宝贵的意见，在此对他们的辛勤工作和热心帮助一并表示衷心的感谢。
    由于计算机算法和程序设计技术发展迅速，作者水平有限，书中的疏漏与不足在所难免，敬请广大读者和同仁不吝赐教，拔冗指正。感谢您选用本书，欢迎您对本教材提出意见和建议。

于北京理工大学
2014 年10 月

第1 章数据结构的基本概念···1

1.1 数据结构的概念和术语···1

1.2 抽象数据类型···3

1.2.1 数据类型···3

1.2.2 数据抽象与抽象数据类型···4

1.3 算法和算法分析···5

1.3.1 算法···5

1.3.2 算法设计的要求···5

1.3.3 算法效率的度量···6

1.4 面向对象概述···8

1.4.1 面向对象的思想···8

1.4.2 面向对象的基本概念···9

1.4.3 面向对象的基本特性···10

1.4.4 面向对象程序设计···12

1.4.5 面向对象的语言···12

1.5 本章小结···13

习题1 ···13

第2 章数组与指针···14

2.1 数组···14

2.1.1 一维数组···14

2.1.2 多维数组···17

2.1.3 字符数组和字符串···21

2.2 指针···24

2.2.1 指针的概念···24

2.2.2 指针变量定义···25

2.2.3 指针运算···25

2.3 指针与数组···27

2.3.1 指向数组的指针···27

2.3.2 指向字符串的指针···31

2.3.3 指针数组和指向指针的指针···31

2.4 指针与函数···34

2.4.1 指向函数的指针···34

·VI· Page

2.4.2 返回指针值的函数···36

2.5 本章小结···36

习题2 ···37

实验训练2···37

第3 章 C++编程基础···39

3.1 C++语言简介···39

3.2 类···39

3.2.1 访问控制···40

3.2.2 成员函数···42

3.2.3 构造函数与析构函数···44

3.2.4 动态存储···50

3.3 丰富的特性···53

3.3.1 引用···53

3.3.2 友元···59

3.3.3 重载···63

3.4 代码重用机制···67

3.4.1 继承···67

3.4.2 多态···72

3.4.3 模板···76

3.5 本章小结···81

习题3 ···81

实验训练3···82

第4 章 STL 标准模板库···89

4.1 STL 简介···89

4.2 序列式容器···90

4.2.1 vector 容器···90

4.2.2 使用迭代器···92

4.2.3 list 容器···93

4.3 关联式容器···95

4.3.1 pair 类型···95

4.3.2 map 容器···97

4.3.3 set 容器···98

4.4 本章小结···100

习题4 ···101

实验训练4···101

第5 章线性表··· 103

5.1 线性表的定义···103

5.1.1 线性表的逻辑结构···103

5.1.2 线性表的抽象类定义···104

5.2 线性表的顺序表示和实现···105

5.2.1 线性表的顺序表示···105

5.2.2 顺序表类的定义···105

5.2.3 顺序表类的实现···106

5.3 线性表的链式表示和实现···110

5.3.1 线性表的链式表示···110

5.3.2 抽象链表类的定义···110

5.3.3 抽象链表类各成员函数的实现···112

5.4 单链表···113

5.4.1 单链表的结构···113

5.4.2 单链表类的定义···113

5.4.3 单链表的常用成员函数的实现···114

5.4.4 单链表举例—一元多项式加法···117

5.5 循环链表···120

5.5.1 循环链表的定义···120

5.5.2 循环链表类的定义···120

5.5.3 循环链表常用函数的实现···121

5.5.4 循环链表举例—约瑟夫问题···124

5.6 双向链表···125

5.6.1 双向链表的定义···125

5.6.2 双向链表类的定义···126

5.6.3 双向链表的常用成员函数的实现···127

5.7 本章小结···130

习题5 ···131

实验训练5···131

第6 章堆栈、队列和递归··· 133

6.1 堆栈的概念及其运算···133

6.2 抽象堆栈类的定义···134

6.3 堆栈的定义及其实现···135

6.3.1 顺序栈的定义···135

6.3.2 顺序栈类的定义及典型成员函数的实现···135

6.3.3 多栈共享空间问题···138

6.3.4 链栈的定义···139

6.3.5 链式栈类的定义及典型成员函数的实现···140

6.4 堆栈的应用举例···143

6.4.1 数制转换···143

6.4.2 一个趣味游戏—迷宫问题···144

6.5 队列的概念及其运算···147

6.6 抽象队列类的定义···148

6.7 队列的定义及其实现···148

6.7.1 队列的顺序存储结构···148

6.7.2 循环队列的定义···150

6.7.3 顺序循环队列类的定义及常用成员函数的实现···150

6.7.4 链式队列的定义···153

6.7.5 链式队列类的定义及常用成员函数的实现···153

6.7.6 链式队列的应用举例···156

6.7.7 优先级队列的定义···157

6.7.8 优先级队列类的定义及常用成员函数的实现···158

6.8 递归···161

6.8.1 递归的概念···161

6.8.2 递归的应用···162

6.8.3 递归在计算机中的实现···163

6.8.4 递归问题的非递归算法···165

6.9 本章小结···168

习题6 ···168

实验训练6···169

第7 章树与二叉树··· 171

7.1 树、二叉树和森林的基本概念···171

7.1.1 树···171

7.1.2 二叉树···173

7.1.3 树与森林的存储结构···177

7.2 二叉树的抽象类和树的类···181

7.2.1 二叉树的抽象类···181

7.2.2 树的类···186

7.3 二叉树的遍历和树的遍历···192

7.3.1 二叉树的遍历···192

7.3.2 树的遍历···195

7.4 二叉排序树···198

7.5 二叉树的计数···203

7.6 哈夫曼树及其应用···204

7.6.1 二叉树（哈夫曼树）···204

7.6.2 哈夫曼编码···205

7.7 本章小结···206

习题7 ···206

实验训练7···208

第8 章图 ··· 209

8.1 图的基本概念···209

8.1.1 图的定义···209

8.1.2 图的术语···210

8.1.3 图的基本操作···212

8.1.4 图的存储表示···213

8.2 图的抽象类···217

8.2.1 图的邻接矩阵类···217

8.2.2 图的邻接表类···222

8.3 图的遍历···228

8.3.1 深度优先搜索DFS···228

8.3.2 广度（或宽度）优先搜索BFS···229

8.4 图的连通性与小生成树···230

8.4.1 无向图的连通分量和生成树···230

8.4.2 小生成树···231

8.4.3 关节点和重连通分量···235

8.5 短路径···237

8.5.1 图结点的可达性···238

8.5.2 从某个源点到其余各顶点的短路径···239

8.5.3 每一对顶点之间的短路径···241

8.6 活动网络···243

8.6.1 用顶点表示活动的网络（AOV 网络） ···243

8.6.2 用边表示活动的网络（AOE 网络）···244

8.7 本章小结···246

习题8 ···246

实验训练8···248

第9 章查找与散列结构··· 250

9.1 基本概念···250

9.2 静态查找表···251

9.2.1 顺序表的查找···251

9.2.2 有序表的查找···253

9.2.3 索引顺序表的查找···255

9.3 动态查找表···256

9.4 Hash 表及其查找···258

9.4.1 Hash 表···258

9.4.2 Hash 函数的构造方法···259

9.4.3 处理冲突的方法···262

9.4.4 Hash 表的查找及其分析···264

9.5 本章小结···266

习题9 ···266

实验训练9···267

第10 章排序··· 269

10.1 排序的基本概念···269

10.2 插入排序···271

10.2.1 直接插入排序···271

10.2.2 其他插入排序···273

10.2.3 希尔排序···276

10.3 快速排序···277

10.4 选择排序···280

10.4.1 简单选择排序···280

10.4.2 锦标赛排序···281

10.4.3 堆排序···284

10.5 归并排序···289

10.5.1 归并···289

10.5.2 迭代的归并排序算法···290

10.6 基数排序···291

10.6.1 多关键字排序···291

10.6.2 链式基数排序···292

10.7 本章小结···294

习题10 ···295

实验训练10···295

参考文献··· 297