数据结构教程PDF电子书下载

第一章 绪论 1

1．1 什么是数据结构 1

1．2 数据结构的发展简史及其在计算机科学中的地位 3

1．3 算法 3

1．4 SPARKS语言简介 5

1．4．1 算法格式 5

1．4．2 SPARKS语句 6

1．5 算法分析 9

1．5．1 时间复杂度 9

1．5．2 空间复杂度 10

1．5．3 其他方面 11

1．6 算法设计的基本步骤 11

习题 12

第二章 线性表 14

2．1 线性表及其基本运算 14

2．1．1 线性表的定主 14

2．1．2 关于线性表的基本运算 15

2．2 线性表的顺序存储结构 16

2．3 线性表的链式存储结构 18

2．3．1 线性链表 19

2．3．2 线性链表的有关算法 21

2．4 循链表及其运算 27

2．5 双向链表及其运算 30

2．5．1 双几链表的构造 30

2．5．2 双向链表的插入与删除算法 31

2．6．1 链式存储结构下的一元多项式加法 33

2．6 链表的应用举例 33

2．6．2 动态存储管理 35

习题 41

第三章 数组 43

3．1 数组的概念 43

3．1．1 一维数组 43

3．1．2 多维数组 43

3．2 数组的存储结构 44

3．3 矩阵的压缩存储 45

3．3．1 对称矩阵的压缩存储 46

3．3．2 对角矩阵的压缩存储 46

3．4 稀疏矩阵的三元组表示 47

3．5 稀疏矩阵的十字链表表示 52

3．6 数组的应用举例 56

3．6．1 一元多项式的数组表示 56

3．6．2 N价魔方 57

习题 58

第四章 堆栈和队列 60

4．1 堆栈的概念及其运算 60

4．1．1 堆栈的定义 60

4．1．2 堆栈的有关运算 61

4．2 堆栈的顺序存储结构 61

4．3 堆栈的链式存储结构 64

4．4 堆栈的应用举例 65

4．4．1 堆栈在递归中的应用 65

4．4．2 表达式的计算 69

4．4．3 一个趣味游戏——迷宫问题 73

4．5 队列的概念及其运算 75

4．5．1 队列的定义 75

4．5．2 队列的有关运算 76

4．6 队列的顺序存储结构 76

4．7 队列的链式存储结构 79

习题 81

第五章 广义表 83

5．1 广义表的概念 83

5．2 广义表的存储结构 84

5．3 多元多项式的表示 86

习题 87

6．1．1 串的定义 88

第六章 串 88

6．1 串的概念 88

6．1．2 串的几个概念 89

6．2 串的基本运算 89

6．3 串的存储结构 90

6．3．1 串的顺序存储结构 90

6．3．2 串的链式存储结构 91

6．4 串的几个运算 92

习题 97

第七章 树与二叉树 98

7．1 树的基本概念 98

7．1．1 树的定义 98

7．1．3 基本术语 100

7．1．2 树的逻辑表示方法 100

7．1．4 树的基本运算 101

7．2 树的存储结构 102

7．2．1 多重锭表表示法 102

7．2．2 三重链表表示 102

7．3 二叉树 103

7．3．1 二叉树的定义 103

7．3．2 二叉树的基本运算 104

7．3．3 满二叉树与完全二叉树 105

7．3．4 二叉树的性质 105

7．3．5 二叉树的存储结构 106

7．4．1 二叉树的顺序存储结构 109

7．4 二叉树的存储结构 109

7．4．2 二叉树的链式存储结构 110

7．5 树的遍历 112

7．5．1 二叉树的遍历 112

7．5．2 树和树林的遍历 118

7．5．3 由遍历序列恢复二叉树 119

7．6 线索二叉树 120

7．6．1 线索二叉树的构造 121

7．6．2 线索二叉树的利用 122

7．6．3 二叉树的线索化算法 124

7．6．4 线索树的更新 124

7．7 二叉排序树的定义 125

7．7．2 二叉排序树的构造 126

7．7．1 二叉排序树的定义 126

7．7．3 在二叉排序树中删除结点 128

