数据结构(C语言描述) 慕课版

本书是中国大学MOOC（慕课）爱课程平台、智慧树平台上由西安理工大学建设的数据结构课程的配套使用教材。为配合线上慕课的实施，本书以慕课教学推进次序为主线，将知识划分为小知识点，并配有相应的教学视频（扫描二维码观看）。本书共8章。第1章介绍数据结构的基本概念，以及算法与评价；第2章介绍线性表的概念，以及两种存储方式（顺序存储和链式存储）下的运算实现；第3章介绍栈、队列的特点，以及不同存储方式下运算的实现；第4章介绍特殊矩阵、稀疏矩阵的压缩存储，广义表的概念与存储，以及串的基础知识和模式匹配算法；第5章介绍树与二叉树的概念、存储、运算与实现，以及哈夫曼编码；第6章介绍图的概念、存储、运算与实现，以及几个图的经典应用；第7章介绍常用的几个静态和动态查找算法；第8章介绍常用的几类排序算法及其性能比较。本书可用于线上、线上线下混合及线下等多种教学模式，适合作为本科、高职高专计算机相关专业教材，也可供对数据结构有兴趣的初学者线上或线下学习使用。

第1章 绪论 1
1.1 数据结构的概念 1
1.1.1 数据结构的研究方向 1
1.1.2 数据结构的基本术语 3
1.1.3 数据类型与抽象数据类型 5
1.2 算法与算法分析 5
1.2.1 算法的概念与描述 5
1.2.2 算法分析 8
1.3 本章小结 12
习题1 12
第2章 线性表 15
2.1 线性表的概念 15
2.1.1 线性表的定义与特点 15
2.1.2 线性表的基本运算 16
2.1.3 线性表的抽象数据类型定义 16
2.2 线性表的顺序存储 17
2.2.1 线性表的顺序存储及其特点 17
2.2.2 顺序表基本运算的实现 17
2.2.3 线性表的顺序存储优缺点 20
2.3 线性表的链式存储 21
2.3.1 线性表的链式存储及其特点 21
2.3.2 单链表的建立 23
2.3.3 单链表插入和删除运算的实现 26
2.3.4 单向循环链表 29
2.3.5 双向链表及其运算 31
2.3.6 静态链表 34
2.3.7 线性表链式存储的优缺点 35
2.4 线性表的应用 36
2.4.1 线性表存储结构的选择 36
2.4.2 线性表的应用举例 36
2.5 本章小结 39
习题2 39
第3章 栈和队列 42
3.1 栈的定义与基本运算 42
3.2 栈的存储与运算实现 43
3.2.1 顺序栈及其运算实现 43
3.2.2 链栈及其运算实现 45
3.2.3 栈的应用―括号匹配 47
3.3 队列的定义与基本运算 49
3.4 队列的存储与运算实现 49
3.4.1 顺序队列及其运算实现 49
3.4.2 假溢出与循环队列 51
3.4.3 链队列及其运算实现 52
3.5 栈和队列的综合应用 54
3.5.1 栈的综合应用 54
3.5.2 队列的综合应用 58
3.6 本章小结 59
习题3 60
第4章 数组、广义表与串 63
4.1 数组的概念与存储 63
4.1.1 数组的概念 63
4.1.2 数组的存储 64
4.1.3 特殊矩阵的压缩存储 65
4.1.4 稀疏矩阵的压缩存储 66
4.2 广义表 69
4.2.1 广义表的概念与术语 69
4.2.2 广义表的运算 69
4.2.3 广义表的存储 70
4.3 串的定义与存储 71
4.3.1 串的定义 71
4.3.2 串的存储 71
4.3.3 串的常见运算 73
4.4 串的模式匹配 74
4.4.1 串的模式匹配BF算法 74
4.4.2 串的模式匹配KMP算法 75
4.5 数组的应用举例 80
4.6 串的应用举例 82
4.7 本章小结 83
习题4 84
第5章 树与二叉树 86
5.1 树的基本概念与性质 86
5.1.1 树的定义与术语 86
5.1.2 树的表示与基本运算 87
5.2 二叉树的概念与存储 88
5.2.1 二叉树的定义及基本运算 88
5.2.2 二叉树的性质 90
5.2.3 二叉树的存储 91
5.2.4 二叉树的建立 93
5.3 二叉树性质应用举例 95
5.4 二叉树的遍历 96
5.4.1 二叉树遍历的概念与思想 96
5.4.2 二叉树遍历的递归算法 97
5.4.3 二叉树的层次遍历 98
5.4.4 二叉树的非递归遍历 99
5.5 线索二叉树 102
5.5.1 二叉树的线索化 103
5.5.2 遍历线索二叉树 105
5.6 树与森林 108
5.6.1 树的存储 108
5.6.2 树及森林与二叉树的转换 111
5.6.3 树与森林的遍历 113
5.7 哈夫曼树与哈夫曼编码 114
5.7.1 哈夫曼编码概述 114
5.7.2 哈夫曼树与哈夫曼编码的实现 115
5.8 树与二叉树的应用举例 120
5.9 本章小结 122
习题5 123
第6章 图 126
6.1 图的概念与性质 126
6.1.1 图的定义 126
6.1.2 图的有关术语 127
6.1.3 图的基本运算 130
6.2 图的存储 131
6.2.1 图的邻接矩阵存储 131
6.2.2 图的邻接表存储 134
6.2.3 图的十字链表存储与邻接多重表存储 136
6.3 图的遍历 137
6.3.1 图的深度优先遍历 138
6.3.2 图的广度优先遍历 141
6.4 最小生成树 146
6.4.1 Prim算法构造最小生成树 147
6.4.2 Kruskal算法构造最小生成树 149
6.5 最短路径 152
6.5.1 单源最短路径―Dijkstra算法 153
6.5.2 任意两个顶点间最短路径―Floyd算法 157
6.6 拓扑序列 160
6.6.1 拓扑序列的概念 161
6.6.2 拓扑序列的构造 162
6.6.3 拓扑序列的应用举例 164
6.7 关键路径 164
6.7.1 关键路径的概念 165
6.7.2 关键路径的构造 166
6.7.3 关键路径的应用举例 167
6.8 图的综合应用举例 169
6.9 本章小结 171
习题6 172
第7章 查找 176
7.1 查找的基本概念 176
7.1.1 查找的定义与分类 176
7.1.2 查找算法的性能评价 177
7.2 基于线性表的查找 178
7.2.1 顺序查找 178
7.2.2 折半查找 179
7.2.3 分块查找 181
7.3 基于树表的查找 182
7.3.1 二叉排序树 183
7.3.2 平衡二叉排序树 187
7.3.3 B-树 191
7.3.4 B+树 195
7.4 基于哈希表的查找 196
7.4.1 哈希查找的基本思想 196
7.4.2 哈希函数的构造 197
7.4.3 常见冲突处理方法 198
7.4.4 哈希表的基本运算 200
7.5 查找算法的应用举例 203
7.6 本章小结 204
习题7 205
第8章 排序 207
8.1 排序的基本概念 207
8.1.1 排序的定义及分类 207
8.1.2 排序算法的性能评价指标 208
8.2 插入排序 209
8.2.1 直接插入排序 209
8.2.2 折半插入排序 211
8.2.3 希尔排序 212
8.3 交换排序 214
8.3.1 冒泡排序 214
8.3.2 快速排序 216
8.4 选择排序 219
8.4.1 简单选择排序 219
8.4.2 堆排序 220
8.5 归并排序 224
8.6 多关键字排序 226
8.6.1 多关键字排序的基本概念 226
8.6.2 基数排序 227
8.7 排序算法的应用举例 230
8.8 本章小结 231
习题8 233
参考资料 236