图书简介

本书在主要介绍数据的逻辑结构、数据的存储结构、数据的运算等基本知识的基础上,从抽象数据类型的角度,讨论各种基本类型的数据结构及相关应用。
全书共分5篇: 第1篇(第1章)为绪论篇,着重介绍数据结构的相关概念和算法的基础知识;第2篇(第2~5章)为线性结构篇,着重讨论线性结构的概念和基本运算的算法实现,介绍了一般的线性结构和特殊的线性结构在不同存储结构之下的基本操作和应用; 第3篇(第6章)为树形结构篇,着重介绍基本的树形结构——二叉树在不同存储结构之下如何实现基本操作和应用; 第4篇(第7章)为图形结构篇,介绍图形结构在不同存储结构之下的基本操作和应用; 第5篇(第8~10章)为数据运算篇,首先介绍数据的查找和排序基本运算的算法实现,接着介绍常见的查找和排序方法,分析并对比它们的算法效率,最后介绍数据结构的基础知识在程序设计竞赛中的应用。全书提供了大量应用实例,每种算法都采用C/C++语言进行描述,帮助读者理解基础理论。

(展开)

编辑推荐

本书叙述清楚,便于教学和读者自学,适合作为高等院校计算机专业及信息相关专业的教材,也可作为计算机应用技术人员的参考书。

(展开)

目录

