本书共10章，分别是绪论、线性表、栈和队列、串、多维数组和广义表、树、图、排序、查找和经典算法分析。全书的算法程序基于C和Java两种语言实现。本书的知识体系符合当前对该课程的主流认知，从文字组织及示例设置上，将本书划分为四个部分，基础理论、基础应用、常规应用和经典算法分析，既体现了由理论到实践的递进，又保证了内容的紧凑完整。本书是应用型本科教材，覆盖了“数据结构”课程绝大部分知识范畴，并给出了算法实现代码，对比较复杂的问题不仅给出了设计思路，还给出了具体示例分析，以帮助读者理解和掌握，因此，本书也适合工程技术人员参考使用，同时可以作为相关专业学生的考研辅导用书。

将“数据结构”课程多年的教学经验总结归纳成书，是编者的初衷。 “数据结构”作为计算机类相关专业学生的专业基础课程，具有较长的开课历史和较广的开设专业，同类教材也非常多，相比而言，本书具有以下一些特色。 （1）知识结构符合当前对该课程的主流认知。 （2）针对当前大学生编程课程普及，但对计算机工作原理掌握却比较薄弱这一特点，本书在编写中强调顺序存储与链式存储，以加强学生对内存管理及计算机工作原理的了解。 （3）强调函数的重要性，包括示例采用函数方式给出，解、栈在递归函数中的应用等，以加强模块化设计理念。 （4）重视内在逻辑性，从文字组织及示例设置上，本书内容隐性地分为四个部分：基础理论（第1、2章）、基础应用（第3～7章）、常规应用（第8、9章）、经典算法分析（第10章），既体现了由理论到实践的递进，又保证了72（56+16）课时的紧凑完整。 作为应用型本科专业基础课教材，“创新”并不是本书主要追求的目标。本书基于编者多年的教学经验，在介绍本课程的一些重点和难点基础上，针对不同内容设计解析过程，除文字描述外，还包括图示分析、示例演算、表格总结等，力求将问题讲清、讲透。其中，对于KMP算法，二叉树线索下的前驱后继的查找，图的遍历、最短路径、关键路径等内容的讲解，本书都不同于一般教材直接给出对应的公式或解决方案，而是从思维的习惯性出发，采用朴实的举例或说理，希望有助于读者的理解；基于完全二叉树提出类完全二叉树的概念，并有效应用在查找、排序算法的时效证明中。诸如此类的尝试，虽然在教学中实践了多次，但作为一本正式出版教材中的内容，我们对其进行了谨慎处理，首先由编写老师共同分析，再请学生参照其他教材阅读比较，给出心得体会和改进意见。每章结尾的小结，给出了具有启发意义的观点，以提高读者朋友深究、探索的兴趣。 本书第2版主要进行了以下改进。 （1）基于OBE理念，在每章前明确本章教学所要达到的目标及对应的教学方法和手段。 （2）算法描述和实现在保留原先C语言代码的基础上，对较复杂的算法又给出了Java代码。 （3）调整习题，修改错误。 由于过去我们一直采用由唐善策等主编的《算法与数据结构——用C语言描述》，所以，在编写本教材时，基本参照了该教材的组织架构，在此特别申明并表示感谢。其他参考文献，已列于本书最后，在此对相关作者一并表示感谢。 作为教材，本书第1～9章的内容作为本课程的传统知识体系，应该在课内讲授，但对于一些较为抽象、复杂的案例或拓展内容，如Josephus问题、链表交叉、迷宫问题，可以考虑选讲或不讲；算法的实现，尤其是比较复杂的算法实现，如哈夫曼树构造及编码、关键路径、二叉排序树等，可以作为学有余力的学生上机调试的参考内容；对一些抽象的问题，如图的遍历，最短路径，某些排序、查找算法，本书采用了事例、图表等多种手段进行演绎解释，若在某一步骤已讲授清楚，则可以忽略后面的说理举证。最后一章作为拓展知识，可以仅选择一两个算法进行讨论分析。 真心感谢电子工业出版社有限公司李静编辑的悉心审稿，她认真的工作态度、执着的精神，真实地感动了我们，也提高了我们对本书质量保证方面的信心。 即便如此，由于知识及能力的有限，疏漏及不足之处在所难免，恳请广大读者给出批评与建议，在此表示衷心感谢！ 编者邮箱：lgs@jit.edu.cn 编　　者 2022年10月

第1章 绪论 1 1.1　数据结构的概念 1 1.2　为什么要学习数据结构 3 1.3　算法 4 本章小结 7 本章习题 8 第２章　 线性表 10 2.1　基本概念与抽象数据类型 10 2.2　顺序表示 12 2.3　链式表示 14 2.4　单链表的改进和扩充 20 2.5　应用举例 23 2.6　链表相关操作的Java实现 27 本章小结 33 本章习题 33 第３章　 栈和队列 36 3.1　栈 36 3.2　队列 42 3.3　堆栈与队列的Java实现 52 本章小结 56 本章习题 56 第4章 　串 59 4.1　串的基本概念与抽象数据类型 59 4.2　串的存储结构 62 4.3　串运算的实现 66 4.4　KMP算法 69 本章小结 72 本章习题 73 第5章 　多维数组和广义表 74 5.1　多维数组 74 5.2　矩阵的压缩存储 76 5.3　广义表 84 本章小结 89 本章习题 89 第6章 　树 91 6.1　树、森林及其相关概念 91 6.2　二叉树及其相关特性 93 6.3　二叉树的存储 96 6.4　二叉树的遍历 99 6.5　线索二叉树 103 6.6　二叉树、树和森林之间的转换 108 6.7　哈夫曼树及其应用 110 6.8　二叉树相关操作的Java实现 118 本章小结 122 本章习题 122 第7章 　图 125 7.1　图的概念 125 7.2　图的存储 128 7.3　图的遍历 135 7.4　生成树和最小生成树 144 7.5　最短路径 153 7.6　拓扑排序 156 7.7　关键路径 159 7.8　相关算法的Java实现 165 本章小结 171 本章习题 171 第8章 　排序 175 8.1　基本概念 175 8.2　插入排序 177 8.3　交换排序 182 8.4　选择排序 188 8.5　归并排序 194 8.6　内部排序方法的比较和选择 198 8.7　排序算法的Java实现 199 本章小结 204 本章习题 204 第9章 　查找 207 9.1　线性表的查找 207 9.2　树表的查找 212 9.3　散列表的查找 225 9.4　散列表（链地址法）的Java实现 234 本章小结 235 本章习题 235 第10章 经典算法分析 238 10.1　分治算法 238 10.2　动态规划算法 241 10.3　贪心算法 245 10.4　回溯算法 249 10.5　分支限界算法 251 本章小结 255 本章习题 255 参考文献 256