数据结构（C语言版）

Preface以计算机科学技术为核心的信息技术正在深刻地改变着人们的工作、生活和思维方式。软件是计算机的灵魂，程序设计是计算机科学技术重要的基础，写出高质量的程序是每个软件开发者追求的目标。要达到这个目标仅靠学习几门高级语言程序设计是远远不够的，正如我们即使认识汉字并懂得中文语法，也难以写出好文章一样。数据结构这门课程正是开启程序设计知识宝库的金钥匙，学习数据结构的主要目的是培养学生将现实世界抽象为数据和数据模型的能力，以及利用计算机进行数据存储和数据加工的能力。学好数据结构，可以使读者掌握更多的程序设计技巧，为以后学习计算机专业课程及走上工作岗位从事计算机大型软件开发打下良好的基础。数据结构是我国高校计算机类专业(含计算机科学与技术、软件工程、网络工程、信息安全等专业)的核心课程之一；是其他信息类专业(含信息管科类、电子信息类、数学类专业等)的必修课程之一；也是全国硕士研究生统一招生考试计算机科学与技术学科联考的科目之一。
本书内容共10章，第2～9章以案例导引的方式引入相关数据结构的基本概念；在具体内容组织上，侧重求解问题的思路导引和具体算法的设计分析，并且在每章实例应用部分给出了导入案例的详细求解过程及其算法实现。
第1章重点介绍数据结构与算法的基本概念，介绍评价算法优劣的主要指标以及衡量算法效率的时间复杂度和空间复杂度；第2～4章重点介绍线性表、栈和队列、串等线性结构的逻辑特性、存储结构，以及基本操作算法；第5～7章重点介绍多维数组、广义表、树、二叉树、图等非线性结构的逻辑特征、存储表示及基本操作算法的实现和具体应用；第8、9章介绍在软件开发中广泛使用的两种操作: 查找和排序，对一些常用的查找和排序算法进行了详细描述及效率分析；第10章将线性结构和非线性结构进行归纳总结，指出线性结构是特殊的非线性结构，树是特殊的图，利用图的相关算法设计思想解决诸多实际问题，通过例题让读者理论联系实际，以加深对各种数据结构知识的理解。书中算法采用C语言描述，针对基础知识、核心算法和典型应用案例，编者精心录制了微课视频供读者学习参考。同时，算法C语言实现源代码遵从友好、统一的编码风格，易懂易读。此外，每章还配有丰富的例题和习题。
数据结构是一门实践性很强的课程，读者在进行理论学习的同时，需要多练习编写程序并上机调试，以加深对所学知识的理解，提高编程能力。
本书可作为高等院校计算机类或信息类相关专业数据结构课程的教材，建议理论课时为50～70学时，上机及课程设计等实践课时为20～30学时。主讲教师可根据本校的专业特点和具体情况适当增删教学内容。
本书配套教材是《数据结构(C语言版)例题详解与课程设计指导》，内容包括各知识点的归纳与总结，有例题详解及习题解答以及课程设计指导。
本书由秦锋、汤亚玲任主编，程泽凯、储岳中、袁志祥、秦飞、黄俊、徐浩任副主编。
第1、6、10章由秦锋编写，第3章由汤亚玲编写，第8章由程泽凯编写，第5章由储岳中编写，第4章由袁志祥编写，第2章由秦飞编写，第9章由黄俊编写，第7章由徐浩编写。
全书由秦锋、汤亚玲负责修改并统稿，因编者水平有限，书中难免有不足甚至错误之处，敬请广大读者批评指正！
读者可以在清华大学出版社官网（http://www.tup.com.cn）下载本书配套的课件、源代码等教学资源，扫描书中的二维码获取相应知识点的微课视频，从封底的刮刮卡处获取配套题库。◆数据结构（C语言版）（第2版·微课版）编者2021年9月

本书通过案例导引，结合各种数据结构基本算法，配合微课视频的讲解，全面介绍了线性表、队列、堆栈、树、图等基本数据结构的概念、存储及算法实现，系统说明了各种查找及排序算法的实现和效率分析，在第10章给出了数据结构综合应用实例。书中各种算法采用C语言描述，注重程序设计风格。 本书语言流畅，内容通俗易懂，算法描述力求精练易读；同时为了适应当前互联网学习、移动学习新浪潮，编者对本书中所描述的各种数据结构核心算法和部分案例录制了微课讲解视频，便于学生自学参考，帮助读者实现随时随地学习。本书可以作为计算机、信息等专业本科生数据结构课程的教材，也可作为广大计算机爱好者或软件开发人员的参考书。

