GESP六级备考

· · 算法·理论

GESP六级备考

树的定义

链

任意一节点所连的边不超过2。

完整二叉树

每个节点的子节点数要么0要么2。

完全二叉树

只有最下层的节点的子节点数可以少于2，优先是左节点。

完美二叉树 （=满二叉树）

叶子节点深度相同，非叶子节点的子节点数都为2。

树的遍历

DFS

先搜父亲，再搜儿子（根，左，右（先序））。

左，根，右（中序）

左，右，根（后序）

推论

已知中序遍历序列和另外一个序列可以求第三个序列。

哈夫曼树

最优二叉树。

(01) 路径和路径长度

定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。  例子：100和80的路径长度是1，50和30的路径长度是2，20和10的路径长度是3。

(02) 结点的权及带权路径长度

定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。  例子：节点20的路径长度是3，它的带权路径长度= 路径长度 权 = 3 20 = 60。

(03) 树的带权路径长度

定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。  例子：示例中，树的WPL= 1100 + 250 + 320 + 310 = 100 + 100 + 60 + 30 = 290。

设 w_i为二叉树第i个叶结点的权值， 为从根结点到第i个叶结点的路径长度，则 WPL 计算公式如下：

WPL=\sum^n_{i=1}{w_i \times l_i}

所以这棵树的

\begin{aligned} WPL &= 2 \times 2 + 3 \times 2 + 4 \times 2 + 7 \times 2 \\ &= 4 + 6 + 8 +14 \\ &=32 \end{aligned}

对于给定一组具有确定权值的叶结点，可以构造出不同的二叉树，其中，WPL 最小的二叉树 称为 霍夫曼树（Huffman Tree）。

霍夫曼编码

如果每个字符的 使用频率相等，那么等长编码无疑是空间效率最高的编码方法，而如果字符出现的频率不同，则可以让频率高的字符采用尽可能短的编码，频率低的字符采用尽可能长的编码，来构造出一种 不等长编码，从而获得更好的空间效率。

在设计不等长编码时，要考虑解码的唯一性，如果一组编码中任一编码都不是其他任何一个编码的前缀，那么称这组编码为 前缀编码，其保证了编码被解码时的唯一性。

霍夫曼树可用于构造 最短的前缀编码，即 霍夫曼编码（Huffman Code），其构造步骤如下：

  1. 设需要编码的字符集为：d_1,d_2,d_3,...,d_n，他们在字符串中出现的频率为：w_1,w_2,w_3,...,w_n。
  2. 以  d_1,d_2,d_3,...,d_n作为叶结点，$w_1,w_2,w_3,...,w_n作为叶结点的权值，构造一棵霍夫曼树。
  3. 规定哈夫曼编码树的左分支代表 ，右分支代表 ，则从根结点到每个叶结点所经过的路径组成的 、 序列即为该叶结点对应字符的编码。

格雷码

格雷码是一个二进制数系，其中两个相邻数的二进制位只有一位不同。举个例子， 3位二进制数的格雷码序列为

000,001,011,010,110,111,101,100

手动构造

  k位的格雷码可以通过以下方法构造。我们从全  0格雷码开始，按照下面策略：

  1. 翻转最低位得到下一个格雷码，（例如 000 \longrightarrow 001）；
  2. 把最右边的  的左边的位翻转得到下一个格雷码，（例如 001 \longrightarrow 011）；

交替按照上述策略生成 2^{k-1}次，可得到k位的格雷码序列。

DFS

该类搜索算法的特点在于，将要搜索的目标分成若干「层」，每层基于前几层的状态进行决策，直到达到目标状态。

BFS

是图上最基础、最重要的搜索算法之一。

所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。

类

类（class）是结构体的拓展，不仅能够拥有成员元素，还拥有成员函数。

类使用关键字 class 或者 struct 定义，下文以 class 举例。

class ClassName {
  ...
};

// Example:
class Object {
 public:
  int weight;
  int value;
} e[array_length];

const Object a;
Object b, B[array_length];
Object *c;

与使用 struct 大同小异。该例定义了一个名为 Object 的类。该类拥有两个成员元素，分别为 weight,value；并在 } 后使用该类型定义了一个数组 e。

定义类的指针形同 struct。

访问说明符

不同于 struct 中的举例，本例中出现了 public，这属于访问说明符。

对于 struct，它的所有成员都是默认 public。对于 class，它的所有成员都是默认 private。

栈

栈的修改与访问是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。

我们可以方便的使用数组来模拟一个栈，如下：

int st[N];
// 这里使用 st[0] (即 *st) 代表栈中元素数量，同时也是栈顶下标

// 压栈 ：
st[++*st] = var1;
// 取栈顶 ：
int u = st[*st];
// 弹栈 ：注意越界问题, *st == 0 时不能继续弹出
if (*st) --*st;
// 清空栈
*st = 0;

C++ 中的 STL 也提供了一个容器 std::stack，使用前需要引入 stack 头文件。

// clang-format off
template<
    class T,
    class Container = std::deque<T>
> class stack;

T 为 stack 中要存储的数据类型。

Container 为用于存储元素的底层容器类型。这个容器必须提供通常语义的下列函数：

STL 容器 std::vector、std::deque 和 std::list 满足这些要求。如果不指定，则默认使用 std::deque 作为底层容器。

STL 中的 stack 容器提供了一众成员函数以供调用，其中较为常用的有：

队列

队列（queue）是一种具有「先进入队列的元素一定先出队列」性质的表。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。通常用一个数组模拟一个队列，用两个变量标记队列的首尾。

  int q[SIZE], ql = 1, qr;

队列操作对应的代码如下：

双栈模拟队列

还有一种冷门的方法是使用两个 栈 来模拟一个队列。这种方法使用两个栈 F, S 模拟一个队列，其中 F 是队尾的栈，S 代表队首的栈，支持 push（在队尾插入），pop（在队首弹出）操作：

C++ 在 STL 中提供了一个容器 std::queue，使用前需要先引入 <queue> 头文件。

STL 中对 queue 的定义

std::queue<int> q1, q2;

// 向 q1 的队尾插入 1
q1.push(1);

// 将 q1 赋值给 q2
q2 = q1;

// 输出 q2 的队首元素
std::cout << q2.front() << std::endl;
// 输出: 1

T 为 queue 中要存储的数据类型。

Container 为用于存储元素的底层容器类型。这个容器必须提供通常语义的下列函数：

STL 容器 std::deque 和 std::list 满足这些要求。如果不指定，则默认使用 std::deque 作为底层容器。

STL 中的 queue 容器提供了一众成员函数以供调用。其中较为常用的有：

循环队列

使用数组模拟队列会导致一个问题：随着时间的推移，整个队列会向数组的尾部移动，一旦到达数组的最末端，即使数组的前端还有空闲位置，再进行入队操作也会导致溢出（这种数组里实际有空闲位置而发生了上溢的现象被称为「假溢出」）。

解决假溢出的办法是采用循环的方式来组织存放队列元素的数组，即将数组下标为 0 的位置看做是最后一个位置的后继。（数组下标为 x 的元素，它的后继为 (x + 1) % SIZE）。这样就形成了循环队列。

End

终于写完了，跟写论文一样，累死我了。