第1篇 绪 论 篇
第1章 绪论…………………………………………………………………………………… 3
1.1 什么是数据结构…………………………………………………………………… 3
1.1.1 数据结构的产生与发展…………………………………………………… 3
1.1.2 数据结构的基本概念……………………………………………………… 3
1.1.3 逻辑结构的种类…………………………………………………………… 5
1.1.4 数据的存储结构…………………………………………………………… 7
1.2 抽象数据…………………………………………………………………………… 10
1.2.1 数据类型………………………………………………………………… 10
1.2.2 抽象数据类型的表示与实现…………………………………………… 12
1.3 算法及其性能分析………………………………………………………………… 14
1.3.1 算法……………………………………………………………………… 14
1.3.2 算法设计的目标………………………………………………………… 14
1.3.3 算法的时间复杂度度量………………………………………………… 16
1.3.4 算法的空间复杂度度量………………………………………………… 21
1.4 STL概述………………………………………………………………………… 22
1.4.1 STL的发展和特点……………………………………………………… 22
1.4.2 C++标准库和STL ……………………………………………………… 22
1.4.3 数据结构和STL的关系………………………………………………… 23
1.5 综合案例…………………………………………………………………………… 24
1.5.1 哥德巴赫猜想问题……………………………………………………… 24
1.5.2 连续整数问题…………………………………………………………… 26
本章小结………………………………………………………………………………… 26
第2篇 线性结构篇
第2章 线性表……………………………………………………………………………… 29
2.1 线性表的抽象数据类型…………………………………………………………… 29
2.1.1 线性表的定义…………………………………………………………… 29
2.1.2 线性表的抽象数据类型描述…………………………………………… 30
2.2 线性表的顺序存储结构…………………………………………………………… 33
2.2.1 线性表的顺序存储结构———顺序表…………………………………… 33
2.2.2 顺序表基本运算的实现………………………………………………… 35
2.3 线性表的链式存储结构…………………………………………………………… 43
2.3.1 线性表的链式存储结构———链表……………………………………… 43
2.3.2 单链表基本运算的实现………………………………………………… 46
2.3.3 双链表…………………………………………………………………… 54
2.3.4 循环链表………………………………………………………………… 58
2.3.5 STL与链表……………………………………………………………… 60
2.4 综合案例…………………………………………………………………………… 66
2.4.1 一元多项式的表示及相加运算………………………………………… 66
2.4.2 魔法师发牌问题………………………………………………………… 67
2.4.3 约瑟夫问题……………………………………………………………… 68
本章小结………………………………………………………………………………… 69
第3章 栈与队列…………………………………………………………………………… 70
3.1 栈…………………………………………………………………………………… 70
3.1.1 栈的概述………………………………………………………………… 70
3.1.2 栈的顺序存储结构……………………………………………………… 71
3.1.3 栈的链式存储结构……………………………………………………… 75
3.2 栈综合案例………………………………………………………………………… 77
3.2.1 进制转换………………………………………………………………… 77
3.2.2 表达式求值……………………………………………………………… 79
3.2.3 检验表达式中的括号匹配情况………………………………………… 81
3.2.4 栈与递归问题…………………………………………………………… 82
3.3 队列………………………………………………………………………………… 85
3.3.1 队列的定义和抽象数据类型…………………………………………… 85
3.3.2 队列的顺序存储………………………………………………………… 86
3.3.3 队列的链式存储………………………………………………………… 91
3.3.4 优先级队列……………………………………………………………… 94
3.4 STL中的栈与队列……………………………………………………………… 96
3.4.1 STL中的栈……………………………………………………………… 96
3.4.2 STL中的队列…………………………………………………………… 97
3.4.3 STL中的优先队列的使用方法………………………………………… 98
3.5 队列综合案例……………………………………………………………………… 99
3.5.1 打印杨辉三角形………………………………………………………… 99
3.5.2 报数问题………………………………………………………………… 102
3.5.3 舞伴问题………………………………………………………………… 103
本章小结………………………………………………………………………………… 104
第4章 串…………………………………………………………………………………… 106
4.1 串的基本概念和抽象数据类型………………………………………………… 106
4.1.1 串的基本概念…………………………………………………………… 106
4.1.2 串的抽象数据类型……………………………………………………… 107
4.2 串的存储结构…………………………………………………………………… 108
4.2.1 串的顺序存储结构———顺序串………………………………………… 108
4.2.2 串的链式存储结构———链串…………………………………………… 113
4.3 串的模式匹配…………………………………………………………………… 116
4.3.1 串的古典匹配算法……………………………………………………… 116
4.3.2 串的KMP算法………………………………………………………… 119
4.4 综合案例………………………………………………………………………… 124
4.4.1 文本编辑………………………………………………………………… 124
4.4.2 建立词索引表…………………………………………………………… 125
本章小结………………………………………………………………………………… 128
第5章 数组和广义表……………………………………………………………………… 129
5.1 数组的定义及抽象数据类型…………………………………………………… 129
5.1.1 数组的定义……………………………………………………………… 129
5.1.2 数组的抽象数据类型…………………………………………………… 129
5.2 数组的顺序存储与寻址………………………………………………………… 130
5.2.1 以行序为主序…………………………………………………………… 131
5.2.2 以列序为主序…………………………………………………………… 132
5.3 特殊矩阵及其压缩存储………………………………………………………… 133
5.3.1 对称矩阵………………………………………………………………… 133
5.3.2 下(上)三角矩阵………………………………………………………… 134
5.3.3 对角矩阵………………………………………………………………… 135
5.4 稀疏矩阵………………………………………………………………………… 136
5.4.1 稀疏矩阵的三元组表示………………………………………………… 136
5.4.2 稀疏矩阵的十字链表表示……………………………………………… 141
5.5 广义表…………………………………………………………………………… 145
5.5.1 广义表的定义…………………………………………………………… 145
5.5.2 广义表的存储结构……………………………………………………… 146
5.5.3 广义表的运算…………………………………………………………… 148
5.6 综合案例………………………………………………………………………… 151
5.6.1 大整数相乘……………………………………………………………… 151
5.6.2 荷兰国旗问题…………………………………………………………… 153
本章小结………………………………………………………………………………… 154
第3篇 树形结构篇
第6章 树和二叉树………………………………………………………………………… 157
6.1 树………………………………………………………………………………… 157
6.1.1 树的定义………………………………………………………………… 157
6.1.2 树的术语………………………………………………………………… 158
6.1.3 树的基本性质…………………………………………………………… 159
6.1.4 树的抽象数据类型……………………………………………………… 160
6.2 二叉树…………………………………………………………………………… 160
6.2.1 二叉树的定义…………………………………………………………… 160
6.2.2 二叉树的性质…………………………………………………………… 162
6.2.3 二叉树的抽象数据类型………………………………………………… 163
6.2.4 二叉树的存储结构……………………………………………………… 164
6.3 二叉树的基本操作……………………………………………………………… 166
6.3.1 中序遍历………………………………………………………………… 166
6.3.2 先序遍历………………………………………………………………… 166
6.3.3 后序遍历………………………………………………………………… 167
6.3.4 层次遍历………………………………………………………………… 167
6.3.5 二叉树遍历的应用……………………………………………………… 170
6.3.6 二叉树遍历的非递归实现……………………………………………… 173
6.4 线索二叉树……………………………………………………………………… 181
6.4.1 线索二叉树的概念……………………………………………………… 181
6.4.2 线索化二叉树…………………………………………………………… 183
6.4.3 遍历线索二叉树………………………………………………………… 184
6.5 树与森林………………………………………………………………………… 185
6.5.1 树的存储结构…………………………………………………………… 185
6.5.2 森林与二叉树的转换…………………………………………………… 188
6.5.3 树的遍历与森林的遍历………………………………………………… 191
6.6 哈夫曼树及其应用……………………………………………………………… 192
6.6.1 哈夫曼树的基本概念…………………………………………………… 192
6.6.2 哈夫曼树构造算法……………………………………………………… 192
6.6.3 哈夫曼编码……………………………………………………………… 194
6.7 STL中实现树结构……………………………………………………………… 197
6.7.1 STL中的vector ……………………………………………………… 197
6.7.2 STL中的map ………………………………………………………… 200
6.8 综合案例———学校建模问题…………………………………………………… 203
本章小结………………………………………………………………………………… 207
第4篇 图形结构篇
第7章 图…………………………………………………………………………………… 211
7.1 图的概念………………………………………………………………………… 211
7.1.1 图的定义和术语………………………………………………………… 211
7.1.2 图的抽象数据类型……………………………………………………… 216
7.2 图的存储表示…………………………………………………………………… 216
7.2.1 邻接矩阵………………………………………………………………… 217
7.2.2 邻接表…………………………………………………………………… 218
7.2.3 十字链表………………………………………………………………… 219
7.3 图的遍历与连通性……………………………………………………………… 222
7.3.1 深度优先遍历…………………………………………………………… 222
7.3.2 广度优先遍历…………………………………………………………… 223
7.3.3 连通分量………………………………………………………………… 226
7.4 最小生成树……………………………………………………………………… 230
7.4.1 普里姆算法……………………………………………………………… 230
7.4.2 克鲁斯卡尔算法………………………………………………………… 233
7.5 最短路径………………………………………………………………………… 238
7.5.1 单源最短路径…………………………………………………………… 239
7.5.2 全源最短路径…………………………………………………………… 244
7.6 活动网络………………………………………………………………………… 248
7.6.1 用顶点表示活动的AOV网络………………………………………… 248
7.6.2 AOE图与关键路径…………………………………………………… 250
7.7 综合案例………………………………………………………………………… 253
7.7.1 道路修建问题…………………………………………………………… 253
7.7.2 回家路线问题…………………………………………………………… 255
7.7.3 棍子还原问题…………………………………………………………… 257
本章小结………………………………………………………………………………… 259
第5篇 数据运算篇
第8章 查找………………………………………………………………………………… 263
8.1 查找的基本概念………………………………………………………………… 263
8.2 静态表的查找…………………………………………………………………… 264
8.2.1 顺序查找………………………………………………………………… 264
8.2.2 折半查找………………………………………………………………… 265
8.2.3 斐波那契查找…………………………………………………………… 268
8.2.4 分块查找………………………………………………………………… 269
8.3 动态查找表……………………………………………………………………… 270
8.3.1 二叉排序树……………………………………………………………… 270
8.3.2 平衡二叉树……………………………………………………………… 278
8.3.3 B-树…………………………………………………………………… 284
8.3.4 B+树…………………………………………………………………… 290
8.4 哈希表查找……………………………………………………………………… 291
8.4.1 哈希表的基本概念……………………………………………………… 291
8.4.2 哈希函数构造方法……………………………………………………… 292
8.4.3 哈希冲突解决方法……………………………………………………… 293
8.4.4 哈希表上的查找分析…………………………………………………… 296
8.5 STL中的查找…………………………………………………………………… 301
8.6 综合案例———拼写检查问题…………………………………………………… 302
本章小结………………………………………………………………………………… 304
第9章 排序………………………………………………………………………………… 305
9.1 排序的基本概念………………………………………………………………… 305
9.2 插入排序………………………………………………………………………… 306
9.2.1 直接插入排序…………………………………………………………… 306
9.2.2 希尔排序………………………………………………………………… 308
9.3 交换排序………………………………………………………………………… 310
9.3.1 冒泡排序………………………………………………………………… 311
9.3.2 快速排序………………………………………………………………… 312
9.4 选择排序………………………………………………………………………… 315
9.4.1 简单选择排序…………………………………………………………… 315
9.4.2 锦标赛排序……………………………………………………………… 317
9.4.3 堆排序…………………………………………………………………… 318
9.5 二路归并排序…………………………………………………………………… 322
9.6 基数排序………………………………………………………………………… 325
9.7 内部排序方法的比较…………………………………………………………… 328
9.8 STL中的排序…………………………………………………………………… 329
9.9 综合案例———比赛排名问题…………………………………………………… 330
本章小结………………………………………………………………………………… 332
第10章 ACM 经典案例…………………………………………………………………… 333
10.1 递归算法……………………………………………………………………… 333
10.1.1 三柱汉诺塔问题…………………………………………………… 333
10.1.2 传染病问题………………………………………………………… 335
10.1.3 N皇后问题………………………………………………………… 337
10.2 DFS与BFS问题……………………………………………………………… 34
10.2.1 DFS之迷宫难题…………………………………………………… 345
10.2.2 BFS之管道和指针游戏…………………………………………… 349
本章小结……………………………………………………………………………… 353
附录A 全国计算机专业数据结构考研大纲……………………………………………… 354
参考文献……………………………………………………………………………………… 357
(展开)

