算法与数据结构（C++语言版）

本书按照“全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲”的要求编写，基本涵盖所有知识点，并加入部分高校及全国统一考试真题作为自测题，同时给出参考答案和题目解析。本书主要介绍各种常用的经典数据结构（如线性表、栈、队列、串、数组、树、图、集合等）和算法，并在时间复杂度和空间复杂度之间进行平衡与取舍。
本书将C 语言作为数据结构的算法描述语言，将数据结构与面向对象技术有机结合。书中的算法讲解都有完整的C 代码实现，并在Visual Studio 2010环境下编译通过。

冯广慧，2004年毕业于吉林大学获工学学士学位，2007年毕业于吉林大学研究生院获工学硕士学位，自2007年起一直从事于《算法与数据结构》课程的一线教学和考研辅导工作，对该课程有深入研究，参编《C语言程序设计教程》、《Access数据库程序设计真题考点分析与讲解》等多部著作。

第1章 概论 1
1.1 什么是数据结构 1
1.2 基本概念和术语 4
1.3 算法和算法分析 7
1.3.1 算法的定义及特性 7
1.3.2 算法的设计要求 8
1.3.3 算法效率的衡量方法 9
1.3.4 算法的时间复杂度 10
1.3.5 算法的空间复杂度 15
1.4 抽象数据类型 16
习题 18
第2章 线性表 20
2.1 线性表的类型定义 20
2.1.1 线性表的概念 20
2.1.2 线性表的抽象数据类型 21
2.2 线性表的顺序表示和实现 22
2.2.1 线性表的顺序表示 22
2.2.2 顺序表基本运算的实现 23
2.3 线性表的链式表示和实现 28
2.3.1 线性表的链式表示 29
2.3.2 单链表上基本运算的实现 32
2.4 双链表 40
2.5 循环链表 44
2.6 线性表实现方法的比较 46
2.7 算法设计举例 47
习题 52
第3章 栈和队列 55
3.1 栈 55
3.1.1 栈的类型定义 55
3.1.2 顺序栈的表示和实现 57
3.1.3 链栈的表示和实现 60

3.2 栈的应用举例 62
3.2.1 十进制数转换为其他进制数 62
3.2.2 表达式中括号的匹配检查 63
3.2.3 表达式求值 64
3.2.4 利用栈消除递归 72
3.3 队列 77
3.3.1 队列的类型定义 77
3.3.2 循环队列—队列的顺序表示和
实现 78
3.3.3 链队列—队列的链式表示和
实现 82
3.4 算法设计举例 83
习题 87
第4章 串 90
4.1 串的基本概念 90
4.2 串的表示和实现 91
4.2.1 串的顺序存储结构 91
4.2.2 串的链式存储结构 94
4.3 串的模式匹配 95
4.3.1 朴素的模式匹配算法 95
4.3.2 KMP算法 96
习题 101
第5章 数组 104
5.1 数组的基本概念 104
5.2 矩阵的压缩存储 107
5.2.1 特殊矩阵 107
5.2.2 稀疏矩阵 110
5.3 算法设计举例 117
习题 121
第6章 树和二叉树 124
6.1 树的概念 124

6.2 二叉树的概念和性质 126
6.2.1 二叉树的概念和抽象数据
类型 126
6.2.2 二叉树的性质 129
6.3 二叉树的表示和实现 131
6.3.1 二叉树的存储结构 131
6.3.2 二叉树的遍历运算 133
6.3.3 二叉树的其他基本运算 140
6.4 树和森林 142
6.4.1 树的存储结构 143
6.4.2 树、森林和二叉树的相互
转换 146
6.4.3 树和森林的遍历运算 148
6.4.4 树和森林的其他基本运算 151
*6.5 线索二叉树 154
6.5.1 线索二叉树的概念 154
6.5.2 线索二叉树的基本运算 157
6.6 算法设计举例 161
习题 162
第7章 树和二叉树的应用 166
*7.1 表达式树 166
7.2 哈夫曼树和哈夫曼编码 171
7.2.1 哈夫曼树 171
7.2.2 哈夫曼编码 175
7.3 堆和优先级队列 178
7.3.1 堆 178
7.3.2 优先级队列 179
*7.4 并查集 184
7.5 算法设计举例 187
习题 189
第8章 图 191
8.1 图的概念 191
8.2 图的存储结构 196
8.2.1 邻接矩阵 196
8.2.2 邻接表 200
*8.2.3 十字链表 205
*8.2.4 邻接多重表 205
8.3 图的遍历 206
8.3.1 深度优先遍历 207
8.3.2 广度优先遍历 209
8.3.3 图的连通分量和生成树 212
习题 213
第9章 图的应用 217
9.1 小生成树 217
9.1.1 小生成树的概念 217
9.1.2 Prim算法 218
9.1.3 Kruskal算法 222
9.2 有向无环图及其应用 225
9.2.1 拓扑排序 225
9.2.2 关键路径 230
9.3 短路径 236
9.3.1 单源点短路径 236
9.3.2 每对顶点之间的短路径 240
习题 243
第10章 集合与查找 247
10.1 基本概念 247
10.2 静态查找表上的查找 248
10.2.1 顺序查找 248
10.2.2 折半查找 250
10.2.3 分块查找 254
10.3 动态查找表上的查找 256
10.3.1 二叉查找树 256
10.3.2 平衡二叉树 263
*10.3.3 B树 275
*10.3.4 B 树 280
*10.3.5 字典树 281
10.4 算法设计举例 282
习题 285
第11章 散列表 288
11.1 散列表的概念 288
11.2 构造散列函数的方法 289
11.2.1 直接定址法 289
11.2.2 折叠法 289
11.2.3 数字分析法 289
11.2.4 平方取中法 290

