1.1 什么是数据结构 1
第1章 绪论 1
1.2 数据的逻辑结构和存储结构 4
1.2.1 数据的逻辑结构 4
1.2.2 数据的存储结构 5
1.3 存储结构的表示与实现 6
1.3.1 数据类型 6
1.3.2 抽象数据类型 6
1.3.3 抽象数据类型的表示与实现 7
1.4 问题、算法和程序 8
1.5.1 算法的描述 9
1.5 算法的描述与分析 9
1.5.2 算法分析 14
学习指导 15
习题 16
第2章 线性表 18
2.1 线性表的逻辑特点 18
2.2 线性表的顺序存储结构——顺序表 19
2.2.1 顺序表的类型定义 19
2.2.2 基本操作的实现 20
2.2.3 典型应用——多项式求值 23
2.3.1 单链表的类型定义 24
11.2 实验二栈和队列及其应用 24
2.3 线性表的链式存储结构——链表 24
2.3.2 基本运算的实现 25
2.3.3 循环链表与双向链表 29
2.3.4 典型应用——多项式相加 33
2.4 链表的数组描述与实现 36
学习指导 38
习题 39
第3章 栈和队列 40
3.1 栈的逻辑特点 40
3.2 栈的顺序存储结构——顺序栈 41
3.2.1 顺序栈的类型定义 41
3.2.2 基本运算的实现 42
3.2.3 多栈共享空间 44
3.2.4 典型应用举例 46
3.3.1 链栈的类型定义 54
3.3.2 基本运算的实现 54
3.3 栈的链式存储结构——链栈 54
3.3.3 典型应用举例 57
3.4 队列的逻辑特点 58
3.5 队列的链式存储结构——链队列 58
3.5.1 链队列的类型定义 58
3.5.2 基本运算的实现 59
3.6 队列的顺序存储结构——循环队列 61
3.6.1 循环队列的类型定义 62
3.6.2 基本运算的实现 63
3.6.3 典型应用举例 65
学习指导 68
习题 69
第4章 数组和串 70
4.1 数组的逻辑特点 70
4.2 数组的顺序存储结构 71
4.3 特殊矩阵的压缩存储 73
4.4 稀疏矩阵运算的实现 75
4.4.1 矩阵转置 75
4.4.2 矩阵相乘 77
4.5 串 80
4.5.1 串的存储表示与操作实现 80
4.5.2 串的模式匹配算法 83
学习指导 87
习题 88
第5章 递归 90
5.1 递归模型与递归算法 90
5.2 递归过程与递归工作栈 93
5.3 递归程序的阅读方法 98
5.4 递归问题的非递归算法 99
5.5 广义表 102
5.5.1 广义表的递归定义 102
5.5.2 广义表的存储结构 103
5.5.3 广义表的递归算法 106
5.5.4 典型应用——m元多项式的表示 109
学习指导 111
习题 111
第6章 树和二叉树 113
6.1 树的逻辑结构 113
6.1.1 树的递归定义 113
6.1.2 树的基本术语 114
6.1.3 树的表示 115
6.2.1 二叉树的递归定义 117
6.2.2 二叉树的性质 117
6.2 二叉树 117
6.2.3 二叉树的存储结构 120
6.3 二叉树遍历 123
6.3.1 二叉树遍历的定义 123
6.3.2 前序遍历算法描述 124
6.3.3 中序遍历算法描述 126
6.3.4 后序遍历算法描述 128
6.3.5 遍历算法的应用 131
6.4 线索化二叉树 135
6.4.1 二叉树的线索化 136
6.4.2 线索二叉树的遍历 138
6.5 树和森林 140
6.5.1 树的存储结构 140
6.5.2树、森林与二叉树的转换 144
6.5.3树和森林的遍历 146
6.6.1 基本术语 147
6.6 哈夫曼树及其应用 147
6.6.2 构造哈夫曼树 148
6.6.3 哈夫曼树的应用 150
学习指导 152
习题 153
第7章 图 156
7.1 图的定义和术语 156
7.2 图的存储结构 158
7.2.1 邻接矩阵 158
7.2.2 邻接表 159
7.2.3 十字链表 160
7.2.4 邻接多重表 161
7.3 图的遍历 162
7.3.1 深度优先搜索 162
7.3.2 广度优先搜索 165
7.4 图的应用 166
7.4.1 图的连通性 166
7.4.2 最小生成树 166
7.4.3 拓扑排序 171
7.4.4 最短路径 173
学习指导 177
习题 179
8.1 查找的基本概念 181
第8章 查找 181
8.2 顺序表查找 182
8.2.1 顺序查找 182
8.2.2 折半查找 183
8.3 索引表查找 185
8.3.1 索引查找 185
8.3.2 分块查找 185
8.4 树表查找 186
8.4.1 二叉排序树 186
8.4.2 平衡二叉树 189
8.4.3 B-树 192
8.5.1 哈希表与哈希函数 196
8.5 哈希表查找 196
8.5.2 处理冲突的办法 197
8.5.3 哈希表的查找 199
学习指导 201
习题 202
第9章 排序 204
9.1 排序的基本概念 204
9.2 插入排序 205
9.2.1 直接插入排序 205
9.2.2 折半插入排序 206
9.2.3 希尔（shell）排序 207
9.3.1 冒泡排序 209
9.3 交换排序 209
9.3.2 快速排序 210
9.4 选择排序 212
9.4.1 简单选择排序 212
9.4.2 堆排序 213
9.5 归并排序 216
9.5.1 两个有序文件的归并 216
9.5.2 归并排序 217
9.6 基数排序 219
9.7 各种排序方法的比较 219
学习指导 221
习题 222
第10章 文件 223
10.1 外部存储设备 223
10.1.1 磁带 223
10.1.2 磁盘 224
10.2 文件的基本概念 225
10.2.1 文件的定义及其分类 225
10.2.2 文件的逻辑结构及物理结构 226
10.3 顺序文件 228
10.4 索引文件 230
10.5 索引顺序文件 232
10.6 散列文件 236
10.7.1 多重链表文件 237
10.7 多关键字文件 237
10.7.2 倒排文件 238
10.8 典型应用举例 239
10.8.1 顺序文件的批量处理实例 239
10.8.2 文件的随机访问实例 241
学习指导 244
习题 244
第11章 《数据结构》实验指导 245
11.1 实验一线性表及其应用 247
11.1.1 课程成绩管理 247
11.1.2 一元稀疏多项式简单计数器 247
11.2.1 停车场管理 249
11.2.2 车厢调度 251
11.2.3 汽车加油 251
11.3 实验三串及其应用——简单行编辑程序 252
11.4 实验四树及其应用 254
11.4.1 二叉树的中序遍历及线索化 254
11.4.2 重言式判别 254
11.5 实验五图及其应用——跳马将军 255
附录 257
源程序1 257
源程序2 263
参考文献 269