第一章 绪论 1
1.1 什么是数据结构 1
1.2 数据结构发展概况 3
1.3 数据结构课程与其它课程的关系 4
1.4 算法所用语言的几点说明 4
第二章 静态结构 8
2.1 向量 8
2.2 数组 11
2.2.1 数组与向量的比较 11
2.2.2 访问公式 13
2.2.3 数组相交部分和子数组 15
2.2.4 三角数组 19
2.2.5 稀疏数组 23
2.2.6 分配 25
2.3 记录 26
2.3.1 记录的逻辑结构 26
2.3.2 记录的物理表示和运算 27
2.3.3 明显命名的作用 29
2.4 记录数组 31
习题 35
第三章 半静态结构 37
3.1 自描述记录 37
3.2 数组的修改 40
3.3 栈、队列和双向队列 47
3.3.1 栈 47
3.3.2 多个栈共享邻接空间 50
3.3.3 栈的应用 52
3.3.4 队列 53
3.3.5 双向队列 56
习题 57
第四章 动态结构 59
4.1 向前链表 60
4.2 循环链表和双向循环链表 66
4.3 链式栈和链式队列 69
4.4 多项式的算术运算 70
4.5 共享元素及稀疏矩阵运算 75
4.6 等价关系的处理 81
4.7 广义链表、多重链表和丛结构 85
习题 89
第五章 串 91
5.1 串的逻辑特征 92
5.2 串的物理表示法 94
5.3 处理串的算法 100
习题 104
第六章 树 105
6.1 术语、树的逻辑结构及物理表示 105
6.2 二叉树 107
6.2.1 二叉树的定义及逻辑结构 107
6.2.2 二叉树的性质 107
6.2.3 二叉树的物理表示法 110
6.3 遍历二叉树 111
6.3.1 二叉树结点的排序 112
6.3.2 前序遍历 112
6.3.3 中序遍历 113
6.3.4 后序遍历 115
6.4 线索树 116
6.5 一般树的二叉树表示、遍历和运算 121
6.5.1 一般树的二叉树表示法 121
6.5.2 一般树的遍历 124
6.5.3 一般树的插入和删除 125
6.6 森林与二叉树间的转换及遍历 129
6.7 树的应用 131
6.7.1 集合表示法 131
6.7.2 表达式求值 135
6.7.3 判定树 138
6.7.4 比赛树 139
6.8 计算二叉树的数目 144
习题 149
第七章 图 151
7.1 术语 151
7.2 图的物理表示法 152
7.2.1 邻接矩阵表示法 152
7.2.2 邻接表 153
7.2.3 邻接多重表 155
7.3 图的遍历与求图的连通分量 156
7.3.1 纵向优先搜索法 156
7.3.2 横向优先搜索法 157
7.3.3 求图的连通分量 158
7.4 生成树和最小（代价）生成树 158
7.5 最短路径和传递闭包 162
7.5.1 从某个源点到其它各顶点的最短路径 162
7.5.2 求每一对顶点之间的最短路径 165
7.5.3 传递闭包 168
7.6 拓扑排序 170
7.7 关键路径 175
7.8 列举所有路径 180
习题 183
第八章 存贮管理 186
8.1 存贮管理的若干问题 186
8.2 空闲存贮块链表 187
8.3 存贮的动态分配与回收 189
8.3.1 首次-配给、最佳-配给、最大-配给方法 189
8.3.2 引用计数器法 192
8.3.3 不用单元收集法 196
8.4 紧凑存贮的方法 203
8.4.1 折叠法 204
8.4.2 紧凑法 206
8.5 伙伴系统 209
习题 212
第九章 内部分类 214
9.1 查找 214
9.2 什么是分类 219
9.3 计数分类 220
9.4 选择分类 221
9.5 冒泡分类 222
9.6 线性插入 224
9.7 折半插入 225
9.8 归并分类 226
9.8.1 分类文件的归并 226
9.8.2 k个分类文件的归并 227
9.8.3 归并分类 229
9.9 堆垒分类 231
9.10 快速分类 237
9.11 基数分类 239
习题 242
第十章 数据查找 244
10.1 链表结构的线性查找 244
10.2 静态树型查找 245
10.3 动态树型查找 254
10.4 Hash（杂凑）技术 259
10.4.1 为什么要引入Hash技术 259
10.4.2 Hash函数 260
10.4.3 冲突处理 262
10.4.4 动态结构下的探测技术 269
习题 273
第十一章 文件 275
11.1 存贮设备 275
11.1.1 磁带 275
11.1.2 磁盘 276
11.2 文件的基本概念和逻辑特性 278
11.3 文件的物理结构 279
11.3.1 顺序式文件 279
11.3.2 索引技术 282
11.3.3 随机式文件 289
11.3.4 链接式文件和多重表文件 291
11.3.5 倒排文件 292
11.4 外存贮器管理 294
习题 294
第十二章 外部分类 296
12.1 关于磁盘文件的归并分类 296
12.1.1 k-路归并 298
12.1.2 并行操作的缓冲区处理 302
12.1.3 初始归并段的生成 308
12.2 关于磁带文件的归并分类 314
12.2.1 平衡归并分类法 315
12.2.2 多阶段归并分类法 320
习题 324
第十三章 数据结构示例 325
13.1 数据及其相适应的运算 325
13.2 访问路径和子结构 326
13.2.1 学生数据子结构 327
13.2.2 课程数据子结构 329
13.3 存贮需要量估算 331
13.4 运算的实现 331
参考文献 332