数据结构理论复习

# 绪论

# 数据结构的定义

• 数据是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。
• 数据元素是数据的基本单位（例如，A 班中的每个学生记录都是一个数据元素），也就是说数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理
• 数据项是具有独立含义的数据最小单位，也称为成员或域
• 数据对象是性质相同的有限个数据元素的集合，它是数据的一个子集。
• 数据结构是指所涉及的数据元素以及数据元素之间的关系，可以看作是相互之间存在着特定关系的数据元素的集合。
• 数据元素之间的逻辑关系 => 数据的逻辑结构
• 数据元素及其关系在计算机存储器中的存储方式 => 数据的存储结构（或物理结构）
• 施加在该数据上的操作 => 数据运算

# 算法及其描述

• 有穷性
• 确定性
• 可行性
• 输入性
• 输出性

# 算法时间性能分析

• 求和定理
• 求积定理

# 算法存储空间分析

• 在对算法进行存储空间分析时，只考察临时变量所占空间

# 线性表

线性表（Linear List）是具有相同数据类型的 $n$ $(n \geq 0)$ 个数据元素的有序序列。

• 相同数据类型
• 有序
• 序列

其中 $n$ 为表长。当 $n=0$ 时线性表是一个空表。

$$L=(\alpha_1,\alpha_2,...,\alpha_i,\alpha_{i+1},...,\alpha_n)$$

• $\alpha_i$ 是线性表中的 “第 $i$ 个” 元素线性表中的位序。
• $\alpha_1$ 是表头元素，$\alpha_n$ 是表尾元素。
• 出第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

# 顺序表

顺序表：用顺序存储方式实现的线性表。

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

• 随机访问：即可以在 $O(1)$ 时间内找到第 $i$ 个元素。
• 存储密度高：每个结点只存储数据元素。
• 扩展容量不方便：静态分配不能扩展容量，动态分配可以扩展但时间复杂度高。
• 插入元素移动的平均次数为$\sum\limits_{i=0}^n p_i (n-i)=\frac{1}{n+1}\times \frac{n(n+1)}{2}=\frac{n}{2}$
• 删除元素移动的平均次数为$\sum\limits_{i=0}^{n-1} p_i (n-i-1)=\frac{1}{n}\times \frac{n(n-1)}{2}=\frac{n-1}{2}$

void reverse(int a[], int low, int high)

{

    while (low < high)

    {

        swap(a[low], a[high]);

        low++;

        high--;

    }

}

int majority(int a[], int n)

{

    int count = 0, candidate;

    for (int i = 0; i < n; i++)

    {

        if (count == 0)

            candidate = a[i];

        count += (a[i] == candidate) ? 1 : -1;

    }

    return candidate;

}

# 链表

# 单链表

• 头结点：链表的第一个结点称为头结点，头结点不存放数据元素
• 尾结点：链表的最后一个结点称为尾结点，尾结点的 next 指针域为空
• 插入 s->next = p->next; p->next = s;
• 删除 q = p->next; p->next = q->next; delete q;
• 头插法建表 s->next = head->next; head->next = s;
• 尾插法建表 rear->next = s; rear = s;

s->next = p->next;

p->next = s;

swap(s->data, p->data);

q = p->next;

p->data = q->data;

p->next = q->next;

delete q;

void findKthFromEnd(Node *head, int k)

{

    Node *p1 = head;

    Node *p2 = head;

    for (int i = 0; i < k; i++)

        p1 = p1->next;

    while (p1 != NULL)

    {

        p1 = p1->next;

        p2 = p2->next;

    }

    return p2;

}

Node *getIntersectionNode(Node *headA, Node *headB)

{

    int lenA = 0, lenB = 0;

    Node *pA = headA, *pB = headB;

    while (pA != NULL)

    {

        lenA++;

        pA = pA->next;

    }

    while (pB != NULL)

    {

        lenB++;

        pB = pB->next;

    }

    int d = abs(lenA - lenB);

    if (lenA > lenB)

        for (int i = 0; i < d; i++)

            headA = headA->next;

    else

        for (int i = 0; i < d; i++)

            headB = headB->next;

    while (headA != NULL && headB != NULL)

    {

        if (headA == headB)

            return headA;

        headA = headA->next;

        headB = headB->next;

    }

    return NULL;

}

Node *findMiddleNode(Node *head)