本书通过案例导引，结合各种数据结构基本算法，配合微课视频的讲解，全面介绍了线性表、队列、堆栈、树、图等基本数据结构的概念、存储及算法实现，系统说明了各种查找及排序算法的实现和效率分析，在第10章给出了数据结构综合应用实例。书中各种算法采用C语言描述，注重程序设计风格。 本书语言流畅，内容通俗易懂，算法描述力求精练易读；同时为了适应当前互联网学习、移动学习新浪潮，编者对本书中所描述的各种数据结构核心算法和部分案例录制了微课讲解视频，便于学生自学参考，帮助读者实现随时随地学习。本书可以作为计算机、信息等专业本科生数据结构课程的教材，也可作为广大计算机爱好者或软件开发人员的参考书。

秦锋,安徽工业大学教授，安徽省人大代表。长期从事机器学习方向的科研及计算机教学工作，发表学术论文40余篇，主持参加省部级以上科研项目10余项。获安徽省教学名师、安徽省优秀教师、宝钢教育基金优秀
教师、全国大学生科技作品优秀指导教师等荣誉称号。是省级教学团队负责人；省级
教学名师工作室负责人。主编出版系列教材6部，获安徽省教学成果一等奖1
次，二等奖1次，三等奖1次。指导学生五次获‘挑战杯’全国大学生课外科技
作品竞赛奖，其中一等奖1次，二等奖1次，三等奖三次。

