数据结构

第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.1 BF算法87

4.4.2 KMP算法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.3 B-树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

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

在结构上呈积木式，适于选择性使用在写作上注重实践应用，从实际出发介绍各种常用的数据结构，避免抽象的理论论述和复杂的公式推导，在典型的算法介绍中深入浅出、简洁明了。每章都设有小结和习题通过这些习题的练习，不仅能加深对基本概念和定义的理解，而且通过上机，能够提高编程能力和程序调试能力。