- 科学出版社
- 9787030753762
- 1版
- 514313
- 46258895-5
- 16开
- 2023-04
- 计算机类
- 本科
内容简介
本书是针对应用型本科教学特征和需求而编写的，书中系统地介绍了常见数据结构和算法的相关理论和实现方法，主要包括线性表、栈、队列、串、数组和广义表、树和二叉树、图等逻辑结构及其对应的存储结构和操作。另外，本书还集中介绍了常见的排序和查找算法，并对算法的效率进行了分析。本书以C语言为算法实现语言，以理论讲解为基石，以案例讲解为驱动，每个章节配备思考题和章后习题（包括理论习题和上机操作习题）。本书致力于将理论和实践相结合，由浅入深地实现理论和实践内容的逐级内化。本书可作为应用型高等院校计算机科学与技术、软件工程、数据科学与大数据技术、信息安全等相关专业的本科生专业教材或参考用书，也可作为计算机相关从业技术人员的自学和参考用书。
目录
第1章 数据结构和算法 1
1.1 数据结构的基本概念 1
1.2 抽象数据类型的表示与实现 5
1.2.1 抽象、数据抽象和过程抽象 5
1.2.2 封装与信息隐蔽 5
1.2.3 数据类型和抽象数据类型 6
1.2.4 数据结构和抽象数据类型 6
1.3 算法 7
1.3.1 算法的概念 7
1.3.2 算法的基本特性 7
1.4 算法的设计与评价 8
1.4.1 评价算法的标准 8
1.4.2 常见的算法设计方法 9
小结 12
习题 12
第2章 线性表 15
2.1 线性表的基本概念 15
2.1.1 线性表的定义 15
2.1.2 线性表的逻辑结构 16
2.1.3 线性表的基本运算 16
2.2 线性表的顺序表示与实现 18
2.2.1 线性表的顺序存储结构 18
2.2.2 顺序表的实现 18
2.2.3 顺序表基本运算的实现 19
2.2.4 顺序表的算法分析 24
2.3 线性表的链式表示与实现 25
2.3.1 线性表的链式存储结构（链表） 25
2.3.2 链表的实现 26
2.3.3 链表基本运算的实现 27
2.3.4 链表的算法分析 32
2.4 单循环链表和双链表 33
2.4.1 单循环链表 33
2.4.2 双链表 33
2.4.3 顺序表和链表的比较 36
2.5 线性表的应用 36
2.5.1 顺序表的应用 36
2.5.2 链表的应用 42
小结 47
习题 47
第3章 栈 53
3.1 基本概念 53
3.1.1 栈的概念 53
3.1.2 栈的基本运算 54
3.2 栈的顺序存储结构 55
3.2.1 顺序栈 55
3.2.2 顺序栈的基本操作 56
3.3 栈的链式存储结构 58
3.3.1 链栈的实现 59
3.3.2 链栈的基本操作 59
3.4 栈的应用 61
3.4.1 数制转换 61
3.4.2 括号匹配 63
3.4.3 “迷宫”游戏 65
小结 69
习题 69
第4章 队列 73
4.1 队列的基本概念和基本运算 73
4.1.1 队列的基本概念 73
4.1.2 队列的基本运算 74
4.2 队列的顺序存储结构 74
4.2.1 队列的顺序表示 74
4.2.2 顺序队列的基本运算 76
4.2.3 循环队列 78
4.2.4 循环队列的基本运算 80
4.3 队列的链式存储结构 82
4.3.1 链队列 82
4.3.2 链队列的实现 83
4.4 队列的应用 86
4.4.1 冲突分组 86
4.4.2 舞伴问题 89
小结 92
习题 92
第5章 串 95
5.1 串的定义和基本操作 95
5.1.1 串的定义 95
5.1.2 串的基本操作 95
5.2 串的存储结构 98
5.2.1 串的顺序存储结构 98
5.2.2 串的链式存储结构 99
5.3 串的抽象数据类型和模式匹配 101
5.3.1 串的抽象数据类型 101
5.3.2 串的模式匹配 102
小结 106
习题 106
第6章 数组和广义表 108
6.1 数组 108
6.1.1 数组的定义及其抽象数据类型 108
6.1.2 C语言的数组 109
6.2 数组的存储结构 111
6.2.1 一维数组 111
6.2.2 二维数组 111
6.2.3 多维数组 113
6.3 特殊矩阵及其压缩存储方法 113
6.4 广义表 116
6.4.1 广义表的定义 116
6.4.2 广义表的抽象数据类型表示 117
6.4.3 广义表的存储结构及运算实现 118
小结 119
习题 120
第7章 树和二叉树 123
7.1 树的定义和基本术语 123
7.1.1 树的定义 123
7.1.2 树的常用术语和运算 124
7.1.3 树的抽象数据类型 125
7.1.4 树的存储存在的挑战 126
7.2 二叉树 128
7.2.1 二叉树的定义 128
7.2.2 二叉树的性质 129
7.2.3 二叉树的抽象数据类型 131
7.2.4 二叉树的存储结构 133
7.2.5 二叉树的简单运算实现 136
7.3 遍历二叉树 137
7.3.1 遍历二叉树的递归算法 138
7.3.2 遍历二叉树的非递归算法 140
7.3.3 遍历序列与二叉树的恢复 144
7.3.4 基于遍历的二叉树运算的实现和应用 147
7.4 线索二叉树 149
7.4.1 线索二叉树的定义 149
7.4.2 线索二叉树的构造方法 150
7.4.3 线索二叉树上的运算实现 151
7.5 树、森林与二叉树的转换 154
7.5.1 树的存储结构 154
7.5.2 森林和二叉树的转换 155
7.5.3 树和森林的遍历 156
7.6 哈夫曼树及其应用 157
7.6.1 相关概念 157
7.6.2 哈夫曼树的构造过程 159
7.6.3 哈夫曼编码 159
小结 161
习题 161
第8章 图 166
8.1 图的基本概念 166
8.1.1 图的定义 166
8.1.2 图的相关术语 167
8.1.3 图的抽象数据类型 169
8.2 图的存储结构 171
8.2.1 邻接矩阵表示法 171
8.2.2 邻接表表示法 172
8.2.3 邻接多重表表示法 173
8.3 图的遍历 174
8.3.1 定义及难点问题 174
8.3.2 深度优先搜索遍历 175
8.3.3 广度优先搜索遍历 176
8.3.4 图的遍历应用 177
8.4 无向连通图的最小代价生成树 179
8.4.1 K
uskal算法 179
8.4.2 P
im算法 182
8.4.3 Sollin算法 183
8.5 有向图的最短路径 184
8.5.1 单源最短路径——Dijkst
a算法 184
8.5.2 所有节点之间的最短路径——Floyd算法 188
8.6 AOV网络与拓扑排序 191
8.6.1 AOV网络的定义 191
8.6.2 拓扑序列和拓扑排序算法 192
8.7 AOE网络与关键路径 195
8.7.1 AOE网络的定义 195
8.7.2 关键路径和关键活动 196
8.7.3 关键路径算法 196
小结 199
习题 199
第9章 查找 204
9.1 顺序查找 204
9.1.1 顺序查找实例 204
9.1.2 顺序查找问题 205
9.2 二分查找 208
9.3 二叉查找树 211
9.3.1 二叉查找树的定义 211
9.3.2 二叉查找树的构建 212
9.3.3 平衡二叉树 216
小结 217
习题 217
第10章 排序 220
10.1 排序的基本概念 220
10.2 冒泡排序 221
10.2.1 冒泡排序的基本思想 221
10.2.2 冒泡排序的性能分析 224
10.3 快速排序 224
10.3.1 快速排序的基本思想 224
10.3.2 快速排序的基本过程 224
10.3.3 快速排序的性能分析 227
10.4 直接插入排序 227
10.5 希尔排序 229
10.5.1 希尔排序的基本思想 230
10.5.2 希尔排序的效率分析 231
10.6 选择排序 232
10.6.1 简单选择排序 232
10.6.2 树形选择排序 232
10.6.3 堆排序 233
小结 235
习题 235
参考文献 238
1.1 数据结构的基本概念 1
1.2 抽象数据类型的表示与实现 5
1.2.1 抽象、数据抽象和过程抽象 5
1.2.2 封装与信息隐蔽 5
1.2.3 数据类型和抽象数据类型 6
1.2.4 数据结构和抽象数据类型 6
1.3 算法 7
1.3.1 算法的概念 7
1.3.2 算法的基本特性 7
1.4 算法的设计与评价 8
1.4.1 评价算法的标准 8
1.4.2 常见的算法设计方法 9
小结 12
习题 12
第2章 线性表 15
2.1 线性表的基本概念 15
2.1.1 线性表的定义 15
2.1.2 线性表的逻辑结构 16
2.1.3 线性表的基本运算 16
2.2 线性表的顺序表示与实现 18
2.2.1 线性表的顺序存储结构 18
2.2.2 顺序表的实现 18
2.2.3 顺序表基本运算的实现 19
2.2.4 顺序表的算法分析 24
2.3 线性表的链式表示与实现 25
2.3.1 线性表的链式存储结构（链表） 25
2.3.2 链表的实现 26
2.3.3 链表基本运算的实现 27
2.3.4 链表的算法分析 32
2.4 单循环链表和双链表 33
2.4.1 单循环链表 33
2.4.2 双链表 33
2.4.3 顺序表和链表的比较 36
2.5 线性表的应用 36
2.5.1 顺序表的应用 36
2.5.2 链表的应用 42
小结 47
习题 47
第3章 栈 53
3.1 基本概念 53
3.1.1 栈的概念 53
3.1.2 栈的基本运算 54
3.2 栈的顺序存储结构 55
3.2.1 顺序栈 55
3.2.2 顺序栈的基本操作 56
3.3 栈的链式存储结构 58
3.3.1 链栈的实现 59
3.3.2 链栈的基本操作 59
3.4 栈的应用 61
3.4.1 数制转换 61
3.4.2 括号匹配 63
3.4.3 “迷宫”游戏 65
小结 69
习题 69
第4章 队列 73
4.1 队列的基本概念和基本运算 73
4.1.1 队列的基本概念 73
4.1.2 队列的基本运算 74
4.2 队列的顺序存储结构 74
4.2.1 队列的顺序表示 74
4.2.2 顺序队列的基本运算 76
4.2.3 循环队列 78
4.2.4 循环队列的基本运算 80
4.3 队列的链式存储结构 82
4.3.1 链队列 82
4.3.2 链队列的实现 83
4.4 队列的应用 86
4.4.1 冲突分组 86
4.4.2 舞伴问题 89
小结 92
习题 92
第5章 串 95
5.1 串的定义和基本操作 95
5.1.1 串的定义 95
5.1.2 串的基本操作 95
5.2 串的存储结构 98
5.2.1 串的顺序存储结构 98
5.2.2 串的链式存储结构 99
5.3 串的抽象数据类型和模式匹配 101
5.3.1 串的抽象数据类型 101
5.3.2 串的模式匹配 102
小结 106
习题 106
第6章 数组和广义表 108
6.1 数组 108
6.1.1 数组的定义及其抽象数据类型 108
6.1.2 C语言的数组 109
6.2 数组的存储结构 111
6.2.1 一维数组 111
6.2.2 二维数组 111
6.2.3 多维数组 113
6.3 特殊矩阵及其压缩存储方法 113
6.4 广义表 116
6.4.1 广义表的定义 116
6.4.2 广义表的抽象数据类型表示 117
6.4.3 广义表的存储结构及运算实现 118
小结 119
习题 120
第7章 树和二叉树 123
7.1 树的定义和基本术语 123
7.1.1 树的定义 123
7.1.2 树的常用术语和运算 124
7.1.3 树的抽象数据类型 125
7.1.4 树的存储存在的挑战 126
7.2 二叉树 128
7.2.1 二叉树的定义 128
7.2.2 二叉树的性质 129
7.2.3 二叉树的抽象数据类型 131
7.2.4 二叉树的存储结构 133
7.2.5 二叉树的简单运算实现 136
7.3 遍历二叉树 137
7.3.1 遍历二叉树的递归算法 138
7.3.2 遍历二叉树的非递归算法 140
7.3.3 遍历序列与二叉树的恢复 144
7.3.4 基于遍历的二叉树运算的实现和应用 147
7.4 线索二叉树 149
7.4.1 线索二叉树的定义 149
7.4.2 线索二叉树的构造方法 150
7.4.3 线索二叉树上的运算实现 151
7.5 树、森林与二叉树的转换 154
7.5.1 树的存储结构 154
7.5.2 森林和二叉树的转换 155
7.5.3 树和森林的遍历 156
7.6 哈夫曼树及其应用 157
7.6.1 相关概念 157
7.6.2 哈夫曼树的构造过程 159
7.6.3 哈夫曼编码 159
小结 161
习题 161
第8章 图 166
8.1 图的基本概念 166
8.1.1 图的定义 166
8.1.2 图的相关术语 167
8.1.3 图的抽象数据类型 169
8.2 图的存储结构 171
8.2.1 邻接矩阵表示法 171
8.2.2 邻接表表示法 172
8.2.3 邻接多重表表示法 173
8.3 图的遍历 174
8.3.1 定义及难点问题 174
8.3.2 深度优先搜索遍历 175
8.3.3 广度优先搜索遍历 176
8.3.4 图的遍历应用 177
8.4 无向连通图的最小代价生成树 179
8.4.1 K
uskal算法 179
8.4.2 P
im算法 182
8.4.3 Sollin算法 183
8.5 有向图的最短路径 184
8.5.1 单源最短路径——Dijkst
a算法 184
8.5.2 所有节点之间的最短路径——Floyd算法 188
8.6 AOV网络与拓扑排序 191
8.6.1 AOV网络的定义 191
8.6.2 拓扑序列和拓扑排序算法 192
8.7 AOE网络与关键路径 195
8.7.1 AOE网络的定义 195
8.7.2 关键路径和关键活动 196
8.7.3 关键路径算法 196
小结 199
习题 199
第9章 查找 204
9.1 顺序查找 204
9.1.1 顺序查找实例 204
9.1.2 顺序查找问题 205
9.2 二分查找 208
9.3 二叉查找树 211
9.3.1 二叉查找树的定义 211
9.3.2 二叉查找树的构建 212
9.3.3 平衡二叉树 216
小结 217
习题 217
第10章 排序 220
10.1 排序的基本概念 220
10.2 冒泡排序 221
10.2.1 冒泡排序的基本思想 221
10.2.2 冒泡排序的性能分析 224
10.3 快速排序 224
10.3.1 快速排序的基本思想 224
10.3.2 快速排序的基本过程 224
10.3.3 快速排序的性能分析 227
10.4 直接插入排序 227
10.5 希尔排序 229
10.5.1 希尔排序的基本思想 230
10.5.2 希尔排序的效率分析 231
10.6 选择排序 232
10.6.1 简单选择排序 232
10.6.2 树形选择排序 232
10.6.3 堆排序 233
小结 235
习题 235
参考文献 238
