数据结构:C语言版

第1章绪论.1

1.1什么是数据结构1

1.2基本概念和术语4

1.3抽象数据类型的表示与实现9

1.4算法和算法分析13

1.4.1算法13

1.4.2算法设计的要求13

1.4.3算法效率的度量14

1.4.4算法的存储空间需求17

第2章线性表18

2.1线性表的类型定义18

2.2线性表的顺序表示和实现21

2.3线性表的链式表示和实现27

2.3.1线性链表27

2.3.2循环链表35

2.3.3双向链表35

2.4一元多项式的表示及相加39

第3章栈和队列44

3.1栈44

3.1.1抽象数据类型栈的定义44

.3.1.2栈的表示和实现45

3.2栈的应用举例48

3.2.1数制转换48

3.2.2括号匹配的检验49

3.2.3行编辑程序49

3.2.4迷宫求解50

3.2.5表达式求值52

**3.3栈与递归的实现54

3.4队列58

3.4.1抽象数据类型队列的定义58

3.4.2链队列——队列的链式表示和实现60

3.4.3循环队列——队列的顺序表示和实现63

**3.5离散事件模拟65

第4章串70

4.1串类型的定义70

4.2串的表示和实现72

4.2.1定长顺序存储表示73

4.2.2堆分配存储表示75

4.2.3串的块链存储表示78

**4.3串的模式匹配算法79

4.3.1求子串位置的定位函数index(s,t,pos)79

4.3.2模式匹配的一种改进算法80

4.4串操作应用举例84

4.4.1文本编辑84

**4.4.2建立词索引表86

第5章数组和广义表90

5.1数组的定义90

5.2数组的顺序表示和实现91

5.3矩阵的压缩存储95

5.3.1特殊矩阵95

5.3.2稀疏矩阵96

5.4广义表的定义106

5.5广义表的存储结构109

**5.6m元多项式的表示110

**5.7广义表的递归算法112

5.7.1求广义表的深度113

5.7.2复制广义表115

5.7.3建立广义表的存储结构115

第6章树和二叉树118

6.1树的定义和基本术语118

6.2二叉树121

6.2.1二叉树的定义121

6.2.2二叉树的性质123

6.2.3二叉树的存储结构126

6.3遍历二叉树和线索二叉树128

6.3.1遍历二叉树128

6.3.2线索二叉树132

6.4树和森林135

6.4.1树的存储结构135

6.4.2森林与二叉树的转换137

6.4.3树和森林的遍历138

**6.5树与等价问题139

6.6赫夫曼树及其应用144

6.6.1最优二叉树(赫夫曼树)144

6.6.2赫夫曼编码146

**6.7回溯法与树的遍历149

**6.8树的计数152

第7章图156

7.1图的定义和术语156

7.2图的存储结构160

7.2.1数组表示法161

7.2.2邻接表163

7.2.3十字链表164

7.2.4邻接多重表166

7.3图的遍历167

7.3.1深度优先搜索167

7.3.2广度优先搜索169

7.4图的连通性问题170

7.4.1无向图的连通分量和生成树..170

**7.4.2有向图的强连通分量172

7.4.3最小生成树173

**7.4.4关节点和重连通分量176

7.5有向无环图及其应用179

7.5.1拓扑排序180

7.5.2关键路径183

7.6最短路径186

7.6.1从某个源点到其余各顶点的最短路径187

7.6.2每一对顶点之间的最短路径190

第8章动态存储管理193

8.1概述193

8.2可利用空间表及分配方法195

8.3边界标识法198

8.3.1可利用空间表的结构198

8.3.2分配算法199

8.3.3回收算法201

8.4伙伴系统203

8.4.1可利用空间表的结构203

8.4.2分配算法204

8.4.3回收算法205

**8.5无用单元收集206

**8.6存储紧缩212

第9章查找214

9.1静态查找表216

9.1.1顺序表的查找216

9.1.2有序表的查找218

**9.1.3静态树表的查找222

9.1.4索引顺序表的查找225

9.2动态查找表226

9.2.1二叉排序树和平衡二叉树227

9.2.2b-树和b+树238

**9.2.3键树247

9.3哈希表251

9.3.1什么是哈希表251

9.3.2哈希函数的构造方法253

9.3.3处理冲突的方法256

9.3.4哈希表的查找及其分析259

第10章内部排序263

10.1概述263

10.2插入排序265

10.2.1直接插入排序265

10.2.2其他插入排序266

10.2.3希尔排序271

10.3快速排序272

10.4选择排序277

10.4.1简单选择排序277

10.4.2树形选择排序278

10.4.3堆排序279

10.5归并排序283

10.6基数排序284

10.6.1多关键字的排序284

10.6.2链式基数排序286

10.7各种内部排序方法的比较讨论288

第11章外部排序293

11.1外存信息的存取293

11.2外部排序的方法295

**11.3多路平衡归并的实现297

**11.4置换惭≡衽判299

**11.5最佳归并树304

第12章文件306

12.1有关文件的基本概念306

12.2顺序文件308

12.3索引文件311

12.4isam文件和vsam文件313

12.4.1isam文件313

12.4.2vsam文件316

12.5直接存取文件(散列文件)317

12.6多关键字文件319

12.6.1多重表文件319

12.6.2倒排文件319

附录a名词索引322

附录b函数索引329

参考书目...334