本书用深入浅出的语言从普通高校学生的学习需求出发，介绍了数据结构的相关知识。本书分为六个部分，从基础知识、线性数据结构、非线性数据结构、数据结构中的重要运算、多维数据结构及大数据数据结构等内容。本书适合作为高等院校计算机及相关专业数据结构课程的教材，也可作为技术人员的自学教材。

本书围绕为什么要学习数据结构、有哪些主要的数据结构、它们有什么用、如何高效地运用它们求解实际问题等内容进行框架设计和编写的。本书的写作目标是帮助读者建立计算思维，学会如何利用计算机求解实际问题。
本书特色：
充分运用实例法深入浅出、形象地讲解各种数据结构。
针对一个讲解实例给出不同的求解方案，让读者能够了解如何选择合适的数据结构求解问题，并切身体会采用同一种数据结构的不同存储结构实现同一个算法在执行效率和编程难度上的差异。
以问题驱动的方式讲解非线性结构存储映射等问题，引导读者逐步进行深入思考，帮助读者建立计算思维，使得读者不仅知其然，而且知其所以然。
以图形跟踪演示的方式介绍算法思想，帮助读者理解和掌握相关算法。
为每个重要知识点准备了大量的思考题和习题，帮助读者对相关知识点进行深入思考和理解，训练读者的发散性思维。
为了方便读者的学习，本书特别增加了“预备知识”部分，这一部分介绍了在学习数据结构时读者可能需要用到的一些数学知识和程序设计方面的知识。

计算机在社会各领域的应用已经无处不在。计算机需要加工处理的数据越来越复杂、规模也越来越大，对数据组织和处理的效率提出了更高的要求。在计算机科学中，数据结构是一种在计算机中组织、存储数据，以便高效利用这些数据的有效方式，它是许多高效算法的基本要素，几乎所有的程序或软件系统都要用到数据结构。“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。1968年，美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧：第1卷基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。数据结构课程是计算机科学的基础核心课程，它对于外围课程的知识与经验具有迁移性、衍生性，并对学生自学知识和获取实践经验具有基础性、发展性。该课程教学的突出难点是知识的抽象性和动态性，学习过程也是复杂程序设计的训练过程，理论性和实践性均较强，被认为是比较难学的课程。对学生来说，学习这门课程的主要难度体现在，不知道如何根据实际问题选择合适的数据结构（包括两个层次，如何选择合适的数据逻辑结构构建问题模型和如何选择合适的数据存储结构实现求解问题模型的算法）和如何应用选择的数据结构进行问题的求解（当然，这个问题还需要“算法设计与分析”这门课程来进一步解决）。
基于上述考虑，本书充分运用实例法深入浅出、形象地讲解各种数据结构，针对一个讲解实例给出了不同的求解方案，让读者能够了解如何选择合适数据结构求解问题，并切身体会采用同一种数据结构的不同存储结构实现同一个算法在执行效率和编程难度上的差异，从而激发学生的学习兴趣和热情。而且，以问题驱动的方式引导学生进行逐步深入思考，有利于帮助学生建立计算思维，使得他们不仅知其然，而且知其所以然。
本书分为四个部分共12章。第一部分包括第1章和第2章，主要介绍数据结构的概念、算法的概念、数据结构和算法之间的密切关联以及简单的算法分析。第二部分包括第3～7章，这一部分以“线性表”为主线分别详细讨论了六种常见的线性结构。第三部分介绍了非线性结构中树（第8章）、二叉树（第9章）和图（第10章）的基本概念、存储结构、一些基本操作的实现以及它们的经典应用。第四部分介绍了查找（第11章）和排序（第12章）的各种常用算法，同时展现了各种数据结构的完美应用。
本书在内容组织上力求丰富充实、科学合理，符合学生的认知规律，力求将每种数据结构分析透彻。在语言描述上力求深入浅出、简单明了。为了帮助学生理解和掌握各种数据结构，书中列举了大量的思考题、例题和习题。本书主要采用面向过程的C语言作为数据结构和算法的描述手段，在保持C语言优点的同时尽量使算法描述简单清晰。
与本书配套的资料有书中程序的源代码、习题参考答案以及电子课件等，教师可登录华章网站下载。
本书第1～10章主要由湖北工业大学沈华博士编写，第11～12章主要由湖南工业大学文志诚博士编写，湖北工业大学杨晓艳博士对书中代码进行了校验，全书由湖北工业大学张明武教授修改定稿。
在本书的编写中，负责本书编辑出版工作的机械工业出版社华章分社策划编辑、教材部副主任朱劼老师和佘洁编辑付出了大量辛勤的劳动。武汉大学何炎祥教授在百忙之中认真审阅了全书，提出了许多宝贵和中肯的意见。在此，谨向每一位关心和支持本书编写工作的各位朋友、老师表示衷心的谢意！
由于作者的知识和写作水平有限，书中难免有错误和不足之处，恳请各位专家、读者批评指正。作者E-mail：nancy78733@126.com。

