《数据结构》

前言页1

第一章概论1

§1.1 什么是数据结构1

§1.2 学习数据结构的意义3

§1.3 算法的描述5

§1.4 算法分析7

习题11

第二章线性表12

§2.1 线性表的定义及其基本运算12

2.1.1 线性表的逻辑结构定义12

2.1.2 线性表的运算13

§2.2 线性表的顺序存贮结构14

2.2.1 顺序表——线性表的顺序存贮结构14

2.2.2 顺序表上的基本运算15

*2.2.3 顺序表上的其它运算举例18

2.3.1 单链表21

§2.3 线性表的链式存贮结构21

2.3.2 单链表上的基本运算23

*2.3.3 单链表上的其它运算举例30

2.3.4 循环链表33

2.3.5 双链表36

*2.3.6 静态链表37

§2.4 顺序表和链表的比较42

习题43

3.1.1 栈的定义和运算44

第三章栈和队列44

§3.1 栈44

3.1.2 顺序栈——栈的顺序存贮结构45

3.1.3 链栈——栈的链式存贮结构47

§3.2 栈的应用举例48

§3.3 栈与递归53

3.3.1 递归的概念53

*3.3.2 递归过程的内部实现54

*3.3.3 递归过程的设计和正确性56

*3.3.4 递归过程到非递归过程的转换59

3.4.1 队列的定义及其运算67

3.4.2 顺序队列——队列的顺序存贮结构67

§3.4 队列67

3.4.3 链队列——队列的链式存贮结构70

*§3.5 队列的应用举例73

习题76

§4.1 串及其运算78

4.1.1 串的基本概念78

第四章串78

4.1.2 串的基本运算79

§4.2 串的存贮结构81

*§4.3 串运算的实现86

习题89

第五章多维数组和广义表91

§5.1 多维数组91

§5.2 矩阵的压缩存贮93

5.2.1 特殊矩阵93

5.2.2 稀疏矩阵95

§5.3 广义表的概念101

*§5.4 广义表的存贮结构102

习题105

第六章 树107

§6.1树的概念107

§6.2 二叉树110

6.2.1 二叉树的概念110

6.2.2 二叉树的性质110

6.2.3 二叉树的存贮结构112

§6.3 二叉树的遍历115

*§6.4 二叉树的其它操作举例120

§6.5 线索二叉树126

§6.6 树和森林132

6.6.1 树、森林与二叉树的转换132

*6.6.2 树的存贮结构134

*6.6.3 树和森林的遍历138

6.7.1 最优二叉树（哈夫曼树）139

§6.7 哈夫曼树及其应用139

6.7.2 哈夫曼编码143

习题146

第七章 图149

§7.1图的概念149

§7.2 图的存贮结构151

7.2.1 邻接矩阵表示法*152

7.2.2 邻接表表示法153

§7.3 图的遍历156

7.3.1 连通图的深度优先搜索遍历156

7.3.2 连通图的广度优先搜索遍历158

7.3.3 非连通图的遍历160

*7.3.4 图的遍历算法的应用161

§7.4 生成树和最小生成树164

§7.5 最短路径171

7.5.1 单源最短路径问题171

7.5.2 所有顶点对之间的最短路径问题177

*§7.6 拓扑排序180

*§7.7 关键路径184

习题189

第八章排序191

§8.1 基本概念191

§8.2 插入排序192

8.2.1 直接插入排序192

8.2.2 希尔排序194

§8.3 交换排序196

8.3.1 起泡排序197

8.3.2 快速排序199

§8.4 选择排序201

8.4.1 直接选择排序202

8.4.2 堆排 序203

§8.5 归并排序208

*§8.6 分配排序210

8.6.1 箱排序211

8.6.2 基数排序212

§8.7 内部排序方法的比较和选择215

*§8.8 外部排序简介216

8.8.1 外存设备216

8.8.2 磁盘排序219

8.8.3 磁带排序221

习题223

第九章查找225

§9.1 基本概念225

§9.2 线性表的查找226

9.2.1 顺序查找226

9.2.2 二分查找227

9.2.3 分块查找229

§9.3 树表的查找231

9.3.1 二叉排序树231

*9.3.2 平衡的二叉排序树237

*9.3.3 B-树243

9.4.1 散列表246

§9.4 散列表的查找246

9.4.2 散列函数的构造方法249

9.4.3 处理冲突的方法251

9.4.4 散列表的查找及分析254

习题257

第十章 文件258

§10.1文件的基本概念258

§10.2 顺序文件260

§10.3 索引文件261

§10.4 索引顺序文件262

10.4.1 ISAM文件263

10.4.2 VSAM文件265

§10.5 散列文件267

*§10.6 多关键字文件268

10.6.1 多重表文件268

10.6.2 例排文件269

习题270

附录 类pascal和标准pascal区别272