本文最后更新于：2022年7月23日下午

408-数据结构-基础笔记

1.顺序表

单链表某节点前插入数据时，可以后插然后交换数据位置，实现O(1)。删除同理

2.栈和队列

2.1.基础知识

判断合法出栈顺序：如果入栈为1234…，那么出栈时对于任意数字，排在它后面比它小的必然是倒序。
- 如果入栈不是按大小排列，那么用序号判断。一回事。
- 所有合法总数为卡塔兰数：$\frac{1}{n+1}C_{2n}^n$
链栈的物理实现：头插头删的单链表
循环队列不能填满，需要空一个位置来判满（与指针重合时的队空区别开）
- 如果不允许浪费，那么元数据添加一个size表示目前数据元素个数；或者一个tag表示最近操作是插入还是删除
双端队列：两边可输入输出。还分为输入受限和输出受限
- 合法顺序：在栈中不合法的组合中挑一些变为合法
  - 输入受限：先把第一个数前面的数全画好再判断
  - 输出受限：先分析第一个数前面的数应该如何输入

2.2.括号匹配问题

遍历所有字符，左括号入栈，右括号弹栈匹配
左括号单身：全走完了栈不空
右括号单身：匹配时栈空
左右不匹配
表达式求值
- 后缀
  - 中缀转后缀
    - 后缀表达式中运算符顺序就是计算生效顺序
    - 机算结果左优先：只要有更靠近左边的运算符可以计算，那么就算左边的
  - 后缀求值：从左往右扫描，有运算符就让它前面两个操作数运算
- 前缀
  - 中缀转前缀
    - 右优先，排列顺序就是计算顺序
  - 前缀求值：从右往左入栈

2.3.特殊矩阵压缩存储

通常行列号下标从1开始，要注意
对称阵：储存对角线和下三角部分，共$1+2+…+n=\frac{n\cdot(n+1)}{2}$个元素，如果按行优先存储的话：
- 在最后元素数组下标为$\frac{n\cdot(n+1)}{2}-1$
- 下标映射公式为$k=\frac{i\cdot(i-1)}{2}+j-1，(i\ge j)；a_{ij}=a_{ji}，(i<j)$
上三角：前面有1～n-1行，元素下标为$[n+(n-1)+…+(n-i+2)]+(j-i)$
三对角
稀疏矩阵

3.串

描述位置一般从1开始
子串：串中任意个连续字符
朴素模式匹配：失败情况下：最坏o(mn)，最好o(n)
KMP算法：用一个next数组储存模式串本身的特征，某位置不匹配时i不变，j应该变为的值。避免了回溯过程
- 复杂度o(n)
- 复杂度o(m) $\begin{cases}next[1],无脑写0\\next[2],无脑写1\\i位置左侧画一条分界线，模式串右移，匹配时候j是多少\end{cases}$
- nextval求法：在next数组基础上计算
  
  1.第一位的nextval值必定为0，第二位如果于第一位相同则为0，如果不同则为1。
  
  2.第三位的next值为1，那么将第三位和第一位进行比较，均为a，相同，则，第三位的nextval值为0。
  
  3.第四位的next值为2，那么将第四位和第二位进行比较，不同，则第四位的nextval值为其next值，为2。
  
  4.第五位的next值为2，那么将第五位和第二位进行比较，相同，第二位的next值为1，则继续将第二位与第一位进行比较，不同，则第五位的nextval值为第二位的next值，为1。

4.树

4.1.概念性质

树的度：度的最大值
深度：默认从1开始
性质：
- 节点数=总度数+1
- 度为0的点比度为2的点多一个
  
  $n=n_0+n_1+n_2$
  
  $n=n_1+2n_2+1$ 作差
- 度为m的树第i层最多有$m^{i-1}$个节点
- 高度为h的m叉树最多$\frac{m^h-1}{m-1}$个节点（等比数列求和），度为m的树至少有h+m-1个节点
- 具有n个节点的m叉树的最小高度为$log_m(n(m-1)+1)$
  
  $\frac{m^{h-1}-1}{m-1}<n\le\frac{m^h-1}{m-1}$ 比上一层多，不能超过这一层
  
  $m^{h-1}<n(m-1)+1\le m^h$
