数据结构（C语言版）（ 第4版 ）（微课版）

图书标准信息

• 作者 李云清 杨庆红 揭安全
• 出版社 人民邮电出版社
• 出版时间 2023-07
• 版次 4
• ISBN 9787115603203
• 定价 69.80元
• 装帧 平装
• 开本 其他
• 纸张 胶版纸
• 页数 324页
• 字数 617千字

【内容简介】

本书介绍了数据结构的基本概念和基本算法。全书共分为10章，包括概论，线性表及其顺序存储，线性表的链式存储，字符串、集合和特殊数组，递归，树型结构，二叉树，图，检索，排序等内容。

  本书内容丰富，逻辑性强，文字清晰流畅，既注重理论知识，又强调工程实用。书中既体现了抽象数据类型的观点，又对每个算法的具体实现给出了完整的C语言源代码描述。本书配套资源丰富，包含代码、PPT课件、教案、教学大纲、实验详细指导、习题答案及解析等教学资源，同时重点内容录制了微课视频，支持线上线下混合教学。
  本书可作为高等院校计算机专业及相关专业本科生“数据结构”课程的教材，也可以作为从事计算机工程与应用的广大读者的参考书。

【作者简介】

李云清， 教授，硕士研究生导师。江西省高等学校中、青年骨干教师，江西省教育厅认定的江西省高等学校首批首级优质精品课程《数据结构》课程负责人。独立系统地为计算机本科专业的学生开设了《数据结构》、《程序设计方法学》、《高级程序设计语言》（如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 综合实验