前言 “数据结构”是计算机及相关专业的一门综合性的专业基础课,同时也是计算机相关专业考研的必考科目。数据结构的研究不仅涉及计算机硬件,例如编码理论、数据存储、存取方法等,而且和计算机软件也有密切的关系,编译程序和操作系统都涉及数据元素在存储器中的分配问题。信息检索领域也涉及数据的组织和查找方式。在计算机学科中,数据结构不仅是程序设计的基础,也是编译原理、操作系统、数据库系统等课程的基础。 算法的设计依赖于逻辑结构,算法的实现则依赖于物理结构。要成为专业的程序开发人员必须能够熟练地选择和设计各种数据结构和算法。要设计出结构合理、效率高的算法,必须研究数据元素的特点、数据元素之间的关系。要在算法的基础上利用高级程序设计语言实现算法,则必须考虑逻辑结构在内存中的实现,即物理结构。 数据结构中涉及许多重要元素的组织方式及算法,例如线性表、栈和队列、树和二叉树、图等重要的数据结构,以及查找、排序、插入、删除等常见操作。对于特定的数据结构和操作,已有许多成熟的经典算法。掌握这些算法有助于培养学生的抽象思维能力,提高他们分析和解决复杂问题的能力。“数据结构”课程的知识点逻辑性和抽象性较强,一些算法设计得较为复杂,如果不付诸实践,很难真正理解算法的精髓。因此要把“数据结构”这门课程学好,必须在熟练掌握理论知识的基础上,加强实践环节。 编者结合多年来从事“数据结构”课程教学的经验,编写了此教材。本书理论和实践并重,采用边学边做的方式,首先对理论知识进行阐述,然后实现各种数据结构常见的算法,并附有程序运行结果和说明。本书采用类C++语言描述算法,基本上涵盖了各种常见的数据结构及算法,也包括了一些扩展应用,例如农夫过河问题和多岔路口交通灯问题等。对于一些较复杂的问题,分别给出了问题描述、模型说明、算法描述、源代码以及实验结果。本书同时提供课件、视频、源代码、课后习题答案等相关教辅材料。请读者用手机微信扫一扫封底刮刮卡内二维码,获得权限,再扫一扫书中二维码,即可观看教学视频。其他配套资源可从清华大学出版社网站下载。本书可作为计算机各相关专业的数据结构教材,也可以作为感兴趣的自学者的参考教材。 感谢山东省教育服务新旧动能转换专业对接产业项目(曲阜师范大学精品旅游)对本书的资助。感谢山东省高等教育本科教改项目(Z2018S022)、曲阜师范大学实验技术研究项目(SJ201726)对本书的资助。 由于编者水平有限,书稿虽几经修改,但仍难免有疏漏和不足之处,敬请读者朋友们批评指正。 编者 2020年4月