本书介绍了数据结构的基本概念和基本算法。全书共分为10章，包括概论，线性表及其顺序存储，线性表的链式存储，字符串、集合和特殊数组，递归，树型结构，二叉树，图，检索，排序等内容。
本书内容丰富，逻辑性强，文字清晰流畅，既注重理论知识，又强调工程实用。书中既体现了抽象数据类型的观点，又对每个算法的具体实现给出了完整的C语言源代码描述。本书配套资源丰富，包含代码、PPT课件、教案、教学大纲、实验详细指导、习题答案及解析等教学资源，同时重点内容录制了微课视频，支持线上线下混合教学。
本书可作为高等院校计算机专业及相关专业本科生数据结构课程的教材，也可以作为从事计算机工程与应用的广大读者的参考书。
【内容特点】
（1）内容全面，结构合理：每章有本章小结、习题，配有整门课程微课教学视频，设置实验和课程设计。
（2）图文并茂，案例丰富：大题量、案例多，贴近实际
【资源特点】配套PPT、程序源代码、大纲、教案、试卷、实验详细指导等
【服务特点】作者提供QQ服务群等支持。
李云清， 教授，硕士研究生导师。江西省高等学校中、青年骨干教师，江西省教育厅认定的江西省高等学校首批首级优质精品课程《数据结构》课程负责人。独立系统地为计算机本科专业的学生开设了《数据结构》、《程序设计方法学》、《高级程序设计语言》（如BASIC语言、PASCAL语言）、《程序设计选讲》等专业课程。独立系统地讲授了《面向对象技术》和《软件自动化》等计算机专业硕士研究生课程。为研究课程进修班和助教进修班讲授《人工智能》、《面向对象技术》和《软件自动化》等课程。（合作）主持完成教改项目1项，主持（完成）江西省教育厅科技项目2项，并且作为第二成员完成了3项国家级科研项目（1项国家863计划，2项国家自然科学基金）和1项江西省跨世纪人才项目。另外，主持完成江西省教育厅省级教学研究项目1项，主持完成3项江西师大科研和教学研究课题。合编出版教材三部。 获得省级优秀教学成果二等奖1次，三等奖2次。获得校级优秀教学成果一等奖1次、二等奖1次，校首届教师CAI课件大赛一等奖1次。
第 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 综合实验
书单推荐
