数据结构（C语言描述）

在编排上，本书内容符合“数据结构”本科教学大纲及最新研究生考试大纲的要求；另外，本书还加强数据结构设计、算法设计等实践应用环节。

本书编者结合自己的教学和编程实践经验，精选基础理论内容，降低了概念的抽象性和理论的难度，突出实用性，便于读者理解和掌握。

本书条理清晰，概念清楚，逻辑推理严谨，内容详实，既注重数据结构和算法原理，又十分强调程序设计训练。

本书力图用生动、通俗易懂的语言，并结合编程实例来讲解各个知识点；书中算法均配有完整的C语言程序，结构清晰，构思精巧。

本书配套有中国水利水电出版社出版的《数据结构习题解答及上机指导》。

数据结构是普通高等院校计算机和信息技术等相关专业的一门主要的专业基础课，也是一门必修的核心课程。它不仅是计算机程序设计的理论基础，还是学习计算机操作系统原理、编译原理、数据库原理等课程的重要基础。

数据结构课程的主要任务是讨论数据的各种逻辑结构和数据在计算机中的存储表示，以及各种非数值运算的算法实现，其内容丰富、涉及面广，并且随着各种基于计算机的应用技术的发展而不断增加新的内容。通过学习，学生可以较全面地理解算法和数据结构概念，掌握各种数据结构和算法的实现方式，比较不同数据结构和算法特点，能够使用数据结构的基本分析方法来提高编写程序的能力和应用计算机解决实际问题的能力。

数据结构内容多、理论深、概念抽象。因此，在本书的编写中，编者结合自己的教学和编程实践经验，精选了基础理论内容，降低了概念的抽象性和理论难度。一方面力图用生动、通俗易懂的语言并结合编程实例来讲解各个知识点，便于读者理解和掌握；另一方面加强了数据结构设计、算法设计等实践应用环节。全书共9章，第1章主要讲述数据结构和算法的基本概念；第2～7章分别讲述线性表、栈和队列、多维数组和广义表、树和图这几种基本数据结构的特点、存储方法和基本运算，作为本书的重点，书中使用大量的篇幅来介绍这些基本数据结构的实际应用；第8章和第9章讲述查找和排序的基本原理与方法。另外，书中所涉及的有关概念及背景知识皆做出详细交代；对相关的定理和性质给出简单证明；对所有算法，都详细讨论其设计思想和实现方法，最后给出完整的C语言代码；书中所有算法和程序代码均在Dev-C++5.0环境下调试通过。

本书配套有《数据结构习题解答及上机指导》，内含与主教材各章内容相配合的习题解答参考和7套模拟考试试题和10个精心设计的实验，每个实验均包括实验目的、实验内容、实验说明、实验指导等，两本书配套使用可以更为全面地掌握数据结构这门课程。

本书第1～5章由李素若编写，第6、8、9章由陈万华编写，第7章由游明坤编写；全书由李素若负责审核和统稿；参加本书编写大纲讨论的教师还有严永松、胡玉荣、任正云、武永成、张牧等。

由于编者水平有限，加之时间仓促，书中难免有疏漏之处，敬请广大读者批评指正，以使本书质量得到进一步提高。

编 者

2014年4月

前言

