在编写计算机程序解决实际问题之前,应该首先建立针对该问题的逻辑模型,包括相关数据的组织结构和处理算法,本书就是针对如何有效地组织数据以及如何设计处理算法而编写的。本书采用通俗易懂的语言,结合大量图示和实例,帮助读者理解和掌握数据结构相关的基本概念、基础知识和主要算法。第2章、第5章和第6章还针对最典型的线性结构、树结构和图结构给出了综合性较强的应用案例,以帮助读者综合运用所学知识解决实际问题。本书用C和Java两种程序设计语言来描述相关的存储结构和处理算法,使学生能够掌握数据结构的面向过程和面向对象程序设计方法。本书适合作为高等院校计算机类专业“数据结构”课程的教材,也适合作为相关领域工作人员的参考图书。
数据结构在计算机科学中具有基础性地位,是高等院校计算机类专业及其他相关专业必修的专业核心基础课程,在进行程序设计之前,首先要利用数据结构知识进行数据的逻辑结构、存储结构及处理算法的设计。本书主要介绍集合、线性结构、树形结构、图形结构、查找和排序等相关理论,帮助读者理解和掌握数据结构与算法的分析设计方法。本书用C和Java两种语言来描述相关的存储结构与算法,帮助读者掌握数据结构的面向过程和面向对象程序设计方法。本书包含以下理论、技术与应用:?线性表;?栈和队列;?串、数组和广义表;?树;?图;?查找;?排序。教学资源?微课视频?教学课件?教学大纲?思政元素?习题解答?算法代码?综合案例?示例插图说明:微课视频在书中扫码即可观看,其他资源可扫描上方二维码获取,也可以到清华大学出版社网站本书页面(或“电子信息教材事业部”微信公众号)下载。
前言
“数据结构”是高等院校计算机类专业及其他相关专业的一门必修的专业核心基础课程,主要讲解数据的各种逻辑结构和存储结构,以及对每种结构的处理算法,使学生能够使用数据结构和算法的基本分析和设计方法,提高学生分析和解决实际问题的能力,也为学生学习后续专业课程奠定基础。
本书内容涉及集合、线性结构、树结构和图结构4种逻辑结构,以及查找和排序方法,学习内容较多,对初学者也有较高的难度。在学习“数据结构”这门课程时,应牢固掌握有关的基本概念、基础知识和主要算法,深刻理解数据组织和处理的思想方法,学会针对具体问题建立有效的逻辑模型,培养分析和解决实际问题的能力。在学习过程中,对于每个具体内容,都要深入思考“3W”,即What(是什么)、How(怎么做)和Why(为什么),切记不要死记硬背,要学会将狭义问题广义化,复杂问题简单化,不同问题统一化,形象问题抽象化,灵活运用,举一反三。
全书共8章,第1章讲解数据结构、算法和算法分析的基本概念,第2章讲解线性表的逻辑结构、存储结构和处理算法,第3章讲解栈和队列这两种特殊的线性结构,第4章讲解串、数组和广义表的基本概念和基础知识,第5章讲解二叉树、树和森林的逻辑结构、存储结构和处理算法,第6章讲解图的逻辑结构、存储结构和处理算法,第7章讲解查找表的组织方式以及查找算法,第8章讲解常用的排序算法。每章之后都有习题,其中,第2章和第5章还借应用案例讲解了集合的线性结构和树结构的实现方法。
本书用通俗易懂的语言,结合大量图示和实例来讲解数据结构的基本概念、基础知识和处理算法,帮助读者理解和掌握相关内容,其中,在第2章、第5章和第6章还给出了应用案例; 注重讲解数据结构和算法的分析设计方法,使读者能够理解数据结构和算法为什么如此设计。本书算法比较全面,并且用C和Java两种程序设计语言来描述相关的存储结构和处理算法,这两种语言正是面向过程程序设计语言和面向对象程序设计语言的典型代表,使读者能够掌握数据结构的面向过程和面向对象程序设计方法。
本书由费如纯、刘丽华和胡楠主编,赵杨川、王彦明和吴吉红副主编。本书第6章由费如纯编写,第5章由刘丽华编写,第2章由胡楠编写,第7章由王彦明编写,第1章和第3章由赵杨川编写,第4章和第8章由吴吉红编写。
本书在编写过程中,参阅了大量图书和网络资料,在此向有关作者表示最诚挚的谢意!由于编者水平有限,本书中难免存在疏漏或不足之处,恳请广大读者批评指正。
编者
2025年4月
费如纯辽宁科技学院教授,武汉大学博士。曾任辽宁科技学院电子与信息工程学院副院长(2010—2016年),辽宁科技学院曙光大数据学院副院长(2016—2018年),辽宁科技学院信息化管理办公室主任(2018—2022年)。目前主要研究方向为密码学、网络安全及大数据技术。出版教材5部、学术专著1部。在国内外学术期刊发表EI检索论文10余篇。
目录
第1章绪论
1.1数据结构有什么用
1.2基本概念
1.2.1数据
1.2.2数据结构
1.2.3数据类型
1.3算法及性能分析
1.3.1算法
1.3.2算法描述
1.3.3性能分析
小结
习题1
第2章线性表
2.1基本概念
2.1.1线性表的概念
2.1.2抽象数据类型
2.2顺序表
2.2.1基本概念
2.2.2插入与删除操作
2.2.3数据类型及算法描述
2.3动态链表
2.3.1基本概念
2.3.2单链表
2.3.3双向链表
2.4静态链表
2.4.1基本概念
2.4.2存储结构
2.4.3基本操作
2.5集合的线性表实现
2.5.1用线性表存储集合元素
2.5.2位图
2.5.3并查集
2.6应用案例
小结
习题2
第3章栈和队列
3.1栈
3.1.1基本概念
3.1.2顺序栈
3.1.3链式栈
3.2队列
3.2.1基本概念
3.2.2顺序队列
3.2.3链式队列
3.2.4优先队列
3.3栈和队列的应用
3.3.1栈的应用
3.3.2栈与递归
3.3.3队列的应用
小结
习题3
第4章串、数组和广义表
4.1串
4.1.1基本概念
4.1.2存储结构
4.1.3模式匹配
4.2数组
4.2.1基本概念和存储结构
4.2.2特殊矩阵的压缩存储
4.3广义表
4.3.1基本概念
4.3.2存储结构
小结
习题4
第5章树
5.1基本概念
5.1.1树的定义
5.1.2树的基本术语
5.2二叉树
5.2.1二叉树的定义
5.2.2二叉树的基本形态
5.2.3满二叉树和完全二叉树
5.2.4二叉树的性质
5.2.5二叉树的顺序存储结构
5.2.6二叉树的链式存储结构
5.3二叉树的遍历
5.3.1按层次遍历
5.3.2先序遍历、中序遍历和后序遍历
5.3.3由遍历序列重构二叉树
5.3.4二元运算表达式与二叉树的遍历
5.3.5非递归遍历
5.3.6通过遍历对二叉树进行处理
5.4线索二叉树
5.4.1线索二叉树的基本概念
5.4.2线索二叉树的构建
5.4.3线索二叉树的遍历
5.5树和森林
5.5.1树和森林的存储结构
5.5.2树和森林与二叉树之间的相互转换
5.5.3树和森林的遍历
5.5.4通过遍历对树和森林进行处理
5.5.5基于森林的并查集
5.6哈夫曼树
5.6.1基本概念
5.6.2哈夫曼树的构建
5.6.3哈夫曼编码与解码
5.7应用案例
小结
习题5
第6章图
6.1基本概念
6.2图的存储结构
6.2.1邻接矩阵
6.2.2邻接表
6.2.3十字链表
6.3图的遍历
6.3.1深度优先搜索
6.3.2广度优先搜索
6.4图的连通性
6.4.1路径
6.4.2生成树
6.4.3可达分量与连通分量
6.4.4最小生成树
6.5最短路径
6.5.1迪杰斯特拉算法
6.5.2弗洛伊德算法
6.6有向无环图
6.6.1拓扑排序
6.6.2关键路径
6.7应用案例
6.7.1迷宫问题
6.7.2华容道游戏
小结
习题6
第7章查找
7.1基本概念
7.2顺序查找
7.3折半查找
7.4索引顺序查找
7.5二叉排序树与平衡二叉树
7.5.1二叉排序树
7.5.2平衡二叉树
7.6B树
7.6.1B树的定义
7.6.2B树的操作
7.7哈希查找
7.7.1基本概念
7.7.2哈希函数
7.7.3解决冲突的方法
7.7.4插入、删除与扩容
小结
习题7
第8章排序
8.1基本概念
8.2插入排序
8.2.1直接插入排序
8.2.2折半插入排序
8.2.3希尔排序
8.3交换排序
8.3.1冒泡排序
8.3.2快速排序
8.4选择排序
8.4.1简单选择排序
8.4.2树状选择排序
8.4.3堆排序
8.5归并排序
8.6基于比较的排序方法的对比
8.7计数排序和基数排序
8.7.1计数排序
8.7.2基数排序
8.8外排序
小结
习题8
参考文献