数据结构与算法（快速基础C++版）

06-02 1683阅读

数据结构与算法（快速基础C++版）

1. 基本概念

第1章绪论

1.1 数据结构的研究内容
1.2 基本概念和术语

1.2.1 数据、数据元素、数据项和数据对象
1.2.2 数据结构
1.2.3 数据类型和抽象数据类型
1.2.4 概念小结
1.3 算法和算法分析
1.4 总结
2. 基本的数据结构

第2章线性表

2.1 线性表的定义和特点
2.2 案例引入

案例2.1 一元多项式的运算
案例2.2 稀疏多项式的运算
案例2.3 图书信息管理系统
总结
2.3 线性的类型定义

2.3.1 基本操作（一）：初始化空表、销毁表、清空表
2.3.2 基本操作（二）：判断表为空、返回表长
2.3.3 基本操作（三）：查找某个元素、查找某个符合条件的元素
2.3.4 基本操作（四）：查找前驱、查找后继
2.3.5 基本操作（五）：插入
2.3.6 基本操作（六）：删除、遍历
总结
2.4 线性表的顺序表示和实现

2.4.1 多项式的顺序存储结构类型定义
2.4.2 图书表的顺序存储结构类型定义
2.4.3 数组定义的补充
2.4.4 代码实例

2.4.4.1 线性表的初始化
2.4.4.2 线性表的销毁
2.4.4.3 线性表的清空
2.4.4.4 线性表的长度
2.4.4.5 判断线性表为空
2.4.4.6 线性表取值
2.4.4.7 线性表的顺序查找
2.4.4.8 线性表的插入
2.4.4.9 线性表的删除
2.4.4.10 总结
2.5 线性表的链式表示和实现

2.5.1 单链表的代码实例

2.5.1.1 单链表的初始化（带头结点的单链表）
2.5.1.2 判断单链表为空
2.5.1.3 单链表的销毁
2.5.1.4 单链表的清空
2.5.1.5 单链表的表长
知识回顾
2.5.1.6 单链表的取值
2.5.1.7 单链表的查找
2.5.1.8 单链表的插入
2.5.1.9 单链表的删除第i个结点
2.5.1.10 单链表头插法
2.5.1.11 单链表尾插法
总结
2.5.2 循环链表的代码实例

2.5.2.1 循环链表的合并
总结
2.5.3 双向链表的代码实例

2.5.3.1 双向链表的插入
2.5.3.2 双向链表的删除
2.6 单链表、循环链表、双向链表的比较
2.7 顺序表和链表的比较
2.8 线性表的应用

2.8.1 线性表的合并
2.8.2 有序表的合并（顺序表实现）
2.8.3 有序表的合并（链表实现）
2.9 案例分析与实现

2.9.1 一元多项式的运算
2.9.2 稀疏多项式的运算
2.9.3 图书信息管理系统
第3章栈和队列

3.1 栈和队列的定义和特点

3.1.1 栈的定义和特点
3.1.2 队列的定义和特点
3.2 案例引入

3.2.1 进制转换
3.2.2 括号匹配的检验
3.2.3 表达式求值
3.2.4 舞伴问题
3.3 栈的顺序表示和操作的实现

3.3.1 栈的抽象数据类型的定义
3.3.2 顺序栈的表示和实现
3.3.2 代码实例

3.3.2.1 栈的初始化
3.3.2.2 判断栈是否为空
3.3.2.3 求顺序栈的长度
3.3.2.4 清空栈
3.3.2.5 销毁栈
3.3.2.6 顺序栈的入栈
3.3.2.7 顺序栈的出栈
3.4 链栈的表示与实现

3.4.1 代码实例

3.4.1.1 链栈的初始化
3.4.1.2 判断链栈是否为空
3.4.1.3 链栈的入栈
3.4.1.4 链栈的出栈
3.4.1.5 取栈顶元素
3.5 栈与递归
3.6 队列的顺序表示和操作的实现

3.6.1 队列的抽象数据类型的定义
3.6.2 队列的顺序表示和实现
3.6.3 代码实例

3.6.3.1 循环队列的初始化
3.6.3.2 求循环队列的长度
3.6.3.3 入队
3.6.3.4 出队
3.6.3.5 取队头元素
3.7 队列的链式表示和实现

3.7.1 代码实例

3.7.1.1 链队的初始化
3.7.1.2 链队的销毁
3.7.1.3 链队的入队
3.7.1.4 链队的出队
3.7.1.5 求链队的队头元素
第4章串、数组和广义表

4.1 串的定义
4.2 案例引入
4.3 串的类型定义、存储结构及其运算

4.3.1 串的类型定义
4.3.2 串的顺序存储结构
4.3.3 串的链式存储结构
4.3.4 串的模式匹配算法及代码实例

4.3.4.1 BF算法
4.3.4.2 BF算法代码实例
4.3.4.3 BF算法的时间复杂度
4.3.4.4 KMP算法
4.4 数组

4.4.1 数组的抽象数据类型和定义
4.4.2 数组的顺序存储
4.4.3 特殊矩阵的压缩存储

4.4.3.1 对称矩阵
4.4.3.2 三角矩阵
4.4.3.3 对角矩阵（带状矩阵）
4.4.3.4 稀疏矩阵
4.5 广义表
4.6 案例分析与实现
第5章树

5.1 树和二叉树的定义

5.1.1 树的定义
5.1.2 树的基本术语
5.1.3 二叉树的定义
5.2 案例引入
5.3 数和二叉树的抽象数据类型定义
5.4 二叉树的性质和存储结构

5.4.1 二叉树的性质

5.4.1.1 满二叉树
5.4.1.2 完全二叉树
5.4.2 二叉树的存储结构

5.4.2.1 二叉树的顺序存储结构
5.4.2.2 二叉树的链式存储结构
5.5 遍历二叉树和线索二叉树

5.5.1 遍历二叉树的算法描述

5.5.1.1 先序遍历二叉树的操作定义
5.5.1.2 中序遍历二叉树的操作定义
5.5.1.3 后序遍历二叉树的操作定义
5.5.2 遍历二叉树的递归代码实例

5.5.2.1 二叉树先序遍历
5.5.2.2 二叉树中序遍历
5.5.2.3 二叉树后序遍历
5.5.2.4 遍历算法的分析
5.5.3 遍历二叉树的非递归代码实例
5.5.4 二叉树的层次遍历代码实例
5.5.5 二叉树遍历算法的应用---二叉树的建立
5.5.6 二叉树遍历算法的应用---赋值二叉树
5.5.7 二叉树遍历算法的应用---计算二叉树的深度
5.5.8 二叉树遍历算法的应用---计算二叉树的结点总数
5.5.9 二叉树遍历算法的应用---计算二叉树的叶子结点总数
5.6 线索二叉树
5.7 树和森林

5.7.1 树的存储结构

5.7.1.1 双亲表示法
5.7.1.2 孩子链表
5.7.1.3 孩子兄弟表示法
5.7.2 树与二叉树的转换
5.7.3 森林与二叉树的转换
5.7.4 树与森林的遍历

5.7.4.1 树的遍历
5.7.4.2 森林的遍历
5.8 哈夫曼树及其应用

5.8.1 哈夫曼树的基本概念
5.8.2 哈夫曼树的构造算法
5.8.3 总结
5.8.4 代码实例
5.8.5 哈夫曼编码
5.8.6 哈夫曼编码的代码实例
5.8.7 哈夫曼编码-解码
第6章图

6.1 图的定义和基本术语
6.2 案例引入
6.3 图的类型定义
6.4 图的存储结构

6.4.1 邻接矩阵

