《数据结构》

1　引言1

2　数据结构概念1

第一章　诸论1

3　算法2

第二章　线性表6

1　线性表的定义、运算；堆栈、队列6

2　线性表的存储结构7

2.1　线性表的顺序分配7

2.2　线性表的链接分配及循环链接结构11

2.3　双重链接结构和动态存储分配22

1.1　数组的顺序分配30

第三章　数组和串30

1　数组和正交表30

1.2 正交链表和稀疏矩阵32

2 串43

2.1　串的概念43

2.2　串的运算与存储结构44

2.2.1　串的运算44

2.2.2 串的存储结构45

2.3　串的匹配运算46

1　树、森林、二叉树和列表的概论52

第四章　树52

2.1 二叉树的表示；先根、中根和后根遍历；中根遍历二叉树算法55

2　二叉树55

2.2　二叉树的穿线结构61

2.3　树的二叉表示；森林表成二叉树；树和森林的先根遍历和后根遍历66

2.4　树的其它表示和链接存储结构69

2.5　废料收集77

3　树的通路长度79

1 有向图（Directed Graph）89

1.1　基本概念与定义89

第五章　图89

1.2　有向图的存储结构90

1.3　单源最短路径91

1.4 每对顶点之间的最短路径95

1.5　遍历有向图97

1.6　拓扑排序101

2　无向图107

2.1　无向图的遍历108

2.2　最小代价生成树111

第六章　排序119

1 内排序119

1.1 枚举排序120

1.2　插入排序121

1.3　交换排序126

1.4　选择排序135

1.5 合并排序143

2　外排序152

2.1　外存储器152

2.1.1　磁带152

2.1.2　磁盘154

2.2　磁带排序155

2.2.1　平衡合并排序155

2 2.2　多路合并和初始游程的生成157

2 2.3　多回合并排序165

2.2.4 反向读带176

2.3　磁盘排序177

2.3.1　最佳合并排序模式177

第七章　查找184

1 顺序查找184

2　比较关键词的查找191

2.1　有序表的查找191

2.2　二叉排序树查找202

2.3　二叉平衡树210

2.4　多叉（进）树和B-树225

2.4.1　多叉（进）树226

2.4.2 B-树（B-tree）226

3 数字查找233

4 杂凑243

4.1　杂凑函数244

4.2　冲突调节245

第八章　文件254

1　文件结构概论254

2　顺序文件256

2.1　串行处理文件256

2.2　顺序处理文件259

2.3　增补文件260

3　杂凑（散列）文件261

3.1 杂凑文件的设计262

3.2　可扩充的杂凑文件264

4　索引文件268

4.1　动态索引结构和静态索引结构272

4.2　索引顺序文件274

4.3 B+树索引文件277

5　倒排文件和多重链表文件280

参考文献289