前言 《数据结构（Python版）》于2019年4月正式出版以来，经过了几次印刷，许多高等学校已将其作为“数据结构”课程的教材。本书不仅深受这些学校师生的钟爱，而且也获得了良好的社会效益。但从另外一个角度来看，作者有责任和义务维护好这本书的质量，及时更新本书的内容，做到与时俱进。 本书修订内容如下。 （1） 重新对每章内容进行了梳理。 （2） 第2～8章中，每章都增加了实验题及其解答，便于提高读者动手能力。 （3） 针对每章章后的应用题，重新对程序进行了运行和调试，使习题答案准确无误。 （4） 针对每章的重点或难点的算法和实验，配置了微课视频进行讲解。 （5） 删去了附录A的考试试题，而是将试题及其答案作为教辅资源，供读者下载。 希望通过这样的修订，让更多的教师和学生喜欢本书，也希望本书信息容量大、知识性强的特色能够很好地延续下去。 本书的作者为吕云翔、郭颖美、孟爻、吴宜航、杨壮，曾洪立参与了部分内容的编写并进行了素材整理及配套资源制作等。 书中如有不当，请读者不吝赐教，及时提出宝贵意见。 作者 2023年3月 第1版前言 随着近年来计算概念的快速拓展，计算科学已经发展成为一个内涵繁杂的综合性学科，其至少可以划分为计算机工程（CE）、计算机科学（CS）、信息系统（IS）、信息技术（IT）和软件工程（SE）5个领域，而且不同领域的人才所应具备的知识结构与能力侧重也不尽相同。尽管如此，数据结构在各领域的知识体系中仍然占据着重要的位置。“数据结构”是普通高等学校计算机专业和信息管理专业的一门必修课程，主要讨论数据的逻辑结构、在计算机中的存储结构以及对其进行的各种处理运算的方法和算法。 N.Wirth早在20世纪70年代就指出“程序=数据结构+算法”。数据结构主要研究数据在计算机中存储、组织、传递和转换的过程及方法，这些也是构成与支撑算法的基础。近年来，随着面向对象技术的广泛应用，从数据结构的定义、分类、组成到设计、实现与分析的模式和方法都有了长足的发展，现代数据结构更加注重和强调数据结构的整体性、通用性、复用性、间接性和安全性。 基于上述情况，本书选择Python作为描述语言。Python语言语法简洁优美，功能强大，有着广泛的应用领域，如互联网、大数据、人工智能等领域。因此，学习Python语言，在未来的学习和工作中，都有用武之地。同时，Python语言相对于大多数高级语言，更加适合初学者学习，Python的语法与伪代码描述很相似，逻辑清晰； 此外，Python语言也同样具有大部分高级语言的特性，对计算机相关专业的学生未来学习其他编程语言有所帮助。 在内容的选取与结构安排上，本书通过分类和讲解典型结构使读者对数据结构形成宏观认识。根据内容的侧重，本书分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 建议先修课程： Python语言。 建议理论教学时数： 32~48学时。 建议实验（实践）教学时数： 16~32学时。 本书中的所有算法都已经通过上机调试，尽量保证算法的正确性。在每章内容后都有小结，便于读者复习总结，并配有丰富的习题，包括选择题、填空题、算法设计题等，给读者更多的思考空间。 本书在以下几方面具有突出特色。 （1） 内容精炼，强化基础，合理安排内容结构，做到深入浅出、循序渐进。 本书各章节都从基本概念入手，逐步介绍其特点和基本操作的实现，把重点放在基础知识的介绍上，缩减难度较大的内容，使理论叙述简洁明了、重点突出、详略得当。 （2） 应用实例丰富、完整。 本书通过丰富的应用实例和源代码使理论和应用紧密结合，增强学生的理解能力，锻炼程序设计思维。代码有详细明了的注释，易于阅读。 （3） 每章后面附有小结和习题，便于学习、总结和提高。 本书结合学生的学习实际选择难度适中、逻辑合理、适于初学者和进阶者开拓思路、深入了解数据结构使用方法和技巧的习题，并附有详细的解答过程和注意要点，达到通俗易懂、深入浅出的效果，培养读者迁移知识的能力。 （4） 采用Python抽象类体现方法的通用性。 本书采用面向对象的观点讨论数据结构技术，先将抽象数据类型定义成接口，再结合具体的存储结构加以实现，并以各实现类为线索对类中各种操作的实现方法加以说明。 （5） 图文并茂，便于读者直观地理解数据结构与算法。 本书通过图表的方式对数据结构及相应操作进行简单直接的描述，使内容更加浅显易懂。 教师可以按照自己对数据结构的理解适当地跳过一些章节，也可以根据教学目标灵活地调整章节的顺序，增减各章的学时数。 本书的作者为吕云翔、郭颖美、孟爻，曾洪立、吕彼佳、姜彦华参与了部分内容的编写并进行了素材整理及配套资源制作等。 由于数据结构本身还在探索之中，加上作者的水平和能力有限，书中难免有疏漏之处，恳请各位同仁和广大读者给予批评指正，也希望各位能将实践过程中的经验和心得与作者交流。 作者 2019年1月