6.4.1.1 邻接矩阵表示
6.4.1.2 无向网的邻接矩阵代码实例
6.4.2 邻接表
6.4.3 邻接表的代码实例
6.4.4 邻接矩阵和邻接表的关系
6.4.5 十字链表
6.4.6 邻接多重表
6.5 图的遍历

6.5.1 深度优先遍历
6.5.2 深度优先搜索遍历算法的实现
6.5.3 广度优先遍历
6.5.4 广度优先遍历的代码实例
6.6 图的应用

6.6.1 生成树
6.6.2 构造最小生成树

6.6.2.1 普利姆（Prim）算法
6.6.2.2 克鲁斯卡尔(Kruskal)算法。
6.6.3 最短路径

6.6.3.1 Dijistra算法
6.6.3.2 Floyd算法
6.6.4 有向无环图及其应用
6.6.5 关键路径
3. 基本的数据处理技术

第7章查找技术

7.1 查找的基本概念
7.2 线性表的查找

7.2.1 顺序查找（线性查找）
7.2.2 折半查找（二分或对分查找）

7.2.2.2 折半查找的代码实例
7.2.3 分块查找
7.3 树表的查找

7.3.1 二叉排序树

7.3.1.1 二叉排序树的存储结构
7.3.1.2 二叉排序树的代码实例
7.3.1.3 二叉排序树的查找分析
7.3.1.4 二叉排序树的插入
7.3.1.5 二叉排序树的生成
7.3.1.6 二叉排序树的删除
7.3.2 平衡二叉树
7.4 哈希表的查找

7.4.1 散列表的基本概念
7.4.2 散列函数的构造方法

7.4.2.1 直接定址法
7.4.2.2 除留余数法
7.4.3 处理冲突的方法

7.4.3.1 开放地址法
7.4.3.2 链地址法（拉链法）
7.4.4 散列表的查找
第8章排序技术

8.1 基本概念和排序方法概述
8.2 插入排序

8.2.1 直接插入排序
8.2.2 折半插入排序
8.2.3 希尔排序
8.3 交换排序

8.3.1 冒泡排序
8.3.2 快速排序
8.4 选择排序
8.5 归并排序
8.6 基数排序

8.7 外部排序

1. 基本概念

“ 程序 = 数据结构 + 算法 ”

说白了就是：

首先，你要操纵的数据是个什么逻辑关系，比如学生信息管理系统，每个学生信息之间就是1对1的线性关系，只有1个前驱和1个后继，那就可以用线性表。

其次，我们要对这个存放学生信息的线性表进行增删改查等操作，就要考虑它选用的存储方式，顺序存储和链式存储。

最后，根据不同的存储方式设计操作，并根据时间复杂度和空间复杂度进行算法操作的性能分析。

数据结构通过算法实现操作，算法根据数据结构设计程序

数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科

第1章绪论

1.1 数据结构的研究内容

通常用计算机解决一个问题的步骤，就是：

1.将具体问题抽象为数学模型；2.设计算法；3.最后进行编程、调试与运行。

那抽象数学模型的实质就是：分析问题、提取操作对象、找出操作对象之间的关系并用数学语言描述出来。

操作对象与操作对象之间的关系就是我们说的：数据结构

随着计算机应用领域的扩展，计算机被越来越多地用于非数值计算。描述非数值计算问题的数学模型不是数值计算的数学方程，而是诸如表、树和图之类的具有逻辑关系的数据。

比如：我们常见的学生教务管理系统。操作对象：每位学生的信息(学号、姓名、性别、籍贯、专业.….)。操作算法：查询、插入、修改、删除等。操作对象之间的关系：线性关系，数据结构：线性数据结构、线性表。

换句话说：

是指相互之间存在一种或多种特定关系的数据元素的集合；

或者说，数据结构是带结构的数据元素的集合。

1.2 基本概念和术语

1.2.1 数据、数据元素、数据项和数据对象

1.数据

是能输入计算机且能被计算机处理的各种符号的集合。是信息的载体，是对客观事物符号化的表示，能够被计算机识别、存储和加工。

包括：

数值型的数据：整数、实数等

非数值型的数据：文字、图像、图形、声音等

2.数据元素

是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。也简称为元素，或称为记录、结点或顶点。

3.数据项

构成数据元素的不可分割的最小单位。

关系：

数据 > 数据元素 > 数据项

例：学生表 > 个人记录 > 学号、姓名…

4.数据对象

是性质相同的数据元素的集合，是数据的一个子集。

例如：

整数数据对象是集合N={0，±1，±2，……}

字母字符数据对象是集合C={‘A’，‘B’，…,‘Z’}

学籍表也可看作一个数据对象

区别：

数据元素：组成数据的基本单位。与数据的关系:是集合的个体

数据对象：性质相同的数据元素的集合。与数据的关系是：集合的子集

1.2.2 数据结构

数据元素不是孤立存在的，它们之间存在着某种关系，数据元素相互之间的关系称为结构（Structure）。是指相互之间存在一种或多种特定关系的数据元素集合或者说，数据结构是带结构的数据元素的集合

数据结构包括以下三个方面的内容：

1.数据元素之间的逻辑关系，也称为逻辑结构。

2.数据元素及其关系在计算机内存中的表示(又称为映像)，称为数据的物理结构或数据的存储结构

3.数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现。

逻辑结构

1.描述数据元素之间的逻辑关系。

2.与数据的存储无关，独立于计算机。

3.是从具体问题抽象出来的数学模型。

划分方法一：

(1）线性结构

有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。

例如:线性表、栈、队列、串

(2）非线性结构

一个结点可能有多个直接前趋和直接后继

例如:树、图

划分方式二：四类基本逻辑结构

(1)集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。

(2)线性结构：结构中的数据元素之间存在着一对一的线性关系。

(3)树形结构：结构中的数据元素之间存在着一对多的层次关系。

(4)图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。

物理结构(存储结构)

1.数据元素及其关系在计算机存储器中的结构（存储方式)。

2.是数据结构在许算机中的表示。

四种基本的存储结构：

1.顺序存储结构

用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。

C语言中用数组来实现顺序存储结构。

2.链式存储结构

用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示

C语言中用指针来实现顺序存储结构。

3.索引存储结构

在存储结点信息的同时，还建立附加的索引表。

4.散列存储结构

根据结点的关键字直接计算出该结点的存储地址。

逻辑结构与存储结构的关系：

1.存储结构是逻辑关系的映象与元素本身的映象。

2.逻辑结构是数据结构的抽象，存储结构是数据结构的实现。

3.两者综合起来建立数据元素之间的结构关系。

1.2.3 数据类型和抽象数据类型

在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。

例如，C语言中:

·提供int,char, float, double等基本数据类型

·数组、结构、共用体、枚举等构造数据类型，还有指针、空(void)类型

·用户也可用typedef自己定义数据类型

一些最基本数据结构可以用数据类型来实现，如数组、字符串等;

而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示。

高级语言中的数据类型明显地或隐含地规定了在程序执行期间变量和表达的所有可能的取值范围，以及在这些数值范围上所允许进行的操作。

例如，C语言中定义变量i为int类型，就表示i是[-min,max]范围的整数，在这个整数集上可以进行+、-、*、%等操作

数据类型的作用：

1.约束变量或常量的取值范围。

2.约束变量或常量的操作。

定义：数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。

数据类型 = 值的集合 + 值集合上的一组操作

抽象数据类型(Abstract Data Type，ADT)

是指一个数学模型以及定义在此数学模型上的一组操作。

1.由用户定义,从问题抽象出数据模型（逻辑结构)