特殊的二叉树
- 满二叉树：按层序从1开始编号，节点为i的左孩子为2i，右孩子为2i+1
- 完全二叉树：编号能和满二叉树一一对应
  - n个节点的完全二叉树高度h为 $log_2(n+1)$
  - 单分支节点只能有0或1个，双分支节点有奇数个
  - $n_0=n_2+1$，已知总数可以推出$n_0\ n_1\ n_2$
- 平衡二叉树：树上任一结点的左右子树深度之差不超过1

4.2.存储结构

顺序存储：节点编号从1开始，数组0位置空着
链式存储：三叉链表：多一个父指针
求深度
层序遍历：辅助队列，广搜。入队的是指针不是值，这样省地方

4.3.线索二叉树

中序线索化
最后一个节点需要特殊处理右线索，让它为空
先序线索化遍历时需要判断左孩子tag是否为0
后序线索化遍历时需要判断右孩子tag是否为0
找前驱后继：
- 中序：后继：右子树的左下角节点；前驱：左子树右下角节点
- 先序：后继：左右孩子；前驱：找不到
- 最后一个遍历的就是右边路走到头、然后左边路走到头这样的最后一个
- 后序：前驱：右左孩子；后驱：找不到
- 最后一个遍历的就是左边路走到头、然后右边路走到头这样的最后一个

4.4.普通的树

双亲表示法：找双亲方便，找孩子不方便（节点中储存双亲的下标）
孩子表示法：找孩子方便，找双亲不方便（节点中储存孩子链表头指针）
孩子兄弟表示法也就是树和二叉树的转化
森林和二叉树转化

4.5.平衡二叉树

二叉排序树BST
- 插入时如果元素已经存在则应当插入失败
- 删除时可以用直接前驱（左子树最小的）或者直接后继（右子树最大的）来替代
平衡二叉树AVL
- $\ $
- 用$n_h$表示深度为h的平衡树中含有的最少节点数，则有$n_0=0,n_1=1,n_2=2$，且$n_h=n_{h-1}+n_{h-2}+1$。含n个节点的平衡二叉树最大深度为$log_2n$
哈夫曼树
- 构造：每次挑权值最小的两个节点组合成树，根节点权值为他们的和
- 前缀编码：任何一个字符的编码都不是另一个编码的前缀
  
  构造n叉哈夫曼树，需要补充0节点，保证严格n叉树。计算 (节点数-1)%(叉数-1)，如果结果不是0，补充0节点直到余数为0，再构造树

5.图

5.1.概念

图的顶点集一定是非空集，但是边集可以是空集
对于n个顶点的无向图G，若G是连通图，则最少有n-1条边；若G是非连通图，则最多可能有$C_{n-1}^2$条边
有向图强连通最少边数就是一个回路，即n条边
生成子图：顶点一样，边可以少一点
无向图中的极大连通子图称为连通分量；有向图中的极大连通子图称为强连通分量（有来无回不是连通）
联通图的生成树：顶点全有，边尽可能少
边 < 顶点 log 顶点一般认为是稀疏图，但不绝对
有向树：从根向叶子有向的树

5.2.存储结构

邻接矩阵：$A^n[i][j]$表示从i到j边长为n的路径数目
邻接表：
十字链表-有向图
邻接多重表-无向图
对比

5.3.经典应用

广搜
- 复杂度：邻接矩阵0(n)，邻接表o(m+n)
- 邻接表表示不唯一，因此它的广度优先生成树也不唯一
深搜
- 最坏空间复杂度：调用栈深度o(n)
- 时间复杂度：邻接矩阵$o(n^2)$，邻接表o(m+n)
最小生成树
- Prim算法：从一个顶点开始构建；将代价最小的新顶点纳入，直到所有顶点都纳入为止
  
  复杂度只和点有关，$o(n^2)$，适合边稠密图
