第1章 绪论 1
1.1数据结构的基本概念和术语 1
1.1.1引言 1
1.1.2数据结构有关概念及术语 4
1.1.3数据结构和抽象数据类型 6
1.2算法描述与分析 7
1.2.1算法的定义 7
1.2.2算法描述工具——C语言 8
1.2.3算法分析技术初步 11
习题1 13
第2章 线性表 15
2.1线性表的定义及其运算 15
2.1.1线性表的定义 15
2.1.2数据运算简介 16
2.2线性表的顺序存储结构（向量） 16
2.2.1顺序存储结构 16
2.2.2向量中基本运算的实现 17
2.3线性表的链式存储结构 31
2.3.1单链表与指针 31
2.3.2单链表的基本运算 33
2.4循环链表和双向链表 46
2.4.1循环链表 46
2.4.2双向链表 47
2.4.3顺序存储结构与链表存储结构比较 52
2.5线性表的算法实现举例 53
2.5.1实现线性表顺序存储结构及运算的C语言源程序 53
2.5.2单链表处理的C语言源程序 56
习题2 64
第3章 栈和队列 66
3.1栈 66
3.1.1栈的定义及运算 66
3.1.2栈的顺序存储结构（向量） 67
3.1.3栈的链式存储结构 72
3.1.4栈的应用 75
3.2队列 78
3.2.1队列的定义 78
3.2.2队列的顺序存储结构（向量） 79
3.2.3队列的链式存储结构 88
3.3栈和队列的算法实现举例 92
习题3 102
第4章串 105
4.1串的定义及其基本运算 105
4.1.1串的定义 105
4.1.2串的基本运算 106
4.2串的存储结构 107
4.2.1串的顺序存储 107
4.2.2串的链式存储 111
4.3串的模式匹配 117
4.3.1 Brute-Force算法 117
4.3.2 KMP算法 118
4.4串的模式匹配C语言程序实现举例 122
4.4.1 Brute-Force算法的实现 122
4.4.2 KMP算法的实现 123
习题4 125
第5章 数组和广义表 127
5.1数组的基本概念 127
5.1.1数组的概念 127
5.1.2数组的顺序表示和实现 127
5.1.3特殊矩阵的压缩存储 130
5.2稀疏矩阵的三元组存储 132
5.2.1稀疏矩阵的三元组表存储 133
5.2.2稀疏矩阵的运算 133
5.3稀疏矩阵的十字链表存储 140
5.3.1十字链表的组成 140
5.3.2十字链表的有关算法 141
5.4广义表 144
5.4.1广义表的概念和特性 144
5.4.2广义表的存储结构 146
5.4.3求广义表的深度 148
5.4.4广义表的输出 149
5.4.5建立广义表的存储结构 149
5.4.6广义表的其他操作算法 150
习题5 155
第6章树 158
6.1树的基本概念和术语 158
6.1.1树的定义 158
6.1.2树的常用术语 159
6.1.3树的表示方法 160
6.1.4树的基本操作 161
6.2二叉树 161
6.2.1二叉树的定义 161
6.2.2二叉树的相关术语 162
6.2.3二叉树的重要性质 163
6.2.4二叉树的存储结构 164
6.2.5二叉树的基本操作及实现 167
6.3遍历二叉树 169
6.3.1先根（序）遍历（DLR） 169
6.3.2中根（序）遍历（LDR） 170
6.3.3后根（序）遍历（LRD） 170
6.3.4层次遍历 170
6.3.5二叉树遍历的非递归实现 171
6.3.6二叉树由遍历序列恢复二叉树 173
6.3.7不用栈的二叉树遍历的非递归方法 174
6.4线索二叉树 175
6.4.1线索二叉树的基本概念 175
6.4.2线索二叉树的逻辑表示图 175
6.4.3线索二叉树的基本操作实现 177
6.4.4二叉树遍历的应用 181
6.5二叉树、树和森林 183
6.5.1树的存储结构 183
6.5.2树与二叉树之间的转换 186
6.5.3森林与二叉树之间的转换 186
6.6树的应用 188
6.6.1哈夫曼树的基本概念 188
6.6.2哈夫曼树的构造算法 190
6.6.3哈夫曼树在编码问题中的应用 191
6.6.4哈夫曼树在判定问题中的应用 193
6.6.5二叉排序树 194
6.7二叉树的建立和遍历C语言源程序示例 197
习题6 200
第7章图 205
7.1图的基本概念 205
7.1.1图的定义 205
7.1.2图的基本术语 206
7.2图的存储结构 208
7.2.1邻接矩阵 208
7.2.2邻接表 209
7.3图的遍历 211
7.3.1深度优先搜索 211
7.3.2广度优先搜索 212
7.3.3求图的连通分量 213
7.4图的生成树 213
7.4.1生成树的概念 213
7.4.2最小生成树 214
7.4.3普里姆算法和克鲁斯卡尔算法 215
7.5图的应用 218
7.5.1拓扑排序 218
7.5.2关键路径 221
7.5.3最短路径 224
7.6图的算法C语言程序实现举例 229
7.6.1无向图的邻接表的建立和遍历 229
7.6.2有向无环图的拓扑排序和求关键路径 231
习题7 237
第8章 查找 239
8.1基本概念 239
8.2静态表查找 240
8.2.1顺序表的查找 241
8.2.2有序表的查找 242
8.2.3索引顺序表的查找 246
8.3动态查找表 247
8.3.1二叉排序树 247
8.3.2平衡二叉树 253
8.3.3 B-树 262
8.4哈希表 265
8.4.1哈希表与哈希函数 265
8.4.2构造哈希函数的常用方法 266
8.4.3哈希冲突的解决方法 269
8.4.4哈希表的查找及其分析 271
8.4.5哈希表算法实现C语言源程序 274
习题8 276
第9章 排序 280
9.1排序的基本概念 280
9.2插入排序 282
9.2.1直接插入排序 282
9.2.2折半插入排序 283
9.2.3希尔排序 284
9.3交换排序 289
9.3.1冒泡排序 289
9.3.2快速排序 290
9.4选择排序 294
9.4.1简单选择排序 294
9.4.2堆排序 296
9.5归并排序 303
9.6基数排序 304
9.7各种内部排序方法的比较讨论 308
9.8有关排序算法的C语言源程序 309
9.9外排序 316
习题9 317
第10章 文件 319
10.1文件的基本概念 319
10.1.1文件的相关概念 319
10.1.2记录的物理结构和逻辑结构 320
10.1.3文件的分类 321
10.1.4文件的运算 321
10.1.5文件的物理结构 323
10.2文件的常见组织形式 323
10.2.1顺序文件 323
10.2.2索引文件 324
10.2.3索引顺序文件 326
10.2.4散列文件 327
10.2.5多重表文件和倒排文件 327
习题10 328
习题答案 329
习题1答案 329
习题2答案 330
习题3答案 332
习题4答案 334
习题5答案 335
习题6答案 338
习题7答案 341
习题8答案 343
习题9答案 347
习题10答案 348
附录A抽象数据类型定义 350
参考文献 359