2.还包括定义在数据模型上的一组抽象运算(相关操作)

3.不考虑计算机内的具体存储结构与运算的具体实现算法

1.2.4 概念小结

1.3 算法和算法分析

算法的定义：

对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。

算法的描述：

自然语言：英语、中文

流程图：传统流程图、NS流程图

伪代码：类语言：类C语言

程序代码：C语言程序、JAVA语言程序…

算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以多种算法。

程序是用某种程序设计语言对算法的具体实现。

算法的特性：

一个算法必须具备以下五个重要特性：

1.有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

2.确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。

3.可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

4.输入：一个算法有零个或多个输入。

5.输出：一个算法有一个或多个输出。

算法设计的要求：

1.正确性(Correctness)

2.可读性(Readability)

3.健壮性(Robustness)

4.高效性(Efficiency)

一个好的算法首先要具备正确性，然后是健壮性，可读性；

主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。

算法效率以下两个方面来考虑:

1.时间效率：指的是算法所耗费的时间;

算法运行时间 = 一个简单操作所需的时间 × 简单操作次数

所以，我们可假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可转化为讨论该算法中所有语句的执行次数，即频度之和了。

2.空间效率：指的是算法执行过程中所耗费的存储空间。

时间效率和空间效率有时候是矛盾的。

1.4 总结

设计一个好的算法的过程：

2. 基本的数据结构

第2章线性表

2.1 线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列。

同一线性表中的元素必定具有相同特性，数据元素间的关系是线性关系。

从以上例子可看出线性表的逻辑特征是：

1.在非空的线性表，有且仅有1个开始结点a1，它没有直接前趋，而仅有一个直接后继az；

2.有且仅有一个终端结点an，它没有直接后继，而仅有1个直接前趋an-1;

3.其余的内部结点ai(2≤i≤n-1)都有且仅有1个直接前趋ai-1和1个直接后继ai+1。

2.2 案例引入

案例2.1 一元多项式的运算

案例2.2 稀疏多项式的运算

顺序存储结构存在问题：

1.存储空间分配不灵活，比如两个多项式相加，最少的情况下相加为0，C数组不分配空间；最多的清空下相加为7项，C数组分配7个内存空间。

2.运算的空间复杂度高

采用链式存储结构，可以灵活解决上述问题。

案例2.3 图书信息管理系统

总结

1.线性表中数据元素的类型可以为简单类型，也可以为复杂类型。

2.许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用单

独编写一个程序。

3.从具体应用中抽象出共性的逻辑结构+基本操作(就是抽象数据类型)，然后实现其存储结构和基本操作。

2.3 线性的类型定义

这里的类型就是抽象数据类型：数据对象、数据对象之间的关系集合、作用在这个数据对象上的基本操作。

2.3.1 基本操作（一）：初始化空表、销毁表、清空表

2.3.2 基本操作（二）：判断表为空、返回表长

2.3.3 基本操作（三）：查找某个元素、查找某个符合条件的元素

2.3.4 基本操作（四）：查找前驱、查找后继

2.3.5 基本操作（五）：插入

2.3.6 基本操作（六）：删除、遍历

总结

以上所提及的运算是逻辑结构上定义的运算。只要给出这些运算的功能是"做什么"，至于"如何做"等实现细节、只有待确定了存储结构之后才考虑。

2.4 线性表的顺序表示和实现

2.4.1 多项式的顺序存储结构类型定义

2.4.2 图书表的顺序存储结构类型定义

2.4.3 数组定义的补充

2.4.4 代码实例

2.4.4.1 线性表的初始化

// 线性表的定义
// 其实就是构造结构体：数组+长度
struct SqList
{
	ElemType* elem;  //顺序线性表的表头
	// 也可以这样定义，但是是数组静态分配，上述是动态的，因为可以使用指针指向数组首地址
	//ElemType elem[MAX_SIZE];  
	int length;      //顺序线性表的长度
};
// 线性表的初始化
bool InitList(SqList& L)
{
	L.elem = new ElemType[MAXSIZE];  // //在堆区开辟内存
	if (!L.elem)
	{
		return false;
	}
	L.length = 0;  //设定空表长度为0
	return 1;
}

2.4.4.2 线性表的销毁

// 线性表的销毁
void DestroyList(SqList& L)
{
	if (L.elem)
	{
		delete L.elem;
	}
}

2.4.4.3 线性表的清空

// 线性表的清空
void CLearList(SqList& L)
{
	L.length = 0;
}

2.4.4.4 线性表的长度

// 线性表的长度
int GetLength(SqList& L)
{
	return L.length;
}

2.4.4.5 判断线性表为空

// 判断线性表是否为空
bool IsEmpty(const SqList& L)
{
	// static_cast(L.length) 的作用是将 L.length 的值转换为布尔值 (bool)。
	return static_cast(L.length);
}

2.4.4.6 线性表取值

// 线性表取值
// 随机存取的时间复杂度是：O(1)
bool GetELem(const SqList &L, const size_t i, ElemType &e)
{
    if (i  MAXSIZE)
    {
        cerr
	for (int i = 0; i next = nullptr;  // // 使用 C++11 的 nullptr，类型安全
	return 1;
}

2.5.1.2 判断单链表为空

// 判断链表是否为空
bool IsEmpty(const LinkList& L)
{
	if (L->next)
	{
		// 非空
		return false;
	}
	else
	{
		// 为空
		return true;
	}
}

2.5.1.3 单链表的销毁

// 单链表的销毁
void DestroyList(LinkList& L)
{
	LinkList p;
	while (L)
	{
		// 就是定义1个指针p指向头结点，然后将头指针指向下一个结点，并删除当前p指向的结点
		p = L;
		L = L->next;
		delete p;
	}
}

2.5.1.4 单链表的清空

// 单链表的清空
void CLearList(LinkList& L)
{
	LinkList p, q;
	p = L->next;
	while (p)  // p非空，表示还没到表尾
	{
		q = p->next;
		delete p;
		p = q;
	}
	L->next = nullptr;  // 头结点指针域为空
}

2.5.1.5 单链表的表长

// 单链表的长度
int GetLength(LinkList& L)
{
	LinkList p;
	p = L->next;  // 将p指向首元结点 
	int i = 0;  // 计数
	while (p)
	{
		// 遍历单链表,统计结点数
		i++;
		p = p->next;
	}
	return i;
}

知识回顾

2.5.1.6 单链表的取值

// 单链表的取值
bool GetElem(const LinkList& L, const int& i, const ElemType& e)
{
	// 因为逻辑顺序和物理顺序相差1，我们说的取第3个数，3代表是物理顺序。
	// 所以我们定义1个指针指向头结点，并当前节点为1，开始遍历直到i=j停止循环
	LinkList p = L->next; 
	int j = 1; // 计数器
	while (p && i > j)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i) return false; // 第i个元素不存在
	e = p->data;
	return true;
}

2.5.1.7 单链表的查找

// 单链表的按值查找，返回L中值为e的数据元素的地址
// 时间复杂度：0(n)
LinkList LocateElem(LinkList& L, ElemType& e)
{
	// 在线性表L中查找值为e的数据元素
	// 找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
	LinkList p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
	}
	return p;
}
// 单链表的按值查找，返回L中值为e的位置序号
int LocateElem(LinkList& L, ElemType& e)
{
	// 返回L中值为e的数据元素的位置序号，查找失败返回
	LinkList p = L->next;
	int j = 1;
	while (p && p->data != e)
	{
		p = p->next;
		j++;
	}
	if (p)
	{
		return j;
	}
	else
	{
		return 0;
	}
}

