《数据结构》(第二版)是“十二五”职业教育国家规划教材，也是新世纪高职高专教材编审委员会组编的计算机应用技术专业系列规划教材之一。
　　数据结构是计算机应用技术相关专业的核心专业基础课，主要研究数据在计算机中的表示和对数据的处理方法。其课程理论已经渗透到编译系统、操作系统、数据库、人工智能和计算机辅助设计等诸多应用领域，本课程的知识内容对学生今后工作的可持续发展有着重要影响。
　　数据结构课程的特点是知识丰富、内容抽象、理论性强。本课程可培养学生掌握处理数据和编写高效率软件的基本方法，同时还培养学生运用数据结构的理论和分析方法去解决相关实际问题的能力。
　　本教材的架构
　　本教材主要面向高职层次的在校学生。针对高职学生的特点，既要有严谨的理论学习，又要注重对实践能力的培养、训练，因此本教材设计了科学、合理的教材体系。我们选用“案例导引”→“知识传授”→“案例实现”→“案例训练”的架构编写教材。每一章都选用有应用价值、难度适中的案例，以引入教学内容，激发学生兴趣；然后，展开理论知识的学习；继而，通过学习的理论知识完成相应的案例；最后，在每章后给出习题和案例题，用于课后训练，以拓展教学深度和广度。这样的安排既提升了学生的学习兴趣，加强了实践训练，又能加强数据结构的原理和方法的学习。
　　本教材的内容
　　本教材共分9章：第1章绪论；第2章线性表；第3章栈和队列；第4章串；第5章数组和广义表；第6章树；第7章图；第8章查找；第9章排序。为了明确教学目的，每章开头都提出了知识目标和技能目标。在知识传授中，我们把要讲授的内容尽量通过图、表等形式予以表示，也安排了例题和小型案例，使读者更容易理解。内容排列由简到繁，由易到难，梯度明确。在知识安排上，考虑到不同基础学生的需求，有些内容设置了选讲或课后扩展，有“*”标注的可以选讲，有“**”标注的可以作为课后拓展。
　　本教材在第一版的基础上对部分内容做了充实和调整。例如：第5章更新了十字链表的表述；第9章增加了归并排序的性能分析等。
　　本教材的配套教学资源
　　为了多角度地促进教学，在纸质教材的基础上，编者整合出多种教学资源，提供给使用本教材的教师用于教学，也便于读者自学。读者可以到大连理工大学出版社教材服务网站免费下载。提供的教学资源有：教学大纲、教学计划、教学课件（含各章案例动态演示库）、教案、源代码、习题库、案例题库、模拟试题和拓展阅读等模块。
　　为了更好地服务教学，接受使用第一版师生的建议，在第二版中着重完成了各个章节对重点、难点知识点的微课设计。将全书所有的重点、难点知识用具有动画效果的课件完成，并聘请有丰富教学经验的一线教师录制成微课，为课堂教学、课后自学提供了方便。本教材共提供44个微课课堂。
　　本教材的特点
　　1.实用性强。充分考虑了各高职院校计算机及相关专业的教学特点，案例设计具有通用性和实用价值，能够引起学生的学习兴趣，调动学习主动性。
　　2.深入浅出，内容充实。知识安排由浅入深，运用分析、图表等多种方式，突破难点，使教师易教，学生易学。
　　3.对接行业标准，培养职业素养。所有案例均上机调试通过，并严格按软件工程规范编写，为学生今后的工作培养良好的习惯。
　　4.教材建设立体化。本教材由纸质教材和丰富的配套教学资源构成。
　　本教材的编者都是长期工作在教学一线的教师，教材中选用的案例和例题都经过了教学实践检验，但由于水平有限，教材中错误和疏漏之处在所难免，恳请广大读者批评指正。
　

第1章　绪　论 / 1
　1.1　数据结构的发展 / 1
　1.2　数据结构的意义 / 2
　1.3　数据结构概述 / 2
　　1.3.1　基本概念和术语 / 2
　　1.3.2　数据的逻辑结构 / 3
　　1.3.3　数据的存储结构 / 5
　　1.3.4　抽象数据类型 / 5
　1.4　算法及其分析 / 6
　　1.4.1　算　法 / 6
　　1.4.2　算法分析 / 7
　本章小结 / 9
　习　题 / 9