{

    Node *slow = head;

    Node *fast = head;

    while (fast != NULL && fast->next != NULL)

    {

        slow = slow->next;

        fast = fast->next->next;

    }

    return slow;

}

Node *reverseList(Node *head)

{

    Node *prev = NULL;

    Node *curr = head;

    while (curr != NULL)

    {

        Node *nextTemp = curr->next;

        curr->next = prev;

        prev = curr;

        curr = nextTemp;

    }

    return prev;

}

# 双向链表

# 基本操作

# 插入

s->next = p->next;

p->next->prior = s;

s->prior = p;

p->next = s;

# 删除

p->next = q->next;

q->next->prior = p;

delete q;

# 循环链表

# 顺序表和链表的比较

# 栈和队列

# 栈

• 判断准则：输入序列为$1,2,…,n,(p_1,p_2,…,p_n)$ 是$1,2,…,n$ 的一种排列，利用一个栈得到输出序列$(p_1,p_2,…,p_n)$ 的充分必要条件是不存在这样的$i、j、k$ 满足$i<j<k$ 的同时也满足$p_j<p_k<p_i$。
• $1\sim n$ 共产生$\frac{1}{n+1} C_{2n}^n$ 种合法出栈序列 (Catalan 数)

# 共享栈

• 栈满条件： top1 + 1 == top2

# 队列

# 顺序队列

• 队空条件： front == rear
• 队满（上溢出）条件： rear == MaxSize - 1

# 循环队列

• 元素出队： front = (front + 1) ％ MaxSize
• 元素 e 进队： rear = (rear + 1) ％ MaxSize
• 队空条件： front == rear
• 队满条件： (rear + 1) % MaxSize == front
• 队列长度： (rear - front + MaxSize) % MaxSize

# 链队

• 队空条件： front = rear = NULL

# 双端队列

注意一端受限的双端队列

# 数组

# 数组的存储结构

# 一维数组

• $LOC(a_i)=LOC(a_0)+i×k, (1≤i<n)$

# 二维数组

• 行优先：$LOC(a_{ij})=LOC(a_{00}) + (i×n + j)×k$
• 列优先：$LOC(a_{ij})=LOC(a_{00}) + (j×m + i)×k$

# 对称矩阵的压缩存储

# 三角矩阵

# 下三角矩阵

下三角矩阵：除了主对角线和下三角区，其余的元素都相同

# 上三角矩阵

上三角矩阵：除了主对角线和上三角区，其余的元素都相同

# 三对角矩阵

三对角矩阵也叫带状矩阵，只有主对角线和主对角线的上下两条对角线上的元素不为 0

# 稀疏矩阵的三元组表示

• 行号、列号、元素值

# 串

# KMP

# KMP 算法简介

KMP（Knuth-Morris-Pratt）算法是一种用于在字符串中查找子串的高效算法，旨在提高匹配速度，减少不必要的比较。

• 前缀：除了最后一个字符外，子串的所有头部子串
• 后缀：除了第一个字符外，子串的所有尾部子串
• 部分匹配值：字符串的前缀和后缀相同的最大长度
• 失配：在匹配过程中，当前字符不相等的情况

# next 数组手算

next[j] 表示当模式串的第 j 个字符失配时，跳到模式串的第 next[j] 个字符继续匹配。

# KMP 算法

void get_next(const string &pattern, vector<int> &next)

{

    int j = 0;

    next[0] = -1;

    for (int i = 1; i < pattern.size(); i++)

    {

        while (j > 0 && pattern[i] != pattern[j])

            j = next[j - 1];

        if (pattern[i] == pattern[j])

            j++;

        next[i] = j;

    }

}

int KMP(const string &text, const string &pattern)

{

    vector<int> next(pattern.size());

    get_next(pattern, next);

    int j = 0;

    for (int i = 0; i < text.size(); i++)

    {

        while (j > 0 && text[i] != pattern[j])

            j = next[j - 1];

        if (text[i] == pattern[j])

            j++;

        if (j == pattern.size())

            return i - j + 1; // 匹配成功，返回匹配位置

    }

    return -1; // 匹配失败

}

# KMP 算法复杂度

• 时间复杂度：O (m+n)，m 为模式串长度，n 为文本串长度
• 空间复杂度：O (m)，存储 next 数组

# KMP 的进一步优化

计算 next 数组时，可以使用 nextval 数组来优化，避免重复计算。