书页展示

更多图书信息

作者:薛晓亚、周丽平、马金霞、陈延波
出版:清华大学出版社

ISBN:9787302510895

出版日期:2019-07-01

清华大学出版社

清华大学出版社成立于1980年6月,是由教育部主管、清华大学主办的综合出版单位。植根于“清华”这座久负盛名的高等学府,秉承清华人“自强不息,厚德载物”的人文精神,清华大学出版社在短短二十多年的时间里,迅速成长起来。作为来自一流大学的出版单位,清华大学出版社始终坚持弘扬科技文化产业、服务科教兴国战略的出版方向,把出版高等学校教学用书和科技图书作为主要任务,并为促进学术交流、繁荣出版事业设立了多项出版基金,逐渐形成了以出版高水平的教材和学术专著为主的鲜明特色,在教育出版领域树立了强势品牌。目前,清华版教材已在全国一百多所院校得到广泛使用。高品质、多层次的计算机图书是清华大学出版社的一大品牌支柱。20世纪80年代末,在席卷全球的信息化浪潮中,清华大学出版社快速切入计算机图书市场,逐渐成为并一直保持这一市场的领先地位,为发展中国计算机教育做出了巨大贡献。

(展开)
Copyright ©2019  文泉书局  |  京ICP证151049号   |  关于我们   |  联系我们   |  版权声明