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

本书是*（网络教育）精品课程的教学成果，也是北京市高等教育精品教材，根据*高等学校大学计算机课程教学指导委员会《大学计算机基础课程教学基本要求》中有关理工类专业的计算机基础课程教学要求组织编写而成，内容由浅入深，案例丰富，通俗易懂，实用性强。本书在介绍了C 语言的程序设计方法的基础上，采用面向对象的思想和抽象数据类型的概念，用C 语言有效地组织和描述了线性表、堆栈、队列、树和图等各种典型的数据结构和相关类的实现，并介绍了每一种数据结构的不同存储方法、典型操作及其应用。全书共11章，包括数据结构的基本概念，数组与指针，函数，C 编程基础，继承和多态，模板和STL，线性表，堆栈与队列，树与二叉树，图，查找与散列结构，排序等。本书各章配有习题和实验训练题，方便实践教学，并为任课教师提供了电子课件和示例源代码。本书可作为高等院校电子信息类以及其他相关专业本科生教材和教学参考书，也可供从事程序设计工程的人员参考使用。

高飞，女，现任北京理工大学信息科学技术学院教授，2006?D?D2010年*高等学校计算机基础课程指导委员会理工类计算机基础课程教学指导分委员会委员，*高等学校教学指导委员会委员会专家工作组专家，全国高等院校计算机基础教育研究会理工专业教学研究会委员。

目 录

