数据结构与算法基础 / “十四五”高等学校新工科计算机类专业系列教材
¥59.00定价
作者: 徐孝凯
出版时间:2023-09
出版社:中国铁道出版社
- 中国铁道出版社
- 9787113303754
- 1版
- 502203
- 48256823-5
- 16开
- 2023-09
- 计算机及相关专业
- 本科
作者简介
内容简介
本书是一部针对高等学校新工科计算机类专业的实用性教材,采用易于学习和使用的C语言来描述算法,并加以详细注释,重点知识配备了二维码视频讲解,可读性好、实用性强。对于不熟悉C语言而熟悉其他任何一种计算机语言的学习者来说,只要掌握了本书中详细介绍的数据结构及其运算方法,一样能够编写出相应语言的算法描述和上机程序。本书共分为10章,主要包括集合、线性表、栈和队列、树和二叉树、二叉树应用、图、图的应用、查找以及排序等内容。
本书适合作为普通高校计算机及相关专业“数据结构”课程的教材,也可供相关证书考试、考研或从事计算机应用与工程工作的科技工作者参考。
本书适合作为普通高校计算机及相关专业“数据结构”课程的教材,也可供相关证书考试、考研或从事计算机应用与工程工作的科技工作者参考。
目录
1.1数据结构的有关概念 2
1.2算法描述 10
1.3算法评价 11
思考与练习 17
第2章集合 22
2.1集合的定义和抽象数据类型 23
2.2集合的顺序存储结构和操作实现 24
2.2.1集合的顺序存储结构和存储类型定义 24
2.2.2集合运算在顺序存储结构下的操作实现 25
2.2.3对顺序集合进行各种运算的程序示例 29
2.3集合的链式存储结构和操作实现 30
2.3.1链式存储集合的有关概念 30
2.3.2集合运算在链式存储结构下的操作实现 32
2.3.3对链式存储集合进行各种运算的程序示例 36
思考与练习 38
第3章线性表 42
3.1线性表的定义和抽象数据类型 43
3.2线性表的顺序存储结构和操作实现 44
3.3链式存储数据的概念和方法 51
3.4线性表的每种运算在单链表上的操作实现 55
思考与练习 61
第4章栈和队列 65
4.1栈的定义和抽象数据类型 66
4.2栈的顺序存储结构和操作实现 67
4.3栈的链式存储结构和操作实现 70
4.4栈的简单应用举例 72
4.5队列 76
4.5.1队列的定义和抽象数据类型 76
4.5.2队列的顺序存储结构和操作实现 77
4.5.3队列的链式存储结构和操作实现 80
4.5.4队列的应用简介 83
4.6算术表达式的计算 84
4.6.1算术表达式的两种表示 84
4.6.2后缀表达式求值的算法 85
4.6.3把中缀表达式转换为后缀表达式的算法 87
4.7栈与递归 90
4.7.1阶乘求解的递归算法 91
4.7.2求解迷宫问题的递归算法 92
4.7.3求解汉诺塔问题的递归算法 96
思考与练习 98
第5章树和二叉树 103
5.1树的概念 104
5.1.1树的定义 104
5.1.2树的表示 105
5.1.3树的基本术语 106
5.1.4树的性质 107
5.2二叉树 108
5.2.1二叉树的定义 108
5.2.2二叉树的性质 108
5.2.3二叉树的抽象数据类型 110
5.2.4二叉树的存储结构 110
5.3二叉树遍历 113
5.4二叉树其他运算 115
5.5树的存储结构和运算 122
5.5.1树的抽象数据类型 122
5.5.2树的存储结构 122
5.5.3树的运算 123
思考与练习 129
第6章二叉树应用 134
6.1二叉搜索树 135
6.1.1二叉搜索树的定义 135
6.1.2二叉搜索树的抽象数据类型 135
6.1.3二叉搜索树的运算 136
6.1.4二叉搜索树运算的应用程序示例 140
6.2堆 142
6.2.1堆的定义 142
6.2.2堆的抽象数据类型 143
6.2.3堆的存储结构 143
6.2.4堆的运算 144
6.2.5堆运算的应用程序示例 147
6.3哈夫曼树 148
6.3.1基本术语 148
6.3.2构造哈夫曼树 149
6.3.3哈夫曼编码 151
思考与练习 154
第7章图 157
7.1图的概念 158
7.1.1图的定义 158
7.1.2图的基本术语 159
7.1.3图的抽象数据类型 161
7.2图的存储结构 161
7.2.1邻接矩阵 162
7.2.2邻接表 164
7.2.3边集数组 166
7.3图的遍历 168
7.3.1深度优先搜索遍历 168
7.3.2广度优先搜索遍历 171
7.3.3非连通图的遍历 174
7.3.4图的遍历算法的上机调试 174
7.4图的其他运算 177
思考与练习 189
第8章图的应用 192
8.1图的生成树和最小生成树 193
8.1.1生成树和最小生成树的概念 193
8.1.2普里姆算法 194
8.1.3克鲁斯卡尔算法 198
8.2最短路径 201
8.2.1最短路径的概念 201
8.2.2从图中一顶点到其余各顶点的最短路径 202
8.2.3图中每对顶点之间的最短路径 207
8.3拓扑排序 211
8.3.1拓扑排序的概念 211
8.3.2拓扑排序算法 212
8.4关键路径 216
思考与练习 222
第9章查找 226
9.1查找的概念 227
9.2顺序表查找 228
9.2.1顺序查找 228
9.2.2二分查找 229
9.3索引查找 233
9.3.1索引的概念 233
9.3.2索引查找算法 236
9.3.3分块查找 238
9.4散列查找 240
9.4.1散列的概念 240
9.4.2散列函数 241
9.4.3处理冲突的方法 243
9.4.4散列表的运算 246
9.5B树查找 252
9.5.1B树定义 252
9.5.2在B树上查找元素的过程 254
9.5.3在B树上插入元素的过程 255
9.5.4在B树上删除元素的过程 257
思考与练习 258
第10章排序 262
10.1排序的基本概念 263
10.2插入排序 264
10.2.1直接插入排序 264
10.2.2希尔排序 265
10.3选择排序 266
10.3.1直接选择排序 266
10.3.2堆排序 267
10.4交换排序 271
10.4.1气泡排序 271
10.4.2快速排序 272
10.5归并排序 276
10.6各种内排序方法的比较 281
10.7外排序 282
10.7.1外排序的有关概念 282
10.7.2外排序算法 284
10.7.3外排序应用程序运行示例 287
思考与练习 290
1.2算法描述 10
1.3算法评价 11
思考与练习 17
第2章集合 22
2.1集合的定义和抽象数据类型 23
2.2集合的顺序存储结构和操作实现 24
2.2.1集合的顺序存储结构和存储类型定义 24
2.2.2集合运算在顺序存储结构下的操作实现 25
2.2.3对顺序集合进行各种运算的程序示例 29
2.3集合的链式存储结构和操作实现 30
2.3.1链式存储集合的有关概念 30
2.3.2集合运算在链式存储结构下的操作实现 32
2.3.3对链式存储集合进行各种运算的程序示例 36
思考与练习 38
第3章线性表 42
3.1线性表的定义和抽象数据类型 43
3.2线性表的顺序存储结构和操作实现 44
3.3链式存储数据的概念和方法 51
3.4线性表的每种运算在单链表上的操作实现 55
思考与练习 61
第4章栈和队列 65
4.1栈的定义和抽象数据类型 66
4.2栈的顺序存储结构和操作实现 67
4.3栈的链式存储结构和操作实现 70
4.4栈的简单应用举例 72
4.5队列 76
4.5.1队列的定义和抽象数据类型 76
4.5.2队列的顺序存储结构和操作实现 77
4.5.3队列的链式存储结构和操作实现 80
4.5.4队列的应用简介 83
4.6算术表达式的计算 84
4.6.1算术表达式的两种表示 84
4.6.2后缀表达式求值的算法 85
4.6.3把中缀表达式转换为后缀表达式的算法 87
4.7栈与递归 90
4.7.1阶乘求解的递归算法 91
4.7.2求解迷宫问题的递归算法 92
4.7.3求解汉诺塔问题的递归算法 96
思考与练习 98
第5章树和二叉树 103
5.1树的概念 104
5.1.1树的定义 104
5.1.2树的表示 105
5.1.3树的基本术语 106
5.1.4树的性质 107
5.2二叉树 108
5.2.1二叉树的定义 108
5.2.2二叉树的性质 108
5.2.3二叉树的抽象数据类型 110
5.2.4二叉树的存储结构 110
5.3二叉树遍历 113
5.4二叉树其他运算 115
5.5树的存储结构和运算 122
5.5.1树的抽象数据类型 122
5.5.2树的存储结构 122
5.5.3树的运算 123
思考与练习 129
第6章二叉树应用 134
6.1二叉搜索树 135
6.1.1二叉搜索树的定义 135
6.1.2二叉搜索树的抽象数据类型 135
6.1.3二叉搜索树的运算 136
6.1.4二叉搜索树运算的应用程序示例 140
6.2堆 142
6.2.1堆的定义 142
6.2.2堆的抽象数据类型 143
6.2.3堆的存储结构 143
6.2.4堆的运算 144
6.2.5堆运算的应用程序示例 147
6.3哈夫曼树 148
6.3.1基本术语 148
6.3.2构造哈夫曼树 149
6.3.3哈夫曼编码 151
思考与练习 154
第7章图 157
7.1图的概念 158
7.1.1图的定义 158
7.1.2图的基本术语 159
7.1.3图的抽象数据类型 161
7.2图的存储结构 161
7.2.1邻接矩阵 162
7.2.2邻接表 164
7.2.3边集数组 166
7.3图的遍历 168
7.3.1深度优先搜索遍历 168
7.3.2广度优先搜索遍历 171
7.3.3非连通图的遍历 174
7.3.4图的遍历算法的上机调试 174
7.4图的其他运算 177
思考与练习 189
第8章图的应用 192
8.1图的生成树和最小生成树 193
8.1.1生成树和最小生成树的概念 193
8.1.2普里姆算法 194
8.1.3克鲁斯卡尔算法 198
8.2最短路径 201
8.2.1最短路径的概念 201
8.2.2从图中一顶点到其余各顶点的最短路径 202
8.2.3图中每对顶点之间的最短路径 207
8.3拓扑排序 211
8.3.1拓扑排序的概念 211
8.3.2拓扑排序算法 212
8.4关键路径 216
思考与练习 222
第9章查找 226
9.1查找的概念 227
9.2顺序表查找 228
9.2.1顺序查找 228
9.2.2二分查找 229
9.3索引查找 233
9.3.1索引的概念 233
9.3.2索引查找算法 236
9.3.3分块查找 238
9.4散列查找 240
9.4.1散列的概念 240
9.4.2散列函数 241
9.4.3处理冲突的方法 243
9.4.4散列表的运算 246
9.5B树查找 252
9.5.1B树定义 252
9.5.2在B树上查找元素的过程 254
9.5.3在B树上插入元素的过程 255
9.5.4在B树上删除元素的过程 257
思考与练习 258
第10章排序 262
10.1排序的基本概念 263
10.2插入排序 264
10.2.1直接插入排序 264
10.2.2希尔排序 265
10.3选择排序 266
10.3.1直接选择排序 266
10.3.2堆排序 267
10.4交换排序 271
10.4.1气泡排序 271
10.4.2快速排序 272
10.5归并排序 276
10.6各种内排序方法的比较 281
10.7外排序 282
10.7.1外排序的有关概念 282
10.7.2外排序算法 284
10.7.3外排序应用程序运行示例 287
思考与练习 290