沈华
2015年4月于武汉南湖

计算机\数据结构

本书主要是围绕为什么要学习数据结构、有哪些主要的数据结构、它们有什么用、如何高效地运用它们求解实际问题等进行框架设计和内容编写的。换句话说，本书作者的写作目标是帮助读者建立计算思维，学会如何利用计算机求解实际问题。
本书特色
1.充分运用实例法深入浅出、形象地讲解各种数据结构；
2.针对一个讲解实例给出不同的求解方案，让读者能够了解如何选择合适的数据结构求解问题，并切身体会采用同一种数据结构的不同存储结构实现同一个算法在执行效率和编程难度上的差异；
3.以问题驱动的方式讲解非线性结构存储映射等问题，引导读者逐步进行深入思考，帮助读者建立计算思维，使得读者不仅知其然，而且知其所以然；
4.以图形跟踪演示的方式介绍算法思想，帮助读者理解和掌握相关算法；
5.为每个重要知识点准备了大量的思考题和习题，帮助读者对相关知识点进行深入思考和理解，训练读者的发散性思维；
6.为了方便读者的学习，本书特别增加了“预备知识”部分，这一部分介绍了在学习数据结构时读者可能需要用到的一些数学知识和程序设计方面的知识。

序
前言
教学建议
第一部分概论部分
第1章数据结构3
11什么是数据3
12什么是数据结构3
121数据的逻辑结构3
122数据的存储结构6
123数据的运算8
13什么是数据类型9
14什么是抽象数据类型9
15知识点小结10
习题10
第2章算法11
21什么是算法11
22算法的描述11
23算法的性能分析12
231时间复杂度13
232渐近符号13
233空间复杂度15
234复杂度分析举例15
24算法的性能度量18
241性能度量的方法18
242生成测试数据19
25知识点小结19
习题19
第二部分线性部分
第3章线性表22
31线性表抽象数据类型22
311线性表的逻辑结构22
312线性表的基本运算22
313线性表的ADT描述23
32线性表的应用——两个一元多项式相加24
321问题描述与分析24
322问题求解25
33线性表的实现26
331顺序表26
332单链表41
333静态单链表52
334一元多项式相加问题的求解实现56
34线性表的其他实现及应用场景分析69
341双（向）链表69
342循环单（向）链表71
343循环双（向）链表74
35知识点小结75
习题75
第4章栈77
41栈抽象数据类型77
411栈的逻辑结构77
412栈的基本运算78
413栈的ADT描述78
42栈的应用——表达式求解79
421问题描述与分析79
422问题求解79
43栈的实现85
431顺序栈85
432链栈88
433在表达式求解问题上的性能分析与比较91
44顺序栈的一种有趣实现——两个方向生长的栈91
45栈与递归的天然联系92
46知识点小结93
习题93
第5章队列95
51队列抽象数据类型95
511队列的逻辑结构95
512队列的基本运算95
513队列的ADT描述96
52队列的应用——模拟舞伴配对问题96
521问题描述与分析96
522问题求解97
53队列的实现97
531顺序队列97
532循环队列101
533链队列107
54双端队列及队列应用场景举例110
541双端队列110
542队列应用场景举例111
55知识点小结111
习题112
第6章串113
61串抽象数据类型113
611串的逻辑结构113
612串的基本运算113
613串的ADT描述114
62串的实现114
621串的顺序存储表示114
622串的堆分配存储表示118
623串的块链存储表示120
63串的模式匹配124
631朴素的模式匹配算法124
632KMP算法128
64知识点小结133
习题133
第7章数组及广义表134
71数组的类型定义134
711数组的定义134
712数组的性质134
713数组的基本运算134
72多维数组的线性存储方法135
73特殊矩阵的压缩存储138
731特殊形状矩阵的压缩存储138
732随机稀疏矩阵的压缩存储及其运算142
74广义表154
741广义表的基本概念154
742广义表的性质155
743广义表的基本运算155
744广义表的存储结构156
75知识点小结159
习题159
第三部分非线性部分
第8章树与森林162
81认识树162
811（根）树的定义162
812基本术语163
813树的基本运算164
82树的实现167
821需要解决的关键问题167
822关键问题的求解思路167
823树的存储结构167
824存储方案的比较分析178
83树的创建178
831问题描述与分析178
832问题求解179
84树的遍历180
841问题描述与分析180
842问题求解180
85树的应用181
851并查集181
852等价类182
853决策树184
86森林184
87知识点小结185
习题185
第9章二叉树186
91认识二叉树186
911二叉树的定义186
912二叉树的基本运算187
913二叉树的性质189
92二叉树的实现194
921需要解决的关键问题194
922关键问题的求解思路195
923二叉树的存储结构195
924方案的比较分析203
93二叉树的创建203
931问题描述与分析203
932问题求解203
94二叉树的遍历204
941问题描述与分析204
942问题求解208
943二叉树遍历应用举例211
95线索二叉树215
951线索二叉树的应用需求215
952二叉树的线索化217
953线索二叉树上的运算219
96二叉树的应用227
961哈夫曼树及其应用227
962二叉排序树及其应用233
963平衡二叉树236
97树、森林与二叉树的关系241
971树、森林与二叉树的相互转换241
972树、森林与二叉树在遍历运算上的关系244
98知识点小结244
习题245
第10章图246
101认识图246
1011图的定义246
1012基本术语246
1013图的基本运算252
102图的实现253
1021需要解决的关键问题253
1022关键问题的求解思路253
1023图的存储结构254
1024存储方案的比较分析261
103图的创建262
1031问题描述与分析262
1032问题求解262
104图的遍历264
1041问题描述与分析264
1042深度优先搜索遍历265
1043广度优先搜索遍历272
1044图遍历的应用277
105生成树277
1051连通图的生成树277
1052连通网的最小生成树278
106最短路径280
1061单源最短路径281
1062每对顶点间的最短路径284
1063最短路径应用举例288
107有向无环图及其应用288
1071AOV网与拓扑排序288
1072AOE网与关键路径290
108知识点小结293
习题293
第四部分重要运算部分
第11章查找296
111查找的基本概念296
112静态查找297
1121顺序查找297
1122二分查找299
1123分块查找303
113动态查找304
114散列技术312
1141散列表的概念312
1142散列函数的构造方法312
1143处理冲突的方法312
1144散列表的查找315
1145散列表的应用317
115知识点小结318
习题318
第12章排序319
121排序的基本概念319
122插入排序321
1221直接插入排序321
1222希尔排序324
123交换排序325
1231冒泡排序325
1232快速排序327
124选择排序330
1241直接选择排序330
1242树形选择排序332
1243堆排序333
125归并排序338
1251（内部）归并排序338
1252外部归并排序339
126分配排序339
1261箱排序339
1262基数排序339
127各种（内部）排序方法的比较341
128知识点小结342
习题342
参考文献344