本书系统地介绍数据结构基础理论知识及算法设计方法，第1～9章从抽象数据类型的角度讨论各种基本类型的数据结构及其应用，主要包括线性表、栈和队列、串、数组和广义表、树和二叉树、图及图算法；第10章和第11章主要讨论查找和排序的各种实现方法及其综合比较；附录给出全书习题中选择、判断、填空题的参考答案。全书采用C语言作为数据结构和算法的描述语言。
　　本书在内容选取上符合人才培养目标的要求及教学规律和认知规律，在组织编排上体现“先理论、后应用、理论与应用相结合”的原则，并兼顾学科的广度和深度，力求适用面广。本书具有结构严谨、层次清楚、概念准确、深入浅出、描述清晰等特点。

更多科学出版社服务，请扫码获取。

　　“数据结构”课程是计算机类、电子信息类及相关专业的专业基础课。它在整个课程体系中处于承上启下的核心地位：一方面扩展和深化在离散数学、程序设计语言等课程学到的基本技术和方法；另一方面为进一步学习操作系统、编译原理、数据库等专业知识奠定坚实的理论与实践基础。本课程在教给学生数据结构设计和算法设计的同时，培养学生的抽象思维能力、逻辑推理能力和形式化思维方法，增强分析问题、解决问题和总结问题的能力，更重要的是培养专业兴趣，树立创新意识。本教材在内容选取上符合人才培养目标的要求及教学规律和认知规律，在组织编排上体现“先理论、后应用、理论与应用相结合”的原则，并兼顾学科的广度和深度，力求适用面广泛。
　　全书共11章。第1章综述数据、数据结构和抽象数据类型等基本概念及算法描述与分析方法；第2～9章主要从抽象数据类型的角度分别讨论线性表、栈和队列、串、数组和广义表、树和二叉树、图等基本类型的数据结构及其应用；第10章和第11章讨论查找和排序的各种方法，着重从时间性能、应用场合及使用范围方面进行分析和比较。本书对数据结构众多知识点的来龙去脉做了详细解释和说明；每章后面配有难度各异的习题，并在附录中给出习题的参考答案，供读者理解知识及复习提高之用。全书采用C语言描述数据结构和算法。
　　从课程性质上讲，“数据结构”是高等院校计算机科学、电子信息科学及相关专业教学计划中的一门专业基础课；其教学要求是学会分析研究计算机加工的数据结构的特性，以便为实际应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时空分析技术。从课程学习上讲，“数据结构”的学习是复杂程序设计的训练过程；其教学目的是着眼于原理与应用的结合，在深化理解和灵活掌握教学内容的基础上，学会把知识用于解决实际问题，书写出符合软件工程规范的文件，编写出结构清晰及正确易读的程序代码。可以说，“数据结构”比“高级程序设计语言”等课程有着更高的要求，它更注重培养分析抽象数据的能力。
　　本书是编者多年从事该课程教学工作的教学成果，编者都是具有副教授以上职称、有15年以上该课程教学经验的一线教师。本书由任志国担任主编、赵传成、蓝才会、祁建宏、达文姣、岳秋菊、刘君担任副主编。其中的第1章、第2章、第5章、第7章、第8章、第9章由任志国编写，第3章由赵传成编写，第4章由岳秋菊编写，第6章由达文姣编写，第10章由蓝才会编写，第11章由祁建宏编写，所有章节习题部分由刘君编写。在本书的构思与编写过程中，得到了安天庆教授、党建武教授、王治和教授的帮助，在算法的实现与调试以及插图的制作过程中，得到了杨业、史淑娟、宗小兵等研究生的帮助，在此表示感谢。

