数据结构

大二上学期数据结构的复习笔记，目前已完结。

一、绪论

1. 基本概念

1. 数据：程序能处理的符号的总称
2. 数据元素：数据的基本单位，由数据项组成（有独立含义的最小单位）
3. 数据结构：有相互关系的数据元素的集合，三元素：逻辑结构、运算、存储结构（物理结构，元素及关系的存储表示，顺序/链式/索引/散列），表现为逻辑抽象模型（抽象数据类型）和具体实现
4. 数据类型：性质相同的值的集合和集合上定义的操作的总称
5. 抽象数据类型 ADT：数据元素的集合（数据对象）、关系集合、操作集合
6. 算法：解决方案的准确完整描述，有穷/确定/可行/输入/输出，正确/可读/健壮/高效，设计取决于逻辑结构，实现依赖于存储结构
7. 程序：数据结构+算法，基于编程语言的算法实现

2. 渐进分析

1. 渐进上界/紧界/下界：$O/\Theta/\Omega$，记作 $T\le/=/\ge g$，$\forall n\ge n_0,c_1g(n)\le f(n)\le c_2g(n)$，$O$ 与 $\Theta$ 常混用
2. 时间复杂度是空间复杂度的上界
3. 主定理：$T(n)=aT(n/b)+f(n)$，$a\ge 1,b>1$
   1. 若 $f(n)=O(n^{\log_b a-\epsilon})$，则 $T(n)=\Theta(n^{\log_b a})$
   2. 若 $f(n)=\Theta(n^{\log_b a}\log^k n)$，则 $T(n)=\Theta(n^{\log_b a}\log^{k+1} n)$
   3. 若 $f(n)=\Omega(n^{\log_b a+\epsilon})$，且 $af(n/b)\le cf(n)$，则 $T(n)=\Theta(f(n))$

3. 常见算法

1. 斐波那契数列

f=1,g=0;
while(0<n--){
    g=g+f;
    f=g-f;
}//f为上一轮的g
return g;

二、线性表

1. 基本概念

1. 线性表（序列）：数据元素的有限序列
2. 向量（顺序表）：线性表基于数组的存储表示
3. 列表（链表）：线性表基于链式存储的表示
4. 串：字符组成的有限序列，空串/空白串
5. 排序码：排序依据

2. 向量

1. 随机打乱

for(int i=V.size();i>0;i--){
    swap(V[i-1],V[rand()%i]);
}//V[i-1]与V[0,i)中某一随机元素交换

2. 二分查找

while(lo<hi){
    Rank mi=(lo+hi)>>1;
    (e<A[mi])?hi=mi:lo=mi+1;
}//循环终止时lo=hi,A[lo-1]<=e<A[hi]
return --lo;//<=e的最后一个元素

3. 归并排序（可用于统计逆序对）

while(i<mid&&j<last)
    if(data[i]<data[j]) sorted[k++]=data[i++];
    else sorted[k++]=data[j++];
while(i<mid) sorted[k++]=data[i++];
while(j<last) sorted[k++]=data[j++];
for(i=first;i<last;i++) data[i]=sorted[i];

4. 快速排序（可用于 K-选取，$O(n)$ 平均复杂度）

int pivotL=l,pivotR=r,x=data[l];
while(pivotL<pivotR){
    while(pivotL<pivotR&&data[pivotR]>x) pivotR--;
    if(pivotL<pivotR) data[pivotL++]=data[pivotR];
    while(pivotL<pivotR&&data[pivotL]<x) pivotL++;
    if(pivotL<pivotR) data[pivotR--]=data[pivotL];
}
data[pivotL]=x;
//改进：小样本采用插入排序；三数取中法选主元

5. 排序算法比较

方法	平均情况	最好情况	最差情况	辅助空间	稳定性
冒泡	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
选择	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
插入	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
希尔	$O(n\log^2 n)$	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定
堆	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定
归并	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定
快速	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	不稳定

3. 列表

