数据结构 用C语言描述

目录 1

序 1

前言 1

第1章　算法分析 1

1.1 算法 1

1.1.1　数组元素相加（Add array members） 1

1.1.2　矩阵相乘（Matrix Multiplication） 1

1.1.4　折半查找（Binary search） 2

1.1.3　顺序查找（Sequential search） 2

1.1.5　斐波那契（Fibonacci）数列（递归的程序段） 3

1.1.6　斐波那契数列（非递归的程序片段） 3

1.2　Big-O（复杂度） 4

1.3　动动脑时间 10

第2章　数组 12

2.1　数组的表示法 12

2.1.1　一维数组（one dimension array） 12

2.1.2　二维数组 12

2.1.3　三维数组 14

2.1.4　n维数组 15

2.2　上三角形和下三角形表示法 16

2.2.1 以列为主 16

2.2.2 以行为主 17

2.3　多项式表示法 17

2.4　魔术方阵 21

2.5　生命细胞游戏 25

2.6　动动脑时间 32

3.1 堆栈与队列的基本概念 34

第3章　堆栈与队列 34

3.2　堆栈的插入与删除 35

3.3　队列的插入与删除 41

3.4　循环队列 42

3.5　堆栈与队列的应用 51

3.6　如何计算后序表达式 57

3.7　动动脑时间 58

4.1　单向链表 60

4.1.1 插入操作 60

第4章　链表 60

4.1.2　删除操作 63

4.1.3　将两个单向链表相互连接 73

4.1.4　将一链表反转 74

4.1.5　计算链表的长度 75

4.2　循环链表 76

4.2.1 插入操作 76

4.2.2　删除操作 78

4.2.4　计算循环链表的长度 80

4.2.3　如何回收整个循环链表 80

4.3　双向链表 81

4.3.1　插入操作 82

4.3.2　删除操作 85

4.4　链表的应用 96

4.4.1 以链表表示堆栈 96

4.4.2　以链表表示队列 96

4.4.3 多项式相加 96

4.5　动动脑时间 102

5.1　一些递归的基本范例 103

第5章　递归 103

5.2　一个典型的递归范例：hanoi塔 111

5.3　另一个范例：8个皇后 115

5.4　何时不要使用递归 120

5.5　动动脑时间 122

第6章　树状结构 123

6.1　树状结构的一些专有名词 123

6.2　二叉树 124

6.3　二叉树的表示方法 127

6.4　二叉树的遍历 129

6.5　线索二叉树 132

6.6　其他问题 136

6.6.1　如何将一般树化为二叉树 136

6.6.2　确定惟一的二叉树 138

6.7　动动脑时间 140

第7章　二叉查找树 143

7.1　什么是二叉查找树 143

7.2　二叉查找树的插入 144

7.3　二叉查找树的删除 145

7.4　动动脑时间 156

第8章　堆 158

8.1 什么是堆 158

8.1.1 Heap的插入 160

8.1.2 Heap的删除 160

8.2 什么是min-heap 171

8.3 min-max heap 173

8.3.1 Max-max-heap的插入 174

8.3.2 min-max-heap的删除 175

8.4　Deap 178

8.4.1　Deap的插入 178

8.4.2　Deap的删除 179

8.5　动动脑时间 181

第9章　平衡二叉查找树 183

9.1　何谓平衡二叉查找树 183

9.2　AVL-tree的插入与删除 184

9.2.1　LL型 184

9.2.2　RR型 185

9.2.3　LR型 186

9.2.4　RL型 187

9.3　AVL-tree的删除 192

9.4　动动脑时间 209

第10章　2-3 tree与2-3-4 tree 210

10.1　2-3 tree 210

10.1.1　2-3 Tree的插入 211

10.1.2 2-3 Tree的删除 213

10.2 2-3-4 Tree 217

10.2.1 2-3-4 Tree的插入 218

10.2.2 2-3-4 Tree的删除 219

10.3　动动脑时间 221

第11章　B-tree 222

11.1　m-way查找树 222

11.1.1　m-way查找树的插入 223

11.1.2　m-way查找树的删除 224

11.2　B-tree 225

11.2.1　B-tree的插入 225

11.2.2　B-tree的删除 227

11.3　动动脑时间 250

第12章　图 251

12.1 图的一些专有名词 252

12.2　图数据结构表示法 255

12.2.1　邻接矩阵（adjacency matrix） 255

12.2.2　邻接表（adjacency list） 256

12.3 图的遍历 258

12.3.1　深度优先搜索（depth first search） 258

12.3.2　广度优先搜索（breadth first search） 261

12.4　最小生成树 266

12.4.1　普里姆算法（Prim's algorithm） 267

12.4.2　克鲁斯卡尔算法（Kruskal's algorithm） 269

12.5　最短路径 275

12.6　拓扑排序 285

12.7　关键路径法 291

12.7.1　计算事件最早发生的时间 293

12.7.2　计算事件最晚发生的时间 294

12.8　动动脑时间 305

第13章　排序 308

13.1　起泡排序 309

13.2　选择排序 311

13.3　插入排序 313

13.4　归并排序（merge sort） 315

13.5　快速排序 319

13.6　堆排序 321

13.7　二叉树排序（binary tree sort） 327

13.8　希尔排序 330

13.9　基数排序 332

13.10　动动脑时间 335

第14章　查找 337

14.1 顺序查找 337

14.2　折半查找 338

14.3　哈希法 341

14.3.1 哈希函数 341

14.3.2 解决溢出的方法（overflow handing） 343

14.4　动动脑时间 351

练习题参考答案 353