《数据结构》（第四版）是“十四五”职业教育国家规划教材、“十三五”职业教育国家规划教材、“十二五”职业教育国家规划教材，也是高等职业教育计算机应用技术专业系列规划教材之一。《数据结构》（第四版）是在前三版的基础上，不断融合新思想、新技术完成的。

　　党的二十大报告中指出，坚持面向世界科技前沿、面向经济主战场、面向国家重大需求、面向人民生命健康，加快实现高水平科技自立自强。以国家战略需求为导向，集聚力量进行原创性引领性科技攻关，坚决打赢关键核心技术攻坚战。“数据结构”作为计算机相关专业的核心基础课，其知识内容是科技攻坚的基石，对后续课程的学习有着深远的影响。本教材将社会主义核心价值观、职业道德、工匠精神、团队合作等方面确定为引入课堂的思政元素，在教学中因势利导、潜移默化地引导学生将个人的成才梦有机融入实现中华民族伟大复兴的中国梦的思想认识。

　　数据结构主要研究数据在计算机中的表示和对数据的处理方法。其课程理论已经渗透到编译系统、操作系统、数据库、人工智能和计算机辅助设计等诸多应用领域，本课程的知识内容对学生今后工作的可持续发展有着重要影响。

　　数据结构课程的特点是知识丰富、内容抽象、理论性强。本课程可培养学生掌握处理数据和编写高效率软件的基本方法，同时还培养学生运用数据结构的理论和分析方法去解决相关实际问题的能力。

　　教材架构

　　本教材主要面向高职层次的在校学生。针对高职学生的特点，既要有严谨的理论学习，又要注重对实践能力的培养、训练，因此本教材设计了科学、合理的教材体系。我们选用“案例导引”→“知识传授”→“案例实现”→“案例训练”的架构编写教材。每一章都选用有应用价值、难度适中的案例，以引入教学内容，激发学生学习兴趣；然后，展开理论知识的学习；继而，通过学习的理论知识完成相应的案例；最后，在每章后给出习题，用于课后训练，以拓展教学深度和广度。这样的安排既提升了学生的学习兴趣，加强了实践训练，又加强了数据结构的原理和方法的学习。

　　教材内容

　　本教材共9章：绪论；线性表；栈和队列；串；数组和广义表；树；图；查找；排序。为了明确教学目的，每章开头都提出了知识目标、技能目标和素质目标。在知识传授中，我们把要讲授的内容尽量通过图、表等形式予以表示，也安排了例题和小型案例，使学生更容易理解。内容安排由简到繁，由易到难，梯度明确。在知识安排上，考虑到不同基础学生的需求，有些内容设置了选讲或课后扩展，有“*”标注的可以选讲，有“**”标注的可以作为课后拓展。

　　本教材在第三版的基础上对部分内容做了调整和充实。例如：第3章更新了循环队列的处理等，并调整修正了全书所有的代码。本教材所有案例代码均按C99标准编写，在DEV C、CodeBlocks平台均调试通过。本教材以可伸缩的智慧树形式为学生提供了分章节的思维导图，有助于教师教学总结和学生复习。

　　为培养学生综合运用理论知识、增强实践能力、提高创新思维，教材中设置了综合案例——学生毕业论文信息检索系统。该案例综合运用了教材中的多项内容，有利于提升学生的综合实践能力，增强学生自信心。限于篇幅，以电子活页形式提供，感兴趣的同学可以扫码观看、学习和实践。

　　配套资源

　　为了多角度地促进教学，在纸质教材的基础上，编者整合出多种教学资源，提供给使用本教材的教师用于教学，也便于学生自学。师生可以到职教数字化服务平台免费下载。提供的教学资源有：教学大纲、教学计划、教学课件（含各章案例动态演示库）、教案、源代码、思维导图、习题答案、课后习题库、案例题库、模拟试题和拓展阅读等模块。

　　本教材共提供了43个微课，将全书所有的重点、难点知识用具有动画效果的课件完成，并聘请有丰富教学经验的一线教师录制成微课，为课堂教学、课后自学提供了方便。

　　在编写本教材的过程中，编者参考、引用和改编了国内外出版物中的相关资料以及网络资源，在此表示深深的谢意！相关著作权人看到本教材后，请与出版社联系，出版社将按照相关法律的规定支付稿酬。

　　本教材的编者都是长期工作在教学一线的教师，教材中选用的案例和例题都经过了教学实践检验，但由于水平有限，教材中错误和疏漏之处在所难免，恳请广大读者批评指正。

　　编  者

　　2024年7月

第1章  绪  论 / 1

  1.1  数据结构的发展 / 1

  1.2  数据结构的意义 / 2

  1.3  数据结构概述 / 2

  1.4  算法及其分析 / 6

  本章小结 / 10

  习  题 / 10

第2章  线性表 / 13

  2.1  案例导引 / 13

  2.2  线性表的逻辑结构 / 14

  2.3  线性表的顺序存储结构 / 16

  2.4  线性表的链式存储结构 / 21

  2.5  顺序表与链表的比较 / 31

  2.6  案例实现：通信录管理 / 32

  本章小结 / 44

  习  题 / 44

第3章  栈和队列 / 47

  3.1  案例导引 / 47

  3.2  栈 / 49

  3.3  队  列 / 66

  3.4  案例实现：汉诺塔问题和机器翻译 / 79

  本章小结 / 85

  习  题 / 85

第4章  串 / 90

  4.1  案例导引 / 90

  4.2  串的逻辑结构 / 91

  4.3  串的存储结构 / 94

  4.4  串的模式匹配 / 100

  4.5  案例实现：文本文件中单词的检索和计数 / 103

  本章小结 / 110

  习  题 / 111

第5章  数组和广义表 / 113

  5.1  案例导引 / 113

  5.2  多维数组 / 114

  5.3  矩阵的压缩存储 / 116

  5.4  广义表 / 123

  5.5  案例实现：稀疏矩阵的运算 / 128

  本章小结 / 134

  习  题 / 134

第6章  树 / 137

  6.1  案例导引 / 138

  6.2  树的概述 / 138

  6.3  二叉树 / 145

  6.4  树、森林与二叉树 / 159

  6.5  线索二叉树* / 162

  6.6  哈夫曼树及其应用 / 164

  6.7  案例实现：团委人事管理系统 / 168

  本章小结 / 178

  习  题 / 179

第7章  图 / 182

  7.1  案例导引 / 182

  7.2  图的逻辑结构 / 183

  7.3  图的存储结构 / 186

  7.4  图的遍历 / 195

  7.5  图的连通性 / 198

  7.6  图的应用 / 201

  7.7  案例实现：课程信息管理 / 207

  本章小结 / 214

  习  题 / 214

第8章  查  找 / 217

  8.1  案例导引 / 217

  8.2  查找的基本概念 / 218

  8.3  线性表的查找 / 219

  8.4  树表的查找 / 224

  8.5  哈希表 / 234

  8.6  案例实现：查找综合练习 / 240

  本章小结 / 248

  习  题 / 248

第9章  排  序 / 254

  9.1  案例导引 / 254

  9.2  排序的基本概念 / 255

  9.3  插入排序 / 256

  9.4  交换排序 / 260

  9.5  选择排序 / 265

  9.6  归并排序 / 271

  9.7  基数排序 / 274

  9.8  排序方法的比较和选择 / 276

  9.9  案例实现：学生成绩管理系统的成绩排序 / 278

  本章小结 / 283

  习  题 / 284

参考文献 / 287