余弦の博客

# ST 表是什么 ST 表是一个用来解决区间最值问题查询的算法 它用 O (nlogn) 复杂度预处理，可以实现 O (1) 复杂度的查询。 缺点：无法支持在线修改 模板题：ST 表 - 洛谷 # 1. 预处理 用一个二维数组 dp [i][j] 表示下标为 i ~ i + 2j - 1 的最值（最大 or 最小值） 则 ①易知边界条件 dp [i][0] 为 a [i]，既 i~i 的最大值为其本身 ②接下来是状态转移方程，如图 # 1 << j 相当于 2j 初始化代码 void init(int n) { for (int i = 0;...

# 一、什么是树 # 1. 树的定义 树（Tree）：n（n≥0）个结点构成的有限集合。 当 n=0 时，称为空树； 对于任一棵非空树（n>0）, 它具备以下性质： 树中有一个称为 “根（Root）” 的特殊结点，用 r 表示。 其余结点可分为 m（m>0）个互不相交的有限集 T1，T2，……，Tm, 其中每个集合本身又是一棵树，称为原来树的 “子树（SubTree）”。 子树是不相交的 除了根结点外，每个结点有且仅有一个父结点； 一个 N 个结点的树有 N-1 条边。 # 2. 树的一些基本术语 1. 结点的度（Degree）： 结点拥有子结点的数量 2....

# 一、队列的抽象数据类型描述 类型名：队列（Queue） 数据对象集：一个有 0 个或多个元素的有穷线性表 操作集：长度为 MaxSize 的堆栈 Q∈Queue, 队列元素 item∈ElementType 1. 生成长度为 MaxSize 的空队列 Queue CreatQueue (int MaxSize); 2. 判断队列 Q 是否已满 bool IsFullQ (Queue Q, int MaxSize); 3. 将数据元素 item 插入队列 Q 中 bool AddQ (Queue Q, ElementType item); 4. 判断队列 Q 是否已空 bool...

# 一、堆栈的抽象数据类型描述 类型名：堆栈（Stack） 数据对象集：一个有 0 个或多个元素的有穷线性表 操作集：长度为 MaxSize 的堆栈 S∈Stack, 堆栈元素 item∈ElementType 1. 生成空堆栈，其最大长度为 MaxSize; Stack CreateStack(int MaxSize); 2. 判断堆栈 S 是否已满 int IsFull (Stack S, int MaxSize); 3. 将元素 item 压入堆栈 void Push (Stack S, ElementType item); 4. 判断堆栈 S 是否已空 int IsEmpty...

# 一、广义表 是线性表的推广 对于线性表而言，n 个元素都是基本的单元素 广义表中，这些元素不仅可以使单元素也可以是另一个广义表 > typedef struct GNode *GList; struct GNode {> int Tag; // 标志域：0 表示结点是单元素，1 表示结点是广义表> union { // 子表指针域 SubList 域单元素数据域 Data 复用，共用存储空间> ElementType Data;> GList SubList;> } URegion;>...

# 一、线性表的抽象数据类型描述 类型名：线性表（List） 数据对象集：线性表示 n (>=0) 个元素构成的有序序列 (a1,a2,……,an) 操作集：线性表 L∈List, 整数 i 表示位置，元素 X∈ElementType # 二、顺序表 # 1. 定义 struct LNode { ElementType Data[MAXSIZE];// 存了一个数组，其最多能存 MAXSIZE 个元素 int Last;// 最后一个元素的下标！};typedef struct LNode *List;访问下标为 i 的元素：L.Data...