《数据结构原理》

第一章 绪论1

1 引言1

2 数据结构概念2

3 算法的概念4

第二章 算法分析基础10

1 引论10

2 算法的时间复杂性分析方法11

3 时间与空间分析15

第三章 线性表18

1 线性表的定义·运算·堆栈和队列18

2 线性表的存储结构19

2.1 线性表的顺序分配19

2.2 线性表的链接分配22

2.3 循环链接结构和双重链接结构26

2.3.1 循环链表26

2.3.2 双重链表29

3 堆栈和队列的应用30

3.1 堆栈与递归30

3.2 算术表达式求值33

3.3 队列35

第四章 数组和串37

1 数组37

2 稀疏矩阵39

2.1 三元组数组表示39

2.2 正交链表40

3 串43

3.1 串的概念及运算43

3.2 串的存储方式44

3.2.1 串的顺序分配44

3.2.2 串的链接分配44

3.3 串的匹配算法46

第五章 树形53

1 基本概念53

2 二叉树形54

2.1 二叉树形的性质54

2.2 二叉树形的表示及遍历方式56

2.2.1 二叉树形的存储方式56

2.2.2 二叉树形的遍历57

2.3 二叉树形的遍历算法58

2.4 二叉树形的应用60

2.4.1 复制二叉树形60

2.4.2 二叉树形与算术表达式61

2.5 二叉树形的穿线结构62

3 树形的表示方式66

3.1 树形和森林的二叉树表示66

3.2 FATHER链接结构69

3.2.1 向上链接69

3.2.2 集合表示与FATHER链接70

3.3 树形的顺序表示74

4 树形的通路长度76

第六章 图89

1 图的基本概念及存储方式89

1.1 基本定义89

1.2 图的存储结构90

1.2.1 邻接矩阵90

1.2.2 邻接表91

2 图的遍历算法92

3 拓扑排序和关键路径94

3.1 拓扑排序94

3.2 关键路径97

4 传递闭包99

5 图的连通分支102

5.1 无向图的连通分支103

5.2 有向图的强连通分支103

6 最短路径111

6.1 单源最短路径111

6.2 每对顶点之间的最短路径113

7 最小支撑树114

第七章 内排序120

1 插入排序120

2 交换排序124

2.1 起泡排序124

2.2 分划交换排序126

3 选择排序131

3.1 直接选择排序132

3.2 堆排序132

4 合并排序136

5 排序下界138

6 分布排序139

6.1 基数分布139

6.2 值分布141

第八章 查找146

1 线性表查找146

1.1 顺序查找146

1.2 有序表的查找147

1.2.1 对半查找148

1.2.2 Fibonacci查找150

1.2.3 插值查找152

1.2.4 索引技术153

2 二叉树查找154

2.1 静态树155

2.2 动态树161

2.2.1 高度平衡树164

2.2.2 重量平衡树170

2.2.3 平衡树的简单应用174

3 树字查找树176

4 杂凑178

4.1 杂凑函数179

4.1.1 抽取法179

4.1.2 压缩法179

4.1.3 除法杂凑函数180

4.1.4 乘法杂凑函数180

4.2 冲突调节181

4.2.1 拉链法181

4.2.2 线性探查185

4.2.3 双重杂凑186

4.2.4 杂凑有序表和杂凑表的删除187

5 （a,b）-树188

第九章 内存管理196

1 均匀大小记录的管理196

1.1 访问计数器法197

1.2 废料收集198

2 不同大小的记录的管理200

2.1 查找分配201

2.2 压缩分配205

3 伙伴系统207

第十章 外排序212

1 外存储器212

1.1 磁带212

1.2 磁盘213

2 磁带排序214

2.1 平衡合并排序215

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

3 磁盘排序222

第十一章 文件229

1 顺序文件229

1.1 串行处理文件229

1.2 顺序处理文件230

2 杂凑（散列）文件231

2.1 杂凑文件的设计231

2.1.1 杂凑函数与文件的构造231

2.1.2 杂凑文件中的操作232

2.2 可扩充的杂凑文件233

3 索引文件237

3.1 动态索引结构和静态索引结构238

3.2 索引顺序文件239

3.3 B＋树索引文件242

4 倒排文件和多重链表文件245

附录252