"本书根据教育部高等学校计算机科学与技术教学指导委员会关于“数据结构”课程的指
导性大纲编写而成，系统介绍了线性结构、树形结构、图形结构中的数据表示和处理方法，
以及查找、排序这两种重要的数据处理技术；阐明了各种数据结构内在的逻辑关系，探讨了
它们在计算机中的存储表示，以及定义在这些数据结构上的运算和算法实现，并对算法的效
率进行了简明的分析。
本书内容丰富、结构清晰，既注重基本原理，又重视算法实现，全书算法采用C++语言
描述，并加以详细的注释，可读性好、实用性强。每章均附有丰富的课后习题，便于学生巩
固所学知识。
本书适合作为高等院校计算机、通信工程、电子工程、信息管理等专业的教材，也可供
相关证书考试、考研或从事计算机应用与工程工作的科技工作者参考。"

数据结构是计算机及相关专业一门重要的专业基础课程，也是一门必修的核心课
程，主要介绍如何合理地组织和表示数据、如何有效地存储和处理数据、如何正确地
设计算法，以及对算法的优劣做出分析和评价。
在计算机科学的各个领域都要用到不同的数据结构，比如在操作系统中要用到队列；
编译系统中要用到栈、散列表、语法树；人工智能中要用到有向图。另外，面向对象程
序设计、计算机图形学、软件工程、多媒体技术等领域，都会用到数据结构的知识。
数据结构是一门理论与实际紧密联系的课程，旨在分析研究计算机加工的数据对
象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算
法达到最优。数据结构课程涉及各种离散结构在计算机上如何存储和处理，其内容丰
富、涉及面广，而且还在随各种基于计算机的应用技术的发展，而不断增加新的内容。
本书层次分明、结构清晰，理论深度把握得当，侧重应用。在内容的组织方式上，
注重从问题求解的角度出发，讨论相关的基本理论、数据和算法抽象、数据结构与算法
设计，以及在 C++程序设计语言中的实现。通过学习本书，学生能够较透彻地理解各种
常用数据结构的逻辑结构、存储结构及相关算法的实现，全面掌握处理数据的理论和方
法；培养学生具备较深入的选用合适的数据结构、编写规范的高质量程序，以及评价算
法优劣的能力；使学生接受系统的、科学的分析问题和解决问题的训练，提高运用数据
结构解决实际问题的能力，为学习后续的软件课程奠定良好的基础。
本书编者结合多年的教学经验，在保持前三版基本框架的基础上进行了修订，完善和优
化了数据结构课程的体系内容：简化了稀疏矩阵的十字链表描述，完善了二叉树性质的证明，
增加平衡二叉树、各个排序过程举例等；用 C++语言重新定义了主要的数据结构，规范化了
全书的算法描述；丰富了习题的题型和内容；给出线性结构、树形结构、图形结构、查找和
排序等多个实验题目，难度适宜、应用性强，利于培养学生的理论联系实际的能力。
本书由刘振鹏、王苗、赵红编著，其中第 1 章～第 7 章由王苗编写修订，第8章～
第 10 章由赵红编写修订，最后由刘振鹏统一定稿。本书作者可以提供教材的电子讲
义和书中习题的答案，有需要者可在中国铁道出版社网站 http://www. 51eds.com进行
下载。
本书在写作和修订过程中，得到了许多专家和同事的大力支持和帮助，他们提出了许多中
肯的意见和建议，对本书的编写、修订起到了很大的指导作用，在此表示衷心的感谢。
本书编者是长期从事数据结构教学的一线教师，尽管做了很大的努力，但由于编
者精力、水平有限，书中难免有疏漏与不足之处，恳请读者批评指正。
编 者
2015年11 月