- Kruskal算法：选择权值最小的边，使这条边的两头连通（原本已经连通的就不选），直到所有结点都连通
  
  复杂度只和边有关，$o(m\cdot log_2m)$，适合边稀疏图
最短路径
- 无权图直接用广度优先
- Dijkstra 每一轮遍历两遍，共n-1轮，时间复杂度$o(n^2)$
- Floyd
  
  代码
  
  可以解决负权值，但不能有负权回路，因为可能没有最短路径
有向无环图DAG
- 描述表达式：给运算符编号，分层写
- 拓扑排序AOV：输出入度为0的点，把它们发出的边删除。重复
  - 邻接表：边和点都要遍历一次，o(m+n)
  - 邻接矩阵：扫描整个表，$o(n^2)$
- 逆拓扑排序：输出出度为0的点，把指向它们的边删除。重复
  - 邻接表效率低，需要逆邻接表。或者邻接矩阵
  - 可以使用DFS递归实现
- 关键路径AOE：
  - 仅有一个开始顶点（源点）和一个结束顶点（汇点）
  - 源点到汇点所有路径中最长的是关键路径
  - 时间余量：某个活动最短开始时间和最长开始时间的差值
  - 步骤：确定点的拓扑排序时间（取大）；确定点的逆拓扑排序时间（取小）；确定边的开始时间；确定边的结束时间；时间余量为0的是关键活动，它们组成关键路径
  - 可能有多条关键路径，只提高一条关腿路径上的关健活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的
    
    边的最迟开始时间是后面的最晚开始时间减去事件的持续时间，不是用出发点算了！和点区分开来

6.查找

关键字：不重复的唯一标识
平均查找长度ASL，通常考虑成功失败两种情况

6.1.折半查找

代码
查找判定树：如果是偶数个元素，那么右边比左边多一个
树高 $log_2(n+1)$，只有最下面一层可以不满
n个数，失败节点n+1个
不是一定比顺序查找快

计算平均查找长度，画一个树出来，路径长度就是成功长度，空指针就是失败

最多 $\lfloor log_2n\rfloor+1$ 次比较。无论成功还是不成功

6.2.分块查找

若索引表中不包含目标关键字，则折半查找索引表最终停在Iow>high，要在low所指分块中查找

原因：最终Iow左边一定小于目标关键字，high右边一定大于目标关键字。而分块存储的索引表中保存的是各个分块的最大关键字
Iow超出索引表范围，查找失败
复杂度

假设，长度为的查找表被均匀地分为b块，每块s个元素。

顺序查找：$ASL=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s}$。$s=\sqrt{n}$时，$ASL_{min}=\sqrt{n}+1$

折半查找：$ASL=log_2(b+1)+\frac{s+1}{2}$

6.3.B+树

非叶根节点至少两颗子树，其他每个分支节点至少$\lceil\frac{m}{2}\rceil$颗子树
每个分支节点最多m颗子树
节点储存分支中最大值
节点子树个数和关键字个数相等
示意图

6.4.B树

含n个关键字的m阶B树

最小高度：让每个结点尽可能的满，有m-1个关键字，m个分叉，则有$n\le(m-1)(1+m+m^2+…+m^{h-1})=m^h-1$，故$h\ge log_m(n+1)$

最大高度：让各层的分叉尽可能的少，即根节点只有2个分叉，其他结点只有$\lceil\frac{m}{2}\rceil$个分叉。

各层结点至少有：第一层1、第二层2、第三层$\lceil\frac{m}{2}\rceil$…第h层$2\lceil\frac{m}{2}\rceil^{h-2}$，第h+1层共有叶子节点$2\lceil\frac{m}{2}\rceil^{h-1}$个。

n个关键字的B树必有n+1个叶子节点（失败空指针），则$n+1\ge 2\lceil\frac{m}{2}\rceil^{h-1}$，即$h\le log_{\lceil\frac{m}{2}\rceil}\frac{n+1}{2}+1$
含n个关键字的m叉B树

最大高度：让每个结点包含的关键字、分叉尽可能的少。记$k=\lceil\frac{m}{2}\rceil$

递推

