《数据结构教程》求取 ⇩

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