第 1 章绪论......................................................................................................... 1
1.1 数据结构的概念.......................................................................................... 1
1.1.1 为什么要学习数据结构.................................................................... 2
1.1.2 相关概念和术语............................................................................... 4
1.1.3 数据结构课程的内容........................................................................ 6
1.2 数据类型和抽象数据类型............................................................................ 7
1.2.1 数据类型.......................................................................................... 7
1.2.2 抽象数据类型................................................................................... 8
1.3 算法和算法分析.......................................................................................... 9
1.3.1 算法特性.......................................................................................... 9
1.3.2 算法描述.........................................................................................10
1.3.3 算法性能分析与度量.......................................................................10
小结...................................................................................................................13
习题...................................................................................................................13
第 2 章线性表 ................................................................................................... 16
2.1 线性表的逻辑结构......................................................................................16
2.1.1 线性表的定义..................................................................................16
2.1.2 线性表的基本操作..........................................................................17
2.2 线性表的顺序存储及运算实现...................................................................17
2.2.1 顺序表.............................................................................................18
2.2.2 顺序表上基本运算的实现...............................................................19
2.2.3 顺序表应用举例..............................................................................22
2.3 线性表的链式存储和运算实现...................................................................24
2.3.1 单链表.............................................................................................24
2.3.2 单链表上基本运算的实现...............................................................26
2.3.3 循环链表.........................................................................................31
2.3.4 双向链表.........................................................................................32
2.3.5 静态链表.........................................................................................34
2.3.6 间接寻址.........................................................................................35
2.3.7 单链表应用举例..............................................................................35
2.4 顺序表和链表的比较..................................................................................37
小结...................................................................................................................38
习题...................................................................................................................38
数据结构 第四版
2
第 3 章栈和队列................................................................................................ 41
3.1 栈...............................................................................................................41
3.1.1 栈的定义及基本运算.......................................................................41
3.1.2 栈的存储实现和运算实现...............................................................42
3.1.3 栈的应用举例..................................................................................45
3.2 队列............................................................................................................54
3.2.1 队列的定义及基本运算...................................................................55
3.2.2 队列的存储实现及运算实现...........................................................55
3.2.3 队列应用举例..................................................................................60
小结...................................................................................................................62
习题...................................................................................................................63
第 4 章串 .......................................................................................................... 65
4.1 串及其基本运算.........................................................................................65
4.1.1 串的基本概念..................................................................................65
4.1.2 串的基本运算..................................................................................66
4.2 串的定长顺序存储及基本运算...................................................................66
4.2.1 串的定长顺序存储..........................................................................67
4.2.2 定长顺序串的基本运算...................................................................67
4.2.3 模式匹配.........................................................................................69
4.3 串的堆存储结构.........................................................................................74
4.3.1 串名的存储映像..............................................................................74
4.3.2 堆存储结构.....................................................................................75
4.3.3 基于堆结构的串的基本运算实现....................................................75
小结...................................................................................................................77
习题...................................................................................................................77
第 5 章数组和广义表......................................................................................... 79
5.1 数组............................................................................................................79
5.1.1 一维数组.........................................................................................79
5.1.2 多维数组.........................................................................................79
5.1.3 数组的内存映像..............................................................................80
5.2 特殊矩阵的压缩存储..................................................................................83
5.2.1 对称矩阵.........................................................................................83
5.2.2 三角矩阵.........................................................................................84
5.2.3 带状矩阵.........................................................................................85
5.3 稀疏矩阵....................................................................................................86
5.3.1 稀疏矩阵的三元组表存储...............................................................86
5.3.2 稀疏矩阵的十字链表存储...............................................................91
5.4 广义表........................................................................................................96
目 录
3
5.4.1 广义表的定义和基本运算...............................................................96
5.4.2 广义表的存储..................................................................................97
5.4.3 广义表基本操作的实现.................................................................100
小结.................................................................................................................102
习题.................................................................................................................103
第 6 章二叉树 ................................................................................................. 105
6.1 二叉树的定义与性质................................................................................105
6.1.1 二叉树的基本概念........................................................................105
6.1.2 二叉树的主要性质........................................................................107
6.2 二叉树的基本操作与存储实现.................................................................109
6.2.1 二叉树的存储................................................................................109
6.2.2 二叉树的基本操作及实现............................................................. 111
6.3 二叉树的遍历...........................................................................................114
6.3.1 二叉树的遍历方法及递归实现......................................................114
6.3.2 二叉树遍历的非递归实现.............................................................116
6.3.3 由遍历序列恢复二叉树.................................................................119
6.3.4 不用栈的二叉树遍历的非递归方法..............................................121
6.4 线索二叉树...............................................................................................121
6.4.1 线索二叉树的定义及结构.............................................................122
6.4.2 线索二叉树的基本操作实现.........................................................123
6.5 二叉树的应用举例....................................................................................129
6.5.1 查找数据元素................................................................................129
6.5.2 统计给定二叉树中叶结点的数目..................................................129
6.5.3 创建二叉树的二叉链表存储.........................................................130
6.5.4 表达式运算...................................................................................131
6.6 哈夫曼树..................................................................................................131
6.6.1 问题引入.......................................................................................131
6.6.2 哈夫曼树的基本概念及其构造方法..............................................132
6.6.3 哈夫曼树的构造算法.....................................................................134
6.6.4 哈夫曼编码...................................................................................135
小结.................................................................................................................138
习题.................................................................................................................138
第 7 章树与森林.............................................................................................. 141
7.1 树的概念与表示.......................................................................................141
7.1.1 树的定义及相关术语.....................................................................141
7.1.2 树的表示.......................................................................................143
7.2 树的基本操作与存储................................................................................143
7.2.1 树的基本操作................................................................................144
7.2.2 树的存储结构................................................................................144
数据结构 第四版
4
7.3 树、森林与二叉树的转换.........................................................................148
7.3.1 树转换为二叉树............................................................................148
7.3.2 森林转换为二叉树........................................................................148
7.3.3 二叉树转换为树和森林.................................................................149
7.4 树和森林的遍历.......................................................................................150
7.4.1 树的遍历.......................................................................................150
7.4.2 森林的遍历...................................................................................151
7.5 树的应用举例...........................................................................................151
7.5.1 判定树...........................................................................................151
7.5.2 集合的表示...................................................................................152
7.5.3 等价问题.......................................................................................154
小结.................................................................................................................155
习题.................................................................................................................156
第 8 章图 ........................................................................................................ 158
8.1 图的基本概念...........................................................................................158
8.1.1 图的定义和术语............................................................................158
8.1.2 图的基本操作及类定义.................................................................161
8.2 图的存储结构...........................................................................................163
8.2.1 邻接矩阵.......................................................................................163
8.2.2 邻接表...........................................................................................165
8.2.3 十字链表.......................................................................................167
8.2.4 邻接多重表...................................................................................170
8.3 图的遍历..................................................................................................171
8.3.1 深度优先搜索................................................................................172
8.3.2 广度优先搜索................................................................................173
8.3.3 应用图的遍历判定图的连通性......................................................175
8.3.4 生成树和生成森林........................................................................176
8.4 最小生成树...............................................................................................177
8.4.1 最小生成树的概念........................................................................178
8.4.2 普里姆（Prim）算法.....................................................................179
8.4.3 克鲁斯卡尔（Kruskal）算法.........................................................181
8.5 最短路径..................................................................................................183
8.5.1 迪杰斯特拉（Dijkstra）算法........................................................183
8.5.2 弗洛伊德（Floyd）算法................................................................187
8.6 拓扑排序与关键路径................................................................................188
8.6.1 有向无环图的概念........................................................................189
8.6.2 拓扑排序.......................................................................................190
8.6.3 关键路径.......................................................................................194
小结.................................................................................................................199
目 录
5
习题.................................................................................................................200
第 9 章查找..................................................................................................... 203
9.1 基本概念..................................................................................................203
9.1.1 相关术语.......................................................................................203
9.1.2 查找表结构...................................................................................204
9.2 静态查找表...............................................................................................205
9.2.1 顺序查找.......................................................................................205
9.2.2 折半查找.......................................................................................206
9.2.3 插值查找和斐波那契查找.............................................................209
9.2.4 分块查找.......................................................................................210
9.3 二叉排序树...............................................................................................211
9.3.1 二叉排序树的定义........................................................................211
9.3.2 二叉排序树的查找过程.................................................................211
9.3.3 二叉排序树的插入操作.................................................................212
9.3.4 二叉排序树的删除操作.................................................................213
9.4 平衡二叉树...............................................................................................216
9.4.1 平衡二叉树的定义........................................................................216
9.4.2 平衡二叉树的平衡化旋转.............................................................217
9.4.3 平衡二叉树的插入........................................................................219
9.4.4 平衡二叉树的查找性能分析.........................................................223
9.5 B树和B
+树..............................................................................................224
9.5.1 B树的定义....................................................................................224
9.5.2 B树的查找....................................................................................225
9.5.3 B树的插入....................................................................................226
9.5.4 B树的删除....................................................................................229
9.5.5 B
+树..............................................................................................230
9.6 哈希表查找...............................................................................................231
9.6.1 哈希表与哈希方法........................................................................231
9.6.2 常用的哈希函数............................................................................232
9.6.3 处理冲突的方法............................................................................234
9.6.4 哈希表的查找性能分析.................................................................236
小结.................................................................................................................237
习题.................................................................................................................238
第 10 章排序................................................................................................... 241
10.1 排序的基本概念.....................................................................................241
10.1.1 相关术语.....................................................................................241
10.1.2 排序的时间开销..........................................................................242
10.2 插入排序................................................................................................242
10.2.1 直接插入排序..............................................................................242
数据结构 第四版
6
10.2.2 折半插入排序..............................................................................243
10.2.3 表插入排序.................................................................................244
10.2.4 希尔排序.....................................................................................247
10.3 交换排序................................................................................................248
10.3.1 冒泡排序.....................................................................................248
10.3.2 快速排序.....................................................................................249
10.4 选择排序................................................................................................252
10.4.1 简单选择排序..............................................................................252
10.4.2 树形选择排序..............................................................................253
10.4.3 堆排序.........................................................................................254
10.5 归并排序................................................................................................256
10.6 基数排序................................................................................................258
10.6.1 多关键码排序..............................................................................258
10.6.2 链式基数排序..............................................................................259
10.7 外排序....................................................................................................262
10.7.1 外排序的方法..............................................................................262
10.7.2 多路平衡归并的实现...................................................................263
小结.................................................................................................................266
习题.................................................................................................................267
附录................................................................................................................... 271
附录A 线性结构............................................................................................271
附录B 树形结构............................................................................................273
附录C 图形结构............................................................................................274
附录D 查找和排序........................................................................................276
参考文献............................................................................................................ 278

主要著译者顺序姓名学历职称学科专长通讯地址1刘振鹏 博士 教授 计算机专业工作单位河北大学 邮政编码 电话13803285676 2 工作单位 邮政编码 电话 3 工作单位 邮政编码 电话 审校者（主审者） 学历 工作单位 邮政编码 电话 职称 工作单位 邮政编码 电话 刘振鹏，男，1966年4月出生，博士，教授。河北大学网络中心主任，硕士生导师，河北省高等学校中青年骨干教师，中国计算机学会（CCF）高级会员，CCF网络与数据通信专业委员会委员，CCF互联网专业委员会委员，中国通信学会云计算与SaaS专家委员会委员，中国教育信息化理事会副理事长，河北省高等院校信息网络技术研究会副理事长。王苗，1975年11月生，河北高阳人。1992年9月考入河北大学就读计算机及应用专业，1996年7月毕业，于同年留校任教至今。2002年被聘为讲师。2003年9月至2006年6月期间就读河北大学数学与计算机学院计算机应用技术专业研究生，获硕士学位 。 赵红,女,副教授,博士，河北大学数学与计算机学院。