本书系统地介绍了各种典型的数据结构，主要包括算法、线性表、栈和伫列、串、数组、树、图、查找、排序、递归和档案；为了加强对算法的理解，也介绍了算法分析方面的内容。本书语言精练、概念清楚、注重实用、逻辑性强，各章中所涉及的数据结构与算法都给出了C语言描述，并附有大量习题，便于学生理解与掌握。本书可作为高等院校计算机专业及相关专业的教材，也可作为计算机套用技术人员的参考书

第1章 绪论1

1.1 问题的提出1

1.2 基本术语2

1.3 数据结构的概念4

1.4 数据的逻辑结构6

1.5 数据的存储结构7

1.6 数据的运算9

1.7 数据的逻辑结构、存储结构及运算的关係9

1.8 算法概述10

1.8.1 算法与算法特性10

1.8.2 算法描述10

1.9 算法分析11

小结13

习题114

第2章 线性表15

2.1 线性表的定义与运算15

2.1.1 线性表的定义15

2.1.2 线性表的运算16

2.2 线性表的顺序存储19

2.2.1 顺序存储19

2.2.2 顺序结构线性表的运算20

2.2.3 顺序存储结构的优点23

2.2.4 顺序存储结构的缺点23

2.3 线性表的链式存储23

2.3.1 线性鍊表23

2.3.2 线性鍊表的运算26

2.3.3 静态鍊表312.3.4 静态鍊表的运算31

2.3.5 循环鍊表32

2.3.6 循环鍊表的运算33

2.3.7 双向鍊表 34

2.3.8 双向鍊表的运算35

2.3.9 链式存储结构的特点37

2.4 链式存储结构的套用37

2.4.1 约瑟夫问题37

2.4.2 一元多项式求和39

2.4.3 在集合方面的套用42

小结44

习题244

第3章栈和伫列46

3.1栈46

3.1.1栈的定义46

3.1.2栈的顺序存储结构47

3.1.3栈的链式存储结构51

3.1.4顺序栈和链式栈的比较53

3.2栈的套用53

3.2.1迷宫问题53

3.2.2算术表达式求值56

3.2.3子程式的调用和返回59

3.2.4数制转换60

3.3伫列61

3.3.1伫列的定义61

3.3.2伫列的顺序存储62

3.3.3伫列的链式存储68

3.3.4优先伫列72

3.4伫列的套用73

3.4.1设备速度不匹配问题73

3.4.2舞伴问题73

小结75

习题375

第4章串77

4.1串的基本概念77

4.2串的存储结构78

4.2.1串的静态存储结构79

4.2.2串的动态存储结构80

4.3串的基本运算及实现82

4.3.1串的基本运算82

4.3.2实现串的基本运算的算法83

4.4模式匹配87

4.4.1BF算法87

4.4.2KMP算法90

小结94

习题494

第5章数组96

5.1数组的概念96

5.1.1数组的定义及基本操作96

5.1.2抽象数据类型数组的定义98

5.2数组的顺序存储结构98

5.3矩阵的压缩存储102

5.3.1特殊矩阵的压缩存储102

5.3.2稀疏矩阵的压缩存储104

小结118

习题5118

第6章树120

6.1树120

6.1.1树的定义120

6.1.2树的表示方法121

6.1.3树的基本术语121

6.1.4树的ADT定义122

6.2二叉树123

6.2.1二叉树的定义及基本形态123

6.2.2二叉树的存储结构125

6.2.3二叉树的遍历127

6.3线索二叉树130

6.3.1二叉树的线索化131

6.3.2利用线索遍历131

6.4树、森林和二叉树的关係136

6.4.1树的存储结构136

6.4.2森林与二叉树的转换139

6.4.3树和森林的遍历142

6.5哈夫曼树及其套用143

6.5.1与哈夫曼树有关的定义143

6.5.2哈夫曼树的构造145

6.5.3哈夫曼树的套用146

小结151

习题6151

第7章图155

7.1图的基本概念155

7.2图的存储结构159

7.2.1邻接矩阵160

7.2.2邻接表162

7.2.3十字鍊表166

7.2.4邻接多重表167

7.3图的遍历169

7.3.1深度优先搜寻169

7.3.2广度优先搜寻172

7.4生成树174

7.4.1普里姆（Prim）算法175

7.4.2克鲁斯卡尔(kruskal)算法178

7.5最短路径180

7.5.1单源最短路径180

7.5.2顶点之间的最短路径183

7.6拓扑排序184

7.7关键路径188

小结195

习题7195

第8章查找199

8.1基本概念199

8.2线性表的查找200

8.2.1顺序查找200

8.2.2折半查找202

8.2.3分块查找205

8.3树表的查找208

8.3.1二叉查找树208

8.3.2平衡二叉树214

8.3.3B-树220

8.4哈希表的查找222

8.4.1哈希表222

8.4.2构造哈希表的基本方法223

8.4.3解决冲突的方法225

8.4.4哈希表的查找方法228

8.5查找方法的比较228

小结229

习题8229

第9章排序232

9.1基本概念232

9.2内部排序方法235

9.2.1插入排序235

9.2.2冒泡排序239

9.2.3快速排序240

9.2.4选择排序243

9.2.5归併排序248

9.2.6基数排序251

9.3内部排序方法比较256

9.4外部排序方法简介257

小结257

习题9258

第10章递归261

10.1递归的定义261

10.2典型递归问题262

10.2.1汉诺塔问题262

10.2.2八皇后问题264

10.3递归的实现266

10.4递归转化为非递归的一般过程270

10.5递归的时间和空间複杂度273

小结274

习题10275

第11章档案276

11.1外存储器的介绍276

11.2有关档案的概念277

11.2.1档案及其类别278

11.2.2档案的操作279

11.3档案的组织280

11.3.1顺序档案281

11.3.2索引档案282

11.3.3散列档案287

11.3.4多关键字档案289

小结291

习题11291

附录上机实验293

参考文献296