基本概念
数据
在计算机科学中，数据是信息的载体，是指输入计算机并被计算机程序识别和处理的所有符号的集合。
数据元素
数据元素，也称为节点，是表示数据的基本单元，通常在计算机程序中作为一个整体来考虑和处理。
数据项
数据项是数据元素的最小不可分割单元。
数据对象
数据对象是具有相同属性的数据元素的集合，并且是数据的子集。
注意：除非发生混淆，否则数据对象简称为数据。
数据结构
数据结构是指彼此之间具有特定关系的数据元素的集合。即数据结构是一个元组DataStructure=(D, R)。这里，D是数据元素的集合，R是关系的集合。在D 中。根据不同的观点，数据结构分为逻辑结构和存储结构。
数据的逻辑结构
数据的逻辑结构是指数据元素之间的整体逻辑关系。数据结构根据数据元素之间逻辑关系的不同分为四类。
(1)集合：数据元素“属于同一集合”并且在其他方面不相关。
(2)线性结构：数据元素之间存在一对一的线性关系。
(3)树结构：数据元素之间存在一对多的层次关系。
(4)图结构：数据元素之间存在任意的多对多关系。
注：数据结构分为两类：线性结构和非线性结构。
数据存储结构
数据存储结构，也称为物理结构，是计算机内数据及其逻辑结构的表示。通常有两种类型的存储结构：顺序存储结构和链接存储结构。
顺序存储结构的基本思想是用一系列连续的存储单元按顺序存储数据元素，数据元素之间的逻辑关系由元素存储的位置来表示。
链接存储结构的基本思想是使用任意一组存储单元来存储数据元素，数据元素之间的逻辑关系由指针表示。
注意：存储结构除了存储数据元素外，还必须存储数据元素之间的逻辑关系。
抽象数据类型
抽象数据类型是数据结构和在该结构上定义的一组操作的通用术语。抽象数据类型提供了两种不同的使用和实现视图，提供封装和信息隐藏。
算法定义
通俗地说，算法就是解决问题的方法，是解决特定问题的步骤的描述，是有限的指令序列。
算法特点
(1) 输入：一个算法有零个或多个输入（即该算法可能没有输入），这些输入通常来自特定的对象集合。
输出：一个算法有一个或多个输出（即算法需要一个输出）。输出和输入之间通常存在一定的关系。
(3) 有限性：算法在执行有限步骤（对于有效输入）后必须始终终止，并且每个步骤必须在有限时间内完成。
(4)确定性：算法中的每条指令必须具有明确且精确的含义。在任何条件下，相同的输入都会产生相同的输出。
(5) 可行性：算法所描述的操作可以通过执行有限次数的基本操作来实现。
定义线性表
线性列表，简称为表，是零个或多个相同类型的数据元素的有限序列。数据元素的数量称为线性列表的长度，如果长度等于0，则称为空列表。
线性表中的逻辑关系
非空列表L=(a1, a2, an) 具有排序关系(ai-1, ai)，其中ai-1 称为ai 的前驱，ai 称为后继。 ai-1的。在此序列中，a1 没有前驱，而an 只有一个后继。其他元素只有一个前任和一个后继。
序列表存储结构定义
MaxSize用于表示数组的长度，序列表存储结构定义如下：
#定义最大尺寸100
类型定义结构
{
ElemType data[MaxSize]; //ElemType 表示不确定的数据类型。
int length; //length表示线性表的长度。
}序列表；
序列表是一种随机访问结构
假设序列表的每个元素占用c个存储单元，则第i个元素的存储地址为：
LOC(ai)=LOC(a1)+(i-1)c
序列表的优缺点
顺序表使用数组元素的物理位置之间的邻接关系来表示线性列表中数据元素之间的逻辑关系。这使得顺序列表具有以下优点：
(1)不需要增加额外的存储空间来表示表中元素之间的逻辑关系。
(2)表内任意位置的元素都可以快速访问(即随机访问)。
同时，序列表也有以下缺点：
(1)插入和删除操作需要移动大量元素。顺序表上的插入和删除操作平均以相同的概率移动表中一半的元素。
表的容量难以理解。由于需要预先确定数组的长度，因此如果线性表的长度变化很大，则很难确定合适的存储规模。
(3)造成存储区域的“碎片”。数组需要的存储空间比需要的多，但又必须是连续的，否则就无法使用，导致存储空间“碎片化”。
单链表存储结构定义
单链表的存储结构定义如下：
结构节点
{ ElemType data; //ElemType 表示不确定的数据类型。
结构节点*下一个；
} *first; //first 是单链表的第一个指针。
双链表的存储结构定义
双向链表的存储结构定义如下。
结构双节点
{
ElemType data; //ElemType 表示不确定的数据类型。
struct DulNode *prior, *next; //previous 是前一个指针字段，next 是后继指针字段
} *first; //first 表示双向链表的第一个指针。
堆栈定义
堆栈是一个线性列表，它将插入和删除操作仅限于列表的末尾。栈中可以插入和删除的一端称为栈顶，另一端称为栈底，不包含数据元素的栈称为空栈。
堆栈运行特性
堆栈操作具有后进先出的特点。
队列定义
队列是一种线性列表，一端只允许插入操作，另一端只允许删除操作。允许插入的一端称为队列的尾部，允许删除的一端称为队列的开头。
提示操作特点
队列操作具有先进先出的特点。
解决循环队列中判断空队列和满队列的条件
方法一：附加一个变量num来存储队列中元素的数量。如果num=0，则队列为空；如果num=QueueSize，则队列已满。
方法二：改变队列满的情况，浪费一个元素空间。当队列已满时，数组中只有一个空闲单元。也就是说队列为空的条件是Front=Rear。将满的队列为(rear+1)%QueueSize=front，队列长度为(rear-front+QueueSize)%QueueSize。
方法三：设置flag标志。如果front=rear 且flag=0，则队列为空。如果front=rear 且flag=1，则队列已满。
字符串定义
字符串是零个或多个字符的有限序列。
空格串和空串的定义
仅包含空格的字符串称为空格字符串。字符串中包含的字符数称为字符串的长度。长度为0的字符串称为空字符串，记为''。
字符串比较
字符串比较是通过比较组成字符串的字符来执行的。
给定两个字符串：
X='x1x2…xn'
Y='y1y2…ym'
接下来，当n=m 且x1=y1,xn=ym 时，我们称X=Y。
如果满足以下任一条件，我们就说X nm且xi=yi(i=1,2,n)；
xi=yi(i=1,2,k-1),xk
节点层次数和树深度（高度）
根节点的层数指定为1。对于其他节点，如果一个节点在第k层，则其子节点在第k+1层，则调用树中所有节点的最大层数。树深度（也称为树高）。
二叉树的定义
二叉树是n (n 0) 个节点的有限集合。该集合要么是一个空集合（称为空二叉树），要么由一个根节点和两个不相交的左节点（每个称为根节点）组成。由子树和右子树组成的二叉树。
二叉树的特点
二叉树的特点是： 每个节点最多有两个子树，二叉树中没有节点的度大于2。 (2)子树的顺序不能任意颠倒，即使节点只有两个节点。如果是单子树，必须区分是左子树还是右子树。
注意：二叉树和树是树结构的两种类型。
二叉树的基本形式
二叉树有五种基本形式。 空二叉树。 根节点只有左子树。 根节点只有右子树。子树。
倾斜树
所有节点只有左子树的二叉树称为左对角树，所有节点只有右对角树的二叉树称为右对角树。倾斜树。
倾斜树的特点：每一层只有一个节点。即只有1个1度和0度的节点，以及1个叶子节点。 倾斜树的节点数等于其深度。
完全二叉树
在二叉树中，如果每个分支节点都有一个左子树和一个右子树，并且所有叶子都在同一层，这样的二叉树称为完全二叉树。
完全二叉树的特点： 所有叶子节点都处于最低层。 仅存在度数为0 和2 的节点。
完全二叉树
具有n 个节点的二叉树按层次顺序编号。如果编号为i (1in) 的节点与同一深度的完全二叉树中编号为i 的节点处于相同位置，则该二叉树为：这棵树称为完全二叉树。
完全二叉树的特点是： 叶子节点只出现在最下面两层，最低层的叶子节点集中在左边连续的位置。 如果存在度数为1的节点，则存在下一层。只有一个，并且该节点仅剩下子节点。
二叉树的基本性质
性质1：二叉树的第i层最多有2i-1个节点（i1）。
性质2 深度为k 的二叉树最多有2k-1 个节点，至少有k 个节点。
性质3 若一棵二叉树的叶子节点数为n0，度数为2的节点数为n2，则
n0=n2+1。
性质4 具有n个节点的完全二叉树的深度为：
性质5：对于n个节点的完全二叉树中的节点，从1开始按层次编号。那么，对于任意编号为i (1in) 的节点，称为节点i：
(1) 如果i>1，则节点i的父节点编号如下。
; 否则，节点i 是根节点并且没有父节点。
若2in，则节点i的左孩子数为2i。否则，节点i 没有左子节点。
若2i+1n，则节点i的右孩子数为2i+1，否则节点i无右孩子。
保存二叉树
包括二叉树的顺序存储和二叉树的链式存储。
二元链表的存储结构定义如下：
结构双节点
{
ElemType 数据。
BiNode *lchild, *rchild;
} *root; //root表示二元链表的顶指针。
结构三节点
{
ElemType 数据。
TriNode *lchild, *rchild, *parent //Parent 指该节点的父节点。
} *root; //3 分割链表的起始指针
遍历的含义
所谓遍历，就是不重复、不遗漏的访问。二叉树的遍历是指从根节点开始，按照特定的顺序访问二叉树中的所有节点，保证每个节点只被访问一次。
二叉树遍历顺序定义
前序遍历（或称根遍历、前序遍历）
如果二叉树为空，则不执行任何操作并返回。
访问根节点。
前序遍历根节点左侧的子树。
前序遍历根节点右侧的子树。
前向扫描（或中间路由扫描）
如果二叉树为空，则不执行任何操作并返回。
按顺序遍历根节点的左子树。
访问根节点。
(3) 按顺序遍历根节点右侧的子树。
后序遍历（或后路由遍历）
如果二叉树为空，则不执行任何操作并返回。
(1)后遍历根节点左侧的子树。
(2)根节点右子树的后遍历。
访问根节点。
按级别遍历
二叉树的层序遍历是从二叉树的第一层（根节点）开始，在同一层内从左到右、逐层、从上到下逐层遍历节点。
线索二叉树的定义
在有n个节点的二元链表中，n+1个空指针字段用于存储指向特定遍历序列中节点的前驱和后继的指针。这些指针称为线索。同样，包含线索的二叉树称为线索二叉树。类似地，包含线索的二元链表称为线索链表。
线索二叉树的存储结构定义
线索列表节点定义如下：
enum flag {Child, Thread} //枚举类型，枚举常量Child=0, Thread=1;
结构ThrNode
{
ElemType data; //ElemType 表示不确定的数据类型。
ThrNode *lchild, *rchild;
标志ltag、rtag；
}*root; //root 表示指向线索列表开头的指针。
树形存储结构
包括家长代表、子女代表和兄弟姐妹代表。
父表示的存储结构定义如下。
#define MaxSize 100; //树中的最大节点数
struct PNode //数组元素的类型
{
ElemType data; //树中节点的数据信息，
intparent; //数组中节点的父索引。
};
PNode树[MaxSize];
子表示的存储结构定义如下。
struct CTNode //子节点
{
整数子代；
CTNode *下一个；
};
struct CBNode //头节点
{
ElemType 数据。
CTNode *firstchild //指向子链表开头的指针
};
子兄弟表示也称为二元链表表示，其存储结构定义如下。
结构TNode
{
ElemType data; //ElemType 表示不确定的数据类型。
TNode *firstchild; //firstchild 指该节点的第一个子节点。
TNode *rightsib; //rightsib 指该节点的右兄弟节点。
};
将树转换为二叉树
以下是将树转换为二叉树的方法：
—— 在树中所有相邻兄弟节点之间添加一条连接线。
从树中的每个节点中删除第—— 行，仅保留其与第一个子节点之间的连接，并删除其与其他子节点之间的连接。
(3)级别调整——将树绕根节点顺时针旋转固定角度，以明确层次结构。
将森林转换为二叉树
以下是将森林转换为二叉树的方法：
将森林中的每棵树转换为二叉树。
从第二棵二叉树开始，获取后一棵二叉树的根节点作为前一棵二叉树根节点的右子节点。一旦所有二叉树都连接起来，得到的二叉树就是变换后的二叉树。森林。
将二叉树转换为树或森林
将树木和森林转换为二叉树的过程是可逆的。要将二叉树恢复为树或森林：
添加第—— 行。如果节点x 是其父节点y 的左子节点，则将节点x 的右子节点、右子节点的右子节点……连接到节点y。
删除第——行，去掉原二叉树中父节点与右子节点的所有连接。
图层调整——将和中得到的树木和森林进行分层组织。
树遍历序列与二叉树遍历序列的对应关系
根据树和二叉树的变换关系，以及树和二叉树遍历的操作定义，一棵树的遍历顺序和由一棵树变换而成的二叉树的遍历顺序有如下对应关系。存在某种关系。树的前序遍历序列等于二叉树的前序遍历序列，树的后序遍历序列等于二叉树的后序遍历序列。
Huffman叶节点权重
叶节点权重是指分配给叶节点的有意义的数值。
二叉树的加权路径长度
假设一棵二叉树有n 个带权叶节点。从根节点到每个叶子节点的路径长度与相应叶子节点的权重的乘积称为二叉树的带权路径长度，记为：
WPL=
其中，wk为第k个叶子节点的权重，lk为从根节点到第k个叶子节点的路径长度。
哈夫曼树定义
给定一组具有特定权重的叶节点，我们可以构造一棵具有最小加权路径长度的二叉树。哈夫曼树也称为最优二叉树。
哈夫曼算法的基本思想
哈夫曼算法的基本思想如下。
初始化：根据给定的n个权重{w1,w2,wn}构造n棵只有一个根节点的二叉树，从而创建二叉树集合F={T1,T2,Tn}。
选择合并：选择F的根节点权值最小的两棵二叉树作为左右子树，新二叉树根节点的权值成为它的左右子树。子树根节点的权重之和。
删除和添加：删除F的左右子树两棵二叉树，并将新建立的二叉树添加到F中。
重复步骤和。如果集合F中只剩下一棵二叉树，那么这棵二叉树就是哈夫曼树。
图形定义
图由有限的、非空的顶点集和顶点之间的一组边组成，通常表示为：
G=(V,E)
其中，G表示图，V表示图G的顶点集合，E表示图G的顶点之间的边集合。
无向图和有向图
如果顶点vi 和vj 之间的边没有方向，则该边称为无向边，用无序对(vi, vj) 表示。如果从顶点vi 到vj 的边有方向，则该边是有向边（也称为弧），并由有序对vi、vj 表示。 vi 称为弧尾，vj 称为弧头。如果图的任意两个顶点之间的边是无向边，则该图称为无向图；否则，该图称为有向图。
简单图解
如果从一个顶点到另一个顶点没有边，并且相同的边不重复出现，这样的图称为简单图。
邻接、依赖
在无向图中，对于任意两个顶点vi 和vj，如果存在边(vi, vj)，则称顶点vi 和vj 彼此相邻，边(vi, vj) 变为如下所示：连接到顶点vi 和vj。
在有向图中，对于任意两个顶点vi 和vj，如果存在弧vi 和vj，则称顶点vj 是vi 的邻居，并且称弧vi 和vj 与顶点vi 相连。还有维杰。
无向完全图、有向完全图
在无向图中，如果任意两个顶点之间存在边，则该图称为无向完全图。具有n 个顶点的无向完全图有n(n-1)/2 条边。
如果任意两个顶点之间存在两条方向相反的弧，则有向图称为有向完全图。具有n 个顶点的有向完全图具有n(n-1) 条边。
稠密图、稀疏图
边较少的图称为稀疏图，边较少的图称为稠密图。
顶度、入度、出度
在无向图中，顶点v的度是指与该顶点相连的边的条数，表示为TD(v)。对于具有n 个顶点和e 个边的无向图，
在有向图中，顶点v的入度是指以该顶点为弧头的弧的数量，记为ID(v)。顶点v的出度指的是弧的数量。设顶点为弧尾，记为OD(v)。对于具有n 个顶点和e 个边的有向图，以下等式成立：
连通图、连通分量
在无向图中，如果顶点vi和vj之间存在路径（ij），则该图称为连通图。无连通图的最大连通子图称为连通分量。
强连通图、强连通分量
如果对于任何顶点vi 和vj (ij)，存在从顶点vi 到vj 以及从顶点vj 到vi 的路径，则称有向图是强连通的。非强连通图的最大强连通子图称为强连通分量。
邻接矩阵存储结构定义
假设图G=(V,E)有n个顶点，则邻接矩阵是一个nn方阵，定义为：
邻接矩阵的存储结构定义如下。
#定义最大尺寸10
类型定义结构
{
ElemType vertex[MaxSize]; //存储图中顶点的信息。 ElemType 表示不确定的数据类型。
int arc[MaxSize][MaxSize]; //存储图边的信息
int vertexNum, arcNum //图中的顶点数和边数；
M图；
邻接表存储结构定义
邻接表是一种结合了顺序存储和链接存储的存储方式。具体方法是将顶点vi的所有邻居链接成一个单链表。这称为顶点vi 的边列表（对于有向图）。边表的起始指针和顶点的数据信息按顺序存储（称为顶点表）。因此，邻接表中有两种类型的节点：顶点列表节点和边列表节点。
其中，Vertex:Data字段存储顶点信息。
firstedge：指针字段，边缘表的第一个指针。
adjvex：相邻点域。将边顶点的邻居的索引存储在顶点表中。
next：指向边缘表中下一个节点的指针字段。
邻接表存储结构定义如下：
struct ArcNode //定义边表节点
{
int adjvex; //相邻点域
ArcNode *下一个；
};
struct VertexNode //定义顶点表节点
{
ElemType Vertex; //ElemType 表示不确定的数据类型。
ArcNode *firstedge;
};
#定义最大尺寸10
类型定义结构
{
VertexNode adjlist[MaxSize] //顶点表
int vertexNum, arcNum //图中的顶点数和边数；
AL图；
定义图的遍历顺序
深度优先遍历
从图中特定顶点v开始深度优先遍历的基本思想如下。
访问顶点v。
从v的未访问邻居中选择顶点w，从w开始进行深度优先遍历。
重复上述两步，直到访问完图中所有有路径连接到v 的顶点。
广度优先遍历
从图中特定顶点v开始进行广度优先遍历的基本思想如下。
访问顶点v.
按顺序访问v 的每个未访问的邻近点v1, v2, vk。
从v1,v2,…,vk开始，依次访问未访问过的邻接点，直到图中与顶点v有路径相连的所有顶点都被访问过。
最小生成树的定义
假设G=(V,E)是一个无向连通网络。生成树上每条边的权重之和称为G中所有生成树中成本最低的生成树的成本。称为最小生成树。
Prim算法的基本思想
设G=(V,E)为无向连接网络，T=(U,TE)为G的最小生成树。 T的初始状态为U={v0}(v0V)，TE={ }，重复进行以下操作。在所有边uU, v 中找到具有最小成本(u, v) 的边。 V-U)合并到边集TE中，v合并到顶点集U中，直到U=V。
Kruskal算法的基本思想
假设无向网络为G=(V,E)，设G的最小生成树为T=(U,TE)，设其初始状态为U=V，TE={}，根据权值Do像这样。从最大的边开始，依次检查边集E 中的每条边。如果所检查的边的两个顶点属于T 的两个不同的连通分量，则将该边添加到TE 并按如下方式分割这两个连通分量：
