数据结构——C++实现（第三版）
定价：￥63.00
作者： 沈俊
出版时间：2023-12
最新印次日期：2023-12
出版社：科学出版社
- 科学出版社
- 9787030773128
- 3版
- 553634
- 2023-12
- 计算机类
- 本科
内容简介
数据结构是计算机专业教学计划中的一门核心课程，也是信息管理、通信电子、自动控制等与计算机技术关系密切的专业的一门基础课程。从事与计算机科学与技术相关的工作，尤其是计算机应用领域的开发和研制工作，必须具备坚实的数据结构基础。本书对C++语言进行简单介绍，然后介绍线性表、栈、队列、数组、广义表、树、图等数据结构，并介绍查找和排序的方法。全书用C++语言描述并实现所有数据结构的类和程序，并附有习题，便于教学。
本书是高等院校数据结构课程的教材，可供计算机专业本科生使用，也可供从事计算机开发和应用的工程技术人员阅读、参考。
本书是高等院校数据结构课程的教材，可供计算机专业本科生使用，也可供从事计算机开发和应用的工程技术人员阅读、参考。
目录
第1章 绪论 1
1.1 程序的定义 1
1.2 数据结构的基本概念 1
1.2.1 数据结构实例 2
1.2.2 数据结构的定义 3
1.3 算法性能与复杂度 4
1.3.1 算法的定义 4
1.3.2 算法的性能标准 5
1.3.3 算法复杂度 6
习题1 9
第2章 C++程序设计语言简介 12
2.1 C++程序设计语言基础 12
2.1.1 程序结构 12
2.1.2 数据声明和作用域 13
2.1.3 输入
输出 15
2.1.4 函数 16
2.1.5 参数传递 16
2.1.6 函数名重载 17
2.1.7 动态内存分配 18
2.1.8 结构与联合 18
2.2 类与对象的基本概念 22
2.2.1 类与对象 22
2.2.2 消息与合作 24
2.2.3 多态性 24
2.3 面向对象的程序设计方法 24
2.4 C++类与对象 25
2.5 构造函数和析构函数 26
2.6 工具函数 29
2.7 继承 31
2.8 this指针的使用 34
2.9 虚函数、多态性以及动态联编 35
2.9.1 虚函数和多态性 35
2.9.2 动态联编 36
2.10 类模板 37
习题2 39
第3章 线性表 42
3.1 线性表的定义 42
3.2 线性表的顺序存储 43
3.2.1 顺序表类模板的定义 43
3.2.2 顺序表相关算法的复杂度分析 48
3.3 线性表的链式存储 49
3.3.1 单链表 49
3.3.2 双向循环链表 57
3.3.3 静态链表 64
3.4 线性表的应用 65
3.4.1 集合的表示和相关运算的实现 65
3.4.2 一元多项式表示和相关运算的实现 66
习题3 69
第4章 栈、队列和递归 72
4.1 栈 72
4.1.1 顺序栈 73
4.1.2 链式栈 76
4.1.3 栈的应用—— 表达式求值 79
4.2 队列 86
4.2.1 顺序队列 87
4.2.2 链式队列 91
4.2.3 队列的应用——车厢调度 94
4.3 递归 96
4.3.1 递归的概念 96
4.3.2 递归过程与递归工作栈 97
4.3.3 消除递归 98
习题4 102
第5章 字符串、数组和广义表 105
5.1 字符串 105
5.1.1 字符串的基本概念 105
5.1.2 常用的C++字符串函数 107
5.1.3 串类的定义及其实现 108
5.1.4 模式匹配 114
5.2 数组 118
5.2.1 数组的基本概念 118
5.2.2 数组的顺序存储结构 119
5.3 稀疏矩阵 121
5.3.1 非零元素的三元组定义 121
5.3.2 三元组顺序表 122
5.3.3 十字链表 125
5.4 广义表 130
5.4.1 广义表的定义 130
5.4.2 广义表的存储结构 131
5.4.3 n元多项式的表示 136
习题5 138
第6章 树和森林 141
6.1 树的概念 141
6.1.1 树的定义 141
6.1.2 树的术语 142
6.1.3 树的表示形式 143
6.1.4 树的基本操作 144
6.2 二叉树 144
6.2.1 二叉树的定义 144
6.2.2 二叉树的性质 145
6.2.3 二叉树的基本操作 146
6.3 二叉树的存储结构 147
6.3.1 顺序二叉树 147
6.3.2 二叉树的链表表示 148
6.3.3 二叉树的二叉链表类模板声明 149
6.4 遍历二叉树 153
6.4.1 先序遍历 154
6.4.2 中序遍历 154
6.4.3 后序遍历 155
6.4.4 层序遍历 156
6.5 线索二叉树 157
6.5.1 线索二叉树的定义 157
6.5.2 线索二叉树的类模板定义 159
6.6 二叉树的应用 165
6.6.1 堆 165
6.6.2 哈夫曼树 171
6.7 树和森林的实现 177
6.7.1 树的存储结构 177
6.7.2 树、森林和二叉树的转换 179
6.7.3 树的遍历 182
6.7.4 森林的遍历 182
6.8 等价类及其表示 183
6.8.1 等价关系与等价类 183
6.8.2 并查集 184
习题6 189
第7章 图 193
7.1 图的基本概念 193
7.1.1 图的定义 193
7.1.2 图的术语 194
7.1.3 图的基本操作 196
7.2 图的存储结构 196
7.2.1 邻接矩阵 197
7.2.2 邻接表 203
7.2.3 邻接多重表 212
7.2.4 十字链表 212
7.3 图的遍历与连通性 213
7.3.1 深度优先遍历 213
7.3.2 广度优先遍历 215
7.3.3 连通分量 217
7.4 最小生成树 217
7.4.1 克鲁斯卡尔算法 218
7.4.2 普里姆算法 221
7.5 最短路径 224
7.5.1 弧上权值为非负情形的单源点最短路径问题 224
7.5.2 弧上权值为任意值的单源点最短路径问题 227
7.5.3 所有顶点之间的最短路径 229
7.6 活动网络 231
7.6.1 用顶点表示活动的网络 231
7.6.2 用边表示活动的网络 235
习题7 239
第8章 查找 243
8.1 基本概念 243
8.2 顺序表 244
8.2.1 顺序表的查找 244
8.2.2 有序表的折半查找 245
8.2.3 有序表的其他查找 248
8.3 索引顺序表和倒排索引表 249
8.3.1 索引顺序表 249
8.3.2 倒排索引表 251
8.4 二叉排序树 253
8.4.1 二叉排序树定义 253
8.4.2 二叉排序树的查找 254
8.4.3 二叉排序树的插入 255
8.4.4 二叉排序树的删除 257
8.4.5 二叉排序树查找的性能分析 258
8.5 平衡二叉树 259
8.5.1 平衡二叉树的定义 259
8.5.2 平衡旋转 259
8.5.3 平衡二叉树中插入结点 261
8.5.4 平衡二叉树中删除结点 264
8.6
-树 266
8.6.1 动态的m路查找树 266
8.6.2
-树的定义 267
8.6.3
-树的插入 268
8.6.4
-树的删除 269
8.6.5
+树 271
8.7 散列表 273
8.7.1 散列表的基本概念 273
8.7.2 散列函数 274
8.7.3 处理冲突的闭散列方法——开地址方法 276
8.7.4 闭散列方法的实现 279
8.7.5 处理冲突的开散列方法——链地址法 282
8.7.6 散列表分析 283
习题8 284
第9章 排序 288
9.1 基础知识 288
9.2 交换排序 289
9.2.1 冒泡排序 289
9.2.2 快速排序 291
9.3 插入排序 293
9.3.1 直接插入排序 293
9.3.2 折半插入排序 296
9.3.3 希尔排序 297
9.4 选择排序 298
9.4.1 简单选择排序 298
9.4.2 锦标赛排序 301
9.4.3 堆排序 302
9.5 归并排序 305
9.5.1 归并 305
9.5.2 两路归并排序 306
9.5.3 递归的归并排序 307
9.6 基数排序 310
9.6.1 多关键字排序 310
9.6.2 链式基数排序 311
9.7 各种排序方法的选择和使用 313
习题9 314
参考文献 317
1.1 程序的定义 1
1.2 数据结构的基本概念 1
1.2.1 数据结构实例 2
1.2.2 数据结构的定义 3
1.3 算法性能与复杂度 4
1.3.1 算法的定义 4
1.3.2 算法的性能标准 5
1.3.3 算法复杂度 6
习题1 9
第2章 C++程序设计语言简介 12
2.1 C++程序设计语言基础 12
2.1.1 程序结构 12
2.1.2 数据声明和作用域 13
2.1.3 输入
输出 15
2.1.4 函数 16
2.1.5 参数传递 16
2.1.6 函数名重载 17
2.1.7 动态内存分配 18
2.1.8 结构与联合 18
2.2 类与对象的基本概念 22
2.2.1 类与对象 22
2.2.2 消息与合作 24
2.2.3 多态性 24
2.3 面向对象的程序设计方法 24
2.4 C++类与对象 25
2.5 构造函数和析构函数 26
2.6 工具函数 29
2.7 继承 31
2.8 this指针的使用 34
2.9 虚函数、多态性以及动态联编 35
2.9.1 虚函数和多态性 35
2.9.2 动态联编 36
2.10 类模板 37
习题2 39
第3章 线性表 42
3.1 线性表的定义 42
3.2 线性表的顺序存储 43
3.2.1 顺序表类模板的定义 43
3.2.2 顺序表相关算法的复杂度分析 48
3.3 线性表的链式存储 49
3.3.1 单链表 49
3.3.2 双向循环链表 57
3.3.3 静态链表 64
3.4 线性表的应用 65
3.4.1 集合的表示和相关运算的实现 65
3.4.2 一元多项式表示和相关运算的实现 66
习题3 69
第4章 栈、队列和递归 72
4.1 栈 72
4.1.1 顺序栈 73
4.1.2 链式栈 76
4.1.3 栈的应用—— 表达式求值 79
4.2 队列 86
4.2.1 顺序队列 87
4.2.2 链式队列 91
4.2.3 队列的应用——车厢调度 94
4.3 递归 96
4.3.1 递归的概念 96
4.3.2 递归过程与递归工作栈 97
4.3.3 消除递归 98
习题4 102
第5章 字符串、数组和广义表 105
5.1 字符串 105
5.1.1 字符串的基本概念 105
5.1.2 常用的C++字符串函数 107
5.1.3 串类的定义及其实现 108
5.1.4 模式匹配 114
5.2 数组 118
5.2.1 数组的基本概念 118
5.2.2 数组的顺序存储结构 119
5.3 稀疏矩阵 121
5.3.1 非零元素的三元组定义 121
5.3.2 三元组顺序表 122
5.3.3 十字链表 125
5.4 广义表 130
5.4.1 广义表的定义 130
5.4.2 广义表的存储结构 131
5.4.3 n元多项式的表示 136
习题5 138
第6章 树和森林 141
6.1 树的概念 141
6.1.1 树的定义 141
6.1.2 树的术语 142
6.1.3 树的表示形式 143
6.1.4 树的基本操作 144
6.2 二叉树 144
6.2.1 二叉树的定义 144
6.2.2 二叉树的性质 145
6.2.3 二叉树的基本操作 146
6.3 二叉树的存储结构 147
6.3.1 顺序二叉树 147
6.3.2 二叉树的链表表示 148
6.3.3 二叉树的二叉链表类模板声明 149
6.4 遍历二叉树 153
6.4.1 先序遍历 154
6.4.2 中序遍历 154
6.4.3 后序遍历 155
6.4.4 层序遍历 156
6.5 线索二叉树 157
6.5.1 线索二叉树的定义 157
6.5.2 线索二叉树的类模板定义 159
6.6 二叉树的应用 165
6.6.1 堆 165
6.6.2 哈夫曼树 171
6.7 树和森林的实现 177
6.7.1 树的存储结构 177
6.7.2 树、森林和二叉树的转换 179
6.7.3 树的遍历 182
6.7.4 森林的遍历 182
6.8 等价类及其表示 183
6.8.1 等价关系与等价类 183
6.8.2 并查集 184
习题6 189
第7章 图 193
7.1 图的基本概念 193
7.1.1 图的定义 193
7.1.2 图的术语 194
7.1.3 图的基本操作 196
7.2 图的存储结构 196
7.2.1 邻接矩阵 197
7.2.2 邻接表 203
7.2.3 邻接多重表 212
7.2.4 十字链表 212
7.3 图的遍历与连通性 213
7.3.1 深度优先遍历 213
7.3.2 广度优先遍历 215
7.3.3 连通分量 217
7.4 最小生成树 217
7.4.1 克鲁斯卡尔算法 218
7.4.2 普里姆算法 221
7.5 最短路径 224
7.5.1 弧上权值为非负情形的单源点最短路径问题 224
7.5.2 弧上权值为任意值的单源点最短路径问题 227
7.5.3 所有顶点之间的最短路径 229
7.6 活动网络 231
7.6.1 用顶点表示活动的网络 231
7.6.2 用边表示活动的网络 235
习题7 239
第8章 查找 243
8.1 基本概念 243
8.2 顺序表 244
8.2.1 顺序表的查找 244
8.2.2 有序表的折半查找 245
8.2.3 有序表的其他查找 248
8.3 索引顺序表和倒排索引表 249
8.3.1 索引顺序表 249
8.3.2 倒排索引表 251
8.4 二叉排序树 253
8.4.1 二叉排序树定义 253
8.4.2 二叉排序树的查找 254
8.4.3 二叉排序树的插入 255
8.4.4 二叉排序树的删除 257
8.4.5 二叉排序树查找的性能分析 258
8.5 平衡二叉树 259
8.5.1 平衡二叉树的定义 259
8.5.2 平衡旋转 259
8.5.3 平衡二叉树中插入结点 261
8.5.4 平衡二叉树中删除结点 264
8.6
-树 266
8.6.1 动态的m路查找树 266
8.6.2
-树的定义 267
8.6.3
-树的插入 268
8.6.4
-树的删除 269
8.6.5
+树 271
8.7 散列表 273
8.7.1 散列表的基本概念 273
8.7.2 散列函数 274
8.7.3 处理冲突的闭散列方法——开地址方法 276
8.7.4 闭散列方法的实现 279
8.7.5 处理冲突的开散列方法——链地址法 282
8.7.6 散列表分析 283
习题8 284
第9章 排序 288
9.1 基础知识 288
9.2 交换排序 289
9.2.1 冒泡排序 289
9.2.2 快速排序 291
9.3 插入排序 293
9.3.1 直接插入排序 293
9.3.2 折半插入排序 296
9.3.3 希尔排序 297
9.4 选择排序 298
9.4.1 简单选择排序 298
9.4.2 锦标赛排序 301
9.4.3 堆排序 302
9.5 归并排序 305
9.5.1 归并 305
9.5.2 两路归并排序 306
9.5.3 递归的归并排序 307
9.6 基数排序 310
9.6.1 多关键字排序 310
9.6.2 链式基数排序 311
9.7 各种排序方法的选择和使用 313
习题9 314
参考文献 317
