目录 1
第一章 绪论 1
1.1 数据结构的研究对象 1
1.2 数据结构发展概况 3
1.3 抽象数据型 3
1.3.1 抽象数据型的定义 3
1.3.2 数据型、数据结构和抽象数据型 6
1.3.3 抽象数据型的规格描述 7
1.3.4 抽象数据型的实现 9
1.3.5 多层次抽象技术 12
1.3.6 抽象数据型的优点 13
1.4 逐步求精的程序设计方法 13
1.4.1 如何求解一个问题 13
1.4.2 算法的逐步求精 14
1.4.3 小结 18
1.5 程序的运行时间 18
1.6 关于本书采用的描述语言 22
习题 23
第二章 线性表 26
2.1 抽象数据型线性表 26
2.2 线性表的实现 27
2.2.1 指针和游标 28
2.2.2 线性表的数组实现 28
2.2.3 线性表的指针实现 31
2.2.4 线性表的游标实现 34
2.2.5 双向链接表 37
2.2.6 环形链表 38
2.3 栈 39
2.3.1 栈的数组实现 40
2.3.2 栈和递归过程 42
2.4 排队 43
2.4.1 排队的指针实现 43
2.4.2 排队的循环数组实现 44
2.5 多项式的代数运算 47
2.6.1 抽象数据型串 49
2.6 串 49
2.6.2 串的表示 51
2.7 数组 55
2.7.1 抽象数据型数组 55
2.7.2 数组的表示 55
2.8 广义表 58
习题 60
3.1 基本术语 64
第三章 树 64
3.2 二元树 65
3.2.1 二元树的定义及遍历 65
3.2.2 二无树的性质 67
3.2.3 抽象数据型二元树 68
3.2.4 二元树的表示 69
3.2.5 二元树的复制 75
3.3 树 77
3.3.1 抽象数据型树 77
3.3.2 树的表示 79
3.4 森林和二元树间的转换 83
3.5 树的应用 86
3.5.1 用树结构表示集合 86
3.5.2 判定树 89
3.5.3 哈夫曼（Huffman）树 91
3.5.4 表达式求值 98
习题 103
4.1 基本定义 107
第四章 有向图 107
4.2 有向图的表示 109
4.2.1 邻接矩阵 109
4.2.2 邻接表 109
4.3 单源最短路径 110
4.4 每一对顶点之间的最短路径 115
4.4.1 Floyd算法 115
4.4.2 最短路径 116
4.4.3 Warshall算法 118
4.5.1 先深搜索 119
4.5 有向图的遍历 119
4.5.2 先广搜索 122
4.6 拓朴分类 124
4.6.1 无环路有向图 124
4.6.2 拓朴分类 125
4.7 关键路径 128
4.8 强连通分量 134
习题 135
第五章 无向图 139
5.1 无向图及其表示法 139
5.1.1 定义 139
5.1.2 无向图的表示法 141
5.2 最小生成树 142
5.2.1 最小生成树的性质 142
5.2.2 Prim算法 143
5.2.3 Kruskal算法 145
5.3 无向图的遍历 148
5.4 迷宫问题 151
习题 153
第六章 查找 156
6.1 线性查找 156
6.2 折半查找 159
6.3 Fibonacci查找 160
6.4 分块查找 163
6.5 二元查找树 165
6.6.1 内散列表 170
6.6 散列法 170
6.6.2 散列函数 173
6.6.3 冲突的处理 175
6.6.4 外散列表 177
习题 179
第七章 分类 182
7.1 简单的分类算法 182
7.1.1 气泡分类 182
7.1.2 插入分类 184
7.1.3 选择分类 185
7.2 Shell分类 186
7.3 快速分类 187
7.4 并分类 191
7.4.1 合并两个分类序列 191
7.4.2 归并分类 192
7.5 堆分类 196
7.6 基数分类 199
习题 203
8.1.1 磁带 206
第八章 文件 206
8.1 外存贮设备 206
8.1.2 磁盘 207
8.2 文件及其逻辑特性 208
8.3 文件组织 210
8.3.1 顺序式文件 210
8.3.2 随机式文件 211
8.3.3 链接式文件和多重链表式文件 215
8.3.4 倒排文件 217
8.4 外部查找树—B树 218
习题 220
第九章 外部分类 222
9.1 磁盘文件的归并分类 222
9.1.1 K路归并 223
9.1.2 并行操作的缓冲区处理 225
9.1.3 初始归并段的生成 225
9.2.1 平衡归并分类 227
9.2 磁带文件的归并分类 227
9.2.2 多阶段归并分类 228
习题 230
第十章 抽象数据型应用实例 231
10.1 抽象数据型Expression 231
10.2 表达式的微分 233
10.3 抽象数据型Expression的实现 236
习题 238
参考文献 239