第2章　线性表 / 12
　案例导引 / 12
　2.1　线性表的逻辑结构 / 13
　　2.1.1　线性表的定义 / 13
　　2.1.2　线性表的抽象数据类型定义 / 14
　2.2　线性表的顺序存储结构 / 14
　　2.2.1　顺序表的结构 / 14
　　2.2.2　顺序表上实现的基本运算 / 15
　2.3　线性表的链式存储结构 / 20
　　2.3.1　链表的结构 / 20
　　2.3.2　单链表上实现的基本运算 / 21
　　2.3.3　循环链表 / 28
　　2.3.4　双链表 / 28
　2.4　顺序表与链表的比较 / 30
　2.5　案例实现——通信录管理 / 31
　　2.5.1　案例分析 / 31
　　2.5.2　案例实现1——用顺序表实现通信录管理 / 31
　　2.5.3　案例实现2——用链表实现通信录管理 / 36
　本章小结 / 43
　习　题 / 43
　案例题 / 45

第3章　栈和队列 / 47
　案例导引 / 47
　3.1　栈 / 48
　　3.1.1　栈的逻辑结构 / 48
　　3.1.2　顺序栈  / 49
　　3.1.3　链　栈 / 54
　　3.1.4　顺序栈和链栈的比较 / 56
　　3.1.5　栈的应用 / 56
　3.2　队　列 / 65
　　3.2.1　队列的逻辑结构 / 65
　　3.2.2　顺序队列 / 66
　　3.2.3　链队列 / 69
　　3.2.4　循环队列和链队列的比较 / 72
　　3.2.5　队列的应用——舞伴问题 / 72
　3.3　案例实现 / 78
　　3.3.1　案例1——汉诺塔问题 / 78
　　3.3.2　案例2——键盘缓冲区 / 81
　本章小结 / 83
　习　题 / 84
　案例题 / 87

第4章　串 / 91
　案例导引 / 91
　4.1　串的逻辑结构 / 91
　　4.1.1　串的定义 / 92
　　4.1.2　串的抽象数据类型 / 92
　　4.1.3　串的基本操作 / 93
　4.2　串的存储结构 / 95
　　4.2.1　串的定长顺序存储结构 / 95
　　4.2.2　串的堆分配存储结构 / 98
　　4.2.3　串的链式存储结构 / 100
　4.3　串的模式匹配 / 100
　　4.3.1　朴素的模式匹配算法 / 101
　　4.3.2　KMP算法** / 103
　4.4　案例实现——文本文件中单词的检索和计数 / 103
　　4.4.1　案例分析 / 103
　　4.4.2　案例实现 / 103
　本章小结 / 111
　习　题 / 111
　案例题 / 112

第5章　数组和广义表 / 113
　案例导引 / 113
　5.1　多维数组 / 114
　　5.1.1　多维数组的定义 / 114
　　5.1.2　数组的存储结构与寻址 / 114
　5.2　矩阵的压缩存储 / 115
　　5.2.1　特殊矩阵的压缩存储 / 116
　　5.2.2　稀疏矩阵的压缩存储 / 117
　5.3　广义表 / 123
　　5.3.1　广义表的逻辑结构 / 123
　　5.3.2　广义表的存储结构 / 124
　5.4　案例实现——稀疏矩阵的运算 / 127
　　5.4.1　案例分析 / 127
　　5.4.2　案例实现 / 127
　本章小结 / 133
　习　题 / 134
　案例题 / 135

