数据结构原理PDF电子书下载

第一章 绪论 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