数据结构（C语言版）

内容详尽，由浅入深

基于需求，面向应用

案例精讲，注重实战

“数据结构”是计算机专业及其相关专业的一门重要专业基础课，也是一门必修的核心课程，并且已成为其他理工专业的热门选修课。

在计算机科学的各领域中，都要使用到各种不同的数据结构，如编译系统中要使用栈、散列表、语法树等，操作系统中要使用队列、存储管理表、目录树等，数据库系统中要使用线性表、链表、索引树等；人工智能中要使用广义表、检索树、有向图等；同样在面向对象的程序设计、计算机图形学、软件工程、多媒体技术、计算机辅助设计等领域，也都会用到各种不同的数据结构。因此，学好数据结构，对从事计算机技术及相关领域的工作人员来说，是非常重要的，用户可掌握各种常用的数据结构及算法实现，以及每一种算法的时间复杂度分析和空间复杂度分析，知道在什么情况下，使用什么样的数据结构最方便，为以后研究和开发大型程序打下基础。

学习数据结构的主要任务是：讨论现实世界中的各种数据（数字、字符、字符串、声音、图形、图像等）的逻辑结构、其在计算机中的各种存储结构（存储表示）以及对各种非数值运算的算法实现；分析各种不同算法的好坏及其在什么地方应用比较合适。通过“数据结构”课程的学习，学生应具备使用所学的数据结构知识来解决实际问题及评价算法优劣的能力，为以后学习后续计算机专业课程及走上工作岗位从事计算机大型软件开发工作铺平道路。

本书内容共11章，第1章介绍了数据结构与算法等一些基本术语，并对算法描述及算法分析作了简单说明，介绍了衡量算法优劣的主要因素，即时间复杂度和空间复杂度的求法；第2章到第4章介绍了线性结构（线性表、栈、队列、串）的逻辑特征，及一些常用算法的实现及基本应用；第5章到第7章介绍了非线性结构（多维数组、广义表、树、二叉树、图）的逻辑特征，及其在计算机中的存储表示和一些常用算法实现及基本应用；第8章到第10章介绍了在计算机中使用得非常广泛的两种运算，即查找和排序（排序又可以分为内排序和外排序），对一些常用的查找、排序方法进行了详细说明，并给出了实现的算法及时间复杂度和空间复杂度分析；第11章介绍了外存的文件的几种存储形式及组织方式。各章内容有相对独立的部分，可便于不同院校不同专业按需要组织教学。全书侧重于数据结构的应用，力求讲授内容与具体的计算机应用实例相结合，以便于学生加深对各章内容的理解和掌握。

本书采用结构化的程序设计语言（C语言）作为算法的描述语言，所有算法都已经上机调试通过。但是，由于篇幅所限，大部分算法都是以单独的函数形式给出，若读者要运行这些算法，还必须给出一些变量的说明及主函数来调用所给的函数。因此，本书中的算法描述比用类Pascal语言或类C语言描述的算法更直观，更易于学生理解和接受。作者在十几年的“数据结构”课程教学中，对数据结构中的各种算法进行了认真的研究和分析，积累了丰富的经验，因此，书中所选的例题和习题都具有一定的针对性，都是针对特定的数据结构来描述的，能为复杂的数据结构算法描述架桥铺路。

本书中所有算法都在VC++ 6.0环境下运行通过，由于篇幅所限，书中仅给出了实现某功能算法的函数。为了方便教学，本书免费为授课教师提供用PowerPoint制作的电子教案，教师在使用时可以根据需要进行必要的修改。

本书可以作为高等院校计算机类或信息类相关专业“数据结构”课程教材，建议讲授课时为50至60学时，上机实践课时为20至30学时。各院校教师可根据自己学校的专业特点和学生的实际情况适当增删。

本书由李根强、刘浩、谢月娥担任主编，李根强负责全书的统稿、修改、定稿工作。

由于编者水平有限，书中难免存在不妥或错误之处，恳请专家和广大读者批评指正。

编 者

2017年1月