void get_nextval(const string &pattern, vector<int> &nextval)

{

    int j = 0;

    nextval[0] = -1;

    for (int i = 1; i < pattern.size(); i++)

    {

        while (j > 0 && pattern[i] != pattern[j])

            j = nextval[j - 1];

        if (pattern[i] == pattern[j])

            j++;

        if (pattern[i] != pattern[nextval[j]])

            nextval[i] = j;

        else

            nextval[i] = nextval[j];

    }

}

nextval[1] = 0

for (int i = 2; i < n; i++)

{

    if (pattern[i] == pattern[next[i]])

        nextval[i] = nextval[next[i]];

    else

        nextval[i] = next[i];

}

# 递归

# 递归算法转换为非递归算法

# 迭代转换法

• 尾递归和单向递归是两种特殊类型的递归，可以采用迭代转换法将它们转换为非递归算法，即将其递归结构用循环结构来替代。
• 尾递归是递归调用语句只有一个，而且是处于算法的最后
• 单向递归是指执行过程总是朝着一个方向进行的，递归函数中虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调用函数有关，参数相互之间无关

# 用栈模拟转换法

• 不能采用迭代转换法的递归算法执行中往往涉及回溯，可以采用栈来保存暂时不能执行的子问题，或者使用栈保存中间结果，称为用栈模拟转换法

  	void nonrecursive(si) //非递归算法框架
  	{ 将大问题状态si进栈;
  	while (栈不为空)
  	{ 退栈一个元素s;
  	if (s可以直接解决)
  	直接求该问题解;
  	else
  	{ 根据递归过程将s转换为若干个相似子问题的状态sj;
  	将每个sj进栈;
  	}
  	}
  	}

# 树和二叉树

# 树的基本术语

• 结点的度：树中每个结点具有的子树数或者后继结点数称为该结点的度
• 树的度：树中所有结点的度的最大值称之为树的度
• 分支结点：度大于 0 的结点称为分支结点或非终端结点。度为 1 的结点称为单分支结点，度为 2 的结点称为双分支结点，依次类推
• 叶子结点：度为零的结点称为叶子结点或终端结点
• 结点层次：树具有一种层次结构，根结点为第一层，其孩子结点为第二层，如此类推得到每个结点的层次
• 树的高度：树中结点的最大层次称为树的高度或深度

# 树的性质

• 树中的结点数$n$ 等于所有结点的度数加 1
• 度为$m$ 的树中第$i$ 层上至多有$m^{i-1}$ 个结点，这里应有$i≥1$
• 高度为$h$ 的$m$ 次树至多有$\frac{m^h-1}{m-1}$ 个结点，最少有$h+m-1$ 个结点
• 具有$n$ 个结点的$m$ 次树的最小高度为$\log_m[n(m-1)+1]$
• 度为$m$ 的树、具有$n$ 个结点的树的最大高度为$n-m+1$

# 二叉树的定义

• 在含$n$ 个结点的二叉树中，所有结点的度小于等于 2，通常用$n_0$ 表示叶子结点个数，$n_1$ 表示单分支结点个数，$n_2$ 表示双分支结点个数

# 满二叉树

• 即一棵高度为$h$ 且有$2^{h}-1$ 个结点的二叉树称为满二叉树，只有度为 0 和度为 2 的结点，
• 含$n$ 个结点的满二叉树的高度为$\log_2(n+1)$，叶子结点个数为$\lfloor n/2\rfloor +1$，度为 2 的结点个数为$\lfloor n/2 \rfloor$
• 按层序编号后，结点的编号为$1,2,…,n$，其中结点$i$ 的左孩子为$2i$，右孩子为$2i+1$，双亲结点为$\lfloor i/2 \rfloor$

# 完全二叉树的特点

• 叶子结点只可能出现在最下面两层中
• 对于最大层次中的叶子结点，都依次排列在该层最左边的位置上
• 如果有度为 1 的结点，只可能有一个，且该结点只有左孩子而无右孩子
• 按层序编号后，一旦出现某结点（其编号为$i$）为叶子结点或只有左孩子，则编号大于$i$ 的结点均为叶子结点
• 具有$n$ 个（$n＞0$）结点的完全二叉树的高度为$\lceil \log_2(n+1)\rceil$ 或$\lfloor\log_2n\rfloor+1$
• 若$n$ 为奇数，则每个分支节点都有两个孩子，若$n$ 为偶数，编号最大的分支节点（$\lfloor n/2 \rfloor$）只有左孩子
• 节点$i$ 的所在层数为$\lfloor \log_2(i) \rfloor+1$