第6章　树 / 137
　案例导引 / 137
　6.1　树的概述 / 138
　　6.1.1　树的定义和基本术语 / 138
　　6.1.2　树的抽象数据类型定义 / 140
　　6.1.3　树的存储结构 / 141
　6.2　二叉树 / 144
　　6.2.1　二叉树的定义 / 145
　　6.2.2　二叉树的基本性质 / 146
　　6.2.3　二叉树的抽象数据类型定义 / 148
　　6.2.4　二叉树的存储结构 / 149
　　6.2.5　二叉树遍历 / 151
　　6.2.6　二叉树遍历的应用 / 156
　6.3　树、森林与二叉树 / 158
　　6.3.1　树与二叉树的转换 / 159
　　6.3.2　森林与二叉树的转换 / 160
　　6.3.3　树与森林的遍历 / 161
　6.4　线索二叉树* / 162
　6.5　哈夫曼树及其应用 / 164
　　6.5.1　哈夫曼树 / 164
　　6.5.2　哈夫曼编码 / 166
　6.6　案例实现——团委人事管理系统 / 167
　　6.6.1　案例分析 / 167
　　6.6.2　案例实现 / 169
　本章小结 / 177
　习　题 / 178
　案例题 / 181

第7章　图 / 182
　案例导引 / 182
　7.1　图的逻辑结构 / 183
　　7.1.1　图的定义和基本术语 / 183
　　7.1.2　图的抽象数据类型定义 / 185
　7.2　图的存储结构 / 186
　　7.2.1　邻接矩阵 / 186
　　7.2.2　邻接表 / 188
　　7.2.3　十字链表 / 191
　　7.2.4　邻接多重表 / 192
　　7.2.5　边集数组 / 193
　　7.2.6　图的存储结构的比较 / 194
　7.3　图的遍历 / 195
　　7.3.1　深度优先搜索 / 195
　　7.3.2　广度优先搜索 / 196
　7.4　图的连通性 / 198
　　7.4.1　无向图的连通性 / 198
　　7.4.2　有向图的连通性 / 198
　　7.4.3　生成树和最小生成树 / 199
　7.5　图的应用 / 201
　　7.5.1　拓扑排序 / 201
　　7.5.2　关键路径 / 202
　　7.5.3　最短路径 / 204
　7.6　案例实现——课程信息管理 / 206
　　7.6.1　案例分析 / 206
　　7.6.2　案例实现 / 207
　本章小结 / 213
　习　题 / 213
　案例题 / 216

第8章　查　找 / 218
　案例导引 / 218
　8.1　查找的基本概念 / 219
　8.2　线性表的查找 / 220
　　8.2.1　顺序查找 / 220
　　8.2.2　二分查找 / 221
　　8.2.3　分块查找 / 224
　8.3　树表的查找 / 225
　　8.3.1　二叉排序树 / 225
　　8.3.2　平衡二叉树* / 232
　　8.3.3　B-树** / 233
　8.4　哈希表 / 235
　　8.4.1　哈希表的定义 / 235
　　8.4.2　哈希函数的构造方法 / 235
　　8.4.3　处理冲突的方法 / 237
　　8.4.4　哈希表的查找及分析 / 240
　8.5　案例实现——查找综合练习 / 241
　　8.5.1　案例分析  / 241
　　8.5.2　案例实现 / 242
　本章小结 / 249
　习　题 / 249
　案例题 / 254

第9章　排　序 / 255
　案例导引 / 255
　9.1　排序的基本概念 / 256
　9.2　插入排序 / 256
　　9.2.1　直接插入排序 / 257
　　9.2.2　二分插入排序 / 259
　　9.2.3　希尔排序 / 259
　9.3　交换排序 / 261
　　9.3.1　冒泡排序 / 261
　　9.3.2　快速排序 / 263
　9.4　选择排序 / 266
　　9.4.1　直接选择排序 / 266
　　9.4.2　堆排序 / 267
　9.5　归并排序 / 272
　9.6　基数排序 / 274
　9.7　排序方法的比较和选择 / 276
　　9.7.1　排序方法的比较 / 276
　　9.7.2　排序方法的选择 / 278
　9.8　案例实现——学生成绩管理系统的成绩排序 / 278
　　9.8.1　案例分析 / 278
　　9.8.2　案例实现 / 279
　本章小结 / 283
　习　题 / 284
　案例题 / 286

参考文献 / 288