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

前 言 本书是中国大学MOOC（慕课）爱课程平台、智慧树平台上由西安理工大学建设的数据结构课程的配套使用教材，它适合本科、高职高专计算机相关专业在校学生和对数据结构有兴趣的初学者线上或线下学习使用。 “数据结构”是计算机科学大类中（包括所有专业方向）的一门核心专业基础课程，是计算机程序设计的重要理论和实践基础。学习本课程可为后续课程（如操作系统、数据库原理、编译原理、软件工程、图形处理等）和未来的工程实践打下良好的理论基础。 为配合线上慕课的实施，本书以慕课教学推进次序为主线，将每章每节中的知识进行合理划分，分为若干个小知识点。知识点的讲解除教材中文字描述外，还配套了相应的教学视频（扫描二维码观看），视频时长控制为3～5分钟。因此本书可用于线上、线上线下混合及线下等多种教学模式。 为落实新工科理念，培养出具有更高编程能力的人才，教材各章内容均有应用实例讲解及学科前沿综合应用案例讲解，使读者可以深入理解数据结构中的经典算法，并将其应用在实际问题的解决中。 本书特别融入了课程思政的内容，体现了立德树人的理念。 数据结构的原理与算法都比较抽象和枯燥，学习起来比较难理解。本书中对抽象的算法进行了深入浅出的描述，并以二维码的方式提供相应算法的动画演示过程，以加深读者对算法的理解，提高读者的学习兴趣。 教材中二维码对应的教学视频是对课程中的重点、难点知识的讲解。如果需要，读者可通过中国大学MOOC爱课程平台、智慧树平台加入由西安理工大学建设的数据结构课程进行学习，并观看完整的教学视频。在讨论区教师可以解答读者提出的问题。 本书共8章。第1章介绍数据结构的基本概念，以及算法与评价；第2章介绍线性表的概念，以及两种存储方式（顺序存储和链式存储）下的运算实现；第3章介绍栈、队列的特点，以及不同存储方式下运算的实现；第4章介绍特殊矩阵、稀疏矩阵的压缩存储，广义表的概念与存储，以及串的基础知识和模式匹配算法；第5章介绍树与二叉树的概念、存储、运算与实现，以及哈夫曼编码；第6章介绍图的概念、存储、运算与实现，以及几个图的经典应用；第7章介绍常用的几个静态和动态查找算法；第8章介绍常用的几类排序算法及其性能比较。 本书由西安理工大学多位有着多年丰富教学经验的教师编写完成。其中：第1、2章由罗作民编写；第3、6章由范翠香编写；第4、5章由宋昕编写；第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