第1章 概述 1
1.1数据结构的发展 1
1.2基本概念 2
1.3算法描述与分析 4
习题1 9
第2章 线性表 13
2.1线性表的定义及基本操作 13
2.1.1线性表的基本概念 13
2.1.2线性表的基本操作 14
2.2顺序表 14
2.2.1顺序表的定义 14
2.2.2基本操作在顺序表上的实现 15
2.3链表 18
2.3.1单链表的表示和实现 19
2.3.2双链表的表示和实现 26
2.3.3循环链表的表示和实现 30
2.3.4静态链表的表示和实现 38
习题2 42
第3章 特殊线性表 47
3.1栈 47
3.1.1栈的定义及其基本操作 47
3.1.2顺序栈的表示和实现 48
3.1.3链栈的表示和实现 52
3.2队列 55
3.2.1队列的定义及其基本操作 55
3.2.2顺序队列的表示和实现 56
3.2.3链队列的表示和实现 60
3.3串 62
3.3.1串的定义及其基本操作 62
3.3.2顺序串的表示和实现 63
3.3.3链串的表示和实现 68
3.3.4串的模式匹配 74
习题3 79
第4章 数组和广义表 83
4.1数组 83
4.1.1数组的定义及基本操作 83
4.1.2数组存储结构 84
4.1.3矩阵的压缩存储 85
4.2广义表 99
4.2.1广义表的定义和基本操作 99
4.2.2广义表的存储 100
习题4 105
第5章 树和二叉树 109
5.1树的定义和基本操作 109
5.1.1树的定义和基本术语 109
5.1.2树的基本操作 110
5.2二叉树的定义和性质 110
5.2.1二叉树的定义 110
5.2.2二叉树的性质与结论 111
5.3二叉树的存储 114
5.3.1二叉树的顺序存储结构 114
5.3.2二叉树的链式存储结构 117
5.4二叉树的遍历及应用 119
5.4.1二叉树的遍历 119
5.4.2二叉树递归遍历应用举例 122
5.4.3二叉树的非递归遍历 125
5.5线索二叉树 128
5.5.1线索二叉树的定义 128
5.5.2线索化处理算法 129
5.6树和森林 132
5.6.1树的存储结构 132
5.6.2树、森林与二叉树之间的转换 135
5.6.3树和森林的遍历 135
5.7霍夫曼树及其应用 136
5.7.1霍夫曼树 136
5.7.2霍夫曼编码 138
习题5 142
第6章图 145
6.1图的基本概念 145
6.2图的存储 148
6.2.1邻接矩阵 148
6.2.2邻接表与逆邻接表 150
6.2.3十字链表 153
6.2.4邻接多重表 154
6.3图的遍历 155
6.3.1深度优先搜索及其生成树 155
6.3.2广度优先搜索及其生成树 156
6.4最小生成树 157
6.4.1 Kruskal算法 157
6.4.2 Prim算法 159
6.5图的应用 160
6.5.1拓扑排序 160
6.5.2关键路径 162
6.5.3最短路径 164
习题6 166
第7章 查找 169
7.1静态查找表 170
7.1.1顺序查找 171
7.1.2二分查找 172
7.1.3分块查找 175
7.2动态查找表 177
7.2.1二叉排序树 177
7.2.2平衡二叉树 184
7.2.3 B树与B+树 190
7.2.4键树 192
7.3散列表 193
7.3.1散列表的定义 193
7.3.2散列函数的构造方法 194
7.3.3处理冲突的方法 196
7.3.4散列表的查找与分析 202
习题7 203
第8章 内部排序 207
8.1概述 207
8.2插入排序 210
8.3交换排序 218
8.4选择排序 222
8.5归并排序 228
8.6计数排序 231
8.7基数排序 232
8.8各种排序方法的综合比较 235
习题8 236
第9章 外部排序 239
9.1外存储器简介 239
9.2外部排序的方法 241
9.3多路归并排序 242
9.4置换-选择排序 244
9.5最佳归并树 246
习题9 247
第10章 动态存储管理 249
10.1概述 249
10.2可利用空间表及分配方法 251
10.3边界标识法 254
10.3.1可利用空间表的结构 254
10.3.2分配算法 255
10.3.3回收算法 257
10.4伙伴系统 258
10.4.1可利用空间表的结构 259
10.4.2分配算法 260
10.4.3回收算法 261
10.5无用单元收集 262
10.6存储紧缩 266
第11章 文件 269
11.1表与文件 269
11.1.1有关文件的基本概念 269
11.1.2记录的逻辑结构和物理结构 270
11.1.3文件的操作 270
11.2外存储器简介 271
11.2.1文件的物理结构 271
11.2.2文件的逻辑结构和文件的存储结构 272
11.2.3顺序文件 273
11.2.4索引文件 275
11.3 ISAM文件 277
11.4 VSAM文件 278
11.5直接存取文件（散列文件） 279
11.6多关键字文件 280
11.6.1多重表文件 280
11.6.2倒排文件 281
习题11 281
参考文献 283