本书是国家级一流本科课程配套教材。 　　全书共9章，主要内容包括：算法设计与分析的基础知识，线性结构、树和图等各种基本数据结构的逻辑特点、存储结构、主要操作的实现与应用，递归、查找和排序等典型算法的实现及应用。每节以“问题导入”引入知识点，通过问题分析、算法设计与实现、算法评价展示问题求解过程，并结合教学内容，在问题导入、应用举例和“思想园地”中融入课程思政元素。全书采用C语言作为算法实现语言，各章的“应用举例”中含有很多实用的算法实例和热点应用，既是本章算法的综合运用，也有助于提高读者运用数据结构解决实际问题的能力。每章还设置了不同难度的思考题、练习题和上机实验题，帮助读者理解和掌握重点、难点问题，提高实践能力。 　　本书可以作为全日制高等院校计算机及信息类专业本科生的专业基础课教材，也可作为广大从事计算机软件开发人员的参考书。为方便教师教学，本书有配套的程序代码、课件、视频等资源。 　　

高等院校教师

前言
目录
目录
前言
第1章绪论1
1.1数据结构研究内容1
1.2基本概念和术语4
1.3算法及其描述方法6
1.3.1什么是算法7
1.3.2什么是“好”算法7
1.3.3算法的描述8
1.4算法分析9
1.4.1算法分析预备知识10
1.4.2算法的时间复杂度12
1.4.3算法的空间复杂度14
本章小结15
思想园地——好算法是反复修正和优化的结果15
思考题16
练习题17
上机实验题18
第2章线性表20
2.1线性表的逻辑结构20
2.1.1线性表的定义20
2.1.2线性表的抽象数据类型描述21
2.2线性表的顺序存储结构及实现22
2.2.1线性表的顺序存储结构——顺序表22
2.2.2顺序表基本运算的实现23
2.2.3顺序表运算应用举例28
2.3线性表的链式存储结构及实现32
2.3.1单链表33
2.3.2单链表运算应用举例41
2.3.3循环链表45
2.3.4双向链表46
2.3.5静态链表50
2.4顺序表和链表的比较50
2.4.1时间性能比较51
2.4.2空间性能比较51
2.5线性表应用举例52
2.5.1一元多项式的表示52
2.5.2多项式的建立与输出53
2.5.3多项式的加法54
本章小结57
思想园地——小错误可能导致大故障58
思考题58
练习题59
上机实验题61
第3章栈和队列64
3.1栈的逻辑结构64
3.1.1栈的定义64
3.1.2栈的抽象数据类型描述65
3.2栈的存储结构66
3.2.1栈的顺序存储结构及实现66
3.2.2栈的链式存储结构及实现69
3.3栈的应用举例72
3.3.1中缀表达式求值72
3.3.2中缀表达式转换为后缀表达式77
3.3.3后缀表达式求值80
3.4队列的逻辑结构82
3.4.1队列的定义82
3.4.2队列的抽象数据类型描述83
3.5队列的存储结构83
3.5.1队列的顺序存储结构及实现83
3.5.2队列的链式存储结构及实现87
3.6队列的应用举例91
本章小结94
思想园地——创新是引领发展的第一动力94
思考题95
练习题95
上机实验题96
第4章字符串和多维数组98
4.1字符串98
4.1.1串的定义98
4.1.2串的存储结构99
4.1.3串的模式匹配100
4.2多维数组104
4.2.1数组的定义104
4.2.2数组的抽象数据类型描述105
4.2.3数组的存储结构与寻址106
4.3特殊矩阵的压缩存储107
4.3.1对称矩阵的压缩存储108
4.3.2三角矩阵的压缩存储109
4.3.3对角矩阵的压缩存储110
4.4稀疏矩阵的压缩存储111
4.4.1稀疏矩阵的三元组表示111
4.4.2稀疏矩阵的十字链表表示114
4.5应用举例116
4.5.1字符串应用举例116
4.5.2数组应用举例118
本章小结121
思想园地——数据压缩与资源优化利用121
思考题122
练习题122
上机实验题123
第5章递归125
5.1什么是递归125
5.1.1递归的定义125
5.1.2何时使用递归126
5.1.3递归模型128
5.2递归调用与实现129
5.2.1函数调用的实现129
5.2.2递归调用的实现130
5.3递归算法设计132
5.3.1递归算法的设计步骤132
5.3.2递归算法的实现形式133
5.4递归算法的性能分析133
5.4.1递归算法的时间复杂度分析133
5.4.2递归算法的空间复杂度分析135
5.5应用举例135
5.5.1杨辉三角问题136
5.5.2迷宫问题137
本章小结140
思想园地——递归中的归纳与演绎之道140
思考题141
练习题142
上机实验题142
第6章树与二叉树143
6.1树的逻辑结构143
6.1.1树的定义和基本术语144
6.1.2树的抽象数据类型描述145
6.1.3树的逻辑表示方法146
6.1.4树的性质147
6.1.5树的遍历148
6.2树的存储结构149
6.2.1双亲表示法149
6.2.2孩子表示法150
6.2.3双亲孩子表示法151
6.2.4孩子兄弟表示法152
6.3二叉树的逻辑结构153
6.3.1二叉树的定义153
6.3.2二叉树的性质155
6.4二叉树的存储结构156
6.4.1二叉树的顺序存储结构156
6.4.2二叉树的链式存储结构158
6.5二叉树的基本运算159
6.5.1二叉树的遍历160
6.5.2二叉树的其他运算举例166
6.6线索二叉树168
6.6.1线索二叉树的概念169
6.6.2二叉树的线索化170
6.6.3线索二叉树上的运算172
6.7树、森林与二叉树的转换173
6.7.1树转换为二叉树174
6.7.2森林转换为二叉树175
6.7.3二叉树转换为树或森林175
6.8哈夫曼树及其应用176
6.8.1哈夫曼树的基本概念176
6.8.2哈夫曼树的构造及实现177
6.8.3哈夫曼树的应用180
6.9并查集183
6.9.1什么是并查集183
6.9.2并查集的算法实现184
本章小结186
思想园地——哈夫曼和他的压缩算法186
思考题187
练习题188
上机实验题189
第7章图192
7.1图的逻辑结构192
7.1.1图的定义和基本术语193
7.1.2图的抽象数据类型描述196
7.2图的存储结构及实现196
7.2.1邻接矩阵表示法196
7.2.2邻接表表示法199
7.2.3其他存储方法202
7.3图的遍历203
7.3.1深度优先遍历204
7.3.2广度优先遍历206
7.4图的生成树和最小生成树207
7.4.1生成树和最小生成树的概念207
7.4.2Prim算法209
7.4.3Kruskal算法211
7.5最短路径214
7.5.1单源最短路径问题214
7.5.2每对顶点之间的最短路径217
7.6AOV网与拓扑排序220
7.6.1AOV网220
7.6.2拓扑排序221
7.7AOE网与关键路径223
7.7.1AOE网224
7.7.2关键路径224
本章小结227
思想园地——主因素建模：破解复杂性的钥匙227
思考题228
练习题229
上机实验题231
第8章查找233
8.1查找的基本概念233
8.2线性表的查找235
8.2.1顺序查找235
8.2.2折半查找236
8.2.3分块查找240
8.3树表的查找241
8.3.1二叉排序树241
8.3.2AVL树247
8.3.3B树256
8.3.4B+树262
8.4散列表的查找264
8.4.1散列表的基本概念264
8.4.2散列函数的设计265
8.4.3处理冲突的方法269
8.4.4散列表的查找及性能分析271
本章小结273
思想园地——查找技术的发展与挑战273
思考题274
练习题274
上机实验题276
第9章排序278
9.1概述278
9.2插入排序280
9.2.1直接插入排序280
9.2.2希尔排序282
9.3交换排序284
9.3.1冒泡排序284
9.3.2快速排序286
9.4选择排序289
9.4.1简单选择排序289
9.4.2堆排序291
9.5归并排序295
9.6基数排序298
9.7各种内排序方法的比较303
9.8外排序简介305
本章小结306
思想园地——正确的选择需要综合了解306
思考题307
练习题308
上机实验题309
附录书配二维码视频清单311
参考文献317