《数据结构》求取 ⇩

第一章 绪论1

1．1 什么是数据结构1

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

1．3 算法5

1．3．1 算法及其性质5

1．3．2 基本算法6

1．3．3 算法的描述7

1．4 SPARKS语言简介9

1．4．1 算法格式9

1．4．2 语句9

1．5 算法分析13

1．5．1 时间复杂度14

1．5．2 空间复杂度15

1．5．3 其他方面16

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

习题17

第二章 线性表19

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

2．1．1 线性表的定义19

2．1．2 线性表的基本运算20

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

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

2．3．1 线性链表24

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

2．4 循环链表及其运算33

2．5．1 双向链表的构造36

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

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

2．6 链表的应用举例39

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

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

习题48

第三章 数组51

3．1 数组的概念51

3．1．1 一维数组51

3．1．2 多维数组51

3．2 数组的存储结构52

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

3．3 矩阵的压缩存储54

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

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

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

3．6 数组的应用举例65

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

3．6．2 n阶魔方66

习题67

第四章 堆栈和队列69

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

4．1．1 堆栈的定义69

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

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

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

4．4 堆栈的应用举例75

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

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

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

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

4．5．1 队列的定义86

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

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

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

习题93

5．1 广义表的概念95

第五章 广义表95

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

*5．3 多元多项式的表示98

习题99

第六章 串100

6．1 串的概念100

6．1．1 串的定义100

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

6．2 串的基本运算101

6．3 串的存储结构102

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

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

6．4 串的几个运算104

习题109

第七章 树与二叉树110

7．1 树的基本概念110

7．1．1 树的定义110

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

7．1．3 基本术语112

7．1．4 树的性质113

7．1．5 树的基本运算114

7．2 树的存储结构115

7．2．1 多重链表表示法115

7．3 二叉树116

7．2．2 三重链表表示法116

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

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

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

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

7．3．5 二叉树与树、树林之间的转换120

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

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

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

7．5 树的遍历126

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

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

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

7．6 线索二叉树135

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

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

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

*7．6．4 线索树的更新139

7．7 二叉排序树140

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

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

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

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

*7．8 平衡二叉树147

7．9．1 哈夫曼树的概念153

7．9哈夫曼树及其应用153

*7．9．2 哈夫曼编码155

习题158

第八章 图161

8．1 图的基本概念161

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

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

8．2 图的存储方法164

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

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

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

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

8．3．1 深度优先搜索171

8．3 图的遍历171

8．3．2 广度优先搜索173

8．4 最小生成树174

8．5 最短路径问题178

8．6 AOV网与拓扑排序181

8．6．1 AOV网181

8．6．2 拓扑排序182

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

8．7 AOE网与关键路径186

8．7．1 AOE网186

8．7．2 关键路径187

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

习题191

第九章 文件及查找194

9．1 文件概述194

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

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

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

9．2 顺序文件197

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

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

9．3 索引文件201

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

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

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

9．4 B-树和B+树204

9．4．1 B-树概述204

9．4．2 B-树的基本操作205

9．4．3 B+树的概念210

9．4．4 B+树的基本操作211

9．5 杂凑（Hash）文件212

9．5．1 概述212

9．5．2 杂凑函数的几种构造方法213

9．5．3 处理冲突的方法214

9．5．4 杂凑文件的操作216

*9．6 多重链表文件218

*9．5．5 散列法的平均查找长度218

*9．7 倒排文件219

习题220

第十章 内排序222

10．1 概述222

10．1．1 排序的概念222

10．1．2 排序的分类222

10．2 插入排序223

10．3 选择排序225

10．4 泡排序227

10．5 谢尔排序228

10．6 快速排序229

10．7．1 堆积的定义231

10．7 堆积排序231

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

10．8 二路归并排序236

10．8．1 归并子算法236

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

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

*10．9 基数排序239

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

10．10．1 稳定性比较242

10．10．2 复杂性比较242

习题243

11．1 概述247

*第十一章 外排序247

11．2 磁带排序248

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

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

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

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

11．3．2 一种产生初始归并段的方法——置换选择排序252

11．4 磁盘排序254

11．4．1 最佳归并树254

习题257

上机实践题259

部分习题参考答案261

附录 北京市高等教育学历文凭考试“数据结构”课程考试大纲282

参考文献288