数算笔记-适合OIer的期中复习

数据结构三要素：逻辑结构，？结构，运算

字符串

（可能和你知道的有所不同的）KMP

• 定义：\(nxt_i\) 表示 \([0,i-1]\) 的 border 长度

  （另，\(\max j\) 使得 \(S_{[0,j-1]}=S_{[i-j,i-1]}\)）

  \(nxt_0=-1\).

于是据此定义有匹配代码

for(i=0,j=0;i<n&&j<m;) {
	if(j==-1||Pattern[j]==Text[i]) i++,j++;
	else j=nxt[j];
	// Pattern[0,j-1] = Text[0,i-1]
}

与求 next 的代码

nxt[0]=-1;
for(i=1,j=0;i<n;i++) {
	while(j!=-1&&Pattern[j]!=Pattern[i]) j=nxt[j];
	j++;
	nxt[i]=j;
}

• 定义优化过的 KMP，\(nxt_i\) 直接指向 nxt 树上第一个字符不同的点

即，

...
if(Pattern[nxt[i]]==Pattern[i]) nxt[i]=nxt[nxt[i]];

带来的好处是，可以用 border 理论来证明每次跳的次数至多是单次 \(O(\log n)\) 的.

一些神秘的定义

极大后缀（maximal suffix）：\(P=uv\)，且不存在 \(u\) 的后缀=\(v\) 的前缀

\(\le |X|/2\) 的 maximal suffix 称为 short maximal suffix

树

二叉树

根深度为 0，叶高度为 1

满二叉树：每个非叶节点有两个孩子

完全二叉树：最后一层叶节点全部靠左，其他层填满

extended binary tree：度为 1 的节点插入空的节点后 -> 形成满二叉树，且外节点（叶节点）个数=内节点（非叶节点）个数+1

内路径长度：\(I=\) 内节点深度之和

外路径长度：\(E=\) 外节点深度之和，有 \(E=I+2n\)，\(n\) 为内节点个数

叶节点个数 = 度为2的节点个数 + 1

给定前/后序遍历，无法确定中序遍历. 另外两种可以.

linked storage：采用正常人类理解的指针

sequential storage：不动态开点的线段树

Heap

堆是一种完全二叉树，采用宽度优先序维护，.

线性建堆：直接将原数组放上去，然后按 BFS 序从后往前，去做向下调整操作. 复杂度相当于高度之和，为线性.

树

deg of node = number of childs

deg of the tree = maximum deg of node

ordered tree = label the siblings in certain order

二叉树并非 ordered tree！（ordered tree 无法有右儿子而无左儿子）

森林 -> 二叉树（本质上就是左儿子为兄弟-儿子表示法的儿子边，右儿子为兄弟边）：

• 令 \(S\) 为树的集合，\(r\) 为 \(S_1\) 的根，\(T_r\) 为 \(r\) 的所有子树，则定义 \(F(S)\) 的根为 \(r\)，\(F(S)\) 中 \(r\) 左子树为 \(T_{r,1}\)，右子树为 \(F((S\setminus S_1)\sqcup (T_r\setminus T_{r,1}))\)

二叉树 -> 森林：

• 每个点的父亲为往上跳的时候，第一次往右上角跳的点

存储树的四种方法：

1. 前向星（list-of-childern structure, static）
2. 兄弟-儿子表示法（first-child-next-sibling, static）
3. vector（list-of-childern structure, dynamic）
4. 二叉树表示法（first-childern-next-sibling, dynamic）

用前序遍历存储在序列上的话就只需要记一下自己是否是叶(ltag)和是否是最右侧的兄弟(rtag). 注意这两个 tag 的定义是叶&最右.

用bfs序遍历也一样只需要记录这两个 tag.

用后序遍历的话需要记录一下 deg. 当然如果能记录 deg 的话前序 bfs 序也都是可以复原的.

这到底是啥玩意儿

当栈满时再做进栈运算必定产生空间溢出, 称“上溢” 。当栈空时再做退栈运算也将产生溢出,称 “下溢” 。队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。将存储队列的数组头尾相接，形成循环队列。队头、队尾指针加1时用语言的取模运算实现。

并查集的两个优化的名字叫：重量权衡合并（即启发式合并），路径压缩.

数据结构三要素：逻辑结构，存储结构，运算

抽象数据结构的组成：操作，数据的对象，数据的关系（不包括存储）

三叉链表存储的树：存储 ls, rs, fa