第1章 绪论 1
1.1 数据结构的基本概念 1
1.1.1 数据结构的含义 1
1.1.2 数据结构的基本术语 3
1.2 数据结构的重要性 6
1.2.1 数据结构理论的发展历史 6
1.2.2 数据结构在计算机课程体系中的重要地位 6
1.3 算法评价 7
1.3.1 算法的定义及表示 7
1.3.2 算法的特征及评价方法 9
1.4 算法分析 10
1.4.1 算法的时间复杂度分析 10
1.4.2 算法的空间复杂度分析 14
小结 15
综合练习一 15
一、选择题 15
二、填空题 16
三、阅读理解题 17
第2章 C语言基础 19
2.1 C语言的数据类型 19
2.1.1 基本数据类型的使用 19
2.1.2 常用构造数据类型的使用 23
2.1.3 指针数据类型的使用 27
2.2 C语言的常用运算符 33
2.2.1 算术运算符的使用 33
2.2.2 逻辑运算符与关系运算符的使用 34
2.2.3 条件运算符与逗号运算符的使用 35
2.2.4 特殊运算符的使用 36
2.2.5 Turbo C运算符的优先级 37
2.3 结构化程序设计 37
2.3.1 结构化程序设计思想 37
2.3.2 顺序结构程序设计 38
2.3.3 选择结构程序设计 38
2.3.4 循环结构程序设计 41
2.4 算法模块化思想 47
2.4.1 模块化思想在算法设计中的重要性 47
2.4.2 使用函数模块化 47
2.5 培养良好的程序设计风格 50
2.5.1 明确需求分析 51
2.5.2 加强程序可读性 51
2.5.3 使用有意义的变量名、函数名 52
小结 52
综合练习二 53
一、选择题 53
二、填空题 56
三、算法及程序设计 57
第3章 基本线性表 58
3.1 应用背景 58
3.2 基本线性表的逻辑结构 58
3.2.1 基本线性表的定义 58
3.2.2 基本线性表的运算 59
3.3 基本线性表的顺序表示及实现 60
3.3.1 基本线性表的顺序存储 60
3.3.2 基本线性表顺序存储的运算 62
3.4 基本线性表的链式表示及实现 68
3.4.1 基本线性表的链式存储 68
3.4.2 基本线性表的单链表操作 69
3.4.3 基本线性表的双链表操作 75
3.4.4 基本线性表的循环链表操作 77
3.5 应用实例 77
小结 83
综合练习三 83
一、选择题 83
二、填空题 84
三、算法及程序设计 85
第4章 特殊线性表 86
4.1 应用背景 86
4.2 队列 87
4.2.1 队列的含义 87
4.2.2 队列的顺序存储及运算 88
4.2.3 队列的链式存储及运算 91
4.2.4 循环队列的表示及实现 92
4.3 堆栈 96
4.3.1 堆栈的含义 96
4.3.2 堆栈的顺序存储及运算 97
4.3.3 堆栈的链式存储结构及运算 99
4.3.4 双栈的表示及实现 100
4.4 堆栈与队列的比较 101
4.4.1 堆栈和队列的相同点 102
4.4.2 堆栈和队列的不同点 102
4.5 字符串 102
4.5.1 字符串的基本概念 103
4.5.2 字符串的顺序存储及运算 103
4.5.3 字符串的链式存储及运算 105
4.5.4 字符串的混合存储及表示 107
4.6 应用实例 108
4.6.1 队列的应用 108
4.6.2 堆栈的应用 109
4.6.3 字符串的应用 109
小结 111
综合练习四 112
一、选择题 112
二、填空题 113
三、算法及程序设计 113
第5章 树与二叉树 114
5.1 应用背景 114
5.2 树 115
5.2.1 树的基本概念与术语 115
5.2.2 树的存储与表示 117
5.2.3 树的性质 120
5.3 二叉树 121
5.3.1 二叉树的基本概念 121
5.3.2 二叉树的性质 121
5.3.3 二叉树的存储与建立 122
5.3.4 二叉树的遍历 125
5.3.5 二叉树遍历与二叉树构造的关系 131
5.3.6 二叉树的基本操作 133
5.3.7 二叉树的线索化 135
5.4 二叉树与树、森林的转换 137
5.4.1 二叉树、树与森林 137
5.4.2 树、森林的遍历 138
5.5 二叉排序树 139
5.5.1 二叉排序树的定义 139
5.5.2 二叉排序树的运算 140
5.6 哈夫曼树 144
5.6.1 哈夫曼树的基本概念 144
5.6.2 哈夫曼树的构造 145
5.6.3 哈夫曼树的应用 146
5.7 应用实例 149
小结 152
综合练习五 152
一、选择题 152
二、填空题 154
三、算法及程序设计 154
第6章 查找 155
6.1 应用背景 155
6.2 基本概念和术语 155
6.3 线性表查找 156
6.3.1 顺序查找 156
6.3.2 折半查找 159
6.3.3 分块查找 161
6.4 树型查找 162
6.4.1 二叉排序树的查找算法 162
6.4.2 平衡二叉树的查找算法 163
6.4.3 B-树查找算法 169
6.4.4 B+树查找算法 171
6.4.5 B＊树查找算法 172
6.5 Hash表查找 172
6.5.1 Hash表的内涵 172
6.5.2 Hash函数的构造 173
6.5.3 关键字冲突处理方法 174
6.6 应用实例 176
小结 178
综合练习六 178
一、选择题 178
二、填空题 180
三、算法及程序设计 180
第7章 排序 181
7.1 应用背景 181
7.2 基本概念 181
7.3 插入排序 183
7.3.1 直接插入排序 183
7.3.2 折半插入排序 184
7.3.3 希尔排序 185
7.4 选择排序 187
7.4.1 简单选择排序 187
7.4.2 树型选择排序 188
7.4.3 堆排序 189
7.5 交换排序 191
7.5.1 冒泡排序 191
7.5.2 快速排序 192
7.6 归并排序 195
7.7 基数排序 197
7.7.1 多关键字排序 197
7.7.2 链式基数排序 198
7.8 内部排序 201
7.8.1 内部排序方法的共同点 201
7.8.2 内部排序方法的不同点 201
7.8.3 排序方法的选择 202
7.9 外部排序 202
7.9.1 外部排序的方法 202
7.9.2 多路平衡归并的实现 204
7.10 应用实例 206
小结 210
综合练习七 211
一、选择题 211
二、填空题 213
三、算法及程序设计 213
第8章 数组、矩阵和广义表 214
8.1 应用背景 214
8.2 多维数组 214
8.2.1 多维数组的逻辑结构 214
8.2.2 多维数组的顺序存储 215
8.3 特殊矩阵的压缩存储 217
8.3.1 对称矩阵 217
8.3.2 三角矩阵 218
8.3.3 带状矩阵 219
8.3.4 稀疏矩阵 220
8.4 广义表 230
8.4.1 广义表的定义和基本运算 230
8.4.2 广义表的存储 233
8.4.3 广义表基本操作的实现 235
小结 237
综合练习八 238
一、选择题 238
二、填空题 239
三、算法及程序设计 239
第9章 图 240
9.1 应用背景 240
9.2 图的基本概念和术语 240
9.3 图的存储结构 243
9.3.1 邻接矩阵表示 243
9.3.2 邻接表表示 245
9.3.3 十字链表表示 247
9.3.4 邻接多重表表示 249
9.4 图的遍历 250
9.4.1 深度优先搜索 250
9.4.2 度优先搜索 252
9.4.3 广度和深度优先搜索的实现 253
9.5 图的连通性 256
9.5.1 无向图的连通性 256
9.5.2 有向图的连通性 257
9.5.3 生成树和生成森林 257
9.5.4 连通性的应用 259
9.6 最小生成树 260
9.6.1 最小生成树的概念 260
9.6.2 构造最小生成树的Prim算法 261
9.6.3 构造最小生成树的Kruskal算法 263
9.7 最短路径 265
9.7.1 Dijkstra算法 265
9.7.2 Floyd算法 267
9.8 有向无环图 269
9.8.1 有向无环图的概念及应用 269
9.8.2 AOV网与拓扑排序 270
9.8.3 AOE网与关键路径 274
9.9 应用实例 278
小结 287
综合练习九 288
一、选择题 288
二、填空题 289
二、算法及程序设计 289
第10章 文件 290
10.1 文件的基本概念 290
10.1.1 文件的概念 290
10.1.2 文件的逻辑结构及操作 290
10.1.3 文件的存储结构 291
10.2 顺序文件 292
10.2.1 顺序文件的定义及分类 292
10.2.2 顺序文件的操作 292
10.3 索引文件 293
10.3.1 索引文件的定义及构成 293
10.3.2 索引文件的存储 294
10.3.3 索引文件的操作 294
10.3.4 利用查找表建立多级索引 295
10.4 散列文件 295
10.5 多关键字文件 297
10.5.1 多关键字文件概述 297
10.5.2 多重表文件 297
10.5.3 倒排文件 298
小结 300
综合练习十 300
一、选择题 300
二、填空题 301
三、算法及程序设计 302
参考答案 303
第1章 303
第2章 304
第3章 307
第4章 310
第5章 313
第6章 316
第7章 318
第8章 321
第9章 324
第10章 328
参考文献 332