数据结构(C语言描述)/李晔

第1章　绪论 1

1.1　什么是数据结构 1

1.2　数据结构的概念及有关术语 1

1.3　算法和算法分析 5

习题 7



第2章　线性表 9

2.1　线性表的定义 9

2.2　线性表的基本运算 9

2.3　顺序存储结构线性表 10

2.3.1　线性表的顺序存储结构 10

2.3.2　顺序存储结构线性表的基本运算 11

2.3.3　顺序存储结构线性表的应用 15

2.4　链式存储结构线性表 20

2.4.1　单链表 20

2.4.2　循环链表 28

2.4.3　双向链表 29

2.4.4　静态链表 30

2.4.5　链式存储结构线性表的应用 31

2.5　小结 38

习题 38



第3章　栈和队列 42

3.1　栈 42

3.1.1　栈的定义及基本运算 42

3.1.2　顺序存储结构栈的基本运算 42

3.1.3　链式存储结构栈的基本运算 45

3.1.4　栈的应用实例 47

3.1.5　栈与递归 48

3.2　队列 50

3.2.1　队列的定义及基本运算 50

3.2.2　顺序存储结构队列的基本运算 50

3.2.3　链式存储结构队列的基本运算 53

3.2.4　队列的应用 55

3.3　小结 57

习题 58



第4章　串 61

4.1　串的概念及基本运算 61

4.1.1　串的基本概念 61

4.1.2　串的基本运算 62

4.2　顺序存储结构串的运算 63

4.2.1　串的定长顺序存储结构 63

4.2.2　定长顺序存储结构串的基本运算 64

4.3　串的堆分配存储结构及其运算 66

4.3.1　串的堆分配存储结构 66

4.3.2　堆分配存储结构串的运算 66

4.4　串的链式存储结构及基本运算 68

4.4.1　串的链式存储结构 68

4.4.2　链串的基本运算 69

4.5　串的模式匹配 70

4.5.1　简单模式匹配算法——BF算法 70

4.5.2　无回溯的模式匹配算法——KMP算法 72

*4.5.3　next函数的改进 77

4.6　小结 79

习题 79



第5章　数组和广义表 81

5.1　数组 81

5.1.1　数组的定义及逻辑结构 81

5.1.2　数组的存储结构 83

5.1.3　特殊矩阵的压缩存储 84

5.1.4　数组应用举例 88

5.2　广义表 91

5.2.1　广义表的定义 91

5.2.2　广义表的存储结构 93

5.2.3　广义表基本操作实现 94

5.2.4　广义表应用举例 97

5.3　小结 98

习题 99



第6章　树和二叉树 102

6.1　树的定义及有关术语 102

6.1.1　树的定义 102

6.1.2　常用术语 102

6.2　二叉树 103

6.2.1　二叉树的定义 103

6.2.2　二叉树的性质 105

6.2.3　二叉树的存储结构 105

6.2.4　二叉树的遍历 107

6.2.5　线索二叉树 113

6.2.6　哈夫曼树 117

6.3　树和森林 122

6.3.1　树的存储结构 122

6.3.2　树或森林与二叉树的转换 124

6.3.3　树和森林的遍历 125

6.4　小结 126

习题 126



第7章　图 130

7.1　图的定义及有关术语 130

7.2　图的存储结构 134

7.2.1　邻接矩阵 134

7.2.2　邻接表 137

7.2.3　十字链表 139

*7.2.4　邻接多重表 141

7.3　图的遍历 143

7.3.1　深度优先搜索 143

7.3.2　广度优先搜索 145

7.3.3　图的连通性 148

7.4　*小生成树 150

7.4.1　普里姆算法 150

7.4.2　克鲁斯卡尔算法 153

7.5　有向无环图及其应用 156

7.5.1　拓扑排序 156

7.5.2　关键路径 161

7.6　*短路径 166

7.6.1　单源*短路径 166

7.6.2　每一对顶点之间的*短路径 169

7.7　图的应用实例 172

7.8　小结 174

习题 175



第8章　查找 180

8.1 查找的有关概念 180

8.2　线性表的查找 181

8.2.1　顺序查找 181

8.2.2　二分查找 182

8.2.3　分块查找 184

8.3　树表的查找 185

8.3.1　二叉排序树 185

8.3.2　平衡二叉树 190

8.3.3　B-树 193

8.3.4　B 树 196

8.4　哈希查找 197

8.4.1　哈希表的概念及哈希函数的构造 197

8.4.2　哈希表的建立 199

8.4.3　冲突的处理方法 199

8.4.4　哈希查找的实现 201

8.5　小结 202

习题 203



第9章　排序 206

9.1　排序的有关概念 206

9.2　插入排序 207

9.2.1　直接插入排序 207

9.2.2　折半插入排序 208

9.2.3　希尔排序 209

9.3　交换排序 211

9.3.1　冒泡排序 211

9.3.2　快速排序 212

9.4　选择排序 214

9.4.1　简单选择排序 214

9.4.2　堆排序 216

9.5　归并排序 219

9.6　基数排序 221

9.7　多关键字排序 223

9.8　小结 224

习题 225



参考文献 229