《数据结构》

第一章绪论1

§1-1 学习数据结构的意义1

§1-2 有关数据结构的基本概念和术语5

§1-3 算法的描述工具——拟PASCAL语言7

§1-4 算法分析技术初步12

练习16

第二章线性表17

§2-1 线性表的定义和运算17

一、线性表的定义17

二、线性表的运算18

§2-2 顺序分配的存贮结构18

一、向量——线性表的顺序存贮结构18

二、向量中基本运算的实现19

三、运算的时间分析23

四、其它运算示例24

§2-3 链式分配的存贮结构30

一、单链表和指针30

二、链表的基本运算34

三、链表的实现36

四、链表的其它运算示例41

五、循环链表49

六、双向链表53

§2-4 向量和链表的综合比较55

练习58

第三章栈和队列60

§3-1 栈的结构特点和运算60

一、栈的定义和运算60

二、栈的存贮结构和基本运算的实现61

§3-2 LIFO原则和栈的应用62

§3-3 队列的结构特点及运算68

一、队列的定义和运算68

二、队列的存贮结构和基本运算的实现68

§3-4 FIFO原则和队列的应用72

§3-5 求迷宫的最短路径——栈和队列的综合应用77

练习82

第四章树和二叉树84

§4-1 树的定义和术语84

§4-2 二叉树88

一、二叉树的定义和存贮结构88

二、二叉树的几个基本性质89

三、几种特殊形态的二叉树90

四、二叉树的生成算法93

§4-3 遍历二叉树95

一、遍历二叉树的递归定义和递归算法96

二、遍历算法的非递归形式100

三、遍历算法应用示例102

§4-4 树的存贮结构和树的遍历113

一、孩子-兄弟链表113

二、树的遍历114

§4-5 二叉排序树115

一、二叉排序树的生成116

二、二叉排序树上结点的删除118

§4-6 哈夫曼树122

§4-7 解答树127

练习132

第五章图134

§5-1 图的定义和基本术语134

§5-2 图的存贮结构137

一、深度优先搜索遍历连通图142

§5-3 图的遍历142

二、广度优先搜索遍历连通图146

三、非连通图的遍历151

四、图的遍历算法的应用152

§5-4 最小生成树156

§5-5 单源最短路径158

§5-6 拓扑排序162

§5-7 关键路径167

练习171

第六章查找173

§6-1 查找的基本概念173

§6-2 顺序表的查找174

一、顺序查找175

二、二分查找176

三、分块查找179

§6-3 二叉排序树查找和动态平衡技术介绍182

§6-4 最优二叉查找树及其近似算法187

§6-5 哈希表及其查找192

一、哈希表192

二、构造均匀的哈希函数的几种方法195

三、解决冲突的方法和建哈希表示例198

四、哈希表的查找及性能分析201

练习205

第七章排序206

§7-1 排序的基本概念206

§7-2 简单排序方法209

一、插入排序209

二、起泡排序211

§7-3 先进排序方法214

一、快速排序214

二、归并排序219

三、堆排序221

四、基数排序226

§7-4 排序方法的选择和使用230

§7-5 外排简介234

练习235

第八章文件236

§8-1 文件的基本概念236

§8-2 顺序文件238

§8-3 索引文件240

§8-4 索引顺序文件241

§8-5 直接存取文件248

§8-6 多关键字文件249

一、多重表文件249

二、倒排文件249

练习251

第九章数据结构的程序设计实例252

§9-1 从问题到程序的一般过程252

一、建立数据模型和设计算法252

二、编制伪码算法253

三、设定存贮结构并求精算法254

四、编制上机代码并调试运行257

§9-2 程序实例262

一、任务分配问题262

二、排队问题的系统仿真271

三、集合的一种表示法及其应用282

四、课程安排问题293

五、建造符号表示例305

六、二叉排序树索引的文件查找310

七、计算网络图的关键路径324

附录 过程名索引335