1. 归并排序：原地归并
2. 排序算法比较：选择排序稳定

4. 串

1. 蛮力匹配

while(j<m&&i<n){
    if(T[i]==P[j]){
        i++;j++;
    }
    else{
        i=i-j+1; j=0;
    }
}
return i-j;//i-j>n-m则匹配失败

2. KMP next

while(j<m&&i<n){
    if(T[i]==P[j]||j<0){
        i++;j++;
    }
    else{
        j=next[j];
    }
}//O(n)

int t=next[0]=-1,j=0;
while(j<m-1){
    if(t<0||P[j]==P[t]){
        j++;t++;
        next[j]=t;
    }
    else t=next[t];
}//next表构建，O(m)

3. KMP nextval

int t=nextval[0]=-1,j=0;
while(j<m-1){
    if(t<0||P[j]==P[t]){
        j++;t++;
        if(P[j]!=P[t]) nextval[j]=t;
        else nextval[j]=nextval[t];
    }
    else t=nextval[t];
}

三、栈与队列

1. 表达式求值

1. 中缀转后缀：数字直接过，左括号入栈，右括号弹栈至左括号，运算符弹栈至栈顶优先级小于自身
2. 后缀求值：数字入栈，遇运算符弹栈两元素，结果入栈
3. 优先级：阶乘 $>$ 指数

2. 栈混洗

1. $n$ 元素：卡特兰数 $h(n)=\frac{C^{n}_{2n}}{n+1}$
2. 递推：$h(n)=h(n-1)h(0)+h(n-2)h(1)+\cdots+h(0)h(n-1)$
3. 判断可行混洗序列

int i=1;
for(int k=1;k<=n;k++){
    while(S.empty()||B[k]!=S.top()){
        if(i>n) return false;
        S.push(i++);
    }
    S.pop();
}
return true;

3. 单调栈

1. 求每个元素右侧第一个比它大的元素下标

for(int i=1;i<=n;i++){
    while(!S.empty()&&A[S.top()]<A[i]){
        temp=S.pop();
        res[temp]=i;
    }
    S.push(i);
}

4. 二项式展开系数

enqueue(0,1,1);
for(int i=1;i<=n;i++){
    enqueue(0);
    for(int j=1;j<=i+2;j++){
        s=dequeue();
        e=front();
        enqueue(s+e);
    }
}

四、树

1. 基本概念

1. 深度：从根到节点的路径长度（根节点为 $0$）
2. 高度：到叶子节点的最长路径长度
3. 树高：根节点高度（单节点为 $0$，空树为 $-1$）
4. 完全二叉树：除最后一层全满，最后一层往左靠

2. 二叉树

1. 节点数：$n_0=n_2+1$
2. 顺序表示：从 $0$ 开始
3. 形态数：卡特兰数（前序固定，中序可能情况）
4. 重构：前/后+中可重构，前+后不可重构（真二叉树可）

3. 堆

1. 插入：末尾插入，和父节点比较交换（上滤）
2. 删除：根和末尾交换，和子节点比较交换（下滤）
3. 构建：从最右的非叶节点逐个下滤，$O(n)$
4. 用堆实现 $\mathrm{Huffman}$ 树

五、搜索树

1. 二叉搜索树

1. 二叉树是二叉搜索树当且仅当中序遍历非降
2. 节点删除：叶节点直接删；单子节点提升子节点；双子节点用中序前驱/后继替换
3. 按排列的平均高度 $O(\log n)$，按形态的平均高度 $O(\sqrt{n})$
4. 理想平衡二叉搜索树：树高 $O(\log n)$，完全/满二叉搜索树
5. 一维范围查询：找 $\mathrm{LCA}$，左路程对左转过程遍历输出右子树，右路程对右转过程遍历输出左子树

2. AVL

1. 右旋 $\mathrm{zig}$，左旋 $\mathrm{zag}$
2. 插入：从插入点回溯，首个不平衡记为 $g$，沿回溯路径取 $p$,$v$（更高的孩子）
3. 删除：从删除点的父节点开始，迭代调整