# 二叉树性质

• 非空二叉树上叶结点数等于双分支结点数加 1。即$n_0=n_2+1$
• 非空二叉树上第 i 层上至多有$2^{i-1}$ 个结点，(i≥1)。
• 高度为 h 的二叉树至多有$2^{h}-1$ 个结点（h≥1）
• $n_1$ 只能是 0 或 1，当 n 为偶数时，$n_1=1$，当 n 为奇数时，$n_1=0$

# 二叉树的遍历

• 前序遍历：根结点 -> 左子树 -> 右子树
• 中序遍历：左子树 -> 根结点 -> 右子树
• 后序遍历：左子树 -> 右子树 -> 根结点
• 层序遍历：从上到下，从左到右

# 二叉树的构造

• 前序遍历 + 中序遍历：前序遍历的第一个结点为根结点，在中序遍历中找到该结点，左边为左子树，右边为右子树
  
• 中序遍历 + 后序遍历：中序遍历的最后一个结点为根结点，在后序遍历中找到该结点，左边为左子树，右边为右子树
  
• 中序遍历 + 层序遍历：中序遍历的第一个结点为根结点，在层序遍历中找到该结点，左边为左子树，右边为右子树
  

# 线索二叉树

• 线索二叉树是对二叉树的一种扩展，增加了指向前驱和后继结点的线索指针

# 线索化（手画）

1. 确定类型：前序？中序？后序？
2. 将结点按遍历顺序编号
3. 将$n+1$ 个空链域连上前驱后继

# 哈夫曼树

• $WPL=\sum\limits_{i=1}^{n_0}w_i\times l_i$
• 哈夫曼树中没有单分支结点
• 对于具有$n_0$ 个叶子结点的哈夫曼树，共有$2n_0-1$ 个结点

# 哈夫曼编码

• 规定哈夫曼树中的左分支为 0，右分支为 1
• 从根结点到每个叶子结点所经过的分支对应的 0 和 1 组成的序列便为该结点对应字符的编码

# 树 / 森林与二叉树的转换及还原

# 一棵树到二叉树的转换

• 加线：在各兄弟结点之间加一连线，将其隐含的 “兄－弟” 关系以 “双亲－右孩子” 关系显示表示出来
• 抹线：对任意结点，除了其最左子树之外，抹掉该结点与其他子树之间的 “双亲－孩子” 关系
• 调整：以树的根结点作为二叉树的根结点，将树根与其最左子树之间的 “双亲－孩子” 关系改为 “双亲－左孩子” 关系，且将各结点按层次排列，形成二叉树

# 特点

• 根结点只有左子树而没有右子树
• 左分支不变（左分支为最左孩子），兄弟变成右分支（右分支实为双亲的兄弟）
• 树中分支结点个数为 m，则二叉树中无右孩子的结点个数为 m+1

# 一棵由树转换的二叉树还原为树

• 加线：在各结点的双亲与该结点右链上的每个结点之间加一连线，以 “双亲－孩子” 关系显示表示出来
• 抹线：抹掉二叉树中所有双亲结点与其右孩子之间的 “双亲－右孩子” 关系
• 调整：以二叉树的根结点作为树的根结点，将各结点按层次排列，形成树

# 特点

• 根结点不变
• 左分支不变（左分支为最左孩子），右分支变成兄弟

# 森林与二叉树的转换及还原

# 森林转换为二叉树

• 转换：将森林中的每一棵树转换成二叉树，设转换成的二叉树为$bt_1、bt_2、…、bt_m$
• 连接：将各棵转换后的二叉树的根结点相连
• 调整：以$bt_1$ 的根结点作为整个二叉树的根结点，将$bt_2$ 的根结点作为$bt_1$ 的根结点的右孩子，将$bt_3$ 的根结点作为$bt_2$ 的根结点的右孩子，…，如此这样得到一棵二叉树，即为该森林转换得到的二叉树

# 二叉树还原为森林

• 抹线：抹掉二叉树根结点右链上所有结点之间的 “双亲－右孩子” 关系，分成若干个以右链上的结点为根结点的二叉树，设这些二叉树为$bt_1、bt_2、…、bt_m$
• 转换：分别将$bt_1、bt_2、…、bt_m$ 二叉树各自还原成一棵树
• 调整：将转换好的树构成森林

