数据结构课程对计算机相关专业来讲是专业基础课，并因其重要性被广泛作为学位课和考研课。数据结构的研究范畴涵盖典型的逻辑结构、这些逻辑结构在计算机中的实现、算法分析及典型算法与应用等。逻辑结构用于研究对象的抽象与建模，存储设计的好坏直接决定问题求解的难易和算法性能，这些都是用计算机解决问题时不可或缺的知识与技能。因此，从课程研究内容看，数据结构课程是一门程序设计基础课，也是程序设计能力提升的进阶课。正因为该课程的重要性，已出版的《数据结构》教材林林总总，且其发展从未停息。2010年，本教学团队出版了《数据结构》（ISBN: 9787302214755）、《数据结构实践教程》（ISBN: 9787302214762）、《数据结构习题及学习指导》（ISBN: 9787302214779）系列教材。十多年过去了，时代发展对工科人才培养的要求不断变化着。变化的时代和变化的学生使我们积累了与时俱进的教学经验。在获得首批线下一流本科课程荣誉之际，编者决定重写《数据结构》教程及修订相关系列教材。为契合新工科人才培养需要和工程专业认证对计算机类学生的毕业要求，本教材立足于实用，以可读可学可教可研可练为宗旨设计编排内容并将教材取名为《数据结构原理与应用》。
●可读。撰写过程中，从多方面考虑教材的可读性。概念及原理等新知识的介绍首先以文字陈述，并做到精准、简明、扼要，直明要义；然后以示例展示，将概念及原理具化，使知识一目了然。所有内容尽可能图文并茂。此外，为了简洁和增加可读性且考虑专业特性，本教材选用C/C 语言，但不拘泥于两者的严格语法，集两者优点呈现算法。 ●可学。首先，在算法描述上，教材选用了对学习者要求较低的面向过程的方法，但借用模板概念解决数据类型的抽象问题。这里主要考虑到面向对象的程序设计有完整的理论体系和架构，用它描述和理解算法对学生要求很高。而在数据结构课程中，语言本身只是一个工具。面向过程的描述进一步简化语法部分，突出问题求解本身，降低学习难度。其次，各种结构都有丰富的应用背景，满足学生希冀获取解决问题的方法及学得可用知识与技能的本能愿望。学生通过理解、记忆、验证、模仿、思考能切实感到收获。
●可教。用实际教学中积累的思路设计与组织教材内容，例如算法讲解给出算法的来龙去脉。首先根据算法思想分析存储设计和辅助变量设计，再给出算法设计，并且将算法步骤与算法描述一一对应，呈现代码的生成过程。教材中大量的图示及应用示例为教师教学提供了丰富的教学素材，教辅PPT将尽量展示算法执行过程。
●可研。许多算法介绍后都设置了算法讨论部分，提出相关问题或更深层次的问题，拓展教学深度与广度，引导思考与研究。例如在用顺序表实现一元多项式求和问题中，在算法讨论部分抛出一元稀疏多项式求和的问题以激发思考，也为后续新知识进行铺垫，增加教材内容的连贯性。
●可练。教材提供多层次的练习素材。填空题用于复习理论知识和加深对原理的理解；简答题与应用题用于知识的应用与分析能力的训练；算法设计题与上机练习题用于设计与编程技能训练。多层次的练习题可满足学习者各层次上的需求。
总之，这是一本考虑当下聚焦的应用型和创新型人才培养需要，以可用实用为宗旨的一部具有时代气息的教材。教材的配套资源有教学PPT、书中算法实现的源码、实践教程等。另应新时代发展需求，后期会提供微课。
后感谢教学团队老师的精诚合作与辛苦付出。周建美编写了第3章和第4章，季峰和陈森博编写了第6章，丁红编写了第7章，徐慧编写了其余章节并进行全稿统稿。团队其他老师（如管致锦教授、顾颀博士、朱玲玲副教授、陈德裕副教授等）参与了本书的审稿工作，在此也谢谢他们的宝贵意见。
虽然竭尽所能，但由于编者知识、能力和时间有限，书中仍难免有疏漏和不足之处，欢迎专家和读者批评指正。
编者2021年7月
徐慧，女，博士，南通大学教授，硕士生导师。从事《数据结构》等课程教学二十多年。主持的《数据结构》课程，获2020国家一流线下课程。
长期以来，专研教学、教研，积累了丰富的教学经验与个性。教学深受学生喜爱。
教学中，主创了多项高质量的教学资源,如 :《数据结构》课程PPT获省优秀多媒体奖；微课数据结构之线性表获2019江苏省优秀微课奖。
主编《数据结构》、《数据结构实践教程》；参编《微机原理》，具备一定的教材编写基础。
第1章绪论1
1.1课程属性与术语1
1.1.1数据结构是程序的重要组成部分1
1.1.2数据结构是提升编程能力的2
1.1.3数据结构与术语2
1.1.4数据结构决定算法4
1.2数据结构的研究内容4
1.2.1逻辑结构5
1.2.2存储结构/物理结构6
1.2.3逻辑结构与物理结构的关系7
1.2.4非数值计算问题8
1.2.5数据结构与程序设计的关系10
1.3抽象数据类型11
1.3.1抽象数据类型的定义11
1.3.2抽象数据类型的实现12
1.4算法与算法分析13
1.4.1算法的概念13
1.4.2算法描述13
1.4.3算法性能分析15
1.5小结20
习题121
第2章线性表25
2.1线性表的定义25
2.1.1线性表的逻辑特性25
2.1.2线性表的抽象数据类型26
2.2顺序表28
2.2.1顺序表的定义28
2.2.2顺序表的存储设计29
2.2.3顺序表的操作及实现30
2.2.4顺序表应用举例36
2.3链表39
2.3.1单链表的定义及特性39
2.3.2单链表的存储设计40
2.3.3单链表的操作及实现41
2.3.4其他形式的链表50
2.3.5链表应用举例53
2.4顺序表与链表的比较57
2.4.1空间性能比较58
2.4.2时间性能比较58
2.4.3环境性能比较58
2.5小结58
习题259
第3章栈和队列63
3.1栈63
3.1.1栈的定义和特点63
3.1.2顺序栈65
3.1.3链栈69
3.1.4顺序栈和链栈的比较73
3.1.5栈的应用73
3.2队列80
3.2.1队列的定义和特点80
3.2.2循环队列81
3.2.3链队85
3.2.4循环队列与链队列的比较89
3.2.5队列的应用89
3.3小结91
习题392
第4章数组和矩阵95
4.1多维数组95
4.1.1数组的定义95
4.1.2数组的顺序存储97
4.2特殊矩阵99
4.2.1对称矩阵100
4.2.2三角矩阵100
4.2.3对角矩阵101
4.3稀疏矩阵102
4.3.1三元组表顺序存储102
4.3.2带行指针向量的链式存储105
4.3.3十字链表108
4.4小结109
习题4110
第5章树和二叉树113
5.1树114
5.1.1树的定义与表示114
5.1.2树的术语115
5.1.3树的抽象数据类型116
5.1.4树的存储设计118
5.1.5树和森林的遍历120
5.2二叉树的定义与特性121
5.2.1二叉树的定义121
5.2.2特殊二叉树122
5.2.3二叉树的性质123
5.2.4二叉树的抽象数据类型125
5.3二叉树的存储结构127
5.4二叉树操作129
5.4.1二叉树遍历129
5.4.2根据遍历序列确定二叉树137
5.4.3先、中、后序遍历的非递归算法139
5.4.4二叉树的其他操作145
5.5线索二叉树148
5.5.1线索二叉树的定义148
5.5.2线索二叉树的建立149
5.5.3线索二叉树的遍历151
5.6树和森林与二叉树的相互转换154
5.6.1树与二叉树相互转换154
5.6.2森林与二叉树相互转换156
5.7二叉树及其应用157
5.7.1基本概念157
5.7.2构造二叉树158
5.7.3哈夫曼编码164
5.8小结167
习题5168
第6章图171
6.1图的定义及相关术语171
6.1.1图的定义171
6.1.2图的术语172
6.1.3图的抽象数据类型176
6.2图的存储及操作177
6.2.1邻接矩阵表示法及操作举例177
6.2.2邻接表表示法及操作举例181
6.2.3十字链表表示法及操作举例184
6.2.4邻接多重表表示法及操作举例186
6.3图的遍历及应用189
6.3.1深度优先遍历189
6.3.2广度优先遍历192
6.3.3遍历应用举例195
6.4图的应用199
6.4.1小生成树199
6.4.2短路径205
6.4.3AOV网与拓扑排序211
6.4.4AOE网与关键路径216
6.5小结220
习题6221
第7章查找225
7.1查找的基本概念225
7.1.1术语225
7.1.2查找性能226
7.2线性表查找技术227
7.2.1顺序查找227
7.2.2折半查找228
7.2.3串的模式匹配231
7.3树表查找236
7.3.1二叉排序树236
7.3.2平衡二叉树243
7.4散列查找247
7.4.1散列函数的构造方法248
7.4.2处理冲突的方法250
7.4.3散列表的查找253
7.5小结255
习题 7256
第8章排序259
8.1排序的基本概念259
8.1.1排序的定义260
8.1.2内排序与外排序261
8.1.3排序性能261
8.1.4内部排序方法的分类262
8.1.5待排序记录的存储方式262
8.2插入排序262
8.2.1直接插入排序263
8.2.2折半插入排序265
8.2.3希尔排序267
8.3交换排序268
8.3.1冒泡排序269
8.3.2快速排序271
8.4选择排序275
8.4.1简单选择排序275
8.4.2树形选择排序277
8.4.3堆排序279
8.5归并排序284
8.6基数排序287
8.6.1分配排序287
8.6.2多关键码排序288
8.6.3基数排序详解289
8.7各种排序方法的比较291
8.7.1性能比较292
8.7.2方法选用293
8.8小结294
习题8294
附录术语表297
参考文献301
书单推荐