第1章绪论1
1.1什么是数据结构1
1.1.1数据结构的定义1
1.1.2学习数据结构的意义4
1.2基本概念和术语5
1.2.1数据与数据元素5
1.2.2数据的逻辑结构与存储结构5
1.2.3数据运算6
1.2.4数据类型与抽象数据类型7
1.3算法和算法描述语言8
1.4算法分析9
1.4.1算法评价9
1.4.2算法性能分析与度量13
本章小结18
习题18
第2章线性表22
2.1案例导引22
2.2线性表的逻辑结构24
2.2.1线性表的定义24
2.2.2线性表的基本操作24
2.3线性表的顺序存储及运算实现25
2.3.1顺序表25
2.3.2顺序表上基本运算的实现27
2.4顺序表应用举例31
2.5线性表的链式存储和运算实现33
2.5.1单链表33
2.5.2单链表基本运算的实现352.5.3循环链表40
2.5.4双向链表40
2.5.5静态链表42
2.6单链表应用举例43
2.7顺序表和链表的比较55
2.8案例分析与实现46
本章小结56
习题57
◆数据结构（C语言版）（第2版·微课版）目录第3章栈和队列61
3.1案例导引61
3.2栈63
3.2.1栈的定义及基本操作63
3.2.2栈的顺序存储及操作实现64
3.2.3栈的链式存储及操作实现67
3.3栈的应用举例70
3.4递归82
3.4.1递归定义82
3.4.2递归和栈的关系83
3.4.3递归算法实例84
3.5队列87
3.5.1队列的定义及基本操作87
3.5.2队列的顺序存储实现及操作实现88
3.5.3队列的链式存储实现及操作实现92
3.6队列应用举例95
3.7案例分析与实现97
本章小结101
习题101
第4章串105
4.1案例导引105
4.2串及其基本运算106
4.2.1串的基本概念106
4.2.2串的基本运算107
4.3串的顺序存储及基本运算108
4.3.1串的定长顺序存储109
4.3.2定长顺序串的基本运算109
4.4模式匹配111
4.4.1简单的模式匹配算法111
4.4.2KMP算法113
4.5串的堆存储结构118
4.5.1动态堆存储118
4.5.2静态堆存储121
4.6串的链式存储结构124
4.7案例分析与实现125
本章小结131
习题132
第5章数组和广义表135
5.1案例导引135
5.2数组139
5.2.1数组的定义139
5.2.2数组的内存映像139
5.3特殊矩阵的压缩存储140
5.3.1对称矩阵140
5.3.2三角矩阵141
5.3.3稀疏矩阵141
5.4广义表147
5.4.1广义表的定义147
5.4.2广义表的存储148
5.4.3广义表基本操作的实现148
5.5案例分析与实现154
本章小结156
习题156
第6章树和二叉树160
6.1案例导引160
6.2树的基本概念162
6.2.1树的定义及其表示162
6.2.2基本术语163
6.3二叉树164
6.3.1二叉树的定义164
6.3.2二叉树的性质165
6.3.3二叉树的存储结构167
6.4遍历二叉树168
6.4.1先序遍历169
6.4.2中序遍历171
6.4.3后序遍历172
6.4.4按层次遍历二叉树175
6.4.5遍历算法的应用举例175
6.5线索二叉树178
6.5.1线索的概念178
6.5.2线索的算法实现180
6.5.3线索二叉树上的运算182
6.6树与森林184
6.6.1树的存储结构184
6.6.2树、森林和二叉树的转换186
6.6.3树和森林的遍历189
6.7哈夫曼树190
6.7.1基本术语191
6.7.2哈夫曼树的建立191
6.8案例分析与实现197
本章小结205
习题205
第7章图210
7.1案例导引210
7.2图的基本概念213
7.2.1图的定义和术语213
7.2.2图的基本操作217
7.3图的存储结构217
7.3.1邻接矩阵218
7.3.2邻接表219
7.3.3十字链表221
7.3.4邻接多重表223
7.4图的遍历224
7.4.1深度优先搜索225
7.4.2广度优先搜索226
7.4.3应用图的遍历判定图的连通性228
7.4.4图的遍历的其他应用229
7.5小生成树239
7.5.1生成树及生成森林239
7.5.2小生成树的概念240
7.5.3构造小生成树的Prim算法241
7.5.4构造小生成树的Kruskal算法243
7.6短路径245
7.6.1从一个源点到其他各点的短路径245
7.6.2每一对顶点之间的短路径249
7.7有向无环图及其应用251
7.7.1有向无环图的概念251
7.7.2AOV网与拓扑排序252
7.7.3AOE图与关键路径256
7.8案例分析与实现261
本章小结265
习题266
第8章查找270
8.1案例导引270
8.2基本概念271
8.3线性表的查找272
8.3.1顺序查找272
8.3.2折半查找273
8.3.3分块查找275
8.4树表查找276
8.4.1二叉排序树277
8.4.2平衡二叉树282
8.4.3平衡二叉树的建立289
8.4.4B树和B 树293
8.5哈希表查找297
8.5.1哈希表与哈希方法297
8.5.2常用的哈希方法298
8.5.3处理冲突的方法299
8.5.4哈希表的操作302
8.5.5哈希表查找及其分析303
8.6案例分析与实现304
本章小结312
习题312
第9章排序316
9.1案例导引316
9.2插入排序319
9.2.1直接插入排序319
9.2.2折半插入排序321
9.2.3希尔排序322
9.3交换排序324
9.3.1冒泡排序324
9.3.2快速排序326
9.4选择排序329
9.4.1简单选择排序329
9.4.2堆排序331
9.5归并排序334
9.6基数排序336
9.6.1多关键码排序336
9.6.2链式基数排序337
9.7案例分析与实现340
本章小结348
习题349
第10章数据结构综合应用352
10.1各种结构类型之间的关系概述352
10.2二叉树与分治策略355
10.3图的遍历及其应用360
本章小结370
习题370
参考文献372

本书通过案例导引，结合各种数据结构基本算法，配合微课视频的讲解，全面介绍了线性表、队列、堆栈、树、图等基本数据结构的概念、存储及算法实现，系统说明了各种查找及排序算法的实现和效率分析，在第10章给出了数据结构综合应用实例。书中各种算法采用C语言描述，注重程序设计风格。 本书语言流畅，内容通俗易懂，算法描述力求精练易读；同时为了适应当前互联网学习、移动学习新浪潮，编者对本书中所描述的各种数据结构核心算法和部分案例录制了微课讲解视频，便于学生自学参考，帮助读者实现随时随地学习。本书可以作为计算机、信息等专业本科生数据结构课程的教材，也可作为广大计算机爱好者或软件开发人员的参考书。

秦锋,安徽工业大学教授，安徽省人大代表。长期从事机器学习方向的科研及计算机教学工作，发表学术论文40余篇，主持参加省部级以上科研项目10余项。获安徽省教学名师、安徽省优秀教师、宝钢教育基金优秀
教师、全国大学生科技作品优秀指导教师等荣誉称号。是省级教学团队负责人；省级
教学名师工作室负责人。主编出版系列教材6部，获安徽省教学成果一等奖1
次，二等奖1次，三等奖1次。指导学生五次获‘挑战杯’全国大学生课外科技
作品竞赛奖，其中一等奖1次，二等奖1次，三等奖三次。