7．7．4 二叉排序树的查找 130

7．8 平衡二叉要地 132

7．9 哈夫曼树胶其应用 138

7．9．1 哈夫曼树的 138

7．9．2 哈夫曼编码 139

7．10 树的一个应用——判定树 142

习题 144

第八章 图 147

8．1 图的基本概念 147

8．1．1 图的定义和基本术语 147

8．2 图的存储方法 150

8．1．2 图的基本运算 150

8．2．1 邻接矩阵存储方法 151

8．2．2 邻接表存储方法 151

8．2．3 有向图的十字链表存储方法 154

8．2．4 无向图的多重邻接表存储方法 154

8．3 图的遍历 155

8．3．1 深度优行搜索（Depth First Search） 156

8．3．2 广度优先搜索（Breadth First Search） 158

8．4 最小生成树 159

8．5 最短路径问题 162

8．5．1 某个源点到其余各个顶点的最短路径 162

8．5．2 每一对顶点之间的最短路径 165

8．6．1 AOV网（Activity on vertex network） 168

8．6 AOV网与拓扑排序 168

8．6．2 拓扑排序 169

8．6．3 拓扑排序算法 169

8．7 AOE网与关键路径 173

8．7．1 AOE网（Activity on edge onetwork） 173

8．7．2 关键路径 174

8．7．3 关键路径的确定 174

习题 176

第九章 文件及查找 179

9．1 文件概述 179

9．1．1 文件的基本术语 179

9．1．2 文件的存储介质 180

9．1．3 文件的基本操作 181

9．2 顺序文件 182

9．2．1 连续顺序文件 182

9．2．2 链接顺序文件 185

9．3 索引文件 186

9．3．1 稠密索引文件 186

9．3．2 非稠密索引文件 186

9．3．3 多级索引文件 187

9．4 索引顺序存取文件 189

9．4．1 空间的划分 189

9．4．2 ISAM匠索引结构 189

9．4．3 ISAM文件的基本操作 191

9．5．1 B-树概述 193

9．5 B-树和B+-树 193

9．4．4 主索引和柱面索引的最佳位置 193

9．5．2 B-树的基本操作 194

9．5．3 B+-树的概念 199

9．5．4 B+-树的基本操作 200

9．6 虚拟存储存取文件 200

9．6．1 VSAM的结构 200

9．6．2 VSAM的操作 201

9．7 静态索引与动态索引的比较 202

9．8 杂凑（Hash）文件 202

9．8．1 概述 202

9．8．2 杂凑函数的几种构造方法 203

9．8．3 处理冲突的方法 205

9．8．4 杂凑文件的操作 206

9．8．5 散列法的平均查找长度 208

9．9 多重链表文件 208

9．10 倒排文件 209

习题 210

第十章 内排序 212

10．1 概述 212

10．1．1 排序的要领 212

10．1．2 排序的分类 212

10．2 插入排序（INSERTION SORT） 213

10．3 选择排序（SELECTION SORT） 215

10．4 泡排序（BUBBLE SORT） 216

10．5 谢尔排序（SHELL SORT ） 218

10．6 快速排序（QUICK SORT） 219

10．7．1 堆积的定义 221

10．7 堆积排序（HEAP SORT ） 221

10．7．2 堆积排序算法 222

10．8 二路归并排序（2-WAY MERGE SORT） 225

10．8．1 归并予算法 225

10．8．2 一趟归并扫描子算法 226

10．8．3 二路归并排序算法 227

10．9 基数排序（RADIX SORT） 228

10．10 各种内排序列算法的比较 231

10．10．1 稳定性比较 231

10．10．2 复杂性比较 231

习题 233

11．1 概述 235

第十一章 外排序 235

11．2 磁带排序 236

11．2．1 多路平衡归并排序法 236

11．2．2 多步归并排序 238

11．3 初始归并段的合理布与产生 239

11．3．1初始归并段的合理分布 239

11．3．2 一处产生初始归并段的方法——转换选择排序 240

11．4 磁盘排序 242

11．4．1 最佳最并树 242

习题 245

附录 部分习题参考答案 246

参考文献 258