《数据结构简明教程》求取 ⇩

第一章 绪论1

第一章 绪论1

1．1 什么是数据结构1

1-1 基本术语1

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

1．3 算法3

1．4．1 算法格式5

1．4 SPARKS语言简介5

1．4．2 SPARKS语句6

1-2 算法描述6

1-3 算法评价8

1．5．1 时间复杂度9

1．5 算法分析9

1．5．2 空间复杂度10

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

1．5．3 其他方面11

习题12

1-4 pascal 语言中的数据类型12

第二章线性表14

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

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

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

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

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

习题一18

2．3．1 线性链表19

一、线性表的定义20

2-1 线性表的定义和顺序存储20

第二章线性表20

二、线性表的顺序存储21

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

2-2 线性表的运算22

2-3 栈27

一、栈的定义27

2．4 循链表及其运算27

二、栈的顺序存储27

三、栈的运算28

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

四、双栈操作30

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

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

2-4 栈的应用举例32

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

2．6 链表的应用举例33

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

习题41

第三章数组43

3．1 数组的概念43

3．1．2 多维数组43

3．1．1 一维数组43

3．2 数组的存储结构44

3．3 矩阵的压缩存储45

二、队列的顺序存储46

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

2-5 队列46

一、队列的定义46

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

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

三、队列的运算47

一、字符串的定义49

2-6 字符串49

四、队列的应用简介49

二、字符串的顺序存储50

三、字符串的运算52

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

习题二54

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

3．6 数组的应用举例56

3-1 链接表的定义57

3．6．2 N价魔方57

第三章 链接表57

习题58

3-2 线性链接表的运算60

4．1．1 堆栈的定义60

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

第四章堆栈和队列60

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

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

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

4．4 堆栈的应用举例65

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

3-3 链接的栈和队列66

一、链栈的定义与运算66

二、链队的定义与运算67

三、可利用空间表68

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

一、稀疏矩阵的三元组线性表表示71

3-4 稀疏矩阵71

二、稀疏矩阵的顺序存储72

三、稀疏矩阵的链接存储72

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

四、稀疏矩阵的运算73

4．5．1 队列的定义75

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

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

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

3-5 广义表77

一、广义表的定义77

二、广义表的存储结构78

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

三、广义表的运算80

习题81

习题三81

第五章广义表83

5．1 广义表的概念83

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

第四章树84

4-1 树的概念84

一、树的定义84

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

二、 树的表示86

三、树的基本术语87

习题87

第六章串88

6．1 串的概念88

6．1．1 串的定义88

4-2 二叉树88

一、二叉树的定义88

二、二叉树的性质88

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

6．2 串的基本运算89

6．3 串的存储结构90

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

三、二叉树的存储结构91

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

6．4 串的几个运算92

四、二叉树的生成93

4-3 二叉树的运算94

一、二叉树的遗历95

三、输出二叉树97

二、求二叉树的深度97

习题97

7．1 树的基本概念98

7．1．1 树的定义98

第七章树与二叉树98

四、二叉树的线索化99

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

7．1．3 基本术语100

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

五、利用线索进行遍历101

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

7．2 树的存储结构102

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

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

7．3 二叉树103

4-4 二叉排序树103

一、二叉排序树的定义103

二、二叉排序树的查找103

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

三、二叉排序树的插入和生成104

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

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

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

四、 二叉排序树的删除106

4-5 哈夫曼树109

一、基本术语109

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

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

二、构造哈夫曼树110

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

三、哈无曼编码111

7．5 树的遍历112

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

一、树的存储结构112

4-6 树的存储结构和运算112

二、树的运算113

习题四117

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

第五章 图119

5-1 图的概念119

一、图的定义119

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

7．6 线索二叉树120

二、图的基本术语120

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

5-2 图的存储结构122

一、 邻接矩阵122

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

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

二、邻接表124

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

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

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

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

三、边集散组127

5-3 图的遍历128

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

一、深度优先搜索遍历128

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

二、广度优先搜索遍历131

7．8 平衡二叉要地132

三、非边通图的遍历133

5-4 图的生成树和最小生成树133

一、普里姆算法135

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

7．9．1 哈夫曼树的138

二、克鲁撕卡尔算法138

7．9．2哈夫曼编码139

5-5 最短路径140

一、从一顶点到其余各顶点的最短路径141

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

二、每对顶点之间的最短路径144

习题144

5-6 拓扑排序147

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

8．1 图的基本概念147

第八章 图147

5-7 关键路径150

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

8．2 图的存储方法150

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

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

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

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

8．3 图的遍历155

习题五156

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

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

6-1 查找的基本概念159

第六章查找159

8．4 最小生成树159

一、顺序查找160

6-2 顺序表查找160

二、二分查找161

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

8．5 最短路径问题162

6-3 索引查找164

一、索引的概念164

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

二、索引查找算法167

8．6 AOV网与拓扑排序168

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

一、散列的概念169

8．6．2 拓扑排序169

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

6-4 散列查找169

二、散列函数170

三、处理冲突的方法172

8．7 AOE网与关键路径173

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

8．7．2 关键路径174

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

四、散列表的插入和查找算法175

习题176

6-5 树表查找177

一、平衡树178

9．1 文件概述179

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

第九章 文件及查找179

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

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

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

9．2 顺序文件182

二、B树183

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

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

9．3 索引文件186

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

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

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

9．4．1 空间的划分189

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

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

习题六191

第七章排序193

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

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

9．5．1 B-树概述193

7-1 排序的基本概念193

7-2 插入排序194

一、直接插入排序194

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

二、希尔排序197

7-3 选择排序198

一、直接选择排序198

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

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

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

9．6．1 VSAM的结构200

二、堆排序200

9．6．2 VSAM的操作201

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

9．8 杂凑（Hash）文件202

9．8．1 概述202

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

一、气泡排序204

7-4 交换排序204

二、快速排序205

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

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

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

9．9 多重链表文件208

9．10 倒排文件209

7-5 归并排序209

习题210

第十章内排序212

10．1 概述212

10．1．1 排序的要领212

10．1．2 排序的分类212

7-6 各种排序方法的比较212

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

习题七213

一、磁带存储器215

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

8-1 外存设备215

第八章文件215

10．4 泡排序（BUBBLE SORT）216

二、磁盘存储器217

8-2 顺序文件218

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

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

8-3 索引文件220

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

10．7．1 堆积的定义221

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

8-4 ISAM文件和VSAM文件223

一、ISAM文件223

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

10．8．1 归并予算法225

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

二、VSAM文件227

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

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

8-5 散列文件229

一、按桶散列法229

二、可扩充散列法230

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

10．10．1 稳定性比较231

10．10．2 复杂性比较231

习题233

8-6 多重链接表文件233

8-7 倒排文件235

11．1 概述235

第十一章外排序235

11．2 磁带排序236

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

习题八236

部分习题参考解答237

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

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

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

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

11．4 磁盘排序242

11．4．1 最佳最并树242

习题245

附录部分习题参考答案246

参考书目247

参考文献258