h层的m阶B树至少包含关键字总数 $1+2(k-1)(k^0+k^1+…+k^{h-2})=1+2(k^{h-1}-1)\le n$

得到 $h\le log_{\lceil\frac{m}{2}\rceil}\frac{n+1}{2}+1$
B树的插入

保证上层节点比它左边节点的子节点的最大值大。一旦超出了阶数就取$\lceil\frac{m}{2}\rceil$节点到上层分裂

例子：
B树的删除

删根节点：找到直接前驱（左子树中最下层最右边）或后继（右子树最下层最左边）顶替

兄弟够借：后继和后继的后继来填补；前驱和前驱的前驱来填补

兄弟不够借：被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均=$\lceil\frac{m}{2}\rceil-1$，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并

6.5.散列查找

装填因子$\alpha=$表中记录个数/散列表表长
查找效率：取决于散列函数、处理冲突的方法、装填因子
散列函数
- 取余法：一般取素数
- 线性变化或直接定址：适用于关键字分布基本连续
- 数字分析法：截取数字的一部分作为散列地址，比如手机号
- 平方取中：取平方值的中间几位。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
处理冲突
- 拉链法
- 开放定址法：
  - 线性探测：看后面一个位置
    
    删除时使用一个删除标记，而不是直接置空。否则可能导致后面删除时查找失败
  - 平方探测：$\pm k^2$。散列表长度m必须是一个可以表示成4j+3的素数，才能探测到所有位置
  - 伪随机序列
- 再散列法

7.排序

算法复杂度与初始状态无关：选择排序、堆排序、归并排序、基数排序

元素总比较次数与初始状态无关：选择排序、基数排序

元素总移动次数与初始状态无关：归并排序、基数排序

排序趟数与初始状态有关：快排、冒泡排序

7.1.插入排序

空间复杂度o(1)
最好时间复杂度o(n)，比较n-1次，不需要移动
最坏时间复杂度$o(n^2)$
平均时间复杂度$o(n^2)$
稳定排序

//插入排序
void InsertSort(int A[],int n)
{
    int i, j, temp;
    for(i = 1; i < n; i++)
        if(A[i] < A[i-1])
        {
            temp = A[i];
            for(j = i-1; j >= 0 && A[j] > temp; --j)
                A[j+1] = A[j];
            A[j+1] = temp
        }
}

使用折半查找来加速。当Iow>high时折半查找停止，应将[low,i-1]内的元素全部右移，并将A[0]复制到Iow所指位置。比较次数减少，移动次数不变。

//折半插入排序。使用了哨兵
void InsertSort(int A[],int n)
{
    int i, j, low, mid, high;
    for(i = 2; i <= n; i++)
    {
        A[0] = A[i];
        low = 1; high = i-1;
        while(low <= high)
        {
            mid = (low + high) / 2;
            if(A[mid] > A[0]) 
                high = mid-1;
            else 
                low = mid+1;
        }
        for(j = i-1; j >= high+1; --j)
            A[j+1] = A[j];
        A[j+1] = A[0];
    }   
}

对链表插入排序，比较$o(n^2)$，移动只需要改几个指针。

7.2.希尔排序

按间隔d划分为子表，使用插入排序。然后缩小d继续，直到d=1
空间复杂度o(1)
最坏时间复杂度为$o(n^2)$，当n在某个范围内时，可达$o(n^{1.3})$
不稳定排序
需要随机访问，只能顺序表，不能链表

//希尔排序
void ShellSort(int A[], int n)
{
    int d, i, j;
    for(d = n/2; d > 1; d = d/2) //步长变化
        for(i = d+1; i <= n; ++i)
            if(A[i] < A[i-d])
            {
                A[0] = A[i]; //用于暂存，不是哨兵
                for(j = i-d; j > 0 && A[0] < A[j]; j -= d)
                    A[j+d] = A[j];
                A[j+d] = A[0];
            }
}

7.3.冒泡排序

空间复杂度o(1)
最好时间复杂度o(n)，比较n-1次，不需要移动
最坏时间复杂度$\frac{n(n-1)}{2}$，等于比较次数和交换次数
稳定排序