# 树、森林与二叉树的遍历

# 并查集

并查集使用树的双亲表示法作为存储结构

• 结点的值为该结点的父结点的编号
• 结点的值为 - 1 表示该结点为根结点

template <typename T>

class UnionFind

{

    private:

        vector<T> parent;

    public:

        UnionFind(int n)

        {

            parent.resize(n);

            for (int i = 0; i < n; i++)

                parent[i] = -1;

        }

        int find(int x)

        {

            if (parent[x] == -1)

                return x;

            return find(parent[x]);

        }

        void unionSet(int x, int y)

        {

            int rootX = find(x);

            int rootY = find(y);

            if (rootX != rootY)

                parent[rootX] = rootY;

        }

        bool connected(int x, int y)

        {

            return find(x) == find(y);

        }

    };

• find(x) ：查找结点 x 的根结点
• unionSet(x, y) ：将结点 x 和结点 y 所在的集合合并
• connected(x, y) ：判断结点 x 和结点 y 是否在同一集合中
• parent[x] ：结点 x 的父结点编号

# 并查集的优化

# 改进的 unionSet 函数

• 按秩合并：将小树的根结点连接到大树的根结点上， parent[rootX] 可以表示树的高度

void unionSet(int x, int y)

{

    int rootX = find(x);

    int rootY = find(y);

    if (rootX == rootY)

        return;

    if (parent[rootX] < parent[rootY]){

        parent[rootX] += parent[rootY];

        parent[rootY] = rootX;

    }

    else{

        parent[rootY] += parent[rootX];

        parent[rootX] = rootY;

    }

}

# 路径压缩

• 在查找结点 x 的根结点时，将路径上的所有结点都直接连接到根结点上，减少树的高度

int find(int x)

{

    if (parent[x] == -1)

        return x;

    parent[x] = find(parent[x]); // 路径压缩

    return parent[x];

}

# 复杂度

• find(x) ：O(α(n))
• unionSet(x, y) ：O(α(n))
• connected(x, y) ：O(α(n))
• 其中 α(n) 为阿克曼函数的反函数，增长极其缓慢，几乎可以认为是常数时间复杂度
• n 为结点个数

# 图

# 图的基本概念

# 简单图与多重图

• 简单图：无向图中任意两个顶点之间最多只有一条边相连，且没有自环
• 多重图：无向图中任意两个顶点之间可以有多条边相连，且没有自环

# 路径、路径长度与回路

• 路径：从一个顶点到另一个顶点的边的序列称为路径
• 路径长度：路径上边的条数称为路径长度
• 回路：从一个顶点出发，经过若干条边后又回到该顶点的路径称为回路
• 若一个图有$n$ 个顶点，且有大于$n-1$ 条边，则该图一定有回路

# 简单路径和简单回路

• 简单路径：路径上没有重复的顶点
• 简单回路：回路上没有重复的顶点，且起点和终点是同一个顶点

# 连通图与强连通图

• 连通图：无向图中任意两个顶点之间都有路径相连
• 极大连通子图：无向图中任意两个顶点之间都有路径相连的子图称为极大连通子图，也叫连通分量
• 一个图有$n$ 个顶点，但是有小于$n-1$ 条边，则该图一定是一个非连通图，若一个图是非连通图，最多有$C_{n-1}^{2}$ 条边
• 强连通图：有向图中任意两个顶点之间都有路径相连
• 极大强连通子图：有向图中任意两个顶点之间都有路径相连的子图称为极大强连通子图，也叫强连通分量
• 一个有向图有$n$ 个顶点，但是有小于$n$ 条边，则该图一定是一个非强连通图

# 完全图

• 完全图：无向图中任意两个顶点之间都有一条边相连，共有$\frac{n(n-1)}{2}$ 条边
• 有向完全图：有向图中任意两个顶点之间都有一条边相连，共有$n(n-1)$ 条边

# 图的存储结构

# 邻接矩阵

适合存储稠密图

# 邻接表

• 对图中每个顶点 i 建立一个单链表，将顶点 i 的所有邻接点链起来
• 每个单链表上添加一个表头结点（表示顶点信息）。并将所有表头结点构成一个数组，下标为 i 的元素表示顶点 i 的表头结点