第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 面向对象的思想 9
1.4.2 面向对象程序设计 9
1.4.3 面向对象的语言 9
1.4.4 面向对象的基本概念 10
1.4.5 面向对象的基本特性 11
1.5 本章小结 13
习题1 13
第2章 C 初步知识 14
2.1 C 语言 14
2.2 数组 14
2.2.1 一维数组 15
2.2.2 二维数组 17
2.2.3 字符数组和字符串 20
2.3 指针 24
2.3.1 指针的概念 24
2.3.2 指针的定义 24
2.3.3 指针的运算 25
2.4 指针和数组 27
2.4.1 指针与数组名 27
2.4.2 指向数组的指针 28
2.4.3 存储指针的数组 31
2.4.4 动态存储 32
2.5 结构 34
2.5.1 结构类型的定义 34
2.5.2 结构变量的说明 35
2.5.3 结构成员的引用 36
2.5.4 结构数组和结构指针 37
2.6 函数 39
2.6.1 函数的声明、定义和调用 40
2.6.2 函数的参数传递 41
2.6.3 带默认参数的函数 42
2.6.4 内置函数 43
2.6.5 函数的重载 44
2.7 本章小结 45
习题2 45
实验训练2 45
第3章 C 类及其对象的封装性 48
3.1 类的声明和对象的定义 48
3.1.1 声明类类型 48
3.1.2 定义对象的方法 50
3.1.3 对象成员的引用 51
3.2 类的成员函数 52
3.2.1 成员函数的访问属性 52
3.2.2 在类外定义成员函数 52
3.2.3 内置成员函数 53
3.2.4 成员函数的存储方式 54
3.3 构造函数和析构函数 55
3.3.1 对象的初始化 55
3.3.2 构造函数的作用 55
3.3.3 带参数的构造函数 57
3.3.4 构造函数的重载 58
3.3.5 拷贝构造函数 58
3.3.6 析构函数 59
3.4 相关特性 61
3.4.1 引用 61
3.4.2 友元 67
3.4.3 运算符重载 70
3.5 本章小结 77
习题3 77
实验训练3 78
第4章 继承性和多态性 81
4.1 继承与派生的概念 81
4.1.1 派生类的声明与构成 81
4.1.2 派生类成员的访问 83
4.2 派生类的构造函数和析构函数 87
4.2.1 简单的派生类的构造函数 87
4.2.2 有子对象的派生类的构造函数 88
4.2.3 多级派生时的构造函数 90
4.2.4 派生类的析构函数 91
4.3 多继承 92
4.3.1 多继承的声明与使用 92
4.3.2 多继承引起的二义性问题 94
4.3.3 虚基类的概念与使用 96
4.4 多态性与虚函数 99
4.4.1 多态的概念 99
4.4.2 虚函数的定义与使用 99
4.4.3 虚析构函数 103
4.4.4 纯虚函数与抽象类 104
4.5 本章小结 107
习题4 107
实验训练4 107
第5章 模板与标准模板库 112
5.1 模板 112
5.1.1 模板的概念 112
5.1.2 函数模板 112
5.1.3 类模板 117
5.2 标准模板库 120
5.3 序列式容器 121
5.3.1 vector容器 121
5.3.2 使用迭代器 123
5.3.3 list容器 124
5.4 关联式容器 125
5.4.1 pair类型 126
5.4.2 map容器 127
5.4.3 set容器 128
5.5 本章小结 130
习题5 131
实验训练5 131
第6章 线性表 133
6.1 线性表的定义 133
6.1.1 线性表的逻辑结构 133
6.1.2 线性表的抽象类定义 134
6.2 线性表的顺序表示和实现 135
6.2.1 线性表的顺序表示 135
6.2.2 顺序表类的定义 135
6.2.3 顺序表类的实现 136
6.3 线性表的链式表示和实现 140
6.3.1 线性表的链式表示 140
6.3.2 抽象链表类的定义 140
6.3.3 抽象链表类各成员函数的实现 142
6.4 单链表 143
6.4.1 单链表的定义 143
6.4.2 单链表类的定义 144
6.4.3 单链表的常用成员函数的实现 144
6.4.4 单链表举例——一元多项式加法 147
6.5 循环链表 150
6.5.1 循环链表的定义 150
6.5.2 循环链表类的定义 150
6.5.3 循环链表常用函数的实现 151
6.5.4 循环链表举例——约瑟夫问题 155
6.6 双向链表 155
6.6.1 双向链表的定义 155
6.6.2 双向链表类的定义 156
6.6.3 双向链表的常用成员函数的实现 157
6.7 本章小结 161
习题6 161
实验训练6 162
第7章 堆栈、队列和递归 169
7.1 堆栈的概念及其运算 169
7.2 抽象堆栈类的定义 170
7.3 堆栈的定义及其实现 170
7.3.1 顺序栈的定义 170
7.3.2 顺序栈类的定义及典型成员函数
的实现 171
7.3.3 多栈共享空间问题 174
7.3.4 链栈的定义 175
7.3.5 链式栈类的定义及典型成员函数
的实现 176
7.4 堆栈的应用举例 179
7.4.1 数制转换 179
7.4.2 迷宫问题 180
7.5 队列的概念及其运算 183
7.6 抽象队列类的定义 184
7.7 队列的定义及其实现 184
7.7.1 队列的顺序存储结构 184
7.7.2 循环队列的定义 186
7.7.3 顺序循环队列类的定义及常用
成员函数的实现 187
7.7.4 链式队列的定义 189
7.7.5 链式队列类的定义及常用成员
函数的实现 190
7.7.6 链式队列的应用举例 193
7.7.7 优先级队列的定义 194
7.7.8 优先级队列类的定义及常用
成员函数的实现 194
7.8 递归 197
7.8.1 递归的概念 197
7.8.2 递归的应用 198
7.8.3 递归在计算机中的实现 199
7.8.4 递归问题的非递归算法 201
7.9 本章小结 204
习题7 204
实验训练7 205
第8章 树与二叉树 212
8.1 树、二叉树和森林的基本概念 212
8.1.1 树 212
8.1.2 二叉树 213
8.1.3 树与森林的存储结构 218
8.2 二叉树的抽象类和树的类 222
8.2.1 二叉树的抽象类 222
8.2.2 树的类 227
8.3 二叉树的遍历和树的遍历 233
8.3.1 二叉树的遍历 233
8.3.2 树的遍历 236
8.4 二叉排序树 239
8.5 二叉树的计数 244
8.6 哈夫曼树及其应用 244
8.6.1 二叉树 244
8.6.2 哈夫曼编码 246
8.7 本章小结 247
习题8 247
实验训练8 248
第9章 图 253
9.1 图的基本概念 253
9.1.1 图的定义 253
9.1.2 图的术语 254
9.1.3 图的基本操作 256
9.1.4 图的存储表示 256
9.2 图的抽象类 260
9.2.1 图的邻接矩阵类 261
9.2.2 图的邻接表类 265
9.3 图的遍历 271
9.3.1 深度优先搜索 272
9.3.2 广度优先搜索 273
9.4 图的连通性与小生成树 274
9.4.1 无向图的连通分量和生成树 274
9.4.2 小生成树 274
9.4.3 关节点和重连通分量 279
9.5 短路径 281
9.5.1 图结点的可达性 281
9.5.2 从某个源点到其余各顶点的
短路径 282
9.5.3 每一对顶点之间的短路径 284
9.6 活动网络 286
9.6.1 AOV网络 286
9.6.2 AOE网络 287
9.7 本章小结 288
习题9 289
实验训练9 290
第10章 查找与散列结构 300
10.1 基本概念 300
10.2 静态查找表 301
10.2.1 顺序表的查找 301
10.2.2 有序表的查找 303
10.2.3 索引顺序表的查找 305
10.3 动态查找表 306
10.4 Hash表及其查找 307
10.4.1 Hash表 307
10.4.2 Hash函数的构造方法 309
10.4.3 处理冲突的方法 312
10.4.4 Hash表的查找及其分析 313
10.5 本章小结 315
习题10 315
实验训练10 316
第11章 排序 324
11.1 排序的基本概念 324
11.2 插入排序 326
11.2.1 直接插入排序 326