3. B-Tree

1. 根节点是第 $0$ 层，高度为 $1$，下分支为第 $0$ 层分支，分支数 $[2,m]$；非根节点 $[\lceil m/2\rceil,m]$
2. $m$ 阶 B-Tree $\Rightarrow$ $(\lceil m/2\rceil,m)$ 树
3. 分支数 $L_{k-1}+N_k=L_k$，$N_k$ 为第 $k$ 层关键码总数，可递推
4. $\log_m(N+1)\le h\le \log_{\lceil m/2\rceil}(\frac{N+1}{2})+1\Rightarrow h=O(\log_m N)$
5. 插入：上溢分裂，迭代进行
6. 删除：叶节点直接删，非叶节点用中序前驱/后继替代，下溢（借父，父借兄弟或合并）

4. 红黑树

1. 任何动态操作（插入删除）引起的结构变化量不超过 $O(1)$
2. 根和外部节点为黑；红节点的父和子为黑；根到任一外部节点经过的黑节点数目一样
3. 推论：根到外部节点路径黑节点不少于红节点
4. 黑深度：除根外经过的黑节点（包括外部节点）
5. 黑高度：从该节点到外部节点经过的黑节点（不包括外部节点）；树黑高度为根黑高度
6. 红黑树等价于 $(2,4)$ 树，节点对应关键码
7. 红黑树高度 $\log_2(n+1)\le h\le 2\log_2(n+1)$
8. 插入：染红，双红修正（父 $p$，祖父 $g$，叔父 $u$）
   1. $u$ 黑：$\mathrm{zigzag}$
   2. $u$ 红：染黑 $p,u$，染红 $g$，递归修正 $g$
9. 删除：双黑修正

5. KD-Tree

1. 建树：找中位点，递归划分 $(O(n\log n))$
2. 范围查询：区域和节点对应分割线不相交则剪枝，否则切割区域后进入两侧，再访问自身
3. 最近邻查询：访问自身后进入一侧，另一侧依垂直距离判断

六、图

1. 基本概念

1. 简单路径：路径上顶点不重复
2. 连通分量：非连通图的极大连通子图
3. 强连通分量：$\mathrm{Tarjan}$ 有向环缩点法

2. 遍历

1. 深度优先搜索：发现次序先序（dTime），访问次序后序（fTime）
2. 边的类型：树边、前向边、后向边、跨边

switch(status(v)){
    case Undiscovered: type=Tree;
    case Discovered: type=Backward;
    default: type=(dTime(v)>dTime(u))?Forward:Cross;
}

3. 图论算法

1. 优先级搜索

PQ.push(start);
while(!PQ.empty()){ 
    int v=PQ.pop();
    if(VISITED==status(v)) continue;
    for(int u=firstNbr(v);-1<u;u=nextNbr(v,u))
        if(VISITED!=status(u)){             
            priority_update(v,u);
            PQ.push(u);
        } 
    status(v)=VISITED; 
}

priority_update(int v,int u){
    u.priority=min(u.priority,weight(v,u));//Prim
    u.priority=min(u.priority,v.priority+weight(v,u));//Dijkstra
    u.priority=v.priority+1;//BFS
    u.priority=v.priority-1;//DFS
}

2. $\mathrm{Bellman-Ford}$
3. $\mathrm{Floyd}$
4. 拓扑排序

七、散列

1. $\mathrm{hash}=f(\mathrm{key})$，$\mathrm{key}$ 为关键码，$f$ 为散列函数，直接定址/除余/MAD/数字分析/平方取中/折叠/随机
2. 冲突处理：多槽位/独立链/公共溢出区
3. 开放定址/闭散列策略：动态删除+线性/平方/双向平方（表长 $M% 4=3$ 前 $M$ 次可遍历）/随机试探+再散列（扩容）
4. 散列码转换：强制转换/分块求和/字符串多项式