本书介绍了数据结构的基本概念和基本算法。全书共分为10章,包括概论,线性表及其顺序存储,线性表的链式存储,字符串、集合和特殊数组,递归,树型结构,二叉树,图,检索,排序等内容。 本书内容丰富,逻辑性强,文字清晰流畅,既注重理论知识,又强调工程实用。书中既体现了抽象数据类型的观点,又对每个算法的具体实现给出了完整的C语言源代码描述。本书配套资源丰富,包含代码、PPT课件、教案、教学大纲、实验详细指导、习题答案及解析等教学资源,同时**内容录制了微课视频,支持线上线下混合教学。 本书可作为高等院校计算机专业及相关专业本科生“数据结构”课程的教材,也可以作为从事计算机工程与应用的广大读者的参考书。

第 1 章 概论 ............................................... 1 1.1 数据结构的基本概念与术语 .................................. 1 1.1.1 数据结构的基本概念..................................................1 1.1.2 数据的逻辑结构.........................................................2 1.1.3 数据的存储结构.........................................................3 1.1.4 数据的运算集合.........................................................5 1.2 数据类型和抽象数据类型..................................... 5 1.2.1 数据类型....................................................................6 1.2.2 抽象数据类型.............................................................6 1.2.3 抽象数据类型的描述和实现........................................7 1.3 算法和算法分析 ................................................ 8 1.3.1 算法的基本概念和基本特征........................................8 1.3.2 算法的时间复杂度和空间复杂度.................................8 本章小结 ................................................................ 9 习题.....................................................................10 第 2 章 线性表及其顺序存储.......................... 12 2.1 线性表...........................................................12 2.2 顺序表 ..........................................................12 2.2.1 顺序表的基本概念及描述 .........................................12 2.2.2 顺序表的实现...........................................................13 2.3 栈 ................................................................17 2.3.1 栈的基本概念及描述 ................................................17 2.3.2 顺序栈及其实现 .......................................................18 2.3.3 栈的应用之一——括号匹配......................................20 2.3.4 栈的应用之二——算术表达式求值 ...........................22 2.4 队列 .............................................................26 2.4.1 队列的基本概念及描述.............................................26 2.4.2 顺序队列及其实现....................................................27 2.4.3 顺序循环队列及其实现.............................................30 2.4.4 队列的应用..............................................................31 本章小结 ...............................................................32 习题.....................................................................32 第 3 章 线性表的链式存储 ............................ 34 3.1 链式存储........................................................34 3.2 单链表 ..........................................................35 3.2.1 单链表的基本概念及描述 .........................................35 3.2.2 单链表的实现...........................................................36 3.3 带头节点的单链表 ........................................... 39 3.3.1 带头节点的单链表的基本概念及描述........................39 3.3.2 带头节点的单链表的实现 .........................................40 3.4 循环单链表.....................................................43 3.4.1 循环单链表的基本概念及描述..................................43 3.4.2 循环单链表的实现....................................................44 3.5 双链表 ......................................................... 49 3.5.1 双链表的基本概念及描述.........................................49 3.5.2 双链表的实现...........................................................49 3.6 链式栈 ......................................................... 54 3.6.1 链式栈的基本概念及描述.........................................54 3.6.2 链式栈的实现...........................................................54 3.7 链式队列........................................................57 3.7.1 链式队列的基本概念及描述......................................57 3.7.2 链式队列的实现 .......................................................57 本章小结 .............................................................. 60 习题.....................................................................61 第 4 章 字符串、集合和特殊数组.................... 63 4.1 字符串...........................................................63 4.1.1 字符串的基本概念....................................................63 4.1.2 字符串类的定义.......................................................64 4.1.3 字符串的存储结构及其实现......................................65 4.2 字符串的模式匹配 ............................................71 4.2.1 朴素模式匹配算法....................................................71 4.2.2 快速模式匹配算法....................................................72 4.3 集合 .............................................................75 4.3.1 集合的定义和性质....................................................75 4.3.2 集合类的定义...........................................................76 4.3.3 集合的存储结构及其实现.........................................76 4.4 数组 ............................................................ 84 4.4.1 数组和数组元素.......................................................84 4.4.2 数组类的定义...........................................................85 4.4.3 数组的顺序存储及其实现.........................................86 4.5 特殊矩阵....................................................... 89 4.5.1 对称矩阵的压缩存储................................................89 2 4.5.2 三角矩阵的压缩存储................................................90 4.5.3 带状矩阵的压缩存储................................................92 4.6 稀疏矩阵....................................................... 93 4.6.1 稀疏矩阵类的定义....................................................93 4.6.2 稀疏矩阵的顺序存储及其实现..................................94 4.6.3 稀疏矩阵的链式存储及其实现..................................96 本章小结 .............................................................100 习题...................................................................100 第 5 章 递归 ........................................... 102 5.1 递归的基本概念与递归程序设计 .........................102 5.2 递归程序执行过程的分析..................................104 5.3 递归程序到非递归程序的转换 ............................106 5.3.1 简单递归程序到非递归程序的转换.........................107 5.3.2 复杂递归程序到非递归程序的转换 .........................109 5.4 递归程序设计的应用实例.................................. 114 本章小结 ............................................................. 116 习题...................................................................116 第 6 章 树状结构...................................... 118 6.1 树的基本概念 ................................................ 118 6.2 树类的定义...................................................120 6.3 树的存储结构................................................120 6.3.1 双亲表示法............................................................120 6.3.2 孩子表示法............................................................121 6.3.3 孩子兄弟表示法.....................................................124 6.4 树的遍历......................................................125 6.5 树的线性表示................................................128 6.5.1 树的括号表示.........................................................128 6.5.2 树的层号表示.........................................................130 6.6 并查集 ........................................................ 131 6.6.1 并查集的定义.........................................................131 6.6.2 并查集的构建.........................................................132 6.6.3 基于树状结构的并查集实现....................................132 本章小结 .............................................................137 习题...................................................................138 3 第 7 章 二叉树 ........................................ 139 7.1 二叉树的基本概念 ..........................................139 7.2 二叉树的基本操作 .......................................... 141 7.3 二叉树的存储结构 .......................................... 141 7.3.1 顺序存储结构.........................................................142 7.3.2 链式存储结构.........................................................143 7.4 二叉树的遍历................................................145 7.4.1 二叉树遍历的定义..................................................145 7.4.2 二叉树遍历的递归实现...........................................145 7.4.3 二叉树遍历的非递归实现.......................................147 7.5 二叉树其他运算的实现.....................................150 7.6 线索二叉树...................................................152 7.6.1 线索二叉树的定义..................................................152 7.6.2 中序线索二叉树的基本操作....................................153 7.6.3 中序线索二叉树的存储结构及其实现......................154 7.7 树、森林和二叉树的转换..................................156 7.7.1 树、森林到二叉树的转换.......................................156 7.7.2 二叉树到树、森林的转换 .......................................157 本章小结 .............................................................158 习题...................................................................158 第 8 章 图 .............................................. 160 8.1 图的基本概念 ................................................160 8.2 图的基本操作................................................163 8.3 图的基本存储结构 ..........................................164 8.3.1 邻接矩阵及其实现..................................................164 8.3.2 邻接表及其实现.....................................................167 8.3.3 邻接多重表............................................................169 8.4 图的遍历......................................................170 8.4.1 深度优先遍历 ........................................................170 8.4.2 广度优先遍历.........................................................172 8.5 生成树与*小生成树 .......................................173 8.5.1 *小生成树的定义 .................................................175 8.5.2 *小生成树的 Prim 算法 ........................................176 8.5.3 *小生成树的 Kruskal 算法 ...................................179 8.6 *短路径......................................................182 8.6.1 单源*短路径 ........................................................182 4 8.6.2 所有顶点对的*短路径...........................................185 8.7 拓扑排序......................................................188 8.8 关键路径...................................................... 191 本章小结 .............................................................196 习题...................................................................196 第 9 章 查找 ........................................... 200 9.1 查找的基本概念 .............................................200 9.2 线性表的查找................................................201 9.2.1 顺序查找................................................................201 9.2.2 二分查找................................................................203 9.2.3 分块查找................................................................205 9.3 二叉排序树...................................................207 9.4 丰满树和平衡树 .............................................213 9.4.1 丰满树...................................................................214 9.4.2 平衡二叉排序树.....................................................215 9.4.3 扩充二叉树............................................................222 9.5 红黑树 ........................................................223 9.5.1 红黑树的定义.........................................................224 9.5.2 红黑树的插入.........................................................224 9.5.3 红黑树的删除.........................................................227 9.6 *佳二叉排序树和 Huffman 树 .........................230 9.6.1 *佳二叉排序树.....................................................230 9.6.2 Huffman 树...........................................................235 9.7 B 树 ...........................................................238 9.7.1 B-树的定义 ...........................................................238 9.7.2 B-树的基本操作 ....................................................239 9.7.3 B 树 .....................................................................243 9.8 散列表查找...................................................245 9.8.1 散列存储 ...............................................................245 9.8.2 散列函数的构造.....................................................246 9.8.3 冲突处理 ...............................................................247 本章小结 .............................................................251 习题...................................................................251 第 10 章 排序.......................................... 255 10.1 排序的基本概念 ...........................................255 5 10.2 插入排序....................................................256 10.2.1 直接插入排序 ......................................................256 10.2.2 二分法插入排序...................................................259 10.2.3 表插入排序..........................................................260 10.2.4 Shell 插入排序 ....................................................262 10.3 选择排序....................................................263 10.3.1 直接选择排序 ......................................................263 10.3.2 树状选择排序 ......................................................265 10.3.3 堆排序.................................................................267 10.4 交换排序....................................................271 10.4.1 冒泡排序 .............................................................271 10.4.2 快速排序 .............................................................272 10.5 归并排序....................................................274 10.6 基数排序....................................................278 10.6.1 多排序码的排序...................................................278 10.6.2 静态链式基数排序 ...............................................278 10.7 外部排序....................................................281 10.7.1 磁盘排序 .............................................................282 10.7.2 多路平衡归并 ......................................................283 10.7.3 置换-选择排序.....................................................285 10.7.4 *佳归并树..........................................................288 本章小结 .............................................................290 习题...................................................................291 附录 1 基础实验 ...................................... 294 实验 1 线性表的顺序存储实现 .................................294 实验 2 不带头节点的单链表....................................297 实验 3 带头节点的单链表.......................................301 实验 4 栈与字符串 ...............................................303 实验 5 递归........................................................306 实验 6 树...........................................................310 实验 7 二叉树.....................................................312 实验 8 图...........................................................315 实验 9 查找........................................................317 实验 10 排序 ......................................................318 附录 2 综合实验