# 特点

• 邻接表表示不唯一
• 对于有 n 个顶点和 e 条边的无向图，其邻接表有 n 个表头结点和 2e 个边结点；对于有 n 个顶点和 e 条边的有向图，其邻接表有 n 个表头结点和 e 个边结点
• 用邻接表存储图时，确定任意两个顶点之间是否有边相连的时间为$O(m)$

# 十字链表

十字链表是有向图的一种存储结构，适合存储稀疏图

# 弧节点

• tailvex ：弧尾结点
• headvex ：弧头结点
• hlink ：弧头结点的下一个弧头结点
• tlink ：弧尾结点的下一个弧尾结点
• info ：弧的权值

# 顶点节点

• data ：顶点信息
• firstin ：指向第一个入弧结点
• firstout ：指向第一个出弧结点

# 邻接多重表

• 邻接多重表是无向图的一种存储结构
  

# 边结点

• ivex ：边的第一个顶点
• ilink ：指向下一个边结点
• jvex ：边的第二个顶点
• jlink ：指向下一个边结点
• info ：边的权值

# 顶点结点

• data ：顶点信息
• firstedge ：指向第一个边结点

# 图的遍历

# 广度优先遍历（BFS）

// 邻接表实现

void BFS(int v)

{

    queue<int> q;

    vector<bool> visited(n, false);

    q.push(v);

    visited[v] = true;

    while (!q.empty())

    {

        int u = q.front();

        q.pop();

        cout << u << " ";

        for (auto p = G.vertices[u].first; p != nullptr; p = p->next)

        {

            int w = p->adjvex;

            if (!visited[w])

            {

                visited[w] = true;

                q.push(w);

            }

        }

    }

}

// 邻接矩阵实现

void BFS(int v)

{

    queue<int> q;

    vector<bool> visited(n, false);

    q.push(v);

    visited[v] = true;

    while (!q.empty())

    {

        int u = q.front();

        q.pop();

        cout << u << " ";

        for (int w = 0; w < n; w++)

        {

            if (G.edges[u][w] != 0 && !visited[w])

            {

                visited[w] = true;

                q.push(w);

            }

        }

    }

}

# BFS 的复杂度

# 深度优先遍历（DFS）

vector<bool> visited(n, false);

// 邻接表实现

void DFS(int v)

{

    visited[v] = true;

    cout << v << " ";

    for (auto p = G.vertices[v].first; p != nullptr; p = p->next)

    {

        int w = p->adjvex;

        if (!visited[w])

            DFS(w);

    }

}

// 邻接矩阵实现

void DFS(int v)

{

    visited[v] = true;

    cout << v << " ";

    for (int w = 0; w < n; w++)

    {

        if (G.edges[v][w] != 0 && !visited[w])

            DFS(w);

    }

}

# DFS 的复杂度

# 最小生成树

# Prim 算法

• Prim 算法是用于寻找加权无向图的最小生成树的一种贪心算法。
• 算法步骤：
  1. 从任一顶点开始，标记为已访问。
  2. 在已访问的顶点中，选择与未访问顶点之间边权最小的边，标记未访问顶点为已访问。
  3. 重复步骤 2，直到所有顶点都被访问。

void Prim(int v)

{

    vector<bool> visited(n, false);

    vector<int> lowcost(n, INT_MAX);

    vector<int> closest(n, -1);

    visited[v] = true;

    lowcost[v] = 0;

    for (int i = 0; i < n - 1; i++)

    {

        int minCost = INT_MAX;

        int u = -1;

        for (int j = 0; j < n; j++)

        {

            if (!visited[j] && lowcost[j] < minCost)

            {

                minCost = lowcost[j];

                u = j;

            }

        }

        visited[u] = true;

        cout << "Edge: " << closest[u] << " - " << u << ", Cost: " << minCost << endl;

        for (int j = 0; j < n; j++)

        {

            if (!visited[j] && G.edges[u][j] != 0 && G.edges[u][j] < lowcost[j])

            {

                lowcost[j] = G.edges[u][j];

                closest[j] = u;

            }

        }

    }

}

# Kruskal 算法

• Kruskal 算法是用于寻找加权无向图的最小生成树的一种贪心算法。
• 算法步骤：
  1. 将图中的所有边按权值从小到大排序。
  2. 初始化一个并查集，用于判断是否形成回路。
  3. 遍历排序后的边，选择不形成回路的边加入最小生成树。