目录
前言
第1章　绪论　1
1.1　引言　1
1.2　数据结构的基本概念　3
1.2.1　有关概念和术语　4
1.2.2　数据的逻辑结构　4
1.2.3　数据的存储结构　5
1.2.4　数据的运算　5
1.3　数据类型和抽象数据类型　6
1.3.1　数据类型　6
1.3.2　抽象数据类型　7
1.4　算法　8
1.4.1　算法及其特征　8
1.4.2　常见的算法描述方法　9
1.4.3　常见的算法设计方法　10
1.5　算法性能分析与度量　10
1.5.1　时间复杂度　11
1.5.2　空间复杂度　14
1.6　关于学习数据结构　14
1.6.1　数据结构课程的地位　14
1.6.2　数据结构课程体系　15
1.6.3　数据结构课程学习特点　15
习题一　16
第2章　线性表　19
2.1　线性表的类型定义　19
2.1.1　线性表的定义　19
2.1.2　线性表的抽象数据类型　20
2.2　线性表的顺序存储及基本操作　21
2.2.1　线性表的顺序存储结构　21
2.2.2　顺序表及相关操作的实现　23
2.2.3　顺序表应用举例　28
2.2.4　线性表顺序存储结构分析　29
2.3　线性表的单链表存储结构　29
2.3.1　线性表的单链表存储结构　30
2.3.2　单链表上相关操作的实现　31
2.3.3　链表应用举例　36
2.3.4　链式存储结构的分析　39
2.4　双链表与其他链式结构　39
2.4.1　线性表的双链表存储结构　39
2.4.2　双链表上相关操作的实现　40
2.4.3　循环链表　43
2.4.4　静态链表　44
2.5　一元多项式的表示及运算　45
2.5.1　一元多项式的表示及存储　45
2.5.2　一元多项式创建与打印　46
2.5.3　一元多项式相加　47
2.5.4　一元多项式相乘　48
习题二　50
第3章　栈　53
3.1　栈的定义及基本运算　53
3.1.1　栈的定义　53
3.1.2　栈的抽象数据类型　53
3.2　顺序栈　54
3.2.1　顺序栈的定义及存储结构　54
3.2.2　顺序栈的基本操作　55
3.3　链栈　57
3.3.1　链栈的定义及存储结构　57
3.3.2　链栈的基本操作　58
3.4　共享栈与多栈　60
3.4.1　共享栈　60
3.4.2　多链栈　63
3.5　栈的应用　65
3.5.1　栈的简单应用　65
3.5.2　栈与递归　70
习题三　71
第4章　队列　74
4.1　队列的定义及基本运算　74
4.1.1　队列的定义　74
4.1.2　队列的抽象数据类型　74
4.2　循环队列　75
4.2.1　循环队列的存储实现　75
4.2.2　循环队列的基本操作　77
4.2.3　动态循环队列　79
4.3　链队列　80
4.3.1　链队列的定义及存储结构　80
4.3.2　链队列的基本操作　81
4.4　队列的其他存储结构　82
4.4.1　循环多队列　82
4.4.2　动态循环多队列与链式多队列　84
4.5　队列的应用　84
习题四　85
第5章　串　88
5.1　串的定义及其基本运算　88
5.1.1　串的定义　88
5.1.2　串的抽象数据类型　88
5.2　串的定长顺序存储　90
5.2.1　定长顺序存储的定义　90
5.2.2　定长顺序串的基本运算　90
5.3　串的模式匹配算法　95
5.3.1　简单模式匹配算法——BF算法　95
5.3.2　改进的模式匹配算法——KMP算法　96
5.4　串的堆存储结构　100
5.4.1　堆存储结构的定义　100
5.4.2　基于堆结构的基本运算　101
5.5　串的块链存储结构　104
5.5.1　块链存储结构的定义及其存储结构　104
5.5.2　基于块链结构的基本运算　105
5.6　串的应用　113
习题五　113
第6章　数组和广义表　116
6.1　数组的概念和存储　116
6.1.1　数组的概念　116
6.1.2　数组的存储结构　117
6.2　特殊矩阵的压缩存储　121
6.2.1　对称矩阵的压缩存储　121
6.2.2　三角矩阵的压缩存储　122
6.2.3　带状矩阵的压缩存储　123
6.3　稀疏矩阵的压缩存储　124
6.3.1　稀疏矩阵的三元组表存储　125
6.3.2　稀疏矩阵的十字链表存储　128
6.4　广义表　133
6.4.1　广义表的基本概念　133
6.4.2　广义表的基本运算　135
6.4.3　广义表的存储结构　136
6.4.4　广义表上的基本算法　138
习题六　140
第7章　二叉树和树　144
7.1　二叉树的定义与性质　144
7.1.1　二叉树的基本概念　144
7.1.2　二叉树的主要性质　146
7.1.3　二叉树的抽象数据类型　147
7.2　二叉树的存储结构及创建　148
7.2.1　顺序存储结构　148
7.2.2　二叉树的链式存储结构　150
7.2.3　二叉树的创建算法　151
7.3　二叉树的遍历及应用　152
7.3.1　二叉树的遍历　152
7.3.2　二叉树遍历的非递归实现　154
7.3.3　遍历算法的应用　158
7.3.4　由遍历序列恢复二叉树　159
7.4　线索二叉树　161
7.4.1　线索二叉树的定义及结构　161
7.4.2　线索二叉树的创建及遍历　163
7.4.3　线索二叉树的其他相关算法　165
7.5　哈夫曼树及其应用　169
7.5.1　哈夫曼树的基本概念　169
7.5.2　构造哈夫曼树　171
7.5.3　哈夫曼编码　172
7.5.4　哈夫曼树的应用　174
7.6　树的概念与表示　175
7.6.1　树的定义及相关术语　175
7.6.2　树的表示　176
7.6.3　树的存储　177
7.7　树与二叉树的转换　180
7.7.1　树或树林转换为二叉树　180
7.7.2　二叉树转换为树或树林　181
7.7.3　树或树林的遍历　183
7.8　树的应用　183
7.8.1　判定树　183
7.8.2　集合的表示　185
习题七　186
第8章　图论　192
8.1　图的基本概念　192
8.1.1　图的定义　192
8.1.2　图的相关术语　193
8.1.3　图的抽象数据类型　193
8.2　图的邻接表存储结构　195
8.2.1　图的邻接表存储结构定义　195
8.2.2　建立在图的邻接表存储结构的基本算法　196
8.2.3　创建图的邻接表存储结构　203
8.3　图的邻接矩阵存储结构　205
8.3.1　图的邻接矩阵存储结构定义　205
8.3.2　建立在图的邻接矩阵存储结构的基本操作算法　207
8.3.3　创建图的邻接矩阵存储结构　212
8.4　图的其他存储结构　214
8.4.1　图的十字链表存储结构　214
8.4.2　图的邻接多重表存储结构　215
8.5　图的广度优先遍历　216
8.5.1　广度优先搜索　216
8.5.2　邻接矩阵存储结构上的BFS算法　217
8.5.3　邻接表存储结构上的BFS算法　218
8.6　图的深度优先遍历　219
8.6.1　深度优先搜索　219
8.6.2　邻接矩阵存储结构上的DFS算法　220
8.6.3　邻接表存储结构上的DFS算法　221
习题八　223
第9章　图算法及应用　226
9.1　最小生成树　226
9.1.1　最小生成树的定义　226
9.1.2　构成最小生成树的Prim算法　227
9.1.3　构成最小生成树的Kruskal算法　230
9.2　最短路径　230
9.2.1　求图中某一顶点到其余各顶点的最短路径——Dijstra算法　231
9.2.2　每一对顶点之间的最短路径——Floyd算法　233
9.3　AOV网的应用　236
9.3.1　AOV网的定义　236
9.3.2　拓扑排序　238
9.4　AOE网的应用　240
9.4.1　AOE网的定义　240
9.4.2　关键路径　241
习题九　247
第10章　查找　252
10.1　查找的基本概念　252
10.2　静态查找表　253
10.2.1　顺序查找　253
10.2.2　有序表的折半查找　254
10.2.3　分块查找　256
10.3　二叉排序树　256
10.3.1　二叉排序树的定义　256
10.3.2　二叉排序树的相关算法　257
10.3.3　二叉排序树的查找效率分析　260
10.4　平衡二叉排序树　260
10.4.1　平衡二叉排序树的定义　260
10.4.2　调整不平衡的二叉排序树　261
10.4.3　创建平衡二叉排序树　263
10.5　其他查找树　264
10.5.1　B树及其基本操作　264
10.5.2　B+树的基本概念　267
10.6　散列表　268
10.6.1　散列表的基本概念　268
10.6.2　散列函数的设计　268
10.6.3　冲突的处理方法　270
10.6.4　散列表的查找分析　272
习题十　273
第11章　排序　280
11.1　排序的基本概念　280
11.1.1　排序的定义　280
11.1.2　排序方法的分类　281
11.1.3　排序算法的分析方法　281
11.2　插入排序　281
11.2.1　直接插入排序　282
11.2.2　折半插入排序　283
11.2.3　希尔排序　285
11.3　交换排序　287
11.3.1　冒泡排序　287
11.3.2　快速排序　289
11.4　选择排序　291
11.4.1　简单选择排序　291
11.4.2　树形选择排序　293
11.4.3　堆排序　294
11.5　归并排序　297
11.6　基数排序　299
11.6.1　多关键码排序　299
11.6.2　链式基数排序　300
11.7　内部排序算法的比较　304
11.7.1　内部排序算法的比较　304
11.7.2　内部排序算法的选用　305
习题十一　306
附录一　习题参考答案　312
附录二　学期考试样卷　318
参考文献　323