2.5.1.8 单链表的插入

// 单链表的插入
// 时间复杂度：0(1)
bool InsertList(LinkList& L, const int& i, const ElemType& e)
{
	LinkList p = L;
	int j = 0;
	while (p && j next;
		j++;
	}
	if (!p || j > i - 1)
	{
		return 0;  // i大于表长+1或者小于1，插入位置非法
	}
	// 生成新结点s，将结点s的数据域置为e
	LinkList s = new Lnode;
	s->data = e;
	// 将结点s插入L中
	s->next = p->next;
	p->next = s;
}

2.5.1.9 单链表的删除第i个结点

// 单链表的删除
// 将单链表L中第i个数据元素删除
// 时间复杂度：0(1)
bool EraseList(LinkList& L, const int& i, const ElemType& e)
{
	LinkList p = L, q;
	int j = 0;
	while (p && j next;
		j++;
	}
	if (!(p->next) || j > i - 1)
	{
		return 0;  // 删除位置不合理
	}
	q = p->next;  // 临时保存被删结点的地址以备释放
	p->next = q->next; // 改变删除结点前驱结点的指针域
	e = q->data;
	delete q;
	return true;
}

2.5.1.10 单链表头插法

头插法是倒序插入，先插入An，再是An-1，直到A1；而尾插法是正序，先插A1，再一直到An。

// 单链表的头插
// n表示结点个数
// 算法时间复杂度：O(n)
void CreatListHead(LinkList& L, int n)
{
	L = new Lnode;
	L->next = nullptr;  // 先建立一个带头结点的单链表
	for (int i = 0; i > p->data; // 输入元素值
		p->next = L->next;  // 插入到表头
		L->next = p;
	}
}

2.5.1.11 单链表尾插法

// 单链表的尾插
// 算法时间复杂度：O(n)
void CreatListTail(LinkList& L, int n)
{
	L = new Lnode;
	L->next = nullptr;
	LinkList r = L;  // 尾指针r指向头结点
	for (int i = 0; i > p->data;  // 生成新结点，输入元素值
		p->next = nullptr;
		r->next = p; // 插入到表尾
		r = p; // r指向新的尾结点
	}
}

总结

1.基本上链表的操作，都是和指针挂钩的，就是额外定义1个指针，因为直接对头指针操作，很容易找不到next元素了。比如销毁，额外的指针从头结点开始；如果是清空，则从首元结点开始；比如，计数，额外的指针从头结点开始。

2.并且如果是插入等操作，先顾后面的结点，如果先链接前面的结点，后面的结点就找不到了。

2.5.2 循环链表的代码实例

2.5.2.1 循环链表的合并

 // 两个链表的合并
 // 算法时间复杂度：O(1)
LinkList ConnectList(LinkList& Ta, LinkList& Tb)
{
	// 假设Ta、Tb都是非空的单循环链表
	LinkList p = Ta->next;  // ①p存表头结点
	Ta->next = Tb->next->next;  // ②Tb表头连结Ta表尾
	delete Tb->next;  // ③释放Tb表头结点
	Tb->next = p;  // ④修改指针
	return Tb;
}

总结

1.单链表使用头指针，比较方便；而单循环链表中，使用尾指针，比较方便。

2.单链表必须通过头指针逐个遍历访问每个结点，而单循环链表可以通过任意一个结点出发。

2.5.3 双向链表的代码实例

如果是双向链表，头结点的prior域和尾结点的next域为空；而如果是双向循环链表，头结点的prior域指向尾结点和尾结点的next域指向头结点。空表，则都是指向空。

2.5.3.1 双向链表的插入

// 双向链表的定义
// 首先定义了一个结构体 DuLnode，然后通过 typedef 定义了一个指向该结构体的指针类型 DuLinkList。
// 这里 typedef 的部分只定义了 DuLnode* 的别名 DuLinkList，而 DuLnode 是单独的结构体定义。
typedef struct DuLnode
{
	ElemType data;  //结点的数据域 
	DuLnode* prior, * next;    
}*DuLinkList;
// 双向链表的初始化
void InitList(DuLinkList& L)
{
	L = new DuLnode;  
	L->prior = nullptr;  
	L->next = nullptr;  
}
// 双向链表的第i个位置插入元素
bool InsertList(DuLinkList& L, const int& i, const ElemType& e)
{
	// 在带头结点的双向循环链表L中第i个位置之前插入元素e
	DuLinkList p = L->next;
	int j = 1;
	while (p->next && j next;
		j++;
	}
	if (j data = e;
	// 重新建立链接关系, 将结点s插入链表中
	s->prior = p->prior;  //第一步：s的前趋等于p的前趋
	p->prior->next = s;  //第二步，用p的前趋结点的next指向插入元素s，更改了第一条链
	s->next = p;        //第三步：s的后继指向p
	p->prior = s;       //第四步：p的前趋改为指向s，更改了第二条链
	return true;
}

2.5.3.2 双向链表的删除

// 双向链表的删除某个元素
bool ListErase_DuL(DuLinkList& L, const int& i, const ElemType& e)
{
	DuLinkList p = L->next;
	int j = 1;
	while (p && j next;
		j++;
	}
	if (j prior->next = p->next;
	p->next->prior = p->prior;
	delete p;
	return true;
}

2.6 单链表、循环链表、双向链表的比较

2.7 顺序表和链表的比较

2.8 线性表的应用

2.8.1 线性表的合并

// 线性表的合并
// 通用算法：顺序表和链表都可以
void Union(LinkList& Ta, LinkList Tb)
{
	La_len = ListLength(Ta);
	Lb_len = ListLength(Tb);
	for (int i = 1; i 
		GetElem(Lb, i, e);
		if (!Locate(Ta, e))
		{
			ListInsert(&Ta, ++La_len, e);
		}
	}
}

	int* pa = list1.elem;
	int* pa_last = list1.elem + list1.length - 1;
	int* pb = list2.elem;
	int* pb_last = list2.elem + list2.length - 1;
	list3.length = list1.length + list2.length;
	list3.elem = new int[list3.length];
	int* pc = list3.elem;
	while (pa 
		// 依次“摘取”两表中值较小的结点
		if (*pa 
			*pc = *pa;
			pa++;
			pc++;
		}
		else
		{
			*pc = *pb;
			pb++;
			pc++;
		}
	}
	// pb表已到达表尾，将pa中剩余元素加入pc
	while (pa  
		*pc = *pa;
		pa++;
		pc++;
	}
	// pa表已到达表尾，将pb中剩余元素加入pc
	while (pb 
		*pc = *pb;
		pb++;
		pc++;
	}
}

	LinkList pa = La-next;
	LinkList pb = Lb-next;
	Lc = La;
	// 用La的头结点作为Lc的头结点
	LinkList pc = Lc;
	while (pa && pb)
	{
		if (pa-data 
			pc-next = pa;
			pc = pa;
			pa = pa-next;
		}
		else
		{
			{
				pc-next = pb;
				pc = pb;
				pb = pb->next;
			}
		}
		pc->next = pa ? pa : pb;
		delete pb;
	}
}

2.9 案例分析与实现

2.9.1 一元多项式的运算

2.9.2 稀疏多项式的运算

