第一章 绪论 1
1.1 数据结构课程的历史背景、内容及其意义 1
1.2 学习方法 1
1.3 关于描述数据结构和算法的语言选择 1
1.4 基本术语 2
1.5 抽象数据类型 2
1.6 复型数据类型 5
1.7 递归函数 5
习题 8
第二章 表 11
2.1 表的概念 11
2.2 链表的存储结构 12
2.2.1 结点的C语言表示 12
2.2.2 预处理宏的使用 13
2.2.3 结点的存储分配 13
2.3 链表上的元操作 14
2.4 应用：多项式加法 19
2.4.1 多项式加法的主程序 20
2.4.2 多项式数据类型的实现 21
2.4.3 关于多项式的表接口程序 24
2.4.4 表的其它元操作 25
习题 27
第三章 栈和队列 29
3.1 栈的概念 29
3.2 应用之一：括号测试 30
3.2.1 括号测试算法 30
3.2.2 关于字符的栈接口程序 33
3.3 栈的实现：静态数组 34
3.4 栈的实现：动态数组 36
3.5 应用之二：数字符号翻译 38
3.5.1 中缀到后缀的转换算法 38
3.5.2 中缀到后缀转换的实现 39
3.5.3 词法分析程序 44
3.6 栈的实现：表函数 45
3.7 队列的概念 46
3.8 队列的应用：操作系统模拟 47
3.8.1 模拟算法 47
3.8.2 事件子系统 48
3.8.3 统计子系统 52
3.8.4 队列接口程序 53
3.8.5 模拟结果 54
3.9 队列的实现：表函数 54
3.10 队列的实现：首结点 55
习题 58
第四章 复杂表结构 60
4.1 循环链表 60
4.2 双向链表 65
4.2.1 双向链表的存储结构 66
4.2.2 双向链表的元操作 67
4.3.1 实现策略 71
4.3 具有头结点的表 71
4.3.2 空表 72
4.4 广义表 72
4.5 稀疏矩阵 73
4.5.1 稀疏矩阵的存储结构 74
4.5.2 结点分配和初始化 75
4.5.3 矩阵元素的存储 76
4.5.5 矩阵元素的删除 81
4.5.4 矩阵元素的查找 81
4.5.6 一些辅助函数 82
4.5.7 主控程序 84
习题 86
第五章 树 88
5.1 树的概念及术语 88
5.2 二叉树 89
5.2.1 二叉树的概念与特殊二叉树 89
5.2.2 二叉树的C表示及元操作 91
5.2.3 遍历二叉树 94
5.3 线索二叉树 97
5.4 N元树与森林 99
5.4.1 N元树与森林的存储结构 100
5.4.2 森林与二叉树的转换 102
5.4.3 N元树与森林的遍历 102
5.5 堆 103
5.5.1 堆的实现 104
5.5.2 堆的元操作 104
5.6 哈夫曼树 109
5.6.1 哈夫曼树 109
5.6.2 哈夫曼编码 112
5.7 树的应用：表达式求值 113
5.7.1 表达式求值程序的设计 113
5.7.2 构造表达式树 115
5.7.3 读表达式 116
5.7.4 打印表达式 119
5.7.5 表达式求值 120
5.7.6 词法分析程序和栈操作程序 121
5.8 树的应用：作业调度 123
5.8.1 优先级队列 123
5.8.2 修改模拟程序 124
5.8.3 模拟结果 125
习题 125
第六章 图 128
6.1 图的概念及元操作 128
6.2 图的存储结构 129
6.3 图的遍历 134
6.4 图的邻接矩阵实现 136
6.5 图的邻接表实现 140
6.6 生成树和最小生成树 145
6.7 最短路径 147
6.7.1 从某源点到其余各顶点间的最短路径 147
6.7.2 每对顶点间的最短路径 151
6.8 拓扑排序 153
习题 156
第七章 集合和查找 158
7.1 算法的形式分析 158
7.2 集合的概念及元操作 159
7.3 集合的位向量表示 159
7.4 集合的顺序表示 161
7.5 集合的有序数组表示 163
7.6 集合的二叉树表示 167
7.7 哈希方法 172
7.7.1 哈希函数的构造 172
7.7.2 冲突处理 173
7.7.3 基本集合操作实现 175
习题 177
第八章 排序 178
8.1 基本概念 178
8.2 选择排序 178
8.3 归并排序 181
8.4 快速排序 185
8.5 堆排序 188
8.6 基数排序 193
8.7 各种排序方法的比较 195
习题 196
第九章 文件 198
9.1 基本术语与概念 198
9.2 顺序文件 199
9.3 直接存取文件（Hash文件） 200
9.4 索引文件 202
9.4.1 B树 203
9.4.2 B+树 210
9.4.3 R树 212
9.5 多关键字文件 215
9.5.1 倒排文件 216
9.5.2 多重表文件 216
习题 217
参考文献 220