　　《数据结构（C语言描述）》：
　　1.2.3数据的存储结构
　　数据结构在计算机中的表示（又称为映像）称为数据的物理结构，又称为存储结构。它不同于逻辑结构，是依赖计算机语言的，是具体的。通常，一个数据元素在计算机内用一块连续的存储单元来表示。那么，在计算机中怎样存储表中所有的数据元素呢？数据结构一般用下面四种基本的存储结构来表示数据元素之间的关系。
　　1.顺序存储结构
　　该方法把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，数据元素之间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构主要应用于线性结构，非线性结构也可以通过某种线性的方法实现顺序存储。其优点是可以实现随机存取，每个元素占用最少的存储空间，即存储密度大。其缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
　　2.链式存储结构
　　该方法不要求逻辑上相邻的数据元素在物理位置上也相邻，数据元素之间的逻辑关系由附加的指针表示，由此得到的存储表示称为链式存储结构。其优点是不会出现碎片现象，可充分利用所有存储单元。其缺点是每个元素因存储指针而占用额外的存储空间，并且只能实现顺序存取。
　　3.索引存储结构
　　该方法通常在存储数据元素信息的同时，还建立附加的索引表。索引表由若干索引项组成。索引项的一般形式是：（关键字、地址）。关键字（Key）是能唯一标识一个数据元素的那些数据项。其优点是检索速度快。缺点是增加附加的索引表占用较多的存储空间。在增加和删除数据时要修改索引表，因而花费较多的时间。
　　4.哈希（散列）存储结构
　　该方法的基本思想是根据数据元素的关键字直接计算出该数据元素的存储地址。其优点是检索、增加、删除结点的操作都很快。缺点是如果散列函数不好，可能出现数据元素存储地址的冲突，而解决冲突会增加时间和空间开销。
　　这四种基本存储方法既可以单独使用，也可以组合起来对数据结构进行存储映像。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构；采用不同的存储结构，其数据处理效率往往不同。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。
　　1.2.4数据的运算
　　为了有效地处理数据，可将数据按一定的逻辑结构组织起来，并选择适当的存储方法存储数据，然后再对数据进行运算。
　　数据的运算是定义在数据的逻辑结构之上的，每一种逻辑结构都有一个运算的集合，并指出运算的功能，例如，查找、插入、删除、修改等，这些运算实际上是在数据元素上施加的一系列的抽象操作。所谓抽象操作，是只知道这些操作要求“做什么”，而无须考虑“如何做”，只有在确定了存储结构之后，才考虑如何具体实现这些运算。下面介绍几种常见的数据运算。
　　……