void Kruskal()

{

    vector<Edge> edges;

    for (int i = 0; i < n; i++)

    {

        for (int j = i + 1; j < n; j++)

        {

            if (G.edges[i][j] != 0)

            {

                edges.push_back({i, j, G.edges[i][j]});

            }

        }

    }

    sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.weight < b.weight; });

    UnionFind uf(n);

    for (auto edge : edges)

    {

        if (!uf.connected(edge.start, edge.end))

        {

            uf.unionSet(edge.start, edge.end);

            cout << "Edge: " << edge.start << " - " << edge.end << ", Cost: " << edge.weight << endl;

        }

    }

}

# 最短路径

# Dijkstra 算法

• Dijkstra 算法是用于寻找加权有向图的单源最短路径的一种贪心算法。
• 算法步骤：
  1. 初始化一个距离数组，存储从源点到各个顶点的最短距离。
  2. 初始化一个优先队列，将源点加入队列。
  3. 从队列中取出距离最小的顶点，更新其邻接顶点的距离。
  4. 重复步骤 3，直到队列为空。

void Dijkstra(int start)

{

    vector<int> dist(n, INT_MAX);

    vector<bool> visited(n, false);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[start] = 0;

    pq.push({0, start});

    while (!pq.empty())

    {

        int u = pq.top().second;

        pq.pop();

        if (visited[u])

            continue;

        visited[u] = true;

        cout << "Vertex: " << u << ", Distance: " << dist[u] << endl;

        for (int v = 0; v < n; v++)

        {

            if (G.edges[u][v] != 0 && !visited[v])

            {

                if (dist[u] + G.edges[u][v] < dist[v])

                {

                    dist[v] = dist[u] + G.edges[u][v];

                    pq.push({dist[v], v});

                }

            }

        }

    }

}

# Floyd-Warshall 算法

• Floyd-Warshall 算法是用于寻找加权有向图的所有顶点对之间的最短路径的一种动态规划算法。
• 算法步骤：
  1. 初始化一个距离矩阵，存储从任意顶点到其他顶点的距离。
  2. 遍历所有顶点，更新距离矩阵。
  3. 返回距离矩阵。

void FloydWarshall()

{

    vector<vector<int>> dist(n, vector<int>(n, INT_MAX));

    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            if (i == j)

                dist[i][j] = 0;

            else if (G.edges[i][j] != 0)

                dist[i][j] = G.edges[i][j];

        }

    }

    for (int k = 0; k < n; k++)

    {

        for (int i = 0; i < n; i++)

        {

            for (int j = 0; j < n; j++)

            {

                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)

                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

            }

        }

    }

}

# 总结

# DAG 描述表达式

• 有向无环图（DAG）是一个有向图，其中不存在从某个顶点出发经过若干条边又回到该顶点的路径

# 拓扑排序

• AOV 网：有向无环图（DAG）中每个顶点表示一个活动，每条边表示活动之间的优先关系
• 拓扑排序：对 AOV 网进行排序，使得每个活动在其所有前驱活动之前，每个 AOV 网都有一个或多个拓扑排序序列

• 逆拓扑排序：对 AOV 网进行排序，使得每个活动在其所有后继活动之前，每个 AOV 网都有一个或多个逆拓扑排序序列

# 关键路径

• 关键路径：从源点到汇点的路径中，具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动

# 最早发生时间$v_e(K)$

• 最早发生时间：从源点到达顶点 K 的最短路径长度称为顶点 K 的最早发生时间，记为$v_e(K)$

# 最晚发生时间$v_l(K)$

• 最晚发生时间：从顶点 K 到达汇点的最短路径长度称为顶点 K 的最晚发生时间，记为$v_l(K)$

# 活动的最早发生时间$e(K)$ 和最晚发生时间$l(K)$

• 活动的最早发生时间：从源点到达活动 K 的最短路径长度称为活动 K 的最早发生时间，记为$e(K)$
• 活动的最晚发生时间：从活动 K 到达汇点的最短路径长度称为活动 K 的最晚发生时间，记为$l(K)$

# 活动的时间余量$d(K)$

• 活动的时间余量：活动 K 的最晚发生时间与最早发生时间之差称为活动 K 的时间余量，记为$d(K)$
• $d(K)=l(K)-e(K)$

# 关键路径的求法

