首页 > 图书中心 > 数据结构教程(C++语言描述)(第2版·微课视频版)

前言

F  O R E W O R D

前言

“数据结构”课程是计算机及相关专业的核心专业基础课,那么什么是数据结构呢?科学百科是这样定义的: “数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往与高效的检索算法和索引技术有关。”

该定义包含两重含义,即数据结构实现和数据结构应用。从数据结构的实现角度看,数据结构是指存在相互关系的数据元素集合,并包含相应的数据运算,在实现时就需要考虑数据的逻辑类型,将这些数据以某种合理方式存储在计算机中,继而高效地实现对应运算的算法。像计算机语言中的数据类型都是已经实现的数据结构。从数据结构的应用角度看,人们不必关心数据的存储和运算的具体实现细节,只需要将其作为一个功能包用于求解更复杂的问题,在适当的抽象层次上考虑程序的结构和算法。理解和掌握数据结构的实现有助于应用数据结构,提高计算机求解问题的能力。

 教学内容设计

“数据结构”课程主要以数据的逻辑结构为主线,介绍线性表、栈和队列、树和二叉树、图等数据结构的实现和应用。该课程一方面培养学生基本的数据结构观,即从逻辑层面理解数据结构的逻辑结构特性以及基本运算,继而合理地实现数据结构,使之成为像程序设计语言中那样可以直接使用的数据类型; 另一方面培养学生运用各种数据结构的能力,即针对一个较复杂的数据处理问题,选择合适的数据结构设计出好的求解算法。

本书围绕这两个目标设计教学内容,总结编者长期在教学第一线的教学研究和教学经验,同时参考近年来国内外出版的多种数据结构教材,考虑教与学的特点,合理地进行知识点取舍和延伸,精心组织编写而成。本书采用C++语言描述数据结构和算法。全书由10章构成,各章内容如下: 

第1章绪论。本章介绍数据结构的基本概念、采用C++语言描述算法的方法和特点、算法分析方法和如何设计好算法等。

第2章线性表。本章介绍线性表的定义、线性表的两类主要存储结构和各种基本运算算法设计; 通过多项式相加的示例讨论线性表的应用; 介绍STL中的vector和list容器及其使用方法。

第3章栈和队列。本章介绍栈的定义、栈的存储结构、栈的各种基本运算算法设计和栈的应用,队列的定义、队列的存储结构、队列的各种基本运算算法设计和队列的应用,STL中的stack(栈)、queue(队列)、deque(双端队列)和priority_queue(优先队列)容器及其使用方法。

第4章串。本章介绍串的定义、串的存储结构和串的各种基本运算算法设计,STL中的string容器的使用方法,串的模式匹配算法BF和KMP及其应用。

第5章数组和稀疏矩阵。本章介绍数组的定义、数组的存储结构、几种特殊矩阵的压缩存储和稀疏矩阵的压缩存储。

第6章递归。本章介绍递归的定义、递归模型、递归算法设计和分析方法,以及递归算法转换为非递归算法的一般过程。

第7章树和二叉树。本章介绍树的定义、树的逻辑结构表示方法、树的性质、树的遍历和树的存储结构,二叉树的定义、二叉树的性质、二叉树的存储结构、二叉树的基本运算算法设计、二叉树的递归和非递归遍历算法、二叉树的构造、线索二叉树和哈夫曼树,树/森林和二叉树的转换与还原过程,并查集的定义与实现。

第8章图。本章介绍图的定义、图的存储结构、图的基本运算算法设计、图的两种遍历算法以及图的应用,图的应用包括求最小生成树、最短路径、拓扑排序和关键路径。

第9章查找。本章介绍查找的定义、线性表上的各种查找算法、各种树表的查找算法,以及哈希表查找算法及其应用、STL中的哈希表容器(如unordered_map和unordered_set)的使用方法。

第10章排序。本章介绍排序的定义、插入排序方法、交换排序方法、选择排序方法、归并排序方法和基数排序方法,以及各种内排序方法比较、外排序的基本过程和相关算法。

教学内容紧扣《高等学校计算机专业核心课程教学实施方案》和《计算机学科硕士研究生入学考试大纲》,涵盖教学方案及考研大纲要求的全部知识点。书中带“*”的章节或示例为选讲或选学内容,难度相对较高,供提高者研习。本书的主要特点如下: 