第1章 绪论 1
本章学习目标 1
1.1 什么是数据结构 1
1.1.1 数据结构示例 1
1.1.2 基本术语 2
1.1.3 数据结构 3
1.2 算法描述 5
1.2.1 基本概念 5
1.2.2 算法描述 5
1.3 算法分析 6
1.3.1 时间复杂度 6
1.3.2 空间复杂度 7
本章小结 8
习题一 8
第2章 线性表 12
本章学习目标 12
2.1 线性表的定义及运算 12
2.1.1 线性表的定义 12
2.1.2 线性表的运算 13
2.1.3 线性表的抽象数据类型描述 13
2.2 线性表的顺序存储结构 14
2.2.1 顺序表结构 14
2.2.2 顺序表运算 15
2.2.3 顺序表存储空间的动态分配 18
2.3 线性表的链式存储结构 19
2.3.1 单链表结构 19
2.3.2 单链表运算 20
2.3.3 循环链表结构 25
2.3.4 双向链表结构 27
2.4 一元多项式的表示及相加 29
2.4.1 一元多项式的表示 29
2.4.2 一元多项式的相加 30
2.5 顺序表与链表的比较 32
2.6 算法应用举例 32
本章小结 35
习题二 35
第3章 栈和队列 37
本章学习目标 37
3.1 栈 37
3.1.1 栈的定义 37
3.1.2 栈的运算 37
3.1.3 栈的抽象数据类型描述 38
3.1.4 顺序栈 39
3.1.5 链栈 42
3.1.6 栈的应用 44
3.2 队列 49
3.2.1 队列的定义 49
3.2.2 队列的基本运算 49
3.2.3 队列的抽象数据类型描述 50
3.2.4 循环队列 50
3.2.5 链队列 53
3.2.6 队列的应用 55
本章小结 55
习题三 55
第4章 串 58
本章学习目标 58
4.1 串的定义及运算 58
4.1.1 基本概念 58
4.1.2 串的运算 59
4.1.3 串的抽象数据类型描述 59
4.2 串的存储结构 60
4.2.1 顺序存储 60
4.2.2 链式存储 61
4.2.3 索引存储 61
4.3 串运算的实现 62
4.3.1 串插入 62
4.3.2 串删除 64
4.3.3 子串定位 65
4.4 串操作应用举例 67
4.4.1 文本编辑 67
4.4.2 建立词索引表 68
本章小结 68
习题四 69
第5章 多维数组和广义表 70
本章学习目标 70
5.1 多维数组 70
5.1.1 多维数组的概念 70
5.1.2 多维数组在计算机内的存储 71
5.2 多维数组的存储结构 71
5.2.1 行优先顺序 71
5.2.2 列优先顺序 72
5.3 特殊矩阵及其压缩存储 72
5.3.1 特殊矩阵 72
5.3.2 压缩存储 73
5.4 稀疏矩阵 76
5.4.1 稀疏矩阵的存储 76
5.4.2 稀疏矩阵的运算 79
5.5 广义表 87
5.5.1 基本概念 87
5.5.2 存储结构 88
5.5.3 基本运算 89
本章小结 91
习题五 92
第6章 树和二叉树 94
本章学习目标 94
6.1 树的基本概念 94
6.1.1 树的定义 94
6.1.2 基本术语 96
6.1.3 树的表示 97
6.1.4 树的性质 97
6.2 二叉树 98
6.2.1 二叉树的定义 98
6.2.2 二叉树的性质 99
6.2.3 二叉树的存储结构 101
6.2.4 二叉树的抽象数据类型 104
6.3 遍历二叉树 104
6.3.1 前根遍历 104
6.3.2 中根遍历 105
6.3.3 后根遍历 106
6.3.4 遍历算法应用举例 109
6.4 线索二叉树 112
6.4.1 线索的概念 112
6.4.2 线索的描述 113
6.4.3 线索的算法实现 114
6.4.4 线索二叉树上的运算 115
6.5 树和森林 118
6.5.1 树的存储结构 118
6.5.2 树、森林和二叉树的转换 120
6.5.3 树和森林的遍历 121
6.6 回溯法与树的遍历 122
6.7 哈夫曼树 124
6.7.1 基本术语 124
6.7.2 哈夫曼树简介 124
6.7.3 哈夫曼树的应用 127
本章小结 128
习题六 129
第7章 图 132
本章学习目标 132
7.1 图的基本概念 132
7.1.1 图的定义 132
7.1.2 图的基本术语 132
7.2 图的存储结构 135
7.2.1 邻接矩阵 135
7.2.2 邻接表 138
7.2.3 邻接多重表 142
7.3 图的遍历 142
7.3.1 深度优先搜索遍历 142
7.3.2 广度优先搜索遍历 147
7.4 生成树和最小生成树 150
7.4.1 基本概念 150
7.4.2 普里姆（Prim）算法 152
7.4.3 克鲁斯卡尔（Kruskal）算法 155
7.5 最短路径 157
7.5.1 单源点最短路径 158
7.5.2 所有顶点对之间的最短路径 160
7.6 有向无环图及其应用 163
7.6.1 拓扑排序 164
7.6.2 关键路径 167
本章小结 172
习题七 172
第8章 查找 176
本章学习目标 176
8.1 查找的基本概念 176
8.2 线性表的查找 177
8.2.1 顺序查找 177
8.2.2 二分查找 178
8.2.3 索引查找 181
8.2.4 分块查找 184
8.3 树表查找 186
8.3.1 二叉排序树查找 186
8.3.2 平衡二叉树查找 190
8.3.3 B树及B+树上的查找 194
8.3.4 键树 195
8.4 散列查找 196
8.4.1 基本概念 196
8.4.2 散列函数的构造 197
8.4.3 解决冲突的方法 199
8.4.4 散列查找算法实现 202
8.4.5 散列查找的性能分析 204
本章小结 206
习题八 207
第9章 内排序 209
本章学习目标 209
9.1 基本概念 209
9.1.1 排序介绍 209
9.1.2 基本概念 210
9.2 插入排序 211
9.2.1 直接插入排序 211
9.2.2 二分插入排序 212
9.2.3 希尔排序 213
9.3 交换排序 214
9.3.1 冒泡排序 214
9.3.2 快速排序 215
9.4 选择排序 218
9.4.1 直接选择排序 218
9.4.2 树形选择排序 219
9.4.3 堆排序 221
9.5 归并排序 225
9.5.1 二路归并排序 225
9.5.2 多路归并排序 227
9.6 分配排序 227
9.6.1 多关键字排序 227
9.6.2 基数排序 227
9.7 各种内排序方法的比较和选择 230
9.7.1 各种内排序方法的比较 230
9.7.2 各种内排序方法的选择 231
本章小结 231
习题九 232
第10章 外排序 234
本章学习目标 234
10.1 外排序的基本概念 234
10.2 多路平衡归并的实现 235
10.2.1 初始归并段的生成 235
10.2.2 多路平衡归并的实现 237
本章小结 242
习题十 243
第11章 文件 244
本章学习目标 244
11.1 文件的基本概念 244
11.2 顺序文件 244
11.3 索引文件 245
11.4 ISAM文件和VSAM文件 246
11.4.1 ISAM文件 246
11.4.2 VSAM文件 247
11.5 散列文件 247
11.6 多关键字文件 248
11.6.1 多重表文件 249
11.6.2 倒排文件 249
本章小结 250
习题十一 251
参考文献 252

