数据结构（C语言）

图书标准信息

• 作者 王海艳 著
• 出版社 人民邮电出版社
• 出版时间 2017-07
• 版次 01
• ISBN 9787115458254
• 定价 38.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 203页
• 字数 353千字
• 正文语种 简体中文
• 丛书 21世纪高等教育计算机规划教材

【内容简介】

　　本书介绍了数据结构的基本概念和基本算法，共分10章。各个章节分别是第1章概述，第2章线性表，第3章栈与队列，第4章数组和矩阵，第5章树，第6章搜索，第7章搜索树，第8章散列表，第9章图，第10章排序。

【作者简介】

　　作者是江苏省精品课程、校骨干课程《数据结构》的课程负责人，获奖情况：2013 年入选江苏省“六大人才高峰”资助，2012 年江苏省第四期＂333 高层次人才培养工程＂培养对象（第三层次），2006 年度江苏省＂青蓝工程＂培养对象，2015年获得第二届全国高校微课教学比赛三等奖，全省高校微课教学比赛（本科组）一等奖，2013年获省高等学校优秀多媒体教学课件竞赛一等奖，2015年获校级微课教学竞赛一等奖，2013年获校级教学成果二等奖＂面向多层次人才培养的计算机类本科专业转型建设与实践＂。

【目录】

目录

第1章绪论1

1．1数据结构起源1

1．2基本概念和术语1

1．2．1基本概念1

1．2．2数据结构2

1．3抽象数据类型4

1．4算法和算法分析5

1．4．1算法5

1．4．2算法的时间复杂度5

1．4．3最坏、最好和平均情况时间复

杂度6

1．4．4算法的空间复杂度7

1．5微课（一）7

习题7

第2章线性表9

2．1线性表定义9

2．2线性表的顺序存储结构和实现10

2．2．1线性表的顺序存储结构10

2．2．2顺序表基本运算的实现10

2．3线性表的链式存储结构和实现14

2．3．1单链表的定义和表示15

2．3．2单链表基本运算的实现15

2．3．3带表头结点的单链表20

2．3．4单循环链表22

2．3．5双向链表22

2．4顺序表与链表的比较23

2．5线性表的应用24

2．6微课（二）27

习题27

第3章堆栈和队列29

3．1堆栈29

3．1．1堆栈ADT29

3．1．2堆栈的顺序表示30

3．1．3堆栈的链接表示31

3．2队列32

3．2．1队列ADT32

3．2．2队列的顺序表示32

3．2．3队列的链接表示35

3．3表达式计算35

3．3．1中缀表达式35

3．3．2后缀表达式及其求值方法36

3．3．3中缀表达式转换为后缀表达式39

3．4递归41

3．4．1递归的概念41

3．4．2递归的实现42

3．5微课（三）43

习题43

第4章数组和字符串45

4．1数组45

4．1．1一维数组45

4．1．2二维数组46

4．1．3多维数组47

4．2数组的抽象数据类型47

4．3特殊矩阵50

4．3．1对称矩阵50

4．3．2三角矩阵51

4．4稀疏矩阵52

4．4．1稀疏矩阵的抽象数据类型52

4．4．2稀疏矩阵的简单转置算法54

4．4．3稀疏矩阵的快速转置算法55

4．5字符串57

4．5．1字符串的抽象数据类型57

4．5．2简单字符串匹配算法58

4．5．3改进的字符串匹配算法61

4．6微课（四）65

习题65

第5章树和二叉树67

5．1树67

5．1．1树的定义67

5．1．2基本术语67

5．1．3树的抽象数据类型68

5．1．4树的存储表示69

5．2二叉树71

5．2．1二叉树的定义及主要性质71

5．2．2二叉树的抽象数据类型73

5．2．3二叉树的顺序存储和链式存储

表示74

5．2．4二叉树的遍历75

5．2．5线索二叉树的基本概念和构造77

5．3树、森林与二叉树的关系78

5．3．1树、森林与二叉树的转换79

5．3．2树和森林的遍历82

5．4堆和优先权队列83

5．4．1堆83

5．4．2优先权队列85

5．5哈夫曼树及其应用88

5．5．1哈夫曼树的基本概念88

5．5．2哈夫曼算法89

5．5．3哈夫曼编码90

5．6微课（五）92

习题92

第6章集合和搜索95

6．1集合的表示95

6．1．1基本概念95

6．1．2动态集ADT96

6．1．3集合的表示96

6．2顺序搜索97

6．2．1无序表的顺序搜索97

6．2．2有序表的顺序搜索98

6．3对半搜索98

6．3．1对半搜索方法98

6．3．2二叉判定树101

6．4微课（六）102

习题102

第7章搜索树104

7．1二叉搜索树104

7．1．1二叉搜索树的定义和表示104

7．1．2二叉搜索树基本运算的实现105

7．2二叉平衡树109

7．2．1二叉平衡树的定义和表示109

7．2．2AVL搜索树基本运算的实现111

7．3B-树113

7．3．1B-树的定义和表示114

7．3．2B-树基本运算的实现116

7．4微课（七）120

习题120

第8章跳表和散列表122

8．1跳表122

8．1．1跳表的定义和表示122

8．1．2跳表基本操作的实现123

8．2散列表125

8．2．1散列表的定义和表示125

8．2．2散列表基本操作的实现127

8．3微课（八）132

习题132

第9章图134

9．1图的基本概念134

9．1．1图的定义134

9．1．2图的基本术语135

9．1．3图的类型定义137

9．2图的存储结构137

9．2．1邻接矩阵表示法137

9．2．2邻接矩阵的实现138

9．2．3图的邻接表表示法141

9．2．4邻接表的实现141

9．3图的遍历144

9．3．1深度优先遍历144

9．3．2宽度优先遍历146

9．4拓扑排序148

9．4．1AOV网148

9．4．2拓扑排序149

9．5关键路径150

9．5．1AOE网150

9．5．2关键路径151

9．6最小代价生成树154

9．6．1基本概念154

9．6．2普里姆（Prim）算法154

9．6．3克鲁斯卡尔（Kruskal）算法156

9．7单源最短路径159

9．7．1最短路径159

9．7．2单源最短路径159

9．8所有顶点之间的最短路径163

9．9微课（九）165

习题165

第10章排序168

10．1排序的基本概念168

10．2简单排序算法169

10．2．1简单选择排序169

10．2．2直接插入排序172

10．2．3冒泡排序174

10．3快速排序算法177

10．4两路合并排序181

10．5堆排序184

10．6外排序187

10．6．1预处理187

10．6．2多路合并191

10．6．3最佳合并树195

10．6．4完整的外排序过程196

10．7微课（十）196

习题196

附录综合实验199