《数据结构案例教程 C语言版》

第1章数据结构基础1

1.1数据结构的基本概念2

1.1.1数据结构的研究内容2

1.1.2基本概念和术语5

1.1.3数据结构课程的内容8

1.2数据类型和抽象数据类型9

1.2.1数据类型9

1.2.2抽象数据类型9

1.3算法和算法分析10

1.3.1算法特性11

1.3.2算法描述12

1.3.3算法性能分析12

1.4本章小结15

习题16

编程实例18

第2章线性表19

2.1线性表的定义20

2.1.1线性表的逻辑结构20

2.1.2线性表的抽象数据类型20

2.2线性表的顺序存储及实现22

2.2.1顺序表22

2.2.2顺序表的基本运算23

2.3线性表的链式存储及实现28

2.3.1单链表29

2.3.2单链表的基本运算30

2.3.3循环链表36

2.3.4双向链表37

2.3.5静态链表39

2.3.6单链表应用举例40

2.4顺序表与链表的比较43

2.5本章小结44

习题44

编程实例46

第3章栈和队列48

3.1栈49

3.1.1栈的定义49

3.1.2栈的表示和实现50

3.2栈的应用55

3.2.1数制转换问题56

3.2.2括号匹配检验57

3.2.3表达式求值58

3.2.4栈与递归61

3.3队列64

3.3.1队列的定义64

3.3.2队列的表示和实现65

3.4队列的应用71

3.5本章小结73

习题74

编程实例75

第4章串79

4.1串的定义和基本运算80

4.1.1串的定义80

4.1.2串的基本操作81

4.2串的存储结构82

4.2.1定长顺序存储82

4.2.2堆存储83

4.2.3链式存储85

4.3串的运算实现86

4.4串的模式匹配90

4.4.1BF算法90

4.4.2 KMP算法92

4.5本章小结95

习题96

编程实例99

第5章数组和广义表103

5.1数组的定义及存储104

5.1.1数组的定义104

5.1.2数组的基本操作105

5.1.3数组的顺序存储105

5.2特殊矩阵的压缩存储107

5.2.1对称矩阵108

5.2.2三角矩阵109

5.2.3对角矩阵110

5.3稀疏矩阵111

5.3.1稀疏矩阵的三元组表存储111

5.3.2稀疏矩阵的十字链表存储115

5.4广义表117

5.4.1广义表的定义117

5.4.2广义表的存储结构119

5.4.3广义表的基本操作实现121

5.5本章小结122

习题123

编程实例124

第6章树和二叉树127

6.1树的定义与基本术语128

6.1.1树的定义128

6.1.2树的基本术语131

6.2二叉树131

6.2.1二叉树的定义131

6.2.2二叉树的性质134

6.2.3二叉树的存储实现136

6.3遍历二叉树139

6.3.1遍历二叉树的递归实现139

6.3.2遍历二叉树的非递归实现141

6.3.3遍历算法的应用145

6.4线索二叉树148

6.4.1线索二叉树的基本概念148

6.4.2线索二叉树的运算实现150

6.5树和森林153

6.5.1树的存储结构153

6.5.2树、森林与二叉树的转换156

6.5.3树和森林的遍历158

6.6哈夫曼树及其应用159

6.6.1哈夫曼树的基本概念159

6.6.2构造哈夫曼树161

6.6.3哈夫曼编码163

6.7本章小结165

习题166

编程实例168

第7章图172

7.1图的定义与基本术语173

7.1.1图的定义173

7.1.2基本术语175

7.2图的存储结构177

7.2.1邻接矩阵177

7.2.2邻接链表179

7.2.3十字链表182

7.2.4邻接多重表183

7.3图的遍历184

7.3.1深度优先搜索185

7.3.2广度优先搜索187

7.4图的应用189

7.4.1最小生成树189

7.4.2最短路径问题195

7.4.3AOV网与拓扑排序200

7.4.4 AOE网与关键路径203

7.5本章小结208

习题209

编程实例211

第8章查找216

8.1查找的基本概念217

8.2线性表的查找218

8.2.1顺序查找218

8.2.2折半查找219

8.2.3分块查找222

8.3树表的查找223

8.3.1二叉排序树223

8.3.2平衡二叉树229

8.3.3B树234

8.4散列表的查找241

8.4.1散列表的基本概念241

8.4.2散列函数的构造方法242

8.4.3处理冲突的方法244

8.4.4散列表的查找247

8.5本章小结248

习题249

编程实例251

第9章排序254

9.1排序的基本概念255

9.1.1什么是排序255

9.1.2排序的实现256

9.2插入排序257

9.2.1直接插入排序257

9.2.2折半插入排序259

9.2.3希尔排序260

9.3交换排序261

9.3.1冒泡排序261

9.3.2快速排序263

9.4选择排序266

9.4.1简单选择排序266

9.4.2堆排序268

9.5归并排序273

9.6基数排序275

9.6.1多关键字排序275

9.6.2链式基数排序275

9.7本章小结279

习题280

编程实例282