// 存放多项式的单链表的定义
struct PNode
{
	float coef;  //数据域：系数 
	int expn;    //数据域：指数 
	PNode* next;    //指针域
}; 
typedef PNode* Polynomial;
// 多项式创建
void CreatePolyn(Polynomial& p, int n)
{
	// 建立—个带头结点的单链表
	p = new PNode;  
	p->next = nullptr;
	for (int i = 0; i > s->coef >> s->expn; // 输入系数和指数
		Polynomial pre = p;
		Polynomial q = p->next;
		while (q && q->expn expn)
		{
			pre = q;
			q = q->next;
		}
		s->next = q;
		pre->next = s;
	}
}
// 稀疏多项式的相加
void Merge(Polynomial& La, Polynomial& Lb, Polynomial& Lc)
{
	Polynomial pa = La->next;
	Polynomial pb = Lb->next;
	Lc = La;
	Polynomial pc = Lc;  // pc指向多项式的当前结点，初值为pa的头结点
	while (pa && pb)
	{
		// 指数相同的情况下
		if (pa ->expn == pb->expn)
		{
			// 系数相加
			pa->coef += pb->coef;
			pc->next = pa;
			// pa、pb、pc指针均向后移
			pa = pa->next;
			pb = pb->next;
			pc = pc->next;
		}
		// pa小，pc与pa连接
		else if (pa->expn expn)
		{
			pc->next = pa;
			// pa、pc指针均向后移
			pa = pa->next;
			pc = pc->next;
		}
		// pb小，pc与pb连接
		else if (pa->expn > pb->expn)
		{
			pc->next = pb;
			// pb、pc指针均向后移
			pb = pb->next;
			pc = pc->next;
		}
	}
	// 将pa 或者pb中余下的接到pc后
	pc->next = (pa ? pa : pb);
	delete Lb;
}

2.9.3 图书信息管理系统

第3章栈和队列

3.1 栈和队列的定义和特点

3.1.1 栈的定义和特点

3.1.2 队列的定义和特点

3.2 案例引入

3.2.1 进制转换

3.2.2 括号匹配的检验

3.2.3 表达式求值

3.2.4 舞伴问题

3.3 栈的顺序表示和操作的实现

3.3.1 栈的抽象数据类型的定义

3.3.2 顺序栈的表示和实现

3.3.2 代码实例

3.3.2.1 栈的初始化

// 顺序栈的定义
struct SqStack
{
	ElemType* base;  // 栈底指针
	ElemType* top;  // 栈顶指针
	int stacksize;  // 栈可用最大容量
};
// 顺序栈的初始化
bool InitStack(SqStack& S)  // 构造一个空栈
{
	S.base = new ElemType[MAXSIZE];
	if (!S.base)
	{
		return false;
	}
	//栈顶指针等于栈底指针
	S.top = S.base;
	S.stacksize = MAXSIZE;
}

3.3.2.2 判断栈是否为空

// 判断顺序栈是否为空
bool IsEmpty(SqStack& S)
{
	if (S.base == S.top)
	{
		return true;
	}
	else
	{
		return false;
	}
}

3.3.2.3 求顺序栈的长度

// 求顺序栈的长度
int StackLength(SqStack& S)
{
	return static_cast(S.top - S.base);
}

3.3.2.4 清空栈

// 清空栈
bool ClearStack(SqStack& S)
{
	if (S.base)
	{
		S.base == S.top;
		return true;
	}
	else
	{
		return false;
	}
}

3.3.2.5 销毁栈

// 销毁顺序栈
bool DestoyStack(SqStack& S)
{
	if (S.base)
	{
		delete S.base;
		S.base = S.top = nullptr;
		S.stacksize = 0;
		return true;
	}
}

3.3.2.6 顺序栈的入栈

// 入栈
bool Push(SqStack& S, ElemType& e)
{
	// (1)判断是否栈满, 若满则出错(上溢)
	if (static_cast(S.top-S.base) == S.stacksize)
	{
		return false;
	}
	// (2)元素e压入栈顶
	*S.top = e;
	// (3)栈顶指针加1
	S.top++;
}

3.3.2.7 顺序栈的出栈

// 出栈
bool Pop(SqStack& S, ElemType& e)
{
	// (1)判断是否栈空，若空则出错（下溢)
	if (S.base == S.top)
	{
		return false;
	}
	// (2)栈顶指针减1
	S.top--;
	// (3)获取栈顶元素
	e = *S.top;
}

3.4 链栈的表示与实现

3.4.1 代码实例

3.4.1.1 链栈的初始化

// 链栈的定义
typedef struct StackNode
{
	ElemType data;  // 数据域
	StackNode* next;  // 栈顶指针
}*LinkStack;
// 链栈的初始化
bool InitStack(LinkStack& S)  // 构造一个空栈
{
	// 这里链栈没有使用链表的头结点，是因为这里会更麻烦
	S = nullptr;
	return true;
}

3.4.1.2 判断链栈是否为空

// 判断链栈是否为空
bool IsEmpty(LinkStack& S)
{
	if (S==nullptr)
	{
		return true;
	}
	else
	{
		return false;
	}
}

3.4.1.3 链栈的入栈

// 入栈
bool Push(LinkStack& S, ElemType& e)
{
	LinkStack P = new StackNode;  // 生成新结点P
	P->data = e;  // 将新结点数据域设置为e
	P->next = S;  // 将新结点插入栈顶
	S = P;  // 修改栈顶指针
	return true;
}

3.4.1.4 链栈的出栈

// 出栈
bool Pop(LinkStack& S, ElemType& e)
{
	if (S==nullptr)
	{
		return false;
	}
	e = S->data;
	LinkStack P = S;
	S = S->next;
	delete P;
	return true;
}

3.4.1.5 取栈顶元素

// 获取栈顶元素
ElemType GetTop(LinkStack& S)
{
	if (S != nullptr)
	{
		return S->data;
	}
}

3.5 栈与递归

3.6 队列的顺序表示和操作的实现

3.6.1 队列的抽象数据类型的定义

3.6.2 队列的顺序表示和实现

3.6.3 代码实例

3.6.3.1 循环队列的初始化

// 队列的定义
typedef struct SqQueue
{
	ElemType* base;  // 初始化的动态分配存储空间
	int front;  // 头指针，若队列不空，指向队列头元素
	int rear;  // 尾指针，若队列不空，指向队列尾元素的下一个位置
};
// 队列的初始化
bool InitQueue(SqQueue& Q)  // 构造一个空栈
{
	Q.base = new ElemType[MAXSIZE];  // 分配数组空间
	if (!Q.base)
	{
		return false;  // 分配失败
	}
	// 头指针尾指针置为0，队列为空
	Q.front = 0;
	Q.rear = 0;
}

3.6.3.2 求循环队列的长度

// 求队列的长度
int GetLength(SqQueue& Q)
{
	return (Q.rear - Q.base + MAXSIZE) % MAXSIZE;
}

3.6.3.3 入队

// 循环队列入队
bool EnQueue(SqQueue& Q, ElemType& e)
{
	if ((Q.rear + 1) % MAXSIZE == Q.front)
	{
		return false;  // 队满
	}
	Q.base[Q.rear] = e;  // 新元素加入队尾
	Q.rear = (Q.rear + 1) % MAXSIZE;  // 队尾指针+1
	return true;
}

3.6.3.4 出队

// 循环队列出队
bool DeQueue(SqQueue& Q, ElemType& e)
{
	if (Q.rear == Q.front)
	{
		return false;  // 队空
	}
	Q.base[Q.front] = e;  // 保存队头元素
	Q.front = (Q.front + 1) % MAXSIZE;  // 队头 指针+1
	return true;
}

3.6.3.5 取队头元素

// 取队头元素
ElemType GetHead(SqQueue& Q)
{
	if (Q.front != Q.rear)  // 队列不为空
	{
		return Q.base[Q.front];
	}
}

3.7 队列的链式表示和实现

3.7.1 代码实例

3.7.1.1 链队的初始化

