第2版前言 党的二十大报告中指出: 教育、科技、人才是全面建设社会主义现代化国家 的基础性、战略性支撑。必须坚持科技是第一生产力、人才是第一资源、创新是 第一动力，深入实施科教兴国战略、人才强国战略、创新驱动发展战略，这三大 战略共同服务于创新型国家的建设。高等教育与经济社会发展紧密相连，对促进 就业创业、助力经济社会发展、增进人民福祉具有重要意义。 自2017年11月出版以来，《数据结构（Java版）》经过了多次印刷，被许多高校选为“数据结构”课程的教材，深受这些学校师生的钟爱，并获得了良好的社会效益。但从另外一个角度来看，作者有责任和义务维护好这本书的质量，及时更新书中内容，做到与时俱进。 近年来，信息技术突飞猛进，在云计算、大数据和人工智能等方面发展得越来越快。即使在前一版的文章中已经涉及的一些技术，由于有了进一步的发展，也有必要将其内容进行及时的更新。本书改动内容如下。 （1） 重新对每章的内容进行了梳理。 （2） 在第2～8章，每章都增加了实验题及其解答，便于读者提高动手能力。 （3） 针对每章的应用题，重新运行原有程序，使习题答案准确无误。 （4） 针对每章的重点或难点的算法和实验，配置了微课视频进行讲解。 （5） 删除了附录A的考试试题，将试题及其答案作为配套资源提供。 通过上述修改，希望教师和学生更喜欢本教材，也希望本教材信息容量大、知识性强的特色能够很好地得到延续。 为便于教学，本书提供丰富的配套资源，包括教学大纲、教学课件、电子教案、程序源码、习题答案和微课视频。本书配套的视频二维码位置如表1所示。 表1视频二维码位置 序号 视频内容标题 视频二维码位置 所在页码 1 U2链表 2.3线性表的链式存储和实现24 2 U3中缀表达式转后缀表达式 3.4.3表达式求值57 3 U4 KMP 4.2.2KMP算法72 4 U5队列实现二叉树的层次遍历 5.2.4二叉树的遍历95 5 U5哈夫曼树 5.3哈夫曼树及哈夫曼编码103 6 U5由二叉树的前序遍历和中序遍历还原树 5.5.3从前序遍历和中序遍历构造二叉树110 7 U6迪杰斯特拉 6.5.1求某个顶点到其余顶点的最短路径133 8 U6拓扑排序 6.6拓扑排序和关键路径135 9 U7快速排序 7.3.2快速排序153 10 U7归并排序 7.5归并排序160 11 U7实验题3——链表归并排序 7.6.3链表排序（进阶）166 12 U8快慢指针查找重复数——理论 8.5.2查找重复数186 13 U8快慢指针查找重复数——代码 8.5.2查找重复数186 资源下载提示 课件等资源： 扫描封底的“课件下载”二维码，在公众号“书圈”下载。 数据文件等资源： 扫描目录上方的二维码下载。 视频等资源： 扫描封底的文泉云盘防盗码，再扫描书中相应章节的二维码，可以在线学习。 本书的作者为吕云翔、郭颖美、王子豪，曾洪立参与了部分内容的编写并进行了素材整理及配套资源制作等。 最后，请读者不吝赐教，及时提出宝贵意见。 编者 2023年5月 前言 随着近年来计算概念的快速发展，计算学科已经发展成为一个内涵繁杂的综合性学科，其至少可以划分为计算机工程(CE)、计算机科学(CS)、信息系统(IS)、信息技术(IT)和软件工程(SE)5个领域，而且不同领域的人才所应具备的知识结构与能力侧重也不尽相同。尽管如此，从目前已经完成的部分来看，数据结构在各领域的知识体系中仍然占据着重要的位置。“数据结构”是普通高等院校计算机和信息管理等专业的一门必修课程，主要讨论数据的逻辑结构、在计算机中的存储结构以及对其进行的各种处理运算的方法和算法。 N.Wirth早在20世纪70年代就指出“程序=数据结构+算法”。数据结构主要研究数据在计算机中存储、组织、传递和转换的过程及方法，这些也是构成与支撑算法的基础。近年来，随着面向对象技术的广泛应用，从数据结构的定义、分类、组成到设计、实现与分析的模式和方法都有了长足的发展，现代数据结构更加注重和强调数据结构的整体性、通用性、复用性、简洁性和安全性。 为遵循上述原则，本书选择Java作为描述语言，因为相对于其他语言，Java程序设计语言是应用最广泛、面向对象程度化最高的语言，利用Java语言中的类和接口能够准确地描述任何一种数据结构的逻辑定义和运算，利用一种存储结构定义的派生类能够高效地实现对数据的运算。 在内容的选取与结构上，本书并未涉及各种数据结构，而是通过分类和讲解典型结构使读者形成对数据结构的宏观认识。根据内容的侧重，本书共分8章，分别为绪论、线性表、栈和队列、串和数组、树结构、图、排序和查找。 第1章介绍数据结构的基本概念，算法的描述和算法时间复杂度、空间复杂度等内容，是全书的基础。 第2章主要介绍线性表的基本概念和抽象数据类型定义、线性表顺序和链式两种存储方式的表示、基本操作的实现和相应的应用。 第3章简要介绍栈和队列的基本概念和抽象数据类型定义、栈和队列在顺序存储和链式存储结构下的基本操作和应用。 第4章主要介绍串的基本概念和数据类型定义、串的存储结构、基本操作实现和应用等内容。 第5章主要介绍树和二叉树的基本概念，详细介绍二叉树的性质和存储结构、遍历方法的实现及应用、哈夫曼树的概念和构造方法。 第6章主要介绍图的基本概念、抽象数据类型定义、存储结构和遍历方法，还介绍最小生成树的基本概念和算法、最短路径的相关算法、拓扑排序的概念和实现方法。 第7章介绍排序的基本概念，插入排序、交换排序、选择排序、归并排序等多种排序的原理、实现方法及性能分析。 第8章主要介绍查找的基本概念，顺序查找、二分查找等查找的原理、实现方法和性能分析，平衡二叉树、哈希表的概念、结构定义和实现方法。 本书理论知识的教学安排建议如下： 章节内容学时数 第1章绪论2 第2章线性表4~6 第3章栈和队列6~8 第4章串和数组2~4 第5章树结构6~8 第6章图4~8 第7章排序4~6 第8章查找4~6 建议先修课程： Java语言 建议理论教学时数： 32~48学时 建议实验(实践)教学时数： 16~32学时 本书中的所有算法都已经通过上机调试，尽量确保算法的正确性。在每章内容后都有小结，便于读者复习总结，并配有丰富的习题，包括选择题、填空题、算法设计题等，给读者更多思考的空间。 本书在以下几个方面具有突出特色： （1） 内容精练，强化基础，合理安排内容结构，做到由浅入深、循序渐进。 本书各章节都从基本概念入手，逐步介绍其特点和基本操作的实现，把重点放在基础知识的介绍上，缩减难度较大的内容，使理论叙述简洁明了、重点突出、详略得当。 （2） 应用实例丰富、完整。 本书通过丰富的应用实例和源代码使理论和应用紧密结合，增强学生的理解能力，锻炼程序设计思维，并且代码有详细明了的注释，易于阅读。 （3） 每章后面附有小结和习题，便于学习、总结和提高。 本书结合学生的学习实际选择难度适中、逻辑合理，适于初学者和进阶者开拓思路、深入了解数据结构使用方法和技巧的习题，并附有详细的解答过程和注意要点，达到通俗易懂、由浅入深的效果，培养读者迁移知识的能力。 （4） 采用Java的泛型方法来体现方法的通用性。 本书采用面向对象的观点讨论数据结构技术，先将抽象数据类型定义成接口，再结合具体的存储结构加以实现，并以各实现类为线索对类中各种操作的实现方法加以说明。 （5） 图文并茂，便于学生直观地理解数据结构与算法。 本书通过图表的方式对数据结构及相应操作进行简单直接的描述，使内容更加浅显易懂。 教师可以按照自己对数据结构的理解适当地跳过一些章节，也可以根据教学目标灵活地调整章节的顺序，增减各章的学时数。 由于数据结构本身还在探索之中，加上我们的水平和能力有限，本书难免有疏漏之处，恳请各位同仁和广大读者给予批评指正，也希望各位能将实践过程中的经验和心得与我们交流。 作者 2017年6月