第2版前言 根据本书第1版使用中读者的反馈意见、实际使用效果，以及编者的新认识，并结合当前新形态教材中所融合的新技术，以更加有利于读者学习为目标，制定了第2版的修改方案。本书第2版基本保留了第1版总体的知识框架体系，并继承了它的叙述风格，同时在实用性、针对性、简洁性和拓展性等方面也做了部分修改、增删与扩充，主要变化体现在以下几个方面。 (1) 为了促进新形态教材在“翻转课堂”教学中的应用，丰富了与该课程教学的配套资源。除有“微课件”“题库”外，每章增加了对应的“学习任务单”“学习导案”“测试题”和“考试题”等，每个微视频还增加了“打点”测试题，能使教师的“翻转课堂”教学更轻松、有效。目前，该课程的所有教学资源都已部署到浙江省高等学校在线开放课程共享平台和超星泛雅平台，也即将在中国大学MOOC平台上线，需要者可在相应网络平台搜索刘小晶负责的"数据结构"课程，然后注册学习或加入课程教学团队后，便可查阅和使用完整的教学资源。 (2) 为了适应当今新技术的发展，对每章后的客观练习题进行了补充， 并且全部以二维码的形式嵌入书中，读者可随时随地通过手机在线检测自己的学习效果，促进其自主学习、自主探究。 (3) 为了突出求解问题中核心算法的分析和实现，删除了大量测试程序的实例，对编程题只保留核心算法代码，使算法精简、重点突出。 (4) 为使书中例题对知识的覆盖面更具针对性和代表性，增加或更换了书中部分例题，如在第1章增加了“问题三”，在第2章和第3章增加了例21、例22等，更换了例24、例26、例27等。 (5) 为了突出栈的递归应用，在第3章增加了“3.1.6 栈与递归”的内容，使读者能更好地理解递归实现与栈的应用之间的实质性内容，为后续递归算法的拓展应用奠定基础。 (6) 为了使算法的描述更加简洁，易于理解，修改了部分算法，如算法55、算法56、算法57等。 (7) 为了使抽象内容能更加生动、形象地表达出来，在第5章对部分算法增加了其执行过程示意图，如图515、图518、图520、图522等，以便读者能快速领会算法的核心思想。 (8) 纠正了第1版中发现的错误，并进一步检测了书中算法及习题参考答案的正确性和合理性。 参加第2版各章编写的人员是： 刘小晶教授、朱蓉教授、杜卫锋副教授、滕姿博士，由刘小晶策划和统稿。书中所有算法（包括习题）都在VC（或CFree）环境下测试通过，源程序代码可扫描下方二维码下载。 教学资源扫码下载 由于数据结构知识的应用非常广泛，加之编者水平有限，书中难免会有疏漏和不足之处，敬请批评指正。 编者 2020年1月 第1版前言 当今以MOOC(慕课)为代表的在线教育在高等教育领域迅速兴起，这不仅是教育技术的革新，更引发了教育观念、教育体制、人才培养、教学方式的深度变革。传统的课堂教学模式及学习方式正发生重大变化，仅以纸质教材为媒介的课堂教学载体已不能适应当前的教学发展需要。因在“互联网+教育”时代，传统的纸质教材存在着明显的不足，如成本高、携带不便、知识信息更新慢、知识容量有限等,而数字化的电子教材能弥补这些不足。但完全数字化的电子教材在当前国情下，受教师的教学习惯、学生的学习和阅读习惯、网络条件、设备条件等制约，难以在所有高等学校或所有课程中全面使用。为此，在“互联网”时代，传统纸质教材与数字化教学资源融合形成的新形态教材，已成为教材建设的一种新趋势，也是现实教育的迫切需求。 本教材将纸质内容与数字媒体内容进行有机融合，与传统教材相比，无论是课程内容还是内容的呈现形式都进行了一定程度上的重构，使其充分发挥纸质教材和数字媒体的优势，实现知识由静态、抽象化向动态、形象化的转变。具体特点阐述如下。 1. 对教材内容的精心设计 对于知识体系相对固定的“数据结构”课程而言，作者在“互联网+” 的思维下重新审视了课程的教学内容，对传统纸质教材的内容进行了重构。并根据使用者的特点进行了一体化的设计，以确定哪些教学内容适合印在纸质教材上， 哪些内容适合以数字媒体形式放在云端。具体设计原则是纸质教材内容在紧扣计算机类考研大纲的前提下，把重点、难点、拓展资源做成微课视频或其他数字媒体资源，以二维码的形式嵌入纸质教材中，并在所有内容设计上做到： (1) 精简内容、强化基础、突出知识的应用性。针对普通高校学生的实际情况，把握“适用”与“够用”的尺度。做到把重点放在基础知识的介绍上，缩减了一些难度较大的内容，并强调其在实际问题中的应用性，充分体现了理论与应用背景的紧密结合。 (2) 理论叙述简洁明了、重点突出、应用实例丰富。各章节都以基本概念为切入点，逐步介绍其特点和基本操作的实现，然后通过应用实例来讲述如何运用所学的原理和方法来解决实际问题，最后附有小结、习题，便于学习总结和提高。这些内容做到“环环相扣，层层推进”，充分体现解析法的精髓，达到通俗易懂、由浅入深的效果，突显了教材对培养读者的算法分析与设计能力，以及知识迁移能力的作用。 2. 对教材内容呈现形式的精心设计 本教材对传统纸质教材内容的呈现形式也进行了重构，它除了呈现传统纸质的文本内容之外，还对课程中的重点、难点和拓展知识进行了分析与设计，并采用二维码的方式嵌入了对应的数字资源，读者通过使用移动终端扫描书中的二维码，就可获得以视频等媒体形式呈现的教学内容或链接到对应的互动平台，不但可突显其重点、难点知识的讲解，增强学习者的趣味性和互动性，从而提高课程教学效果； 更可适应喜好不同学习方式的人群使用，实现随时随地学习、交流与互动； 而且这些内容的更新不再受制于纸质教材的改版更新，可以根据需要随时更新和拓展资源内容。 本教材的内容由9章组成。 （1） 绪论，内容主要涉及数据结构课程讨论的内容； 数据结构的常用术语及基本概念； 数据结构算法的描述和算法分析方法以及相关约定等。 （2） 线性表，内容主要涉及线性表的抽象数据类型定义； 线性表类型在顺序存储和链式存储两种存储结构下的实现方法以及线性表的应用等。 （3） 栈与队列，内容主要涉及栈与队列的抽象数据类型定义； 栈与队列在顺序存储和链式存储结构下其基本操作的实现方法以及栈与队列的应用等。 （4） 串与数组，内容主要涉及串的基本概念、存储结构、基本操作实现； 数组的定义、基本操作、存储结构以及矩阵的压缩存储和数组的应用等。 （5） 树，内容主要涉及树与二叉树的基本概念和存储结构； 树、二叉树和森林的遍历； 树、二叉树与森林之间的转换方法以及哈夫曼树与哈夫曼编码等。 （6） 图，内容主要涉及图的基本概念； 图的邻接矩阵和邻接表两种最基本的存储结构； 图的广度优先搜索和深度优先搜索两种最基本的遍历方法； 有关最小生成树的克鲁斯卡尔（Kruskal）和普里姆(Prim）两种实现算法； 拓扑排序和求关键路径等。 （7） 内排序，内容主要涉及排序的基本概念； 常用内部排序（插入排序、交换排序、选择排序、归并排序和基数排序）方法的实现及性能分析以及各种内部排序方法的比较等。 （8） 外排序，内容主要涉及外部排序的方法； 磁盘排序的信息存取、多路平衡归并排序、置换—选择排序和最优归并树等。 （9） 查找，内容主要涉及查找的基本概念； 静态表查找（顺序查找、二分查找和分块查找）、动态表查找（二叉排序树、平衡二叉树、B树和红黑树）、哈希表查找的实现方法及性能分析等。 本教材是由课程组成员协作完成： 第1～3章及第7～8章由刘小晶教授执笔，第5、9章由朱蓉教授执笔，第4、6章由杜卫锋副教授和滕姿博士执笔。全书由刘小晶策划并统稿。 本书在编写过程中参阅了大量的参考资料，列于书末的参考文献中，在此谨向其作者表达衷心的感谢。 由于编者学识所限，书中定有不足之处，敬请读者批评指正，提出宝贵意见。