① 结构清晰,内容丰富,文字叙述简洁明了,可读性强。

② 图文并茂,全书用了300多幅图表述和讲解数据的组织结构和算法设计思想。

③ 力求归纳各类算法设计的规律,如单链表算法中很多是基于建表算法,二叉树算法中很多是基于4种遍历算法,图算法中很多是基于两种遍历算法,如果读者掌握了相关的基础算法,那么对于较复杂的算法设计就会驾轻就熟。

④ 深入讨论递归算法设计方法。递归算法设计是数据结构课程中的难点之一,编者从递归模型入手,介绍了从求解问题中提取递归模型的通用方法,讲解了从递归模型到递归算法设计的基本规律。

⑤ 书中提供了大量的教学示例并详细解析,将抽象概念和抽象的算法过程具体化。

⑥ 结合知识点提供了若干相关的实战题,实战题来源于力扣(https://leetcodecn.com/)、POJ(http://poj.org/)和HDU(http://acm.hdu.edu.cn/)网站。

⑦ 与C++语言深度结合,充分利用C++语言的特点实现书中的所有算法,全部算法及其示例均在Dev C++5.1中调试通过。

⑧ 提供了大量的练习题、上机实验题和在线编程题,供教学中选用。

 教学实验设计

教学实验是提高利用数据结构原理解决实际问题必不可少的环节,本书将实验教学和理论教学有机结合,构成完整的体系。

① 每章包含基础实验和应用实验。基础实验属于验证性实验,是上机实现相关数据结构或者算法,用于强化对基本数据结构观的认知; 应用实验属于设计或者综合性实验,是利用相关数据结构完成较复杂的算法实现,用于提高运用各种数据结构解决复杂问题的能力。

② 每章包含若干与教学内容紧密结合的、难度适中的在线编程题,所有题目都经过精心挑选,均来自力扣、POJ和HDU网站。力扣(中国)是一个极好的学习和实验在线编程平台,POJ和HDU是目前国内最优秀的ACM训练网站。每道在线编程题都提供了多个测试用例,可以对实验算法进行时间和空间的全方位测试。

 配套教学资源

本书配套的辅助教材为《数据结构教程(C++语言描述)(第2版)学习与上机实验指导》和《数据结构在线编程实训(C++语言)(全程视频讲解版)》,前者提供了所有练习题和上机实验题的解题思路和参考答案,后者提供了所有实战题和在线编程题的解题思路和参考答案(含全部题目的视频讲解),所有程序均在相关平台中验证通过并给出了时间和空间数据。

为了方便教师教学和学生学习,本书提供了全面、丰富的教学资源。配套教学资源包中的内容如下: 

① 教学PPT。提供全部教学内容的精美PPT课件,仅供任课教师在教学中使用。

② 源程序代码。所有源代码按章组织,例如ch2文件夹中存放第2章的源代码,其中,ch2\\Exam23.cpp为例2.3的源代码。

③ 数据结构课程教学大纲和电子教案。包含54学时课堂讲授的教学内容安排和18学时实验的实验教学内容安排,供教师参考。

④ 在线作业。包括选择题、判断题、填空题、简答题和编程题。

⑤ 书中配套绝大部分知识点的教学视频,视频采用微课碎片化形式组织(含266个小视频,累计超过45小时)。

资源下载提示

课件等资源: 扫描封底的“课件下载”二维码,在公众号“书圈”下载。

素材(源码)等资源: 扫描目录上方的二维码下载。

在线作业: 扫描封底作业系统二维码,登录网站在线做题及查看答案。

视频等资源: 扫描封底刮刮卡中的二维码,再扫描书中相应章节中的二维码,可以在线学习。

本书第2、3、6、7和10章由李春葆编写,第1、4和5章由匡志强编写,第8和9章由蒋林编写,李春葆完成全书的规划和统稿工作。本书的出版得到清华大学出版社魏江江分社长的全力支持,王冰飞老师给予精心编辑,力扣(中国)网站提供了无私的帮助,编者在此一并表示衷心的感谢。尽管编者不遗余力,但由于水平所限,本书难免存在不足之处,敬请教师和同学们批评指正,在此表示衷心的感谢。

编者2021年5月

版权所有(C)2019 清华大学出版社有限公司 京ICP备10035462号 京公网安备11010802013248号

联系我们 | 网站地图 | 法律声明 | 友情链接 | 盗版举报 | 人才招聘