数据结构 C语言描述 慕课版

  

数据结构是计算机及相关专业的基础课程。它不仅具有很强的理论性，也具有很强的实践性。本书对查找、排序进行了分析讨论，对线性结构、树结构、图结构采用了统一的讲解模式：逻辑结构+物理结构+基本操作实现+典型应用，并围绕这4个方面进行了详细讨论，条理清晰。另外，本书除了对各部分的操作实现算法进行理论分析之外，还用C语言进行了具体实现，从基本理论和基本技能两个方面对学生进行训练。本书内容丰富、条理清晰、深入浅出、讲解详尽，适合计算机类、信息类、电类、自动控制类、数学类专业的学生使用，也适合软件设计人员、工程技术人员参考。

张同珍，上海交通大学副教授，曾获上海市很好教材奖、上海市教学成果奖、上海交通大学烛光奖。主要讲授“数据结构”“程序设计”“计算引论”等课程，其中，“数据结构”课程被评重量精品课程、“程序设计”课程被评上海市精品课程。

   第1章绪论1

1.1数据结构的定义2

1.1.1数据的逻辑结构2

1.1.2基本操作2

1.1.3抽象数据类型3

1.1.4数据的存储结构3

1.1.5基本操作的实现3

1.1.6典型应用4

1.2数据结构的C语言实现4

1.3算法及算法分析4

1.3.1算法及其要求4

1.3.2时间复杂度的度量5

1.3.3空间复杂度的度量7

1.4小结7

1.5习题8

第2章线性表9

2.1线性表的定义及ADT10

2.2线性表的顺序存储结构11

2.2.1顺序表11

2.2.2顺序表基本操作的实现12

2.3线性表的链式存储结构17

2.3.1单链表18

2.3.2单链表基本操作的实现19

2.3.3单向循环链表24

2.3.4双链表、双向循环链表25

2.4线性表的应用27

2.4.1一元多项式的加法27

2.4.2字符串的存储和实现32

2.4.3稀疏矩阵42

2.5小结43

2.6习题43

第3章栈和队列45

3.1栈46

3.1.1栈的定义和抽象数据类型46

3.1.2栈的顺序存储及实现47

3.1.3栈的链式存储及实现51

3.2栈的应用54

3.2.1括号配对检查54

3.2.2表达式计算55

3.3队列60

3.3.1队列的定义和抽象数据类型60

3.3.2队列的顺序存储及实现61

3.3.3队列的链式存储及实现64

3.3.4优先队列67

3.4小结68

3.5习题69

第4章树及二叉树70

4.1树的定义、术语和结构71

4.2二叉树72

4.2.1二叉树的定义72

4.2.2二叉树的性质74

4.2.3二叉树的存储和实现75

4.3二叉树的遍历及实现81

4.4很优二叉树及其应用92

4.4.1基本概念92

4.4.2哈夫曼算法的实现94

4.4.3哈夫曼编码96

4.5等价类问题99

4.5.1等价关系及等价类99

4.5.2不相交集及其存储99

4.5.3不相交集的基本操作100

4.6树和森林101

4.6.1孩子兄弟表示法101

4.6.2树、森林与二叉树的转换102

4.6.3树的遍历104

4.6.4森林的遍历105

4.7小结106

4.8习题106

第5章图108

5.1图的基本概念109

5.1.1图的概念和术语109

5.1.2图的抽象数据类型111

5.2图的存储表示112

5.2.1邻接矩阵和加权邻接矩阵112

5.2.2邻接表119

5.2.3多重邻接表127

5.2.4十字链表128

5.3图的遍历和连通性129

5.3.1深度优先遍历DFS129

5.3.2广度优先遍历BFS132

5.3.3图的连通性134

5.4最小代价生成树136

5.4.1普里姆算法137

5.4.2克鲁斯卡尔算法140

5.5最短路径问题141

5.5.1单源最短路径141

5.5.2所有顶点对之间的最短路径145

5.6AOV网和AOE网150

5.6.1拓扑排序150

5.6.2关键路径153

5.7小结163

5.8习题163

第6章查找165

6.1静态查找技术166

6.1.1顺序查找166

6.1.2折半查找167

6.1.3插值查找168

6.2二叉查找树168

6.2.1二叉查找树的定义168

6.2.2基本操作169

6.2.3顺序统计174

6.3平衡二叉查找树（AVL树）175

6.3.1插入176

6.3.2删除180

6.3.3优选高度181

6.4红黑树182

6.4.1插入操作183

6.4.2删除操作188

6.5B树和B+树192

6.5.1B树192

6.5.2B树的查找分析193

6.5.3插入操作194

6.5.4删除操作195

6.5.5B+树197

6.6哈希（hash）方法198

6.6.1常用的哈希函数198

6.6.2线性探测法199

6.6.3二次探测法200

6.6.4链地址法200

6.7小结200

6.8习题201

第7章排序202

7.1引言203

7.2冒泡排序203

7.3插入排序205

7.3.1简单插入排序205

7.3.2折半插入排序206

7.3.3希尔排序206

7.4归并排序208

7.5快速排序213

7.6选择排序和堆排序216

7.6.1选择排序216

7.6.2堆排序218

7.6.3堆和优先队列224

7.7基数排序225

7.7.1多关键字排序225

7.7.2口袋排序法225

7.8内排序算法的比较229

7.9外排序230

7.9.1外排序处理过程230

7.9.22k路归并230

7.9.3初始归并段232

7.9.4很好归并树233

7.10小结233

7.11习题234