- 科学出版社
- 9787030801975
- 1版
- 570759
- 2025-02
- 工学
- 计算机类
- 计算机
- 本科
内容简介
本书以提升学生的数据组织与处理能力为目标，依据“数据结构”课程教学大纲组织编写。全书系统地介绍各种常用数据结构的逻辑特征、存储方式和基本运算，主要内容包括顺序表、链表、串、树形结构、图、多维数组和广义表、排序、查找、文件等。本书结构清晰，内容丰富，示例充实，符号、图表规范，既适合教师课堂讲授，又便于自学者阅读。
本书可作为高等院校计算机专业、数据科学与大数据技术、数字媒体技术及人工智能等相关专业的本科教材，也可作为参加相关专业研究生入学考试，以及从事计算机工程和应用的行业人员的参考书。
本书可作为高等院校计算机专业、数据科学与大数据技术、数字媒体技术及人工智能等相关专业的本科教材，也可作为参加相关专业研究生入学考试，以及从事计算机工程和应用的行业人员的参考书。
目录
第1章 概论 1
1.1 数据结构的概念 2
1.2 数据结构的组成与分类 3
1.2.1 数据的逻辑结构 3
1.2.2 数据的存储结构 3
1.2.3 数据的运算 6
1.3 数据类型与抽象数据类型 6
1.3.1 数据类型 6
1.3.2 抽象数据类型 7
1.4 算法的概念与描述 9
1.4.1 算法的概念 9
1.4.2 算法的描述 9
1.5 算法分析 16
1.5.1 算法性能的评价标准 16
1.5.2 算法的时空复杂度 17
本章小结 21
习题 22
第2章 顺序表 24
2.1 向量 26
2.1.1 向量的存储与运算 26
2.1.2 目录表 30
2.2 栈 30
2.2.1 栈的定义与基本操作 31
2.2.2 顺序栈 33
2.3 栈与递归 36
2.3.1 递归的概念 36
2.3.2 递归过程的实现 38
2.4 队列 41
2.4.1 队列的定义与基本操作 41
2.4.2 顺序队列 43
2.5 应用举例 47
2.5.1 向量应用——约瑟夫斯问题 47
2.5.2 栈的应用——括号匹配的检验与数制转换 51
2.5.3 队列应用——输出杨辉三角形 57
*2.6 顺序表的类表示 60
2.6.1 顺序表（向量） 60
2.6.2 顺序栈 64
2.6.3 顺序队列 65
本章小结 67
习题 68
第3章 链表 70
3.1 单链表 71
3.1.1 单链表的概念 71
3.1.2 单链表的存储描述 71
3.1.3 在单链表上实现的基本运算 73
3.1.4 带表头结点的单链表 76
3.2 栈和队列的链接存储表示 76
3.2.1 链栈 77
3.2.2 链队列 78
3.3 循环链表 80
3.4 双链表 82
3.4.1 双链表的概念 82
3.4.2 带表头结点的双循环链表 83
3.4.3 双循环链表的基本操作 83
3.5 应用举例 85
3.5.1 消除链表中的重复数据 85
3.5.2 用循环链表求解约瑟夫斯问题 89
*3.6 链表的类表示 91
本章小结 99
习题 100
第4章 串 103
4.1 串的基本概念 104
4.2 串的存储结构 105
4.2.1 顺序存储 105
4.2.2 链接存储 107
4.3 串的操作 108
*4.4 模式匹配 110
4.4.1
ute-fo
ce算法 110
4.4.2 KMP算法 112
4.5 应用举例 117
本章小结 118
习题 118
第5章 树形结构 121
5.1 树形结构的概念 122
5.1.1 树的概念 122
5.1.2 二叉树的概念 124
5.1.3 树（森林）与二叉树之间的相互转换 126
5.1.4 树形结构的遍历 128
5.2 树形结构的存储方式 131
5.2.1 链式存储 131
5.2.2 顺序存储 133
5.2.3 二叉树的顺序存储转换为二叉链表存储 136
5.3 二叉树的遍历算法 138
5.3.1 遍历二叉树的非递归算法 138
5.3.2 遍历二叉树的递归算法 142
5.3.3 二叉树遍历的应用举例 144
5.4 线索二叉树 145
5.4.1 线索二叉树的概念 145
5.4.2 二叉树的线索化 146
5.4.3 线索二叉树的遍历 148
5.4.4 线索二叉树的插入 151
5.5 堆 152
5.5.1 堆的定义 152
5.5.2 堆的构造 153
5.5.3 堆的插入与删除 156
5.6 哈夫曼树 158
5.6.1 扩充的二叉树 159
5.6.2 哈夫曼树的构造 160
5.6.3 哈夫曼树的应用举例 165
5.7 应用举例 169
5.7.1 判定树的应用——伪币鉴别问题 169
5.7.2 集合的表示与并查集 170
5.7.3 二叉树的建立与遍历 173
*5.8 树形结构的类表示 175
本章小结 178
习题 179
第6章 图 183
6.1 图的概念 184
6.2 图的存储表示 186
6.2.1 邻接矩阵表示法 187
6.2.2 邻接表表示法 188
*6.2.3 邻接多重表表示法 190
6.3 图的遍历 192
6.3.1 深度优先遍历 192
6.3.2 广度优先遍历 195
6.4 最小（代价）生成树 198
6.4.1 普里姆算法 199
6.4.2 克鲁斯卡尔算法 202
6.5 最短路径问题 204
6.5.1 单源最短路径 205
6.5.2 每对顶点间的最短路径 208
6.6 拓扑排序 211
*6.7 关键路径 218
*6.8 图的类表示 223
6.8.1 图的抽象数据类型 223
6.8.2 用邻接矩阵法表示的图类 224
6.8.3 用邻接表法表示的图类 225
本章小结 228
习题 229
第7章 多维数组和广义表 233
7.1 多维数组 234
7.2 矩阵的压缩存储 236
7.2.1 特殊矩阵 236
7.2.2 稀疏矩阵 238
7.3 广义表 244
7.3.1 广义表的概念 244
7.3.2 广义表的存储结构 246
7.3.3 广义表的运算 249
本章小结 251
习题 251
第8章 排序 254
8.1 排序的基本概念 255
8.2 插入排序 256
8.2.1 直接插入排序 256
8.2.2 谢尔排序 259
*8.2.3 表插入排序 260
8.3 交换排序 263
8.3.1 冒泡排序 263
8.3.2 快速排序 265
8.4 选择排序 268
8.4.1 直接选择排序 268
8.4.2 树形选择排序 270
8.4.3 堆排序 272
8.5 归并排序 275
*8.6 基数排序 279
8.6.1 多排序码排序 279
8.6.2 基数排序算法描述 280
*8.7 外排序 284
8.7.1 二路平衡归并 284
8.7.2 k路平衡归并与败者树 286
8.7.3 最佳归并树 288
本章小结 289
习题 290
第9章 查找 294
9.1 基本概念 295
9.2 线性表的查找 296
9.2.1 顺序查找 296
9.2.2 折半查找 298
9.2.3 分块查找 301
9.3 树形表的查找 304
9.3.1 二叉排序树 304
9.3.2 最佳二叉排序树 309
9.3.3 AVL树 313
*9.3.4
-树与
+树 321
9.4 散列表的查找 332
9.4.1 基本概念 332
9.4.2 散列函数 335
9.4.3 冲突的解决 337
9.4.4 散列查找的性能 343
本章小结 344
习题 345
第10章 文件 349
10.1 文件的基本概念 350
10.2 顺序文件 352
10.3 索引文件 353
10.4 索引顺序文件 354
10.4.1 ISAM文件 354
10.4.2 VSAM文件 356
10.5 散列文件 358
10.6 多关键字文件 359
10.6.1 多重表文件 359
10.6.2 倒排文件 360
本章小结 361
习题 362
参考文献 365
1.1 数据结构的概念 2
1.2 数据结构的组成与分类 3
1.2.1 数据的逻辑结构 3
1.2.2 数据的存储结构 3
1.2.3 数据的运算 6
1.3 数据类型与抽象数据类型 6
1.3.1 数据类型 6
1.3.2 抽象数据类型 7
1.4 算法的概念与描述 9
1.4.1 算法的概念 9
1.4.2 算法的描述 9
1.5 算法分析 16
1.5.1 算法性能的评价标准 16
1.5.2 算法的时空复杂度 17
本章小结 21
习题 22
第2章 顺序表 24
2.1 向量 26
2.1.1 向量的存储与运算 26
2.1.2 目录表 30
2.2 栈 30
2.2.1 栈的定义与基本操作 31
2.2.2 顺序栈 33
2.3 栈与递归 36
2.3.1 递归的概念 36
2.3.2 递归过程的实现 38
2.4 队列 41
2.4.1 队列的定义与基本操作 41
2.4.2 顺序队列 43
2.5 应用举例 47
2.5.1 向量应用——约瑟夫斯问题 47
2.5.2 栈的应用——括号匹配的检验与数制转换 51
2.5.3 队列应用——输出杨辉三角形 57
*2.6 顺序表的类表示 60
2.6.1 顺序表（向量） 60
2.6.2 顺序栈 64
2.6.3 顺序队列 65
本章小结 67
习题 68
第3章 链表 70
3.1 单链表 71
3.1.1 单链表的概念 71
3.1.2 单链表的存储描述 71
3.1.3 在单链表上实现的基本运算 73
3.1.4 带表头结点的单链表 76
3.2 栈和队列的链接存储表示 76
3.2.1 链栈 77
3.2.2 链队列 78
3.3 循环链表 80
3.4 双链表 82
3.4.1 双链表的概念 82
3.4.2 带表头结点的双循环链表 83
3.4.3 双循环链表的基本操作 83
3.5 应用举例 85
3.5.1 消除链表中的重复数据 85
3.5.2 用循环链表求解约瑟夫斯问题 89
*3.6 链表的类表示 91
本章小结 99
习题 100
第4章 串 103
4.1 串的基本概念 104
4.2 串的存储结构 105
4.2.1 顺序存储 105
4.2.2 链接存储 107
4.3 串的操作 108
*4.4 模式匹配 110
4.4.1
ute-fo
ce算法 110
4.4.2 KMP算法 112
4.5 应用举例 117
本章小结 118
习题 118
第5章 树形结构 121
5.1 树形结构的概念 122
5.1.1 树的概念 122
5.1.2 二叉树的概念 124
5.1.3 树（森林）与二叉树之间的相互转换 126
5.1.4 树形结构的遍历 128
5.2 树形结构的存储方式 131
5.2.1 链式存储 131
5.2.2 顺序存储 133
5.2.3 二叉树的顺序存储转换为二叉链表存储 136
5.3 二叉树的遍历算法 138
5.3.1 遍历二叉树的非递归算法 138
5.3.2 遍历二叉树的递归算法 142
5.3.3 二叉树遍历的应用举例 144
5.4 线索二叉树 145
5.4.1 线索二叉树的概念 145
5.4.2 二叉树的线索化 146
5.4.3 线索二叉树的遍历 148
5.4.4 线索二叉树的插入 151
5.5 堆 152
5.5.1 堆的定义 152
5.5.2 堆的构造 153
5.5.3 堆的插入与删除 156
5.6 哈夫曼树 158
5.6.1 扩充的二叉树 159
5.6.2 哈夫曼树的构造 160
5.6.3 哈夫曼树的应用举例 165
5.7 应用举例 169
5.7.1 判定树的应用——伪币鉴别问题 169
5.7.2 集合的表示与并查集 170
5.7.3 二叉树的建立与遍历 173
*5.8 树形结构的类表示 175
本章小结 178
习题 179
第6章 图 183
6.1 图的概念 184
6.2 图的存储表示 186
6.2.1 邻接矩阵表示法 187
6.2.2 邻接表表示法 188
*6.2.3 邻接多重表表示法 190
6.3 图的遍历 192
6.3.1 深度优先遍历 192
6.3.2 广度优先遍历 195
6.4 最小（代价）生成树 198
6.4.1 普里姆算法 199
6.4.2 克鲁斯卡尔算法 202
6.5 最短路径问题 204
6.5.1 单源最短路径 205
6.5.2 每对顶点间的最短路径 208
6.6 拓扑排序 211
*6.7 关键路径 218
*6.8 图的类表示 223
6.8.1 图的抽象数据类型 223
6.8.2 用邻接矩阵法表示的图类 224
6.8.3 用邻接表法表示的图类 225
本章小结 228
习题 229
第7章 多维数组和广义表 233
7.1 多维数组 234
7.2 矩阵的压缩存储 236
7.2.1 特殊矩阵 236
7.2.2 稀疏矩阵 238
7.3 广义表 244
7.3.1 广义表的概念 244
7.3.2 广义表的存储结构 246
7.3.3 广义表的运算 249
本章小结 251
习题 251
第8章 排序 254
8.1 排序的基本概念 255
8.2 插入排序 256
8.2.1 直接插入排序 256
8.2.2 谢尔排序 259
*8.2.3 表插入排序 260
8.3 交换排序 263
8.3.1 冒泡排序 263
8.3.2 快速排序 265
8.4 选择排序 268
8.4.1 直接选择排序 268
8.4.2 树形选择排序 270
8.4.3 堆排序 272
8.5 归并排序 275
*8.6 基数排序 279
8.6.1 多排序码排序 279
8.6.2 基数排序算法描述 280
*8.7 外排序 284
8.7.1 二路平衡归并 284
8.7.2 k路平衡归并与败者树 286
8.7.3 最佳归并树 288
本章小结 289
习题 290
第9章 查找 294
9.1 基本概念 295
9.2 线性表的查找 296
9.2.1 顺序查找 296
9.2.2 折半查找 298
9.2.3 分块查找 301
9.3 树形表的查找 304
9.3.1 二叉排序树 304
9.3.2 最佳二叉排序树 309
9.3.3 AVL树 313
*9.3.4
-树与
+树 321
9.4 散列表的查找 332
9.4.1 基本概念 332
9.4.2 散列函数 335
9.4.3 冲突的解决 337
9.4.4 散列查找的性能 343
本章小结 344
习题 345
第10章 文件 349
10.1 文件的基本概念 350
10.2 顺序文件 352
10.3 索引文件 353
10.4 索引顺序文件 354
10.4.1 ISAM文件 354
10.4.2 VSAM文件 356
10.5 散列文件 358
10.6 多关键字文件 359
10.6.1 多重表文件 359
10.6.2 倒排文件 360
本章小结 361
习题 362
参考文献 365
