(**版获第二届**级**教材特等奖,获**级科技进步奖,同时获电子部**教材特等奖)严蔚敏 吴伟民 编著数据结构(1992年第二版)是1987年初版的修订版。修订版在保持原书基本框架和特色的基础上对主要各章作了增删和修改。 本书详细介绍了线性表、栈和队列、串、数组和广义表、树和二叉树以及图等几种基本类型的数据结构,以及在程序设计中经常遇到的两个问题--查找和排序。全书共分12章。第1章以三个非数

**章 绪论1
1．1 什么是数据结构1
1．2 基本概念和术语3
1．3 数据结构的发展简史及它在计算机科学中所处的地位12
1．4 算法的描述和算法分析13
1．4．1 算法的描述13
1．4．2 算法设计的要求15
1．4．3 算法效率的度量16
1．4．4 算法的存储空间需求18

第二章 线性表19
2．1 线性表的逻辑结构19
2．2 线性表的顺序存储结构22
2．3 线性表的链式存储结构27
2．3．1 线性链表27
2．3．2 循环链表35
2．3，3 双向链表35
2．4 一元多项式的表示及相加37

第三章 栈和队列41
3．1 栈41
3．1．1 抽象数据类型栈的定义41
3．1．2 栈的表示和实现43
3．2 表达式求值45
**3．3 栈与递归过程47
3．3．1 递归过程及其实现47
3．3．2 递归过程的模拟52
3．4 队列59
3．4．1 抽象数据类型队列的定义59
3．4．2 链队列——队列的链式存储结构61
3．4．3 循环队列——队列的顺序存储结构63
3．5 离散事件模拟66

第四章 串71
4．1 串及其操作71
4．1．1 串的逻辑结构定义71
4．1．2 串的基本操作72
4．2 串的存储结构73
4．2．1 静态存储结构74
4．2．2 动态存储结构74
4．3 串基本操作的实现77
4．3．1 静态结构存储串时的操作77
4．3．2 模式匹配的一种改进算法80
4．3．3 堆结构存储串时的操作84
4．4 串操作应用举例86
4．4．1 文本编辑86
**4．4．2 建立词索引表87

第五章 数组和广义表93
5．1 数组的定义和运算93
5．2 数组的顺序存储结构95
5．3 矩阵的压缩存储96
5．3．1 特殊矩阵97
5．3．2 稀疏矩阵97
5．4 广义表的定义107
5．5 广义表的存储结构109
**5．6 m元多项式的表示110
**5．7 广义表的递归算法112
5．7．1 求广义表的深度113
5．7．2 复制广义表114
5．7．3 建立广义表的存储结构115

第六章 树和二叉树118
6．1 树的结构定义和基本操作118
6．2 二叉树120
6．2．1 定义与基本操作120
6．2．2 二叉树的性质122
6．2．3 二叉树的存储结构124
6．3 遍历二叉树和线索二叉树125
6．3．1 遍历二叉树125
5．3．2 线索二叉树128
6．4 树和森林134
6．4．1 树的存储结构134
6．4．2 森林与二叉树的转换135
6．4．3 树的遍历137
**6．5 树与等价问题138
6．6 哈夫曼树及其应用142
6．6．1 *优二叉树（哈夫曼树）142
6．6．2 哈夫曼编码144
**6．7 回溯法与树的遍历148
**6．8 树的计数150

第七章 图155
7．1 图的定义和术语155
7．2 图的存储结构159
7．2．1 数组表示法159
7．2．2 邻接表161
7．2．3 十字链表162
7．2．4 邻接多重表164
7．3 图的遍历165
7．3．1 深度优先搜索166
7．3．2 广度优先搜索167
7．4 图的连通性问题168
7．4．1 无向图的连通分量和生成树168
**7．4．2 有向图的强连通分量171
7．4．3 *小生成树171
**7．4．4 关节点和重连通分量174
7．5 有向无环图及其应用177
7．5．1 拓扑排序179
7．5．2 关键路径184
7．6 *短路径188
7．6．1 从某个源点到其余各顶点的*短路径189
7．6．2 每一对顶点之间的*短路径191
**7．7 二部图与图匹配193

第八章 动态存储管理198
8．1 概述198
8．2 可利用空间表及分配方法200
8．3 边界标识法203
8．3．1 可利用空间表的结构203
8．3．2 分配算法204
8．3．3 回收算法206
8．4 伙伴系统208
8．4．1 可利用空间表的结构208
8．4．2 分配算法209
8．4．3 回收算法210
8．5 无用单元收集211
8．6 存储紧缩216

第九章 查找219
9．1 静态查找表220
9．1．1 顺序表的查找220
9．1．2 有序表的查找223
9．1．3 静态树表的查找226
9．1．4 索引顺序表的查找230
9．2 动态查找表231
9．2．1 二叉排序树和平衡二叉树231
9．2．2 B_树和B+树241
9．2．3 键树249
9．3 哈希表253
9．3．1 什么是哈希表253
9．3．2 哈希函数的构造方法255
9．3．3 处理冲突的方法258
9．3．4 哈希表的查找及其分析260

第十章 内部排序264
10．1 概述264
10．2 插入排序265
10．2．1 直接插入排序265
10．2．2 其它插入排序268
10．2．3 希尔排序272
10．3 快速排序274
10．4 选择排序278
10．4．1 简单选择排序278
10．4．2 树形选择排序280
10．4．3 堆排序281
10．5 归并排序284
10．6 基数排序285
10．6．1 多关键字的排序286
10．6．2 链式基数排序287
10．7 各种内部排序方法的比较讨论289

第十一章 外部排序294
11．1 外存信息的存取294
11．2 外部排序的方法296
11．3 多路平衡归并的实现298
11．4 置换-选择排序300
**11．5 缓冲区的并行操作处理305
11．6 *佳归并树307
**11．7 磁带归并排序308
11．7．1 平衡归并308
11．7．2 多步归并308

第十二章 文件311
12．1 有关文件的基本概念311
12．2 顺序文件313
12．3 索引文件316
12．4 ISAM文件和VSAM文件318
12．4．1 ISAM文件318
12．4．2 VSAM文件321
12．5 直接存取文件(散列文件）322
12．6 多关键字文件324
12．6．1 多重表文件324
12．6．2 倒排文件325

附录一 类PASCAL语言扩充部分的语法图327
附录二 名词索引329
附录三 过程和函数索引336
参考书目340