11.2.5 除留余数法 290
11.3 解决冲突的方法 291
11.3.1 闭散列法 291
11.3.2 开散列法 293
11.4 散列表的实现 294
11.4.1 闭散列表的表示和实现 294
11.4.2 开散列表的表示和实现 298
11.4.3 闭散列表与开散列表的
比较 302
11.5 散列表的查找性能分析 302
习题 303
第12章 排序 306
12.1 排序的基本概念 306
12.2 插入排序 307
12.2.1 直接插入排序 307
12.2.2 折半插入排序 308
12.2.3 希尔排序 309

12.3 交换排序 310
12.3.1 冒泡排序 310
12.3.2 快速排序 311
12.4 选择排序 315
12.4.1 直接选择排序 315
12.4.2 堆排序 316
*12.4.3 锦标赛排序 320
12.5 归并排序 320
*12.6 基数排序 322
12.7 各种内部排序方法的比较 324
*12.8 外部排序 327
12.8.1 置换选择排序 328
12.8.2 多路归并排序 330
习题 331
附录A 上机实验参考题目 334
参考文献 336

随着计算机技术的飞速发展，计算机在各个学科和领域得到广泛应用，而这些应用所面临的首要问题就是对于信息量大、种类繁多、结构复杂的数据和数据关系的处理，因此必须设计好数据结构和数据组织方式，以便有效地实现数据存储、数据传输和数据处理等操作。数据结构主要研究数据的逻辑结构，数据在计算机中的存储实现，以及处理不同结构数据的算法。我们研究数据结构的目的是编写更高效的程序，而高效、简捷的程序取决于数据结构和算法的设计。
“数据结构”是计算机程序设计的重要理论基础，是计算机专业为核心的一门专业基础课程，也是非计算机专业的主要选修课程，同时还是一门考研课程。数据结构前承高级语言程序设计和离散数学，后接操作系统、编译原理、数据库原理等专业课程，为研制开发各种系统和应用软件奠定理论和实践基础。该课程的学习效果不仅关系到后续课程的学习，而且直接关系到软件设计水平的提高和专业素质的培养，在计算机学科教育中有非常重要的作用。
考虑到初学者普遍对算法设计问题感到比较困难且思路不明确，本书不仅注重基本概念的引入和阐述，更加注重算法的设计、分析与实现，强调实践环节的重要性。本书具有如下特点。
（1）将C 语言作为数据结构的算法描述语言，让数据结构与面向对象技术有机结合。在设置例题时，充分考虑应用型人才培养的需求，更加侧重于算法的程序实现。书中的算法讲解都有风格优美而完整的C 代码实现，并在Visual Studio 2010环境下编译通过，这将有利于读者掌握算法的程序实现及对算法进行分析与比较。
（2）按照“全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲”的要求编写，基本涵盖该考试大纲所有的知识点，并在重要知识点之后附加部分高校及全国统一考试真题作为自测题。读者在完成相应问题的同时，既能巩固知识点，又能有选择地提高能力，还能有效地检验阶段学习效果。
（3）系统、全面地介绍各种传统的数据结构，按照“线性结构、树结构、图结构、集合结构”四大模块顺序安排内容。部分章节还设有算法设计举例，意在提高初学者的算法分析和设计的能力。
全书分为12章。
第1章介绍基础知识，讨论什么是数据结构，给出数据结构和算法的相关概念与描述方法，介绍算法分析的基本方法。
线性结构包括第2～5章。第2章介绍线性表的有关概念及其基本操作，是后续章节的基础。第3章在第2章的基础上讨论操作受限的线性表——栈与队列。第4章讨论数据元素为字符的特殊的线性表——串。第5章介绍程序设计中常用的数据类型——数组。
树结构包括第6、7章。第6章介绍树和二叉树的有关概念及基本操作。第7章讨论树和二叉树的应用。
图结构包括第8、9章。第8章介绍图的基本概念、存储结构及遍历运算。第9章讨论图的应用。
集合结构包括第10～12章。第10章以集合作为数据模型，讨论查找的方法和技术，包括静态查找表和动态查找表。第11章介绍一种专用于集合的存储和检索的数据结构——散列表。第12章介绍一些常用的排序算法，包括内部排序和外部排序。
本书由教学一线的教师主笔，结合作者多年的教学经验和教学素材，针对数据结构这门课程的特点撰写而成，目的是使学生在扎实的编程能力基础上，掌握如何合理地组织数据、有效地存储和处理数据，并学会在时间复杂度和空间复杂度之间进行平衡与取舍。本书满足多样化的人才培养模式的需求，既可作为普通高等院校计算机及相关专业的数据结构课程教材，也可作为考研参考书，还可作为工程技术人员的工具书。在本书目录中加“*”的章节可以酌情处理。
在本书的编写和出版过程中得到电子工业出版社冉哲编辑和《算法与数据结构考研试题精析》的编者陈守孔教授的诸多帮助，得到吉林大学珠海学院领导的大力支持，在此深表感谢。
由于作者水平所限，加上计算机学科的发展十分迅速，书中难免有不妥之处，恳请读者批评指正。

作　者