《数据结构》

第一章　绪论1

1-1　基本术语1

目录1

1-2　算法描述6

1-3　算法评价9

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

习题18

2-1　线性表的定义和顺序存贮21

一、线性表的定义21

第二章　线性表21

二、线性表的顺序存贮22

2-2　线性表的运算23

2-3 栈28

一、栈的定义28

二、栈的顺序存贮28

三、栈的运算29

四、双栈操作31

2-4　栈的应用举例32

一、队列的定义48

2-5 队列48

二、队列的顺序存贮49

三、队列的运算50

四、队列的应用简介52

2-6　字符串52

一、字符串的定义52

二、字符串的顺序存贮52

三、字符串的运算55

习题二58

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

第三章　链接表61

3-1　链接表的定义61

3-3　链接的栈和队列71

一、链栈的定义与运算71

二、链队的定义与运算72

三、可利用空间表74

3-4　稀疏矩阵77

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

二、稀疏矩阵的顺序存贮77

　三、稀疏矩阵的链接存贮78

　四、稀疏矩阵的运算80

3-5　广义表84

一、广义表的定义84

二、广义表的存贮结构85

三、广义表的运算86

习题三88

二、树的表示方法91

一、树的定义91

4-1　树的基本概念91

第四章　树91

三、树的基本术语92

四、树的存贮结构93

4-2　二叉树94

一、二叉树及其性质94

二、二叉树的存贮结构97

三、树和二叉树之间的转换98

4-3　二叉树的遍历101

一、二叉树的遍历101

4-4　线索二叉树102

二、递归形式的遍历过程102

一、什么是线索二叉树103

二、如何建立线索树103

三、利用线索的遍历过程105

4-5　二叉排序树106

一、什么是二叉排序树107

二、构造二叉排序树107

三、构造线索二叉树110

二、构造哈夫曼树111

一、基本术语111

4-6　哈夫曼树111

　三、哈夫曼树的应用113

习题四118

第五章　图120

5-1　图的基本概念120

一、图的定义121

二、图的基本术语121

5-2　图的存贮结构123

一、邻接矩阵表示法123

二、邻接表125

三、十字链表126

四、邻接多重表127

五、边集数组128

5-3　图的遍历128

一、深度优先搜索129

二、广度优先搜索131

三、图的生成树和连通分量132

5-4　最小生成树133

一、普里姆算法134

二、克鲁斯卡尔算法136

5-5　最短路径139

一、从某源点到其余各顶点之间的最短路径140

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

5-6　AOV网与拓扑排序145

5-7　AOE网与关键路径150

一、基本术语150

二、关键路径的算法152

习题五158

6-1　查找的基本概念161

第六章　查找161

6-2　基本查找方法162

　一、顺序查找164

二、折半查找164

三、查找有序表的其它方法168

四、分块查找170

6-3　静态树型查找172

一、问题的提出172

三、次优查找树及其构造方法173

二、静态最优查找树173

6-4　动态树型查找176

一、二叉排序树查找176

二、平衡树179

三、B树185

一、散列法的基本思想194

二、构造散列（哈希）函数的几种方法195

6-5　散列法196

四、散列法的平均查找长度204

习题六205

第七章　排序207

7-1　排序的基本概念207

7-2　插入排序208

一、直接插入排序208

二、折半插入排序209

三、解决冲突的方法209

三、希尔排序210

7-3　选择排序211

一、直接选择排序212

　二、树形选择排序213

　三、堆排序214

一、起泡排序219

7-4　交换排序219

二、快速排序220

7-5　基数排序223

7-6　归并排序226

7-7　外排序229

一、多路归并排序230

二、置换-选择排序233

三、最佳归并树235

习题七237

一、文件的逻辑结构239

第八章　文件239

8-1　文件的基本概念239

二、文件的存取240

三、文件的操作（运算）240

四、文件的存贮结构241

8-2　顺序文件241

一、顺序文件的特点241

二、磁带上的顺序文件操作举例241

三、顺序文件的查找242

一、概述243

8-3　索引文件243

二、静态索引——ISAM文件245

三、动态索引——VSAM文件247

8-4　散列文件249

一、按桶散列249

　二、可扩充的散列250

8-5　多重链接表文件254

8-6　倒排文件256

习题八257

参考文献260