// 链队的初始化
bool InitQueue(LinkQueue& Q)  
{
	Q.front = Q.rear = new Qnode;
	Q.front->next = nullptr;
	return true;
}

3.7.1.2 链队的销毁

// 链队的销毁
bool DestroyQueue(LinkQueue& Q)
{
	while (Q.front)
	{
		Qnode* p = Q.front->next;
		delete Q.front;
		Q.front = p;
	}
		return true;
}

3.7.1.3 链队的入队

// 入队
bool EnQueue(LinkQueue& Q, const ELemType& e)
{
	//把元素插在最后面
	Qnode* p = new Qnode;
	p->data = e;
	p->next = nullptr;
	Q.rear->next = p;
	Q.rear = p;
	return true;
}

3.7.1.4 链队的出队

// 出队
bool DeQueue(LinkQueue& Q, const ELemType& e)
{
	if (Q.front == Q.rear)  // 队空
	{
		return false;
	}
	Qnode* p = Q.front->next;
	e = p->data;
	Q.front->next = p->next;
	delete p;
}

// 出队
bool DeQueue(LinkQueue& Q, const ELemType& e)
{
	if (Q.front == Q.rear)  // 队空
	{
		return false;
	}
	Qnode* p = Q.front->next;
	e = p->data;
	Q.front->next = p->next;
	if (Q.rear == p)
	{
		// 
		Q.rear = Q.front;
	}
	delete p;
}

3.7.1.5 求链队的队头元素

// 求链队的队头元素
bool GetHead(LinkQueue& Q, const ELemType& e)
{
	if (Q.front == Q.rear)  // 队空
	{
		return false;
	}
	e = Q.front->next->data;
	return true;
}

第4章串、数组和广义表

4.1 串的定义

4.2 案例引入

4.3 串的类型定义、存储结构及其运算

4.3.1 串的类型定义

4.3.2 串的顺序存储结构

4.3.3 串的链式存储结构

4.3.4 串的模式匹配算法及代码实例

4.3.4.1 BF算法

4.3.4.2 BF算法代码实例

#define MAXLEN 25
// 串的顺序存储定义
struct SString
{
	char ch[MAXLEN];  // 存储串的一维数组
	int length;  // 串的当前长度
};
int index_BF(SString S, SString T)
{
	// 如果不是从第一个字符开始匹配，要从指定的位置开始查找，将i参数化  -->  int i = pos;
	int i = 1, j = 1;
	while (i 
		//  主串和子串当前字符相等
		if (S.ch[i] == T.ch[j])
		{
			// 依次匹配下一个字符
			i++;
			j++;
		}
		// 主串、子串指针回溯重新开始下-次匹配
		else
		{
			// 主串回到下一个字符
			i = i - j + 2;
			// 子串回到第一个字符等到下一次匹配
			j = 1;
		}
	}
	if (j = T.length)
	{
		return i - T.length;  // 返回匹配的第一个字符的下标
	}
	else
	{
		return 0;  // 模式匹配不成功
	}
}

	// 如果不是从第一个字符开始匹配，要从指定的位置开始查找，将i参数化  --  int i = pos;
	int i = 1, j = 1;
	while (i 
		if (j == 0 || S.ch[i] == T.ch[j])
		{
			// 依次匹配下一个字符
			i++;
			j++;
		}
		// 主串、子串指针回溯重新开始下-次匹配
		else
		{
			j = next[j];  // i不变，j后退
		}
	}
	if (j = T.length)
	{
		return i - T.length;  // 返回匹配的第一个字符的下标
	}
	else
	{
		return 0;  // 模式匹配不成功
	}
}

	ElemType data;
	BiNode* lchild, * rchild;  // 左、右孩子指针
}BiNode, *BiTree;
// 二叉树的先序遍历 DLR
bool PreOrderTraverse(BiTree& T)
{
	if (T == nullptr)
	{
		return false;  // 空树
	}
	// 首先访问根节点
	visit(T);  // 比如cout
	if (T == nullptr)
	{
		return false;  // 空树
	}
	
	//递归遍历左孩子
	InOrderTraverse(T-lchild);
	// 访问根节点
	visit(T);
	//递归遍历右孩子
	InOrderTraverse(T->rchild);
	return true;
}

5.5.2.3 二叉树后序遍历

// 二叉树的后序遍历 LDR
bool PostOrderTraverse(BiTree& T)
{
	if (T == nullptr)
	{
		return false;  // 空树
	}
	//递归遍历左孩子
	PostOrderTraverse(T->lchild);
	//递归遍历右孩子
	PostOrderTraverse(T->rchild);
	// 访问根节点
	visit(T);
	return true;
}

5.5.2.4 遍历算法的分析

5.5.3 遍历二叉树的非递归代码实例

以中序遍历为例，因为根节点在最先，而中序先访问左子树，所以根节点入栈，访问完左子树，再将根节点出栈，最后再访问右子树。

// 顺序栈的定义
struct SqStack
{
	ElemType* base;  // 栈底指针
	ElemType* top;  // 栈顶指针
	int stacksize;  // 栈可用最大容量
};
// 顺序栈的初始化
bool InitStack(SqStack& S)  // 构造一个空栈
{
	S.base = new ElemType[MAXSIZE];
	if (!S.base)
	{
		return false;
	}
	//栈顶指针等于栈底指针
	S.top = S.base;
	S.stacksize = MAXSIZE;
}
// 判断顺序栈是否为空
bool IsEmpty(SqStack& S)
{
	if (S.base == S.top)
	{
		return true;
	}
	else
	{
		return false;
	}
}
// 入栈
bool Push(SqStack& S, ElemType& e)
{
	// (1)判断是否栈满, 若满则出错(上溢)
	if (static_cast(S.top - S.base) == S.stacksize)
	{
		return false;
	}
	// (2)元素e压入栈顶
	*S.top = e;
	// (3)栈顶指针加1
	S.top++;
}
// 出栈
bool Pop(SqStack& S, ElemType& e)
{
	// (1)判断是否栈空，若空则出错（下溢)
	if (S.base == S.top)
	{
		return false;
	}
	// (2)栈顶指针减1
	S.top--;
	// (3)获取栈顶元素
	e = *S.top;
}
// 二叉树的中序遍历——非递归算法
// 以“中序遍历”为例，因为根节点在最先，
// 而中序先访问左子树，所以根节点`入栈`，访问完左子树，再将根节点出栈，最后再访问右子树。
bool InOrderTraverse(BiTree& T)
{
	//第一步：创建一个栈，用于保存二叉树的结点
	SqStack S;
	InitStack(S);
	BiTree p = T;  // p也指向根节点
	// 首先判断是根节点不为空的话，将根节点入栈
	while (p || !IsEmpty(S))
	{
		if (p)
		{
			Push(S, p);
			// 根节点入栈后，访问左子树
			p = p->lchild;
		}
		else
		{
			Pop(S, q);
			visit(q);
			p = p->rchild;
		}
	}
	return true;
}

5.5.4 二叉树的层次遍历代码实例

