数据结构 （C语言版）

第1章 数据结构的基本概念及算法 1

1.1概述 1

1.2基本概念及术语 3

1.3算法 7

1.3.1算法的定义及特点 8

1.3.2算法的描述 8

1.3.3算法设计的要求 9

1.3.4算法效率的分析 9

1.3.5算法存储空间的分析 11

小结 11

习题1 12

第2章 线性表 14

2.1线性表的定义及基本运算 14

2.1.1线性表的定义 14

2.1.2线性表的基本运算 14

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

2.2.1线性表的顺序存储结构 15

2.2.2顺序表的基本运算 16

2.2.3顺序表算法的复杂度分析 18

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

2.3.1单链表 19

2.3.2循环链表 25

2.3.3双向链表 26

2.4特殊的线性表之一——栈 28

2.4.1基本概念 28

2.4.2顺序栈 29

2.4.3链栈 32

2.5特殊的线性表之二——队列 34

2.5.1基本概念 34

2.5.2顺序队列 35

2.5.3循环队列 36

2.5.4链式队列 39

2.6特殊的线性表之三——串 41

2.6.1基本概念 41

2.6.2串的存储结构 42

2.6.3串的基本运算 44

2.6.4串的模式匹配 46

小结 54

习题2 55

上机实验1线性表的基本操作 60

第3章 数组及广义表 62

3.1数组 62

3.1.1定义 62

3.1.2基本操作 63

3.1.3数组的顺序存储结构 63

3.1.4规则矩阵的压缩存储 65

3.2稀疏矩阵 67

3.2.1稀疏矩阵的三元组表示 67

3.2.2稀疏矩阵的十字链表表示 72

3.3广义表 76

3.3.1定义 76

3.3.2广义表的存储结构 77

3.3.3广义表的基本操作 77

小结 78

习题3 79

上机实验2数组的基本操作 81

第4章 树和二叉树 82

4.1树的基本概念与存储表示 82

4.2二叉树 84

4.2.1二叉树的基本概念 84

4.2.2二叉树的基本性质 85

4.2.3二叉树的存储结构 86

4.3二叉树的遍历 88

4.3.1先序遍历 88

4.3.2中序遍历 89

4.3.3后序遍历 89

4.3.4二叉树的建立 90

4.3.5二叉树遍历的应用 91

4.4线索二叉树 93

4.5树、森林与二叉树的转换及遍历 95

4.5.1树的二叉树表示 95

4.5.2森林与二叉树的转换 97

4.5.3树、森林的遍历 97

4.6哈夫曼树及其应用 97

4.6.1哈夫曼树的基本概念 98

4.6.2哈夫曼树的构造 99

4.6.3哈夫曼树在编码中的应用 100

小结 103

习题4 103

上机实验3 二叉树的基本操作 106

第5章 图 108

5.1基本概念 108

5.1.1图的定义 108

5.1.2图的相关术语及基本概念 108

5.1.3图的基本运算 111

5.2图的存储结构 111

5.2.1邻接矩阵 111

5.2.2邻接表 113

5.2.3邻接多重表 116

5.2.4十字链表 117

5.3图的遍历 119

5.3.1深度优先搜索遍历 119

5.3.2广度优先搜索遍历 121

5.4最小生成树 122

5.4.1生成树和最小生成树 122

5.4.2普里姆算法 123

5.4.3克鲁斯卡尔算法 126

5.5最短路径 128

5.5.1单源最短路径 128

5.5.2每对顶点之间的最短路径 132

5.6拓扑排序 133

5.6.1 AOV网和拓扑排序的概念 134

5.6.2拓扑排序的算法 135

小结 137

习题5 137

上机实验4图的基本操作 141

第6章 查找 143

6.1基本概念 143

6.2线性查找 144

6.2.1顺序查找 144

6.2.2对分查找 146

6.2.3分块查找 149

6.3树表查找 150

6.3.1二叉排序树查找 151

6.3.2多层索引树查找 156

6.4哈希查找 162

6.4.1哈希表与哈希函数 162

6.4.2构造哈希函数的常见方法 164

6.4.3冲突解决方法 166

6.4.4哈希表的查找及分析 167

小结 169

习题6 169

上机实验5查找的基本操作 171

第7章 排序 173

7.1基本概念 173

7.2内排序 175

7.2.1交换类排序 175

7.2.2插入类排序 181

7.2.3选择类排序 185

7.2.4其他排序方法 192

7.2.5内排序方法比较 198

7.3外部排序简介 199

小结 200

习题7 200

上机实验6排序的基本操作 203

第8章 文件 205

8.1基本概念 205

8.1.1文件的逻辑结构和物理结构 206

8.1.2文件的操作（运算） 206

8.2顺序文件 206

8.3索引文件 207

8.4索引顺序文件 208

8.4.1 ISAM文件 208

8.4.2 VSAM文件 210

8.5散列文件 212

8.6多关键字文件 212

8.6.1多重表文件 212

8.6.2倒排序文件 214

小结 215

习题8 215

模拟试题一 216

模拟试题二 219

附录一 习题参考答案 223

习题1 223

习题2 224

习题3 232

习题4 235

习题5 243

习题6 252

习题7 256

习题8 263

附录二 上机实验参考程序 265

上机实验1 265

上机实验2 274

上机实验3 276

上机实验4 280

上机实验5 283

上机实验6 291

附录三 模拟试题参考答案 297

模拟试题一 297

模拟试题二 298

参考文献 301