分别求出每个活动的最早发生时间和最晚发生时间，若$d(K)=0$，则该活动为关键活动

# 各种图算法的复杂度

# 查找

# 查找的基本概念

• 静态查找表是只作查找操作的查找表，主要操作有查询某个 “特定的” 数据元素是否在查找表中，检索某个 “特定的” 数据元素及其属性
• 动态查找表是在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素

# 顺序查找

• $ASL_{成功}=\sum\limits_{i=0}^{n-1}p_ic_i=\frac{1}{n}\sum\limits_{i=0}^{n-1}(i+1)=\frac{1}{n}\times\frac{n(n+1)}{2}=\frac{n+1}{2}$
• $ASL_{不成功}=\sum\limits_{i=0}^{n-1}q_in=n$
• $ASL=ASL_{成功}+ASL_{不成功}\ \ \ \ (p+q=1)$

# 折半查找

• $ASL_{成功}=\sum\limits_{i=0}^{n-1}p_i\times level(k_i)$
• $ASL_{不成功}=\sum\limits_{i=-1}^{n-1}q_i\times (level(u_i)-1)$
• 满二叉树：$ASL_{成功}=\sum\limits_{i=0}^{n-1}p_ic_i=\frac{1}{n}\sum\limits_{j=1}^h2^{j-1}\times j=\frac{n+1}{n}\log_2(n+1)\approx\log_2(n+1)-1$

# 索引存储结构和分块查找

# 过程

• 查找索引表（有序）：可以顺序查找块，也可以二分查找块。
• 查找数据块（无序）：只能顺序查找块中元素。

# 性能（若有 n 个元素，每块中有 s 个元素（块数$b=\lceil n/s \rceil$））

• 折半：$ASL_{blk}=ASL_{bn}+ASL_{sq}=\log_2(b+1)-1+\frac{s+1}{2}\approx \log_2(\frac{n}{s}+1)+\frac{s}{2}$
• 顺序：$ASL^`_{blk}=ASL_{bn}+ASL_{sq}=\frac{b+1}{2}+\frac{s+1}{2}=\frac{1}{2}(\frac{n}{s}+s)+1$

# 二叉排序树

• 查找序列（$k_1，k_2，…，k_n$）的查找树画法是，每一层只有一个结点，首先 k1 为根结点，再依次画出其他结点，若$k_{i+1}<k_i$，则$k_{i+1}$ 的结点作为$k_i$ 结点的左孩子，否则作为右孩子

# 哈希表

• 对于两个不同的关键字$k_i$ 和$k_j$（$i≠j$）出现$h(k_i)=h(k_j)$，这种现象称为哈希冲突，同义词冲突

# 构造方法

• 直接定址法 $h(k)=k+c$
• 除留余数法 $h(k)=k\%p$
• 数字分析法

# 哈希冲突解决方法

• 装填因子 α 是指哈希表中已存入的元素数 n 与哈希地址空间大小 m 的比值，即$α=\frac{n}{m}$

# 开放定址法

• 线性探测法$d_0=h(k),\ d_i=(d_{i-1}+1)\% m \ \ \ \ (1≤i≤m-1)$
• 平方探测法$d_0=h(k),\ d_i=(d_0±i^2)\% m\ \ \ \ (1≤i≤m-1)$

# 拉链法

# 排序

# 希尔排序（不稳定）

• d=n/2
• 将排序序列分为 d 个组，在各组内进行直接插入排序
• 递减 d=d/2，重复② ，直到 d=0 为止

# 快速排序（不稳定）

• 每趟使表的第 1 个元素放入适当位置（归位），将表一分为二，对子表按递归方式继续这种划分，直至划分的子表长为 0 或 1（递归出口）

# 堆排序（不稳定）

• 大根堆：对应的完全二叉树中，任意一个结点的关键字都大于或等于它的孩子结点的关键字
• 最小关键字的元素一定是某个叶子结点
• 堆排序的关键是构造堆，这里采用筛选算法建堆
• 自顶向下筛选：从根结点 R [low] 开始向下依次查找较大的孩子结点
• 所有筛选的时间复杂度为$O(\log_2n)$

# 自底向上的二路归并排序

# 平衡归并

• 有清晰的趟数（同一趟产生的归并段优先归并）
• 归并树高度$h=\lfloor \log_2n\rfloor+1$
• 归并的趟数$h-1$