第1章 绪论 1
1.1 引言 1
1.2 数据结构的基本概念 3
1.2.1 有关概念和术语 4
1.2.2 数据的逻辑结构 4
1.2.3 数据的存储结构 5
1.2.4 数据的运算 5
1.3 数据类型和抽象数据类型 6
1.3.1 数据类型 6
1.3.2 抽象数据类型 7
1.4 算法 8
1.4.1 算法及其特征 8
1.4.2 常见的算法描述方法 9
1.4.3 常见的算法设计方法 10
1.5 算法性能分析与度量 10
1.5.1 时间复杂度 11
1.5.2 空间复杂度 14
1.6 关于学习数据结构 14
1.6.1 数据结构课程的地位 14
1.6.2 数据结构课程体系 15
1.6.3 数据结构课程学习特点 15
习题一 16
第2章 线性表 19
2.1 线性表的类型定义 19
2.1.1 线性表的定义 19
2.1.2 线性表的抽象数据类型 20
2.2 线性表的顺序存储及基本操作 21
2.2.1 线性表的顺序存储结构 21
2.2.2 顺序表及相关操作的实现 23
2.2.3 顺序表应用举例 28
2.2.4 线性表顺序存储结构分析 29
2.3 线性表的单链表存储结构 29
2.3.1 线性表的单链表存储结构 30
2.3.2 单链表上相关操作的实现 31
2.3.3 链表应用举例 36
2.3.4 链式存储结构的分析 39
2.4 双链表与其他链式结构 39
2.4.1 线性表的双链表存储结构 39
2.4.2 双链表上相关操作的实现 40
2.4.3 循环链表 43
2.4.4 静态链表 44
2.5 一元多项式的表示及运算 45
2.5.1 一元多项式的表示及存储 45
2.5.2 一元多项式创建与打印 46
2.5.3 一元多项式相加 47
2.5.4 一元多项式相乘 48
习题二 50
第3章 栈 53
3.1 栈的定义及基本运算 53
3.1.1 栈的定义 53
3.1.2 栈的抽象数据类型 53
3.2 顺序栈 54
3.2.1 顺序栈的定义及存储结构 54
3.2.2 顺序栈的基本操作 55
3.3 链栈 57
3.3.1 链栈的定义及存储结构 57
3.3.2 链栈的基本操作 58
3.4 共享栈与多栈 60
3.4.1 共享栈 60
3.4.2 多链栈 63
3.5 栈的应用 65
3.5.1 栈的简单应用 65
3.5.2 栈与递归 70
习题三 71
第4章 队列 74
4.1 队列的定义及基本运算 74
4.1.1 队列的定义 74
4.1.2 队列的抽象数据类型 74
4.2 循环队列 75
4.2.1 循环队列的存储实现 75
4.2.2 循环队列的基本操作 77
4.2.3 动态循环队列 79
4.3 链队列 80
4.3.1 链队列的定义及存储结构 80
4.3.2 链队列的基本操作 81
4.4 队列的其他存储结构 82
4.4.1 循环多队列 82
4.4.2 动态循环多队列与链式多队列 84
4.5 队列的应用 84
习题四 85
第5章 串 88
5.1 串的定义及其基本运算 88
5.1.1 串的定义 88
5.1.2 串的抽象数据类型 88
5.2 串的定长顺序存储 90
5.2.1 定长顺序存储的定义 90
5.2.2 定长顺序串的基本运算 90
5.3 串的模式匹配算法 95
5.3.1 简单模式匹配算法——BF算法 95
5.3.2 改进的模式匹配算法——KMP算法 96
5.4 串的堆存储结构 100
5.4.1 堆存储结构的定义 100
5.4.2 基于堆结构的基本运算 101
5.5 串的块链存储结构 104
5.5.1 块链存储结构的定义及其存储结构 104
5.5.2 基于块链结构的基本运算 105
5.6 串的应用 113
习题五 113
第6章 数组和广义表 116
6.1 数组的概念和存储 116
6.1.1 数组的概念 116
6.1.2 数组的存储结构 117
6.2 特殊矩阵的压缩存储 121
6.2.1 对称矩阵的压缩存储 121
6.2.2 三角矩阵的压缩存储 122
6.2.3 带状矩阵的压缩存储 123
6.3 稀疏矩阵的压缩存储 124
6.3.1 稀疏矩阵的三元组表存储 125
6.3.2 稀疏矩阵的十字链表存储 128
6.4 广义表 133
6.4.1 广义表的基本概念 133
6.4.2 广义表的基本运算 135
6.4.3 广义表的存储结构 136
6.4.4 广义表上的基本算法 138
习题六 140
第7章 二叉树和树 144
7.1 二叉树的定义与性质 144
7.1.1 二叉树的基本概念 144
7.1.2 二叉树的主要性质 146
7.1.3 二叉树的抽象数据类型 147
7.2 二叉树的存储结构及创建 148
7.2.1 顺序存储结构 148
7.2.2 二叉树的链式存储结构 150
7.2.3 二叉树的创建算法 151
7.3 二叉树的遍历及应用 152
7.3.1 二叉树的遍历 152
7.3.2 二叉树遍历的非递归实现 154
7.3.3 遍历算法的应用 158
7.3.4 由遍历序列恢复二叉树 159
7.4 线索二叉树 161
7.4.1 线索二叉树的定义及结构 161
7.4.2 线索二叉树的创建及遍历 163
7.4.3 线索二叉树的其他相关算法 165
7.5 哈夫曼树及其应用 169
7.5.1 哈夫曼树的基本概念 169
7.5.2 构造哈夫曼树 171
7.5.3 哈夫曼编码 172
7.5.4 哈夫曼树的应用 174
7.6 树的概念与表示 175
7.6.1 树的定义及相关术语 175
7.6.2 树的表示 176
7.6.3 树的存储 177
7.7 树与二叉树的转换 180
7.7.1 树或树林转换为二叉树 180
7.7.2 二叉树转换为树或树林 181
7.7.3 树或树林的遍历 183
7.8 树的应用 183
7.8.1 判定树 183
7.8.2 集合的表示 185
习题七 186
第8章 图论 192
8.1 图的基本概念 192
8.1.1 图的定义 192
8.1.2 图的相关术语 193
8.1.3 图的抽象数据类型 193
8.2 图的邻接表存储结构 195
8.2.1 图的邻接表存储结构定义 195
8.2.2 建立在图的邻接表存储结构的基本算法 196
8.2.3 创建图的邻接表存储结构 203
8.3 图的邻接矩阵存储结构 205
8.3.1 图的邻接矩阵存储结构定义 205
8.3.2 建立在图的邻接矩阵存储结构的基本操作算法 207
8.3.3 创建图的邻接矩阵存储结构 212
8.4 图的其他存储结构 214
8.4.1 图的十字链表存储结构 214
8.4.2 图的邻接多重表存储结构 215
8.5 图的广度优先遍历 216
8.5.1 广度优先搜索 216
8.5.2 邻接矩阵存储结构上的BFS算法 217
8.5.3 邻接表存储结构上的BFS算法 218
8.6 图的深度优先遍历 219
8.6.1 深度优先搜索 219
8.6.2 邻接矩阵存储结构上的DFS算法 220
8.6.3 邻接表存储结构上的DFS算法 221
习题八 223
第9章 图算法及应用 226
9.1 最小生成树 226
9.1.1 最小生成树的定义 226
9.1.2 构成最小生成树的Prim算法 227
9.1.3 构成最小生成树的Kruskal算法 230
9.2 最短路径 230
9.2.1 求图中某一顶点到其余各顶点的最短路径——Dijstra算法 231
9.2.2 每一对顶点之间的最短路径——Floyd算法 233
9.3 AOV网的应用 236
9.3.1 AOV网的定义 236
9.3.2 拓扑排序 238
9.4 AOE网的应用 240
9.4.1 AOE网的定义 240
9.4.2 关键路径 241
习题九 247
第10章 查找 252
10.1 查找的基本概念 252
10.2 静态查找表 253
10.2.1 顺序查找 253
10.2.2 有序表的折半查找 254
10.2.3 分块查找 256
10.3 二叉排序树 256
10.3.1 二叉排序树的定义 256
10.3.2 二叉排序树的相关算法 257
10.3.3 二叉排序树的查找效率分析 260
10.4 平衡二叉排序树 260
10.4.1 平衡二叉排序树的定义 260
10.4.2 调整不平衡的二叉排序树 261
10.4.3 创建平衡二叉排序树 263
10.5 其他查找树 264
10.5.1 B树及其基本操作 264
10.5.2 B＋树的基本概念 267
10.6 散列表 268
10.6.1 散列表的基本概念 268
10.6.2 散列函数的设计 268
10.6.3 冲突的处理方法 270
10.6.4 散列表的查找分析 272
习题十 273
第11章 排序 280
11.1 排序的基本概念 280
11.1.1 排序的定义 280
11.1.2 排序方法的分类 281
11.1.3 排序算法的分析方法 281
11.2 插入排序 281
11.2.1 直接插入排序 282
11.2.2 折半插入排序 283
11.2.3 希尔排序 285
11.3 交换排序 287
11.3.1 冒泡排序 287
11.3.2 快速排序 289
11.4 选择排序 291
11.4.1 简单选择排序 291
11.4.2 树形选择排序 293
11.4.3 堆排序 294
11.5 归并排序 297
11.6 基数排序 299
11.6.1 多关键码排序 299
11.6.2 链式基数排序 300
11.7 内部排序算法的比较 304
11.7.1 内部排序算法的比较 304
11.7.2 内部排序算法的选用 305
习题十一 306
附录一 习题参考答案 312
附录二 学期考试样卷 318
参考文献 323