// 队列的定义
typedef struct SqQueue
{
	ElemType* base;  // 初始化的动态分配存储空间
	int front;  // 头指针，若队列不空，指向队列头元素
	int rear;  // 尾指针，若队列不空，指向队列尾元素的下一个位置
};
// 队列的初始化
bool InitQueue(SqQueue& Q)  // 构造一个空栈
{
	Q.base = new ElemType[MAXSIZE];  // 分配数组空间
	if (!Q.base)
	{
		return false;  // 分配失败
	}
	// 头指针尾指针置为0，队列为空
	Q.front = 0;
	Q.rear = 0;
}
// 循环队列入队
bool EnQueue(SqQueue& Q, ElemType& e)
{
	if ((Q.rear + 1) % MAXSIZE == Q.front)
	{
		return false;  // 队满
	}
	Q.base[Q.rear] = e;  // 新元素加入队尾
	Q.rear = (Q.rear + 1) % MAXSIZE;  // 队尾指针+1
	return true;
}
// 循环队列出队
bool DeQueue(SqQueue& Q, ElemType& e)
{
	if (Q.rear == Q.front)
	{
		return false;  // 队空
	}
	Q.base[Q.front] = e;  // 保存队头元素
	Q.front = (Q.front + 1) % MAXSIZE;  // 队头 指针+1
	return true;
}
// 二叉树的层次遍历
bool InOrderTraverse(BiTree& T)
{
	SqQueue Q;
	InitQueue(Q);
	EnQueue(Q, T); // 将根节点入队
	BiTree p;
	while (!QueueEmpty(Q)) // 队不为空，则循环
	{
		// 将根节点出队
		DeQueue(Q, p);
		//访问根结点
		cout data lchild != nullptr)
		{
			EnQueue(Q, p->lchild);
		}
		// 有右孩子时将其讲队
		if (p->rchild != nullptr)
		{
			EnQueue(Q, p->rchild);
		}
	}
}
// 二叉树的后序遍历 LDR
bool PostOrderTraverse(BiTree& T)
{
	if (T == nullptr)
	{
		return false;  // 空树
	}
	//递归遍历左孩子
	PostOrderTraverse(T->lchild);
	//递归遍历右孩子
	PostOrderTraverse(T->rchild);
	// 访问根节点
	visit(T);
	return true;
}

5.5.5 二叉树遍历算法的应用—二叉树的建立

// 二叉树的链式定义
typedef struct BiNode
{
	ElemType data;
	BiNode* lchild, * rchild;  // 左、右孩子指针
}BiNode, * BiTree;
// 二叉树的建立（DLR先序遍历，递归算法）
bool CreatBiTree(BiTree& T)
{
	ElemType ch;
	cin >> ch;
	if (ch == "#")//建立空结点的标志为 #
	{
		T = nullptr;
	}
	else
	{
		T = new BiNode;  // 开辟内存 分配1个新结点
		T->data = ch;  // 生成根结点，并存放数据域
		CreatBiTree(T->lchild);  // 构造左子树
		CreatBiTree(T->rchild);  // 构造右子树
	}
	return true;
}

5.5.6 二叉树遍历算法的应用—赋值二叉树

// 二叉树的复制
bool Copy(const BiTree& T, BiTree& NewT)
{
	if (T == nullptr)  // 空树
	{
		return 0;
	}
	else
	{
		NewT = new BiNode;
		NewT->data = T->data;
		Copy(T->lchild, NewT->lchild);
		Copy(T->rchild, NewT->rchild);
	}
}

5.5.7 二叉树遍历算法的应用—计算二叉树的深度

// 求二叉树的深度
int Depth(BiTree& T)
{
	if (T == nullptr)
	{
		return 0;
	}
	int m = Depth(T->lchild);
	int n = Depth(T->rchild);
	if (m > n )
	{
		return m + 1;
	}
	else
	{
		return n + 1;
	}
}

5.5.8 二叉树遍历算法的应用—计算二叉树的结点总数

// 求二叉树的结点数
int CountNode(BiTree& T)
{
	if (T == nullptr)
	{
		return 0;
	}
	 //L
	 int m = CountNode(T->lchild);
	 //R
	 int n = CountNode(T->rchild);
	 //
	 return m + n + 1;
	//更加简单的语句
	//return CountNode(T->lchild) + CountNode(T->rchild) + 1;
}

5.5.9 二叉树遍历算法的应用—计算二叉树的叶子结点总数

// 求二叉树的叶子结点数
int LeadNode(BiTree& T)
{
	if (T == nullptr)
	{
		return 0;  // 空树返回0
	}
	// 不是空树，那么下面要判断是不是叶子节点
	// 左右子树都为空，那么是叶子结点
	if (T ->lchild == nullptr && T->rchild == nullptr)
	{
		return 1;
	}
	// 不是叶子结点，那么继续往下遍历下面的左右子树
	else
	{
		return LeadNode(T->lchild) + LeadNode(T->rchild);
	}
}

5.6 线索二叉树

因为，如果是n个结点，会有2n个指针域，而有n-1个孩子，也就是2n个指针域中，有n-1个用来指示结点的左右孩子，其余n+1个指针域都为空。

5.7 树和森林

5.7.1 树的存储结构

5.7.1.1 双亲表示法

5.7.1.2 孩子链表

5.7.1.3 孩子兄弟表示法

5.7.2 树与二叉树的转换

5.7.3 森林与二叉树的转换

5.7.4 树与森林的遍历

5.7.4.1 树的遍历

5.7.4.2 森林的遍历

5.8 哈夫曼树及其应用

5.8.1 哈夫曼树的基本概念

5.8.2 哈夫曼树的构造算法

5.8.3 总结

5.8.4 代码实例