第1章 绪论 1
1.1 数据结构的概述 1
1.2 基本概念和常用术语 2
1.3 数据抽象和抽象数据类型 6
1.3.1 数据抽象 6
1.3.2 抽象数据类型 7
1.3.3 抽象数据类型的描述和实现 8
1.4 算法和算法分析 10
1.4.1 算法及性能标准 10
1.4.2 算法时间复杂度和渐近时间复杂度 11
1.4.3 算法的空间复杂度 13
习题1 13
第2章 线性表 17
2.1 线性表的逻辑结构 17
2.1.1 线性表的定义 17
2.1.2 线性表的ADT定义 18
2.2 线性表的顺序存储和实现 19
2.2.1 线性表顺序存储结构 19
2.2.2 线性表在顺序存储结构下的运算 20
2.3 线性表的链式存储和实现 23
2.3.1 线性链表 23
2.3.2 循环链表 30
2.3.3 双向循环链表 32
2.3.4 循环链表 34
2.4 一元多项式的表示及相加 35
习题2 38
第3章 栈和队列 42
3.1 栈 42
3.1.1 栈的定义 42
3.1.2 栈的ADT定义 42
3.1.3 顺序栈 44
3.1.4 多栈共享邻接空间 46
3.1.5 链栈 48
3.1.6 栈的应用举例 50
3.1.7 栈与递归的实现 56
3.2 队列 60
3.2.1 队列的定义 60
3.2.2 队列的ADT定义 60
3.2.3 顺序队列 61
3.2.4 链队列 65
3.2.5 队列应用举例 66
习题3 69
第4章 串 73
4.1 串 73
4.1.1 串的定义与相关概念 73
4.1.2 串的ADT定义 74
4.2 串的定长顺序存储 77
4.2.1 串的定长顺序存储结构 77
4.2.2 定长顺序存储的基本运算 77
4.3 串的堆存储结构 80
4.3.1 串名存储映像 81
4.3.2 堆存储结构 82
4.3.3 基于堆存储结构的基本运算 82
4.4 串的块链存储结构 85
4.5 串的模式匹配 87
习题4 92
第5章 数组和广义表 96
5.1 数组类型的定义 96
5.1.1 数组的定义 96
5.1.2 数组的ADT定义 98
5.2 数组的顺序存储和实现 99
5.3 矩阵压缩存储 101
5.3.1 对称矩阵 101
5.3.2 三角矩阵 102
5.3.3 带状矩阵 103
5.4 稀疏矩阵 104
5.4.1 稀疏矩阵三元组表存储 104
5.4.2 稀疏矩阵十字链表存储 113
5.5 广义表 117
5.5.1 广义表的定义和基本运算 117
5.5.2 广义表的存储 119
5.5.3 广义表基本操作的实现 121
习题5 124
第6章 树 128
6.1 树的基本概念 128
6.1.1 树的定义 128
6.1.2 树的逻辑表示方法 129
6.1.3 树的基本术语 130
6.1.4 树的ADT定义 131
6.2 二叉树的概念和性质 132
6.2.1 二叉树的概念 132
6.2.2 二叉树的性质 133
6.3 二叉树的存储结构 135
6.3.1 二叉树的顺序存储结构 135
6.3.2 二叉树的链式存储结构 136
6.4 二叉树的遍历及其他操作 137
6.4.1 二叉树遍历的概念 137
6.4.2 二叉树遍历的递归算法 138
6.4.3 二叉树遍历的非递归算法 140
6.4.4 二叉树的其他操作 143
6.5 线索二叉树 145
6.5.1 线索二叉树的概念 145
6.5.2 线索化二叉树 146
6.5.3 遍历线索二叉树 148
6.6 树和森林 149
6.6.1 树的存储结构 149
6.6.2 二叉树与树、森林之间的转换 152
6.6.3 树和森林的遍历 154
6.7 哈夫曼树 155
6.7.1 哈夫曼树的概述 155
6.7.2 哈夫曼树的构造 156
6.7.3 哈夫曼编码 157
6.7.4 相关算法 158
习题6 161
第7章 图 165
7.1 图的概述 165
7.1.1 图的定义 165
7.1.2 图的相关术语 166
7.1.3 图的ADT描述 169
7.2 图的存储结构 170
7.2.1 邻接矩阵存储结构 170
7.2.2 邻接表存储结构 173
7.3 图的遍历 176
7.3.1 深度优先遍历 177
7.3.2 广度优先遍历 179
7.3.3 非连通图的遍历 181
7.4 最小生成树 182
7.4.1 生成树和最小生成树的概念 182
7.4.2 普里姆算法 183
7.4.3 克鲁斯卡尔算法 185
7.5 拓扑排序与关键路径 187
7.5.1 拓扑排序 187
7.5.2 关键路径 191
7.6 最短路径 195
7.6.1 单源最短路径 196
7.6.2 任意两个顶点间的最短路径 199
习题7 202
第8章 查找 208
8.1 基本概念 208
8.1.1 相关术语 208
8.1.2 查找表结构 209
8.2 静态查找表 209
8.2.1 顺序查找 210
8.2.2 二分查找 210
8.2.3 分块查找 213
8.3 动态查找表 214
8.3.1 二叉排序树 214
8.3.2 平衡二叉树 220
8.3.3 B-树 227
8.3.4 B+树 232
8.4 哈希表查找 233
8.4.1 哈希表的基本概念 233
8.4.2 哈希函数构造方法 234
8.4.3 哈希冲突解决方法 236
8.4.4 哈希表的查找过程 240
8.4.5 哈希表的性能分析 240
习题8 241
第9章 排序 246
9.1 排序的相关术语与概念 246
9.2 插入排序 247
9.2.1 直接插入排序 247
9.2.2 希尔排序 249
9.3 交换排序 251
9.3.1 冒泡排序 251
9.3.2 快速排序 253
9.4 选择排序 256
9.4.1 直接选择排序 256
9.4.2 堆排序 257
9.5 归并排序 261
9.6 基数排序 264
9.7 各种排序方法比较 267
习题9 268
参考文献 272

1. C语言程序设计实验指导与实训（第二版） [主编 倪燃]
2. 程序思维与C语言实现 [张祎 王俊海 吕波]
3. C语言程序设计 [魏琴 刘祖珉 赵仕波 肖阳春]
4. C语言程序设计实验教程 [张小刚 司春景]
5. Java Web项目化设计实践教程 [邱云 曾陈萍]
6. C语言程序设计（第三版） [主编 丁红 王立新 蔡开立]
7. Python数据分析 [主编　冯志辉　赵磊　李放]
8. 大学信息技术 [曾翰颖 编著]
9. 多维视域下的高校篮球教学创新研究 [张利超 李宁 著]
10. 创新创业训练实践教程 [主编 王日华 陈武 黄喆诚]
11. 实用运筹学 [主编　邢育红　于晋臣]
12. 电子技术（第二版） [主编 覃爱娜 李飞]
13. 劳动争议处理实务 [主编 王秀卿 罗静]
14. 语音识别理论与实践 [主编　莫宏伟]
15. 武术基础教程 [主编 李代勇 谢志民]
16. 画法几何与机械制图习题集（多学时） [主编 赵军]
17. 机械设计基础（第二版） [主编 田亚平 李爱姣]
18. 画法几何与机械制图 [主编 赵军]
19. C语言程序设计习题与实验指导（第二版） [主编 甄增荣 张宾]
20. C语言程序设计（第二版） [主编 甄增荣 田云霞]
21. Unity3D虚拟现实应用开发实践 [主 编 刘龙]
22. C语言程序设计实践教程（活页式） [主编 郑茵 陈巍 滕泓虬]
23. 面向对象程序设计 [主编 张勇 张平华 赵小龙]
24. 数据结构（Python语言描述） [曹岳辉　刘卫国　康松林　编著]
25. 网络营销 [主编 夏薇薇 刘婷 尚洁]
26. C语言程序设计 [姜雪]
27. 数据库技术与应用实践教程（SQL Server 2019） [主 编 严晖 周肆清]
28. C语言程序设计项目化教程（活页式） [主编 张利华 潘晓利]
29. 功能材料制备与表征实验指导书 [龚伟平 赵军峰 梅海娟 等编著]
30. 信号与系统（第二版） [主编 张宇]