11.2.2 其他插入排序 327
11.2.3 希尔排序 330
11.3 快速排序 331
11.4 选择排序 334
11.4.1 简单选择排序 334
11.4.2 锦标赛排序 335
11.4.3 堆排序 338
11.5 归并排序 343
11.5.1 归并 343
11.5.2 迭代的归并排序算法 344
11.6 基数排序 346
11.6.1 多关键字排序 346
11.6.2 链式基数排序 346
11.7 本章小结 348
习题11 349
实验训练11 349
参考文献 354

高等学校规划教材

C 与数据结构
（第4版）

杨心强  陈国友  编著

 
Publishing House of Electronics Industry
北京?BEIJING
 

内 容 简 介
本书是（网络教育）精品课程的教学成果，也是北京市高等教育精品教材，根据*高等学校大学计算机课程教学指导委员会《大学计算机基础课程教学基本要求》中有关理工类专业的计算机基础课程教学要求组织编写而成，内容由浅入深，案例丰富，通俗易懂，实用性强。
本书在介绍了C 语言的程序设计方法的基础上，采用面向对象的思想和抽象数据类型的概念，用C 语言有效地组织和描述了线性表、堆栈、队列、树和图等各种典型的数据结构和相关类的实现，并介绍了每一种数据结构的不同存储方法、典型操作及其应用。
全书共11章，包括数据结构的基本概念，数组与指针，函数，C 编程基础，继承和多态，模板和STL，线性表，堆栈与队列，树与二叉树，图，查找与散列结构，排序等。本书各章配有习题和实验训练题，方便实践教学，并为任课教师提供了电子课件和示例源代码。
本书可作为高等院校电子信息类以及其他相关专业本科生教材和教学参考书，也可供从事程序设计工程的人员参考使用。

图书在版编目（CIP）数据
算法设计与分析：C 语言描述 / 陈慧南编著. —3版. —北京：电子工业出版社，2018.1
ISBN 978?7?121?33054?4
Ⅰ. ①算…  Ⅱ. ①陈…  Ⅲ. ①C 语言－数据结构－算法分析－高等学校－教材  Ⅳ. ①TP312.8 ②TP311.12
中国版本图书馆CIP数据核字（2017）第284089号
策划编辑：冉  哲    特约编辑：杨永毅
责任编辑：冉  哲
印    刷：
装    订：
出版发行：电子工业出版社
北京市海淀区万寿路173信箱  邮编  100036
开   本：787×1092  1/16    印张：19.75    字数：502.4千字
版   次：2006年5月第1版
印   次：2018年1月第1次印刷
定   价：49.00元

凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888，88258888。
质量投诉请发邮件至[email protected]，盗版侵权举报请发邮件至[email protected]。
本书咨询联系方式：192910558（QQ群）。
 

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

                                                           编  者   
                                                        于北京理工大学
                                                         2017年10月