数据结构与算法(第4版十三五普通高等教育规划教材)

本书自2008年第1版和2013年第2版发行以来，在计算机基础教学中发挥了应有的作用，深受读者欢迎

《数据结构与算法 第4版》共包括8章内容，详细讲述了线性结构、树结构和图结构中的数据表示及数据处理的方法，并对查找和排序两种重要的数据处理技术做了细致的探讨。《数据结构与算法 第4版》对每一类数据结构的分析均按照“逻辑结构—存储结构—基本运算的实现—时空性能分析—典型应用实例—知识小结—练习题—实验题”的顺序进行讲解，算法全部采用C语言描述，很容易转换成程序。《数据结构与算法 第4版》语言叙述通俗易懂、由浅入深，算法可读性好、应用性强。《数据结构与算法 第4版》不仅配有算法设计的应用实例和大量的练习题，还针对重点、难点问题配有授课视频讲解，扫描二维码即可观看。

前言第1章 绪论11.1 引言11.1.1 为什么要学习数据结构11.1.2 “数据结构”课程的内容41.2 数据结构的概念51.2.1 基本概念和术语51.2.2 抽象数据类型71.3 算法81.3.1 算法及其特征81.3.2 算法的描述91.3.3 算法的性能分析91.4 递归121.4.1 递归的概念121.4.2 递归调用的实现原理131.4.3 递归转换为非递归151.4.4 递归应用举例161.5 本章知识点小结17练习题18实验题20题目1 比较算法复杂性描述函数的 增长20题目2 全排列的递归实现21题目3 皇后问题21第2章 基本线性结构222.1 线性表222.1.1 问题提出222.1.2 线性表的定义232.1.3 线性表的基本运算232.2 线性表的顺序存储242.2.1 顺序表242.2.2 顺序表上基本运算的实现262.2.3 顺序表应用举例292.3 线性表的链式存储312.3.1 单链表312.3.2 单链表上基本运算的实现332.3.3 循环链表392.3.4 双向链表392.3.5 链表应用举例412.4 顺序表和链表的比较442.5 堆栈452.5.1 堆栈的定义452.5.2 堆栈的存储及基本运算的 实现462.5.3 堆栈应用举例492.6 队列582.6.1 队列的定义582.6.2 队列的存储及基本运算的 实现592.6.3 队列应用举例642.7 本章知识点小结67练习题68实验题72题目1 Josephus环问题72题目2 模拟停车场管理73第3章 线性结构的扩展753.1 字符串753.1.1 字符串的基本概念753.1.2 顺序串763.1.3 模式匹配793.2 多维数组与特殊矩阵843.2.1 多维数组843.2.2 特殊矩阵863.2.3 稀疏矩阵903.3 广义表993.3.1 广义表的基本概念993.3.2 广义表的存储1013.4 本章知识点小结103练习题104实验题107题目 格式化文本107第4章 树结构1104.1 引言1104.1.1 问题提出1104.1.2 相关概念1114.2 二叉树1134.2.1 二叉树的概念1134.2.2 二叉树的主要性质1144.2.3 二叉树的存储1164.2.4 二叉树基本运算的实现1194.3 二叉树的遍历1214.3.1 递归方法实现二叉树的遍历1214.3.2 非递归方法实现二叉树的遍历1234.3.3 队列方法实现二叉树的层次遍历1264.4 二叉树遍历的应用1274.4.1 构造二叉树的二叉链表存储1274.4.2 在二叉树中查找值为x的数据元素1284.4.3 统计给定二叉树中叶子结点的数目1284.4.4 由遍历序列恢复二叉树1294.5 线索二叉树1304.5.1 线索二叉树的定义及结构1304.5.2 线索二叉树的构建1324.5.3 线索二叉树的遍历1334.6 很优二叉树1364.6.1 很优二叉树的概念1364.6.2 很优二叉树的构造1384.6.3 很优二叉树的应用——哈夫曼编码1414.7 树和森林1434.7.1 树的基本操作与表示1434.7.2 树的存储1444.7.3 树和森林与二叉树之间的转换1484.7.4 树或森林的遍历1504.7.5 树的应用1514.8 本章知识点小结153练习题155实验题159题目 哈夫曼编码/译码器159第5章 图结构1615.1 引言1615.1.1 问题提出1615.1.2 相关概念1625.1.3 图的基本操作1655.2 图的存储方法1655.2.1 邻接矩阵1655.2.2 邻接表167*5.2.3 十字链表169*5.2.4 邻接多重表1715.3 图的遍历1735.3.1 深度优先搜索1735.3.2 广度优先搜索1755.3.3 应用图的遍历判定图的连通性1775.4 生成树与最小生成树1785.4.1 生成树和生成森林1785.4.2 最小生成树1795.4.3 构造最小生成树的Prim算法1805.4.4 构造最小生成树的Kruskal算法1835.5 最短路径1865.5.1 从一个源点到其他各点的最短路径186*5.5.2 每一对顶点之间的最短路径——弗洛伊德算法1895.6 拓扑排序1935.6.1 有向无环图的概念1935.6.2 AOV网与拓扑排序1945.7 关键路径1985.7.1 AOE网与关键路径1985.7.2 关键路径的确定1995.8 本章知识点小结203练习题206实验题208题目 校园导游程序208第6章 查找2106.1 引言2106.1.1 问题提出2106.1.2 相关概念2106.2 线性表查找2126.2.1 顺序查找2126.2.2 在顺序存储的有序表上查找2146.3 树表查找2186.3.1 二叉排序树2186.3.2 平衡二叉树224*6.3.3 B树和B+树2306.4 散列表查找2366.4.1 散列表2366.4.2 常用的散列函数2376.4.3 处理冲突的方法及散列表的构造2386.4.4 散列表上的查找2426.4.5 散列表上的插入2446.4.6 散列表上的删除2456.5 本章知识点小结245练习题246实验题249题目1 职工信息检索系统249题目2 个人图书管理系统250第7章 排序2527.1 引言2527.1.1 问题提出2527.1.2 相关概念2527.2 插入排序2547.2.1 直接插入排序2547.2.2 折半插入排序2567.2.3 希尔排序2567.3 交换排序2587.3.1 冒泡排序2587.3.2 快速排序2597.4 选择排序2617.4.1 简单选择排序2617.4.2 树型选择排序2627.4.3 堆排序2637.5 归并排序2667.5.1 两个有序表的合并2667.5.2 二路归并排序的迭代算法2677.5.3 二路归并排序的递归算法268*7.6 基数排序2687.6.1 多关键码排序2687.6.2 链式基数排序2697.7 排序方法比较2727.8 本章知识点小结274练习题275实验题278题目 各种内部排序的性能比较278第8章 扩展应用举例2798.1 求优选子段和2798.1.1 问题描述2798.1.2 问题分析与解决2798.2 表达式树的构造2838.2.1 问题描述2838.2.2 问题分析与解决2838.3 由等价关系求划分2878.3.1 问题描述2878.3.2 问题分析与解决2878.4 本章知识点小结289练习题290实验题290题目1 模拟银行排队办理业务290题目2 0-1背包问题291附录292附录A 实验要求292实验题目294附录B 模拟试卷295模拟试卷一295模拟试卷二296模拟试卷三299模拟试卷四301参考文献304