本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用;后半部分主要讨论查找和排序的各种实现方法及综合分析比较。

第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