F  O R E W O R D

前言

“数据结构”课程是计算机及相关专业的核心专业基础课，以常用的数据结构为主线讨论基本的数据组织和处理方法。该课程的要求是学生能够掌握数据的逻辑结构、存储结构及基本运算的实现，能够对算法进行基本的时间复杂度与空间复杂度分析，能够运用数据结构的基本原理和方法进行问题分析与求解，并具备采用计算机语言设计与实现算法的能力。

该课程要求分为两个层次，一是掌握各种数据结构的基本原理，从逻辑层面理解各种数据结构的逻辑结构特性以及基本运算，继而合理地实现数据结构，使之成为像程序设计语言中那样可以直接使用的数据类型； 二是掌握各种数据结构的应用，针对一个较复杂的数据处理问题选择合适的数据结构，设计出好的求解算法。

本书基于作者长期在教学第一线从事教学研究的教学经验的积累和总结，同时参考近年来国内外出版的多种数据结构教材，考虑教与学的特点，合理地进行内容取舍和延伸，精心组织编写而成。本书采用Java语言的面向对象方法描述数据结构和算法。全书由10章组成，各章的内容如下。

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

第2章线性表： 介绍线性表的定义、线性表的两种主要存储结构和各种基本运算算法设计，以及Java中的ArrayListE和LinkedListE集合及其使用，最后通过示例讨论线性表的应用。

第3章栈和队列： 介绍栈的定义、栈的存储结构、栈的各种基本运算算法设计和栈的应用，以及队列的定义、队列的存储结构、队列的各种基本运算算法设计和队列的应用，Java中的StackE、QueueE、DequeE和PriorityQueueE集合及其使用。

第4章串： 介绍串的定义、串的存储结构和串的各种基本运算算法设计，以及Java中的String类及其使用，串的模式匹配算法BF和KMP及其应用。

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

第6章数组和稀疏矩阵： 介绍数组的定义、数组存储方法和Java中的数组类Arrays及其使用，以及几种特殊矩阵的压缩存储方式、稀疏矩阵的压缩存储及相关算法设计。

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

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

第9章查找： 介绍查找的定义、线性表上的各种查找算法、树表上的各种查找算法、哈希表查找算法，以及Java中的TreeMapE、TreeSetE、HashMapE和HashSetE集合的使用方法。

前言

数据结构教程（Java语言描述）

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

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

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

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

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

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

（5） 书中提供大量的教学示例，将抽象概念具体化，所有算法设计示例均在JDK 1．8中调试通过。

（6） 与Java语言深度结合，在讲授各种数据结构实现原理的基础上介绍Java中已实现的相关集合，并通过示例利用这些集合求解实际问题。

（7） 强调实践教学过程，锻炼在线编程能力，以POJ和HDU为平台，提供了若干个与课程内容紧密结合、难度适中的在线编程实验题，方便课程实训。

(8) 绝大部分知识点配有教学视频，采用微课碎片化形式组织，累计超过32小时。

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

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

（1） 教学大纲： 包含48课时和60课时参考教学内容安排。

（2） 教学课件： 提供超过1500页的精美PPT课件，仅供任课教师在教学中使用。

（3） 程序源码： 所有源代码按章组织，例如ch2文件夹存放第2章的源代码，其中SqList子文件夹存放顺序表类文件SqListClass．java和相关示例源代码文件，例如ch2下的SqList中的Exam2_3．java为例2．3的源代码。

资源下载提示

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

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

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

在线作业： 扫描封底刮刮卡中的二维码，登录在线作业平台。

本书出版前已作为武汉大学的弘毅学堂的“数据结构”课程讲义使用过多次，并在教学中根据实际情况和同学们的建议做了多次修订，在出版过程中得到清华大学出版社计算机与信息分社魏江江分社长的全力支持，同时王冰飞老师给予精心指导，在此一并表示衷心的感谢。

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

作者2020年5月于西雅图