//冒泡排序
void BubbleSort(int A[], int n)
{
    for(int i = 0; i < n-1; i++)
    {
        bool flag = flase;
        for(int j = n-1; j > i; j--)
            if(A[j-1] > A[j])
            {
                swap(A[j-1], A[j])
                    flag = true;
            }
        if(flag == flase) return; //本趟遍历后没有发生交换，说明表已经有序
    }
}

7.4.快排

最好时间复杂度$o(nlog_2n)$
- 最坏时间复杂度$o(n^2)$
最好空间复杂度$o(log_2n)$
- 最坏空间复杂度$o(n)$
不稳定排序
优化：
- 选头中尾，取中间值作为枢轴
- 随机选枢轴
定义辨析：一趟排序，对所有数据进行一次处理，相当于快排处理一层。可以一次确定多个元素的位置

//快速排序
int Partition(int A[], int low, int high)
{
    int pivot = A[low]; //第一个元素作为枢轴
    while(low < high)
    {
        while(low < high && A[high] >= pivot) --high;
        A[low] = A[high];
        while(low < high && A[low] <= pivot) ++low;
        A[high] = A[low];
    }
    A[low] = pivot; //枢轴元素放到最终位置
    return low; //返回存放枢轴元素的位置
}
void QuickSort(int A[], int low, int high)
{
    if (low < high) //递归跳出条件
    {
        int pivotpos = Partition(A, low, high); //划分
        QuickSort(A, low, pivotpos-1);
        QuickSort(A, pivotpos+1, high);
    }
}

例题：找到第k小元素

int findKth(int a[], int l ,int r,int k){
    if (l == r) return a[l];
    
    int x = a[l + r >> 1] , i = l - 1 , j = r + 1;
    while (i < j){
        while (a[++i] < x);
        while (a[--j] > x);
        if (i < j) swap(a[i] , a[j]);
    }
    //计算主元左边数字个数
    int lcnt = j - l + 1;
    //判断第k个数在左边还是右边
    if (k <= lcnt) return findKth(a, l, j, k);
    else return findKth(a, j + 1, r, k - lcnt);
}

7.5.简单选择排序

空间复杂度$o(1)$
时间复杂度$o(n^2)$，需要对比$\frac{n(n-1)}{2}$次
不稳定排序

//选择排序
void SelectSort(int A[], int n)
{
    for(int i = 0; i < n-1; i++)
    {
        int min = i;
        for(nt j = i+1; j < n; j++)
            if(A[j] < A[min]) 
                min = j;
        if(min != i) 
            swap(A[i],A[min]);
    }
}

7.6.堆排序

调整方法：检查当前结点是否根比左、右都大。若不满足，将当前结点与更大的一个孩子互换
构建大根堆，把堆顶和堆底元素换，然后继续维护堆
建堆的时间不超过4n，复杂度o(n)
排序过程每一趟复杂度不超过o(height)，即$o(log_2n)$。共n-1趟，故$o(nlog_2n)$
空间o(1)
不稳定排序

//堆排序
void BuildMaxHeap(int A[], int len)
{
    for(int i = len/2; i > 0; i--) //从后往前调整所有非终端节点
        HeapAdjust(A, i, len);
}
void HeapAdjust(int A[], int k, int len) //调整以k为根的子树
{
    A[0] = A[k]; //暂存根节点
    for(int i = 2*k, i <= len; i *= 2) //沿key较大的子结点向下筛选
    {
        if(i < len && A[i] < A[i+1])
            i++; //取key较大的子结点的下标
        if(A[0] >= A[i]) 
            break; //筛选结束
        else
        {
            A[k] = A[i]; //将A[i]调整到双亲结点上
            k = i; //继续向下筛选
        }
    }
    A[k] = A[0]; //被筛选结点的值放入最终位置
}
void HeapSort(int A[], int len)
{
    BuildMaxHeap(A, len);
    for(int i = len; i > 1; i--)
    {
        swap(A[1], A[i]);
        HeapAdjust(A, 1, i-1);
    }
}

