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月