// 哈夫曼树的定义
typedef struct HNode
{
	int weight;                  //权重
	int parent, lchild, rchild;  //每个结点的双亲、左右孩子的数组下标
} *HuffmanTree;
// 哈夫曼树的初始化
void InitHTree(HuffmanTree& HT, const int n)
{
	if (n 
		return;
	}
	int m = 2*n - 1;  // 数组共2n-1个元素
	HT = new HNode[m + 1];  // 0号单元未用，HT[m]表示根结点
	// 将2n-1个元素的lch、rch、parent置为0
	for (int i = 1; i 
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
	}
	// 输入前n个元素的weight值
	for (int i = 1; i 
		cin  HT[i].weight;
	}
}
// 哈夫曼树的构造算法
void CreatHuffman(HuffmanTree& HT, const int n)
{
	// 初始化
	InitHTree(HT, n);
	// 合并产生n-1个结点——构造Huffman树
	for (int i = n + 1; i 
		int s1 = 0, s2 = 0;
		// 在HT[k](1≤k≤i-1)中选择两个其双亲域为0,
		// 且权值最小的结点, 并返回它们在HT中的序号s1和s2
		Select(HT, i - 1, s1, s2);//重点是这个Select算法
		// 表示从F中删除s1,s2
		HT[s1].parent = i;
		HT[s2].parent = i;
		// s1,s2分别作为i的左右孩子
		HT[i].lchild = s1;
		HT[i].rchild = s2;
		// i的权值为左右孩子权值之和
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
}

	char Vexs[MAXSIZE];  // 图的顶点向量
	int Arcs[MAXSIZE][MAXSIZE];  // 图的邻接矩阵
	int vexnum, arcnum;  // 图的总顶点数和总边数
};
// 邻接矩阵的LocateVex函数
int LocateVex(AMGraph& G, const char& e)
{
	for (int i = 0; i > G.arcnum; //输入总顶点数和总边数
	for (int i = 0; i > G.Vexs[i];  // 依次输入点的信息 
	}
	// 初始化邻接矩阵
	for (int i = 0; i > v1 >> v1 >> weight;   // 输入一条边所依附的顶点及边的权值
		//由输入的顶点v1和v2查找到对应的下标i,j
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G.Arcs[i][j] = weight;
		G.Arcs[j][i] = weight;
	}
	return true;
}

6.4.2 邻接表

6.4.3 邻接表的代码实例

// 邻接表表示法
//顶点的结点结构的定义
typedef struct VNode
{
	VecTexType data;  // 数据域，存放顶点
	ArcNode* firstarc;  //指针域，用于保存邻接表的
}VNode, AdjList[MAXSIZE];
//弧（边）的结点结构的定义
struct ArcNode  // 边结点
{
	int adjvex;       // 该边所指向的顶点的位置
	ArcNode* nextarc; //指向下一个边结点
};
//图的结构的定义
struct ALGraph
{
	//定义一个数组，保存图的顶点
	AdjList vertics;
	//定义两个变量，保存当前图的顶点个数以及边的条数
	int vexnum, arcnum;
};
// 邻接表的LocateVex函数
int LocateVex(ALGraph& G, const char& v)
{
	for (int i = 0; i > G.vexnum >> G.arcnum;  // 输入总顶点数，总边数
	// 输入各点，构造表头结点表
	for (int i = 0; i > G.vertics[i].data;  // 输入结点值
		G.vertics[i].firstarc == nullptr;  // 初始化表头结点的指针域
	}
	// 输入各边，构造邻接表
	for (int k = 0; k > v1 >> v2;
		int i = LocateVex(G, v1);
		int j = LocateVex(G, v2);
		ArcNode* p1 = new ArcNode;  // 生成一个新的边结点*p1
		p1->adjvex = j; // 邻接点序号为j
		p1->nextarc = G.vertics[i].firstarc;
		G.vertics[i].firstarc = p1;  // 将新结点*p1插入顶点v[i]的边表头部
		// 因为是无向图，所以b-->e，也得e-->b
		ArcNode* p2 = new ArcNode;  // 生成另一个对称的新的边结点*p2
		p2->adjvex = i;  // 邻接点序号为i
		p2->nextarc = G.vertics[j].firstarc;
		G.vertics[j].firstarc = p2;  // 将新结点*p2插入顶点v[j]的边表头部
	}
	return true;
}

6.4.4 邻接矩阵和邻接表的关系

6.4.5 十字链表

6.4.6 邻接多重表

6.5 图的遍历

6.5.1 深度优先遍历

6.5.2 深度优先搜索遍历算法的实现

// 邻接矩阵表示法
struct AMGraph
{
	char Vexs[MAXSIZE];  // 图的顶点向量
	int Arcs[MAXSIZE][MAXSIZE];  // 图的邻接矩阵
	int vexnum, arcnum;  // 图的总顶点数和总边数
};
// 定义一个visited数组作标志
int visited[MAXSIZE] = {0};
// 深度优先遍历算法DFS
void DFS(AMGraph& G, int v)
{
	cout 
		if (!visited[w] && G.Vexs[v][w])
		{
			DFS(G, w);  // //w是v的邻接点，如果w未访问，则递归调用DFS
		}
	}
}

	ElemType* base;  // 初始化的动态分配存储空间
	int front;  // 头指针，若队列不空，指向队列头元素
	int rear;  // 尾指针，若队列不空，指向队列尾元素的下一个位置
};
// 队列的初始化
bool InitQueue(SqQueue& Q)  // 构造一个空栈
{
	Q.base = new ElemType[MAXSIZE];  // 分配数组空间
	if (!Q.base)
	{
		return false;  // 分配失败
	}
	// 头指针尾指针置为0，队列为空
	Q.front = 0;
	Q.rear = 0;
}
// 循环队列入队
bool EnQueue(SqQueue& Q, ElemType& e)
{
	if ((Q.rear + 1) % MAXSIZE == Q.front)
	{
		return false;  // 队满
	}
	Q.base[Q.rear] = e;  // 新元素加入队尾
	Q.rear = (Q.rear + 1) % MAXSIZE;  // 队尾指针+1
	return true;
}
// 循环队列出队
bool DeQueue(SqQueue& Q, ElemType& e)
{
	if (Q.rear == Q.front)
	{
		return false;  // 队空
	}
	Q.base[Q.front] = e;  // 保存队头元素
	Q.front = (Q.front + 1) % MAXSIZE;  // 队头 指针+1
	return true;
}
int visited[MAXSIZE] = {0};
// 广度优先遍历算法BFS
void BFS(AMGraph& G, int v)
{
	cout 
		// 队头元素出队
		DeQueue(Q, u);
		// 循环遍历u的每个邻接点
		for (int w = FistAdjVex(G,u); w = 0; w=NextAdjVex(G,u,w))
		{
			// 如果这个邻接点还没访问，就入队
			if (!visited[w])
			{
				visited[w] = true;
				EnQueue(Q, w);  // v入队
			}
		}
	}
}

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们。

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

数据结构与算法（快速基础C++版）

1. 基本概念

第1章 绪论

1.1 数据结构的研究内容

1.2 基本概念和术语

1.2.1 数据、数据元素、数据项和数据对象

1.2.2 数据结构

1.2.3 数据类型和抽象数据类型

1.2.4 概念小结

1.3 算法和算法分析

1.4 总结

2. 基本的数据结构

第2章 线性表

2.1 线性表的定义和特点

2.2 案例引入

案例2.1 一元多项式的运算

案例2.2 稀疏多项式的运算

案例2.3 图书信息管理系统

总结

2.3 线性的类型定义

2.3.1 基本操作（一）：初始化空表、销毁表、清空表

2.3.2 基本操作（二）：判断表为空、返回表长

2.3.3 基本操作（三）：查找某个元素、查找某个符合条件的元素

2.3.4 基本操作（四）：查找前驱、查找后继

2.3.5 基本操作（五）：插入

2.3.6 基本操作（六）：删除、遍历

总结

2.4 线性表的顺序表示和实现

2.4.1 多项式的顺序存储结构类型定义

2.4.2 图书表的顺序存储结构类型定义

2.4.3 数组定义的补充

2.4.4 代码实例

2.4.4.1 线性表的初始化

2.4.4.2 线性表的销毁

2.4.4.3 线性表的清空

2.4.4.4 线性表的长度

2.4.4.5 判断线性表为空

2.4.4.6 线性表取值

2.5.1.2 判断单链表为空

2.5.1.3 单链表的销毁

2.5.1.4 单链表的清空

2.5.1.5 单链表的表长

知识回顾

2.5.1.6 单链表的取值

2.5.1.7 单链表的查找

2.5.1.8 单链表的插入

2.5.1.9 单链表的删除第i个结点

2.5.1.10 单链表头插法

2.5.1.11 单链表尾插法

总结

2.5.2 循环链表的代码实例

2.5.2.1 循环链表的合并

总结

2.5.3 双向链表的代码实例

2.5.3.1 双向链表的插入

2.5.3.2 双向链表的删除

2.6 单链表、循环链表、双向链表的比较

2.7 顺序表和链表的比较

2.8 线性表的应用

2.8.1 线性表的合并

2.9 案例分析与实现

2.9.1 一元多项式的运算

2.9.2 稀疏多项式的运算

2.9.3 图书信息管理系统

第3章 栈和队列

3.1 栈和队列的定义和特点

3.1.1 栈的定义和特点

3.1.2 队列的定义和特点

3.2 案例引入

3.2.1 进制转换

3.2.2 括号匹配的检验

3.2.3 表达式求值

3.2.4 舞伴问题

3.3 栈的顺序表示和操作的实现

3.3.1 栈的抽象数据类型的定义

3.3.2 顺序栈的表示和实现

3.3.2 代码实例

3.3.2.1 栈的初始化

3.3.2.2 判断栈是否为空

3.3.2.3 求顺序栈的长度

第1章绪论

第2章线性表

第3章栈和队列

第4章串、数组和广义表

5.5.9 二叉树遍历算法的应用—计算二叉树的叶子结点总数