小根堆
- 插入：新元素加入堆底，然后一路和父亲比大小，一路上升直到无法继续为止
- 删除：删除它，把堆底放上来，不断下坠

7.7.归并排序

2路归并：两个指针依次比较后移，更小的放到新数组里。一个序列空了之后另一个序列剩下的直接整个复制进来。
示意图
时间复杂度$o(nlog_2n)$。n个元素进行2路归并，共$\lceil\frac{m}{2}\rceil$趟，每一趟n个数都处理一遍
空间复杂度o(n)
稳定排序

//归并排序
int *B = (int*)malloc(n * sizeof(int)); //辅助数组
void Merge(int A[], int low, int mid, int high) //mid左右两个数组各自有序
{
    int i, j, k;
    for(k = low; k <= high; k++)
        B[k] = A[k]; //将A中所有元素复制到B中
    for(i = low,j = mid+1,k = i; i <= mid && i <= high; k++)
    {
        if(B[i] <= B[j])
            A[k] = B[i++]; //将较小值复制到A中
        else
            A[k] = B[j++];
    }
    while(i <= mid)
        A[k++] = B[i++];
    while(j <= high)
        A[k++] = B[j++];
}
void MergeSort(int A[], int low, int high)
{
    if(low < high)
    {
        int mid = (low + high) / 2; //划分
        MergeSort(A, low, mid); //左半部分归并
        MergeSort(A, mid+1, high); //右半部分归并
        Merge(A, low, mid, high); //归并
    }
}

7.8.基数排序

按照每一位数字取值范围划分几个不同的队伍，按位数从低到高划分队伍后用链表接起来，重复
r个辅助队列（关键字的范围），n个元素，d趟分配（关键字划分几部分）
- 空间复杂度o(r)
- 时间复杂度o(d(n+r))。一趟分配o(n)，一趟收集o(r)，总共d趟分配、收集
稳定排序
擅长的问题：
- 数据元素的关键字可以方便地拆分为不太多的组（d）：~~给5个人的身份证号排序~~
- 每组关键字的取值范围不大（r）：~~给中文人名排序~~
- 数据元素较多（n）：给十亿人的身份证号排序

7.9.外部排序

2路归并：每次归并合并两个归并段。输入缓冲区空了马上用归并段没读如的部分补上。以此类推直到合并为一个归并段
示意图
r个归并段，k路归并，归并趟数$=\lceil log_kr\rceil$。使用多路归并，减少初始归并段数量，减少磁盘IO，加速排序
- k路归并，得到一个最小值需要k-1次对比
定义：k路平衡归并：
- 最多只能有k个段归并为一个
- 每一趟归并中，若有m个归并段参与归并，则经过这一趟处理得到$\lceil\frac{m}{k}\rceil$个新的归并段
改进：败者树
- 结构
- 新补上的元素沿着上一次胜者的路径比较即可
- k路归并，第一次需要对比关键字k-1次，接下来只需要$\lceil log_2k\rceil$次
改进：置换-选择排序
- 记录上一次输出的最小值，要是补进来的比它还小就不动，直到整个内存工作区中的数都比上一次输出的最小值小
- 结构
- 使用置换-选择排序，可以让每个初始归并段的长度超越内存工作区大小的限制
改进：最佳归并树
- 磁盘IO次数等于归并树的带权路径长度乘二
- 2路归并：按照初始归并段的长度，构造哈夫曼树
- 多路归并：类似于哈夫曼树，每次选最小的k个子树。需要提前补0
  
  $\begin{cases}n=n_0+n_k\\k\cdot n_k=n-1\end{cases}\Longrightarrow n_0=(k-1)n_k+1\Longrightarrow n_k=\frac{(n_0-1)}{(k-1)}$
  
  初始归并段数量+补0数量刚好能除尽 k-1
  
  (初始数量-1) % （k-1）= u，需要补充 (k-1)-u 个0

考研

本博客所有文章除特别声明外均为原创，均采用 CC BY-SA 4.0 协议，转载请注明出处！

408-计网-基础笔记上一篇

408-计组-基础笔记下一篇