《数据结构与算法 第4版》共包括8章内容，详细讲述了线性结构、树结构和图结构中的数据表示及数据处理的方法，并对查找和排序两种重要的数据处理技术做了细致的探讨。《数据结构与算法 第4版》对每一类数据结构的分析均按照逻辑结构存储结构基本运算的实现时空性能分析典型应用实例知识小结练习题实验题的顺序进行讲解，算法全部采用C语言描述，很容易转换成程序。《数据结构与算法 第4版》语言叙述通俗易懂、由浅入深，算法可读性好、应用性强。《数据结构与算法 第4版》不仅配有算法设计的应用实例和大量的练习题，还针对重点、难点问题配有授课视频讲解，扫描二维码即可观看。
配套资源丰富：教学课件、习题解答、附录、57个知识点视频
新型态立体化教材，有重点难点的视频讲解；
经过4次改版，教材结构和内容更加稳定，更加适用于教育教学。
前 言数据结构是计算机及相关专业的一门重要的专业基础课，是介于数学计算机硬件和计算机软件之间的一门计算机科学与技术领域的核心课程，同时数据结构技术也被广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。该课程主要介绍如何合理地组织和表示数据、如何有效地存储和处理数据、如何正确地设计算法以及对算法的优劣进行分析和评价。
本书结合编者多年教学经验，在《数据结构与算法》（第 3 版）的基础上进行了修订，定位于应用研究型本科层次，坚持以面向应用，易教易学为目标，数据结构与算法设计简单明了，语言叙述通俗易懂，讲解由浅入深，并在以下几方面有所改进。
1）增加部分章节的内容。为加强应用型本科教学的深入，注重培养学生灵活运用数据结构进行程序设计解决实际问题的能力，适应学生参加程序能力相关考试和竞赛以及考研的需要，在第5章加入Floyd算法的详细描述与举例。
2）对重点、难点内容提供对应的视频讲解，方便学习者在课下进行有针对地学习，也方便教学组织翻转教学，让学生提前预习。
3）丰富了每章知识点小结的内容。不仅描述了知识点的内容和学习要求，还指出部分知识点在学习和运用中容易误解和使用错误的地方。
4）丰富了配套练习。补充和修改了每章的课后练习题和实验题，尤其是增加了一些引导学生思考的简答题和灵活运用相关知识点解决实际问题的算法设计题。
5）补充了配套的教案资源，方便教学组织和翻转课堂的使用。针对翻转课堂对教学过程课前、课中和课后的要求，在提供的配套教案中，选择了部分适合翻转课堂的内容，给出适合翻转课堂教学使用的教案。
本书由罗文劼教授组织编定并负责统稿。其中第1、2、3、4、8章由罗文劼编写，第5章由苗秀芬编写，第6、7章由史青宣编写。在本书的编写过程中，张小莉、王苗、石强、和张瑜等多位从事数据结构教学的老师对本书的编写提出了宝贵的意见和建议，河北大学教务处也为本书的改版给予支持，在此一并表示感谢。
由于编者水平有限，书中难免存在疏漏之处，恳请各位读者批评指正。
编 者
前言
第1章 绪论1
1.1 引言1
1.1.1 为什么要学习数据结构1
1.1.2 数据结构课程的内容4
1.2 数据结构的概念5
1.2.1 基本概念和术语5
1.2.2 抽象数据类型7
1.3 算法8
1.3.1 算法及其特征8
1.3.2 算法的描述9
1.3.3 算法的性能分析9
1.4 递归12
1.4.1 递归的概念12
1.4.2 递归调用的实现原理13
1.4.3 递归转换为非递归15
1.4.4 递归应用举例16
1.5 本章知识点小结17
练习题18
实验题20
题目1 比较算法复杂性描述函数的
增长20
题目2 全排列的递归实现21
题目3 皇后问题21
第2章 基本线性结构22
2.1 线性表22
2.1.1 问题提出22
2.1.2 线性表的定义23
2.1.3 线性表的基本运算23
2.2 线性表的顺序存储24
2.2.1 顺序表24
2.2.2 顺序表上基本运算的实现26
2.2.3 顺序表应用举例29
2.3 线性表的链式存储31
2.3.1 单链表31
2.3.2 单链表上基本运算的实现33
2.3.3 循环链表39
2.3.4 双向链表39
2.3.5 链表应用举例41
2.4 顺序表和链表的比较44
2.5 堆栈45
2.5.1 堆栈的定义45
2.5.2 堆栈的存储及基本运算的
实现46
2.5.3 堆栈应用举例49
2.6 队列58
2.6.1 队列的定义58
2.6.2 队列的存储及基本运算的
实现59
2.6.3 队列应用举例64
2.7 本章知识点小结67
练习题68
实验题72
题目1 Josephus环问题72
题目2 模拟停车场管理73
第3章 线性结构的扩展75
3.1 字符串75
3.1.1 字符串的基本概念75
3.1.2 顺序串76
3.1.3 模式匹配79
3.2 多维数组与特殊矩阵84
3.2.1 多维数组84
3.2.2 特殊矩阵86
3.2.3 稀疏矩阵90
3.3 广义表99
3.3.1 广义表的基本概念99
3.3.2 广义表的存储101
3.4 本章知识点小结103
练习题104
实验题107
题目 格式化文本107
第4章 树结构110
4.1 引言110
4.1.1 问题提出110
4.1.2 相关概念111
4.2 二叉树113
4.2.1 二叉树的概念113
4.2.2 二叉树的主要性质114
4.2.3 二叉树的存储116
4.2.4 二叉树基本运算的实现119
4.3 二叉树的遍历121
4.3.1 递归方法实现二叉树的遍历121
4.3.2 非递归方法实现二叉树的遍历123
4.3.3 队列方法实现二叉树的层次遍历126
4.4 二叉树遍历的应用127
4.4.1 构造二叉树的二叉链表存储127
4.4.2 在二叉树中查找值为x的数据元素128
4.4.3 统计给定二叉树中叶子结点的数目128
4.4.4 由遍历序列恢复二叉树129
4.5 线索二叉树130
4.5.1 线索二叉树的定义及结构130
4.5.2 线索二叉树的构建132
4.5.3 线索二叉树的遍历133
4.6 最优二叉树136
4.6.1 最优二叉树的概念136
4.6.2 最优二叉树的构造138
4.6.3 最优二叉树的应用哈夫曼编码141
4.7 树和森林143
4.7.1 树的基本操作与表示143
4.7.2 树的存储144
4.7.3 树和森林与二叉树之间的转换148
4.7.4 树或森林的遍历150
4.7.5 树的应用151
4.8 本章知识点小结153
练习题155
实验题159
题目 哈夫曼编码/译码器159
第5章 图结构161
5.1 引言161
5.1.1 问题提出161
5.1.2 相关概念162
5.1.3 图的基本操作165
5.2 图的存储方法165
5.2.1 邻接矩阵165
5.2.2 邻接表167
*5.2.3 十字链表169
*5.2.4 邻接多重表171
5.3 图的遍历173
5.3.1 深度优先搜索173
5.3.2 广度优先搜索175
5.3.3 应用图的遍历判定图的连通性177
5.4 生成树与最小生成树178
5.4.1 生成树和生成森林178
5.4.2 最小生成树179
5.4.3 构造最小生成树的Prim
算法180
5.4.4 构造最小生成树的Kruskal
算法183
5.5 最短路径186
5.5.1 从一个源点到其他各点的最短路径186
*5.5.2 每一对顶点之间的最短路径弗洛伊德算法189
5.6 拓扑排序193
5.6.1 有向无环图的概念193
5.6.2 AOV网与拓扑排序194
5.7 关键路径198
5.7.1 AOE网与关键路径198
5.7.2 关键路径的确定199
5.8 本章知识点小结203
练习题206
实验题208
题目 校园导游程序208
第6章 查找210
6.1 引言210
6.1.1 问题提出210
6.1.2 相关概念210
6.2 线性表查找212
6.2.1 顺序查找212
6.2.2 在顺序存储的有序表上查找214
6.3 树表查找218
6.3.1 二叉排序树218
6.3.2 平衡二叉树224
*6.3.3 B树和B 树230
6.4 散列表查找236
6.4.1 散列表236
6.4.2 常用的散列函数237
6.4.3 处理冲突的方法及散列表的构造238
6.4.4 散列表上的查找242
6.4.5 散列表上的插入244
6.4.6 散列表上的删除245
6.5 本章知识点小结245
练习题246
实验题249
题目1 职工信息检索系统249
题目2 个人图书管理系统250
第7章 排序252
7.1 引言252
7.1.1 问题提出252
7.1.2 相关概念252
7.2 插入排序254
7.2.1 直接插入排序254
7.2.2 折半插入排序256
7.2.3 希尔排序256
7.3 交换排序258
7.3.1 冒泡排序258
7.3.2 快速排序259
7.4 选择排序261
7.4.1 简单选择排序261
7.4.2 树型选择排序262
7.4.3 堆排序263
7.5 归并排序266
7.5.1 两个有序表的合并266
7.5.2 二路归并排序的迭代算法267
7.5.3 二路归并排序的递归算法268
*7.6 基数排序268
7.6.1 多关键码排序268
7.6.2 链式基数排序269
7.7 排序方法比较272
7.8 本章知识点小结274
练习题275
实验题278
题目 各种内部排序的性能比较278
第8章 扩展应用举例279
8.1 求最大子段和279
8.1.1 问题描述279
8.1.2 问题分析与解决279
8.2 表达式树的构造283
8.2.1 问题描述283
8.2.2 问题分析与解决283
8.3 由等价关系求划分287
8.3.1 问题描述287
8.3.2 问题分析与解决287
8.4 本章知识点小结289
练习题290
实验题290
题目1 模拟银行排队办理业务290
题目2 0-1背包问题291
附录292
附录A 实验要求292
实验题目294
附录B 模拟试卷295
模拟试卷一295
模拟试卷二296
模拟试卷三299
模拟试卷四301
参考文献304
书单推荐
