F  O R E W O R D

前言

数据结构课程是计算机及相关专业的核心专业基础课程。数据结构是指存在相互关系的数据元素集合，并包含相应的数据运算。从数据结构的应用角度看，人们不必关心数据的存储和运算的具体实现细节，将其作为一个功能包用于求解更复杂的问题，这样能在适当的抽象层次上考虑程序的结构和算法； 从数据结构的实现角度看，则需要考虑数据的逻辑类型，将这些数据以某种合理的方式存储在计算机中，继而高效地实现对应运算的算法。

  教学内容设计

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

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

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

第2章线性表。本章介绍线性表的定义、线性表的两种主要存储结构和各种基本运算算法设计，最后通过示例讨论线性表的应用。

第3章栈和队列。本章介绍栈的定义、栈的存储结构、栈的各种基本运算算法设计和栈的应用； 队列的定义、队列的存储结构、队列的各种基本运算算法设计和队列的应用； Python中的deque和heapq及其使用。

第4章串和数组。本章介绍串的定义、串的存储结构、串的各种基本运算算法设计、串的模式匹配BF和KMP算法及其应用

； 数组的定义、数组的存储方法、几种特殊矩阵的压缩存储和稀疏矩阵的压缩存储。

第5章递归。本章介绍递归的定义、递归模型、递归算法设计和分析方法。

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

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

第8章查找。本章介绍查找的定义、线性表上的各种查找算法、树表上的各种查找算法以及哈希表查找算法及其应用。

第9章排序。本章介绍排序的定义、插入排序方法、交换排序方法、选择排序方法、归并排序方法和基数排序方法，

以及各种内排序方法的比较、外排序过程和相关算法。

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

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

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

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

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

 书中提供了大量的教学示例，将抽象概念和抽象的算法过程具体化。

 与Python语言深度结合，充分利用Python语言中数据类型灵活的特点实现书中的所有算法，所有算法及其示例均在Python 3.7中调试通过。

  教学实验设计

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

 除第1章外，每一章均包含基础实验和应用实验，基础实验属于验证性实验，是上机实现相关数据结构或者算法，用于培养学生的基本数据组织和数据处理； 应用实验属于设计或者综合性实验，是利用相关数据结构完成较复杂的算法实现，用于提高

学生运用各种数据结构解决问题的能力。

 每一章包含若干与教学内容紧密结合的、难度适中的在线编程题，所有题目都经过精心挑选，均来自

力扣(中国)

（https://leetcodecn.com/）网站。力扣（中国）是一个极好的学习和实验在线编程平台，每一题都提供了多个测试用例，可以对实验算法进行时间和空间的全方位测试。

  配套教学资源

本书配套的辅助教材《数据结构教程（Python语言描述）学习与上机实验指导》提供了所有练习题和实验题的参考答案，其中所有在线编程题均在相关平台中验证通过。

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

(1) 教学PPT： 提供全部教学内容的精美PPT课件，仅供任课教师在教学中使用。

(2) 源程序代码： 所有源代码按章组织，例如ch2文件夹中存放第2章的源代码，其

“示例”子文件夹中是相关示例的源代码文件，例如ch2的“示例”子文件夹中的Exam23.py是例2.3的源代码。

(3) 数据结构课程教学大纲： 包含32/48/60课堂讲授学时的教学内容安排和相应的实验教学内容安排，供教师参考。

(4) 练习题中算法设计题源代码： 提供所有算法设计练习题的源程序代码,仅供任课教师在教学中使用。

(5) 配有绝大部分知识点和全部Leet Code在线编程题讲解

的教学视频，视频采用微课碎片化形式组织（含238个小视频，累计超过40小时）。

资源下载提示

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

素材（源码）等资源： 扫描目录上方的二维码下载。

视频等资源： 扫描封底刮刮卡中的二维码，再扫描书里章节中的二维码，可以在线学习。

本书第2、3、6、7章由李春葆编写，第1、4、5章由蒋林编写，第8、9章由李筱驰编写，李春葆完成全书的规划和统稿工作。本书的出版得到清华大学出版社计算机与信息分社

魏江江分社长的全力支持，王冰飞老师给予精心编辑，力扣（中国）网站提供了无私的帮助，编者在此一并表示衷心

的感谢。尽管编者不遗余力，但由于水平所限，本书难免存在不足之处，敬请教师和同学们批评指正，

在此表示衷心的感谢。

编者2020年8月