第1章 绪论 1
1.1 数据 1
1.1.1 数据的基本概念 1
1.1.2 数值型数据与非数值型数据 2
1.2 数据项与数据元素 2
1.3 数据类型与抽象数据类型 3
1.3.1 数据类型 3
1.3.2 抽象数据类型 4
1.4 数据模型与数据结构 6
1.4.1 数据逻辑结构 6
1.4.2 数据存储结构 7
1.5 数据操作与算法 8
1.5.1 数据运算 9
1.5.2 算法及其基本特征 9
1.5.3 算法设计与分析 11
1.6 数据结构课程的地位与本书内容体系 13
1.6.1 数据结构课程的地位 13
1.6.2 本书的内容组织 14
1.6.3 课程学习建议 15
本章小结 16
第2章 线性表 19
2.1 线性表的概念 19
2.1.1 线性表的逻辑结构 19
2.1.2 线性表的ADT描述 20
2.2 线性表的顺序存储 21
2.2.1 顺序存储结构 21
2.2.2 基于顺序存储的基本操作 23
2.3 线性表的链式存储 28
2.3.1 单链表的概念 28
2.3.2 单链表的基本操作 30
2.3.3 循环链表 35
2.3.4 双向链表 37
2.3.5 静态链表 39
2.3.6 单链表的应用 43
2.4 线性表存储结构的比较 48
本章小结 49
第3章 栈与队列 51
3.1 栈 51
3.1.1 栈的基本概念 51
3.1.2 栈的顺序存储结构 52
3.1.3 栈的链式存储结构 55
3.1.4 栈的应用 57
3.2 队列 70
3.2.1 队列的基本概念 70
3.2.2 顺序队列与循环队列 71
3.2.3 队列的链式存储结构 75
3.2.4 队列的应用 77
本章小结 79
第4章 数组、串与广义表 81
4.1 数组 81
4.1.1 二维数组 82
4.1.2 矩阵的顺序表示与实现 82
4.1.3 特殊矩阵的压缩存储 83
4.1.4 稀疏矩阵的压缩存储 86
4.2 串 93
4.2.1 串及其相关概念 94
4.2.2 串的基本操作 94
4.2.3 串的存储结构 95
4.2.4 串的模式匹配 97
4.3 广义表 104
4.3.1 广义表的基本概念 104
4.3.2 广义表的存储结构 106
4.3.3 广义表的基本操作 107
本章小结 110
第5章 二叉树 112
5.1 二叉树及其基本性质 112
5.1.1 二叉树的基本概念 112
5.1.2 满二叉树和完全二叉树 114
5.1.3 二叉树的基本性质 115
5.2 二叉树的存储 116
5.2.1 二叉树的顺序存储 117
5.2.2 二叉树的链式存储 118
5.3 二叉树的遍历 121
5.4 线索二叉树 131
5.4.1 线索与线索二叉树 131
5.4.2 创建线索二叉树 132
5.4.3 线索二叉树的遍历 135
5.5 二叉树的应用 136
5.5.1 等长编码与非等长编码 136
5.5.2 Huffman树的构造思想 137
5.5.3 基于顺序存储的Huffman树构造 138
5.5.4 Huffman编码 141
本章小结 144
第6章 树与森林 146
6.1 树及其相关概念 146
6.1.1 树 146
6.1.2 结点及其相关概念 148
6.2 树的存储结构 150
6.2.1 父结点表示法存储 150
6.2.2 子结点表示法存储 151
6.2.3 左子结点／右兄弟结点表示法存储 152
6.3 树的遍历 153
6.3.1 层次遍历 153
6.3.2 先序遍历 156
6.3.3 后序遍历 157
6.4 森林 157
6.5 树与二叉树的转换 158
6.5.1 树转换为二叉树 159
6.5.2 二叉树还原为树 159
6.5.3 森林与二叉树的转换 160
本章小结 161
第7章 图 163
7.1 基本概念与相关描述 163
7.1.1 图的基本概念 163
7.1.2 图的相关概念 164
7.2 图的存储 167
7.2.1 基于邻接矩阵的存储 167
7.2.2 基于邻接表的存储 169
7.3 图的遍历 172
7.3.1 深度优先遍历 173
7.3.2 广度优先遍历 174
7.3.3 简单路径与长度最短的路径 177
7.4 生成树与最小生成树 178
7.4.1 图的生成树 178
7.4.2 最小生成树 180
7.5 最短路径 187
7.6 有向无环网及应用 192
7.6.1 拓扑排序 192
7.6.2 关键路径 195
本章小结 202
第8章 查找 204
8.1 数据查找 204
8.2 基于线性表的查找 206
8.2.1 顺序查找 206
8.2.2 分块查找 207
8.2.3 二分查找 209
8.3 基于二叉树的查找 212
8.3.1 二叉查找树的概念 212
8.3.2 基于二叉查找树的查找 213
8.3.3 二叉查找树的插入与创建 214
8.3.4 二叉查找树的删除 216
8.3.5 平衡二叉树 218
8.4 基于散列表的查找 221
8.4.1 常用散列函数的构造 222
8.4.2 散列冲突处理 224
本章小结 227
第9章 排序 229
9.1 数据排序 229
9.1.1 排序的基本概念与分类 229
9.1.2 排序算法的稳定性 230
9.2 插入排序 231
9.2.1 直接插入排序 231
9.2.2 二分插入排序 235
9.2.3 表插入排序 237
9.2.4 Shell插入排序 239
9.3 交换排序 241
9.3.1 冒泡排序 241
9.3.2 快速排序 243
9.4 选择排序 247
9.4.1 直接选择排序 247
9.4.2 堆排序 248
9.5 归并排序 253
9.6 外排序 256
9.6.1 外排序的基本步骤 256
9.6.2 败者树的k路归并算法 258
9.6.3 k路归并算法的实现 259
本章小结 261
第10章 文件 266
10.1 文件的基本概念 266
10.1.1 文件的分类 266
10.1.2 文件的结构与操作 268
10.2 顺序文件 270
10.2.1 顺序文件的存储结构 270
10.2.2 基于磁带／磁盘的顺序存储 271
10.3 索引文件 271
10.3.1 索引的概念及操作 271
10.3.2 ISAM文件 273
10.3.3 VSAM文件 275
10.4 动态索引B－树 277
10.4.1 B－树 277
10.4.2 B＋树 283
10.5 散列文件 284
10.6 多关键字文件 285
10.6.1 多重表文件 286
10.6.2 倒排文件 287
本章小结 288
参考文献 290