1. 机械制图 [许淑珍 于利民]
2. 微积分（经管类）导学篇（下册） [王海棠 曹海军 周玲丽]
3. 大学生创新创业基础 [主编 姜国权 姜福佳]
4. 农产品云仓模式研究—以北京农产品流通物流供应链重构为例 [武晓钊 王成林 王春娟 等著]
5. 信息技术（微课版） [王云　徐江鸿　李清霞　罗学锋　]
6. 管理基础与实务 [主编 王凤基 颜汉军]
7. 高等数学导学篇（下册） [主编 李文婧 胡雷 尹金生]
8. 高等数学导学篇（上册） [主编 李文婧 胡雷 尹金生]
9. 高等数学（下册） [主编 李爱芹 胡雷 尹金生]
10. 高等数学（上册） [主编 李爱芹 胡雷 尹金生]
11. 庭院风骨—树、灌、篱 [创意房主 著]
12. Python语言程序设计教程 [郭其标 房宜汕]
13. 微积分（经管类）教程篇（下册） [曹海军 王海棠 周玲丽]
14. 微积分（经管类）教程篇（上册） [曹海军 王海棠 周玲丽]
15. 微积分（经管类）导学篇（上册） [王海棠 曹海军 周玲丽]
16. 网站前端技术案例教程（HTML+CSS+JavaScript）（第二版） [黄华升]
17. 线性代数 [主编 史昱 陈凤欣]
18. 电力电子技术课程学习及实验指导 [主编 陈荣]
19. 成长对话：青春的榜样 [主编　施端银　黄武刚　应巨林]
20. 人工智能应用基础 [主编 杨缨 李佳]
21. 中华水文化（慕课版）（第二版） [毕雪燕 杨华轲 罗玲谊 等编著]
22. 电路与电子技术Ⅱ——电路分析基础 [主编 陈晓 金哲]
23. 飞机维修专业英语——飞机系统（第二版） [赵迎春]
24. 英语大爆炸：跟趣味情景剧学口语（微课版） [秦然　编著]
25. 机械工程制图任务跟踪训练 [主编 王瑞清 赵金考 周彦云 ]
26. 机械工程制图 [主编 覃国萍 刘百顺 禹晨]
27. 平面设计与制作项目化教程 [主编　李晨]
28. 后期影像剪辑技术 [主编　郭建伟]
29. 人工智能概论（第二版） [主编　任云晖　丁红　徐迎春 ]
30. 信息时代美育之道 [主编　刘宏宇　黎娅]