目录

     第1章绪论1

     1.1什么是数据结构1

     1.2基本概念和术语4

     1.3抽象数据类型的表示与实现9

     1.4算法和算法分析13

     1.4.1算法13

     1.4.2算法设计的要求13

     1.4.3算法效率的度量14

     1.4.4算法的存储空间需求17

     第2章线性表18

     2.1线性表的类型定义18

     2.2线性表的顺序表示和实现21

     2.3线性表的链式表示和实现27

     2.3.1线性链表27

     2.3.2循环链表35

     2.3.3双向链表35

     2.4一元多项式的表示及相加39

     第3章栈和队列44

     3.1栈44

     3.1.1抽象数据类型栈的定义44

     3.1.2栈的表示和实现45

     3.2栈的应用举例48

     321数制转换48

     322括号匹配的检验49

     323行编辑程序49

     324迷宫求解50

     325表达式求值52

     **3.3栈与递归的实现54

     3.4队列58

     3.4.1抽象数据类型队列的定义58

     3.4.2链队列——队列的链式表示和实现60

     3.4.3循环队列——队列的顺序表示和实现63

     **3.5离散事件模拟65

     第4章串70

     4.1串类型的定义70

     4.2串的表示和实现72

     4.2.1定长顺序存储表示73

     4.2.2堆分配存储表示75

     423串的块链存储表示78

     **43串的模式匹配算法79

     4.3.1求子串位置的定位函数Index(S,T,pos)79

     4.3.2模式匹配的一种改进算法80

     4.4串操作应用举例84

     4.4.1文本编辑84

     **4.4.2建立词索引表86

     第5章数组和广义表90

     5.1数组的定义90

     5.2数组的顺序表示和实现91

     5.3矩阵的压缩存储95

     5.3.1特殊矩阵95

     5.3.2稀疏矩阵96

     5.4广义表的定义106

     5.5广义表的存储结构109

     **5.6m元多项式的表示110

     **5.7广义表的递归算法112

     5.7.1求广义表的深度113

     5.7.2复制广义表115

     5.7.3建立广义表的存储结构115

     第6章树和二叉树118

     6.1树的定义和基本术语118

     6.2二叉树121

     6.2.1二叉树的定义121

     6.2.2二叉树的性质123

     6.2.3二叉树的存储结构126

     6.3遍历二叉树和线索二叉树128

     6.3.1遍历二叉树128

     6.3.2线索二叉树132

     6.4树和森林135

     6.4.1树的存储结构135

     6.4.2森林与二叉树的转换137

     6.4.3树和森林的遍历138

     **6.5树与等价问题139

     6.6赫夫曼树及其应用144

     6.6.1最优二叉树(赫夫曼树)144

     6.6.2赫夫曼编码146

     **6.7回溯法与树的遍历149

     **6.8树的计数152

     第7章图156

     7.1图的定义和术语156

     7.2图的存储结构160

     7.2.1数组表示法161

     7.2.2邻接表163

     7.2.3十字链表164

     7.2.4邻接多重表166

     7.3图的遍历167

     7.3.1深度优先搜索167

     7.3.2广度优先搜索169

     7.4图的连通性问题170

     7.4.1无向图的连通分量和生成树170

     **7.4.2有向图的强连通分量172

     7.4.3最小生成树173

     **7.4.4关节点和重连通分量176

     7.5有向无环图及其应用179

     7.5.1拓扑排序180

     7.5.2关键路径183

     7.6最短路径186

     7.6.1从某个源点到其余各顶点的最短路径187

     7.6.2每一对顶点之间的最短路径190

     第8章动态存储管理193

     8.1概述193

     8.2可利用空间表及分配方法195

     8.3边界标识法198

     8.3.1可利用空间表的结构198

     8.3.2分配算法199

     8.3.3回收算法201

     8.4伙伴系统203

     8.4.1可利用空间表的结构203

     8.4.2分配算法204

     8.4.3回收算法205

     **8.5无用单元收集206

     **8.6存储紧缩212

     第9章查找214

     9.1静态查找表216

     9.1.1顺序表的查找216

     9.1.2有序表的查找218

     **9.1.3静态树表的查找222

     9.1.4索引顺序表的查找225

     9.2动态查找表226

     9.2.1二叉排序树和平衡二叉树227

     9.2.2B-树和B+树238

     **9.2.3键树247

     9.3哈希表251

     9.3.1什么是哈希表251

     9.3.2哈希函数的构造方法253

     9.3.3处理冲突的方法256

     9.3.4哈希表的查找及其分析259

     第10章内部排序263

     10.1概述263

     10.2插入排序265

     10.2.1直接插入排序265

     10.2.2其他插入排序266

     10.2.3希尔排序271

     10.3快速排序272

     10.4选择排序277

     10.4.1简单选择排序277

     10.4.2树形选择排序278

     10.4.3堆排序279

     10.5归并排序283

     10.6基数排序284

     10.6.1多关键字的排序284

     10.6.2链式基数排序286

     10.7各种内部排序方法的比较讨论288

     第11章外部排序293

     11.1外存信息的存取293

     11.2外部排序的方法295

     **11.3多路平衡归并的实现297

     **11.4置换选择排序299

     **11.5最佳归并树304

     第12章文件306

     12.1有关文件的基本概念306

     12.2顺序文件308

     12.3索引文件311

     12.4ISAM文件和VSAM文件313

     12.4.1ISAM文件313

     12.4.2VSAM文件316

     12.5直接存取文件(散列文件)317

     12.6多关键字文件319

     12.6.1多重表文件319

     12.6.2倒排文件319

     附录A名词索引322

     附录B函数索引329

     参考书目334