绪论

数据结构的定义

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

算法及其描述

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

算法时间性能分析

  • 求和定理
  • 求积定理

算法存储空间分析

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

线性表

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

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

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

L=(α1,α2,...,αi,αi+1,...,αn)L=(\alpha_1,\alpha_2,...,\alpha_i,\alpha_{i+1},...,\alpha_n)
  • αi\alpha_i 是线性表中的 “第 ii 个” 元素线性表中的位序。
  • α1\alpha_1 是表头元素，αn\alpha_n 是表尾元素。
  • 出第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

注意：位序是从 11 开始的，而数组下标是从 00 开始的。

解释

线性表就像一队排队的人。

  • 每个人：都是一个数据元素，它们的数据类型相同。
  • 队伍：是有顺序的（有序）。
  • 队伍长度：队伍里的人数，可以是0（空队）。

关键点

  • 数据类型相同：队伍里的人必须是同一种类型，比如都是学生。
  • 有序：每个人都有一个位置，不能随意乱站。
  • 序列：强调数据元素之间的顺序关系。

术语

  • 表长：队伍的总人数。
  • 空表：队伍里没有人的情况。
  • 位序：队伍中每个人的编号，从1开始。
  • 表头元素：队伍中的第一个人。
  • 表尾元素：队伍中的最后一个人。
  • 直接前驱：排在某个人前面的人。
  • 直接后继：排在某个人后面的人。

顺序表

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

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

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

解释

顺序表就像一排排座位，用来存放有序的数据元素。
可以当成一个数组，元素在内存中是连续存放的。

题目

  • 设线性表有 nn 个元素，以下哪些操作在顺序表上实现比在链表上实现更高效？
    A. 输出第 ii 个元素
    B. 交换第 ii 个元素和第 jj 个元素
    C. 顺序输出所有元素

    答案
    !! AC 交换第 ii 个元素和第 jj 个元素，顺序表仅需要3次赋值，链表则要分别找到第 i−1i-1 和第 j−1j-1 个元素，再交换指针。!!

常用算法

逆置算法

逆置算法可以用来逆置线性表中的元素，也可以将指定范围的元素与其他元素交换。

void reverse(int a[], int low, int high)
{
    while (low < high)
    {
        swap(a[low], a[high]);
        low++;
        high--;
    }
}

博耶-摩尔多数投票

博耶-摩尔多数投票法可以用来找出线性表中出现次数超过 n2\frac{n}{2} 的元素。

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;

常用算法

O(1)的前插法

可转化为后插，设待插入节点为s，将s插入p前，仍然可以将s插到p后，交换s和p的data即可

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

O(1)的删除p

用删除p的后继节点，将p的后继节点的data赋值给p，删除p的后继节点

q = p->next;
p->data = q->data;
p->next = q->next;
delete q;

查找倒数第k个节点

先用p1指针走k步，然后p2指针和p1指针一起走，直到p1指针到达尾结点

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;
}

相同后缀

先分别遍历两个链表，得到长度差d，然后让长的链表先走d步，再一起走

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;
}

链表找中点

先用快慢指针法找到链表的中点：

  1. 快指针每次走两步，慢指针每次走一步；
  2. 当快指针到达链表末尾时，慢指针所指即为中点。
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;
}

双向链表

基本操作
插入

picture 2

s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
删除

picture 3

p->next = q->next;
q->next->prior = p;
delete q;

循环链表

顺序表和链表的比较

项目 顺序表 链表
存储方式 顺序存储/随机访问 链式存储/顺序访问
按值查找 O(n) O(n)
按位查找 O(1) O(n)
插入 O(n) O(1)
删除 O(n) O(1)

栈和队列

栈

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

共享栈

picture 1

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

队列

顺序队列

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

循环队列

picture 0

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

链队

  • 队空条件：front = rear = NULL

通常将链队设计为带有头结点的单链表

  • 入队：rear->next = s; rear = s;
  • 出队： 
    q = front->next;
front->next = q->next;
if (rear == q)
    rear = front; // 原队列出队后为空
delete q;

常用算法

基于循环链表的队列

出队元素的占用空间可重复利用，即整个队列的空间只增不减。

  • 队空条件：front == rear
  • 队满条件：front == rear->next

此处的队满条件是相对的，实际上是队列的空间不够，需要扩展了。

  • 入队 
    if (front == rear->next)
{
    // 扩展空间
    Node *p = new Node;
    p->next = front;
    rear->next = p;
    rear = p;
}
rear = rear->next;
  • 出队 
    if (front == rear)
    return;
Node *p = front;
front = front->next;
delete p;

双端队列

注意一端受限的双端队列

数组

数组的存储结构

一维数组

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

二维数组

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

对称矩阵的压缩存储

picture 4

k={i(i−1)2+j−1i≥j时(下三角+主对角线)j(j−1)2+i−1当i<j时(aij=aji)k=\begin{cases}\frac{i(i-1)}{2}+j - 1 &i≥j时(下三角+主对角线) \\ \frac{j(j-1)}{2}+i-1 &当i<j时(a_{ij}=a_{ji})\end{cases}

三角矩阵

下三角矩阵

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

k={i(i−1)2+j−1i≥j(下三角+主对角线)n(n+1)2i<j(上三角)k = \begin{cases}\frac{i(i-1)}{2}+j - 1 &i≥j (下三角+主对角线) \\ \frac{n(n+1)}{2} &i<j (上三角)\end{cases}

上三角矩阵

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

k={(i−1)(2n−i+2)2+(j−i)i≤j(上三角+主对角线)n(n+1)2i>j(下三角)k = \begin{cases}\frac{(i-1)(2n-i+2)}{2} + (j-i) &i≤j (上三角+主对角线) \\ \frac{n(n+1)}{2} &i>j (下三角)\end{cases}

三对角矩阵

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

picture 7

  • 按照行优先原则，aija_{ij}的存储位置为：
    k=2i+j−3k = 2i + j - 3
  • 已知三对角矩阵的存储位置k，求出行号i和列号j： i=⌈k+13+1⌉j=k−2i+3 \begin{align*} i &= \lceil\frac{k+1}{3} + 1\rceil \\ j &= k - 2i + 3 \end{align*}

稀疏矩阵的三元组表示

  • 行号、列号、元素值

串

KMP

KMP算法简介

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

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

next数组手算

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

  • next[1] = 0
  • next[2] = 1
  • next[n]：在不匹配的位置前画一道分界线，模式串向后退，直到分界线前能对上或完全跨过分界线为止，next[n] = j

若串的编号从0开始，next数组需要整体减1

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数组的手算方法，已经有了next数组

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的结点称为双分支结点，依次类推
  • 叶子结点：度为零的结点称为叶子结点或终端结点
  • 结点层次：树具有一种层次结构，根结点为第一层，其孩子结点为第二层，如此类推得到每个结点的层次
  • 树的高度：树中结点的最大层次称为树的高度或深度

picture 8

树的性质

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

题目

  • 在一棵度为44的树T中，若有20个度为 4 的结点，10个度为 3 的结点，1 个度为 2 的结点，10个度为 1 的结点，则T的叶节点个数为多少？

    答案

    \begin{align*} n &= 1+20n_4+10n_3+2n_2+10n_1 \\ 
    &= n_0+n_1+n_2+n_3+n_4 \\
     n_0 &= 82
    \end{align*}

二叉树的定义

  • 在含nn个结点的二叉树中，所有结点的度小于等于2，通常用n0n_0表示叶子结点个数，n1n_1表示单分支结点个数，n2n_2表示双分支结点个数

满二叉树

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

完全二叉树的特点

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

二叉树性质

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

二叉树的遍历

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

二叉树的构造

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

线索二叉树

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

线索化（手画）

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

哈夫曼树

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

哈夫曼编码

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

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

一棵树到二叉树的转换

  • 加线：在各兄弟结点之间加一连线，将其隐含的“兄－弟”关系以“双亲－右孩子”关系显示表示出来
  • 抹线：对任意结点，除了其最左子树之外，抹掉该结点与其他子树之间的“双亲－孩子”关系
  • 调整：以树的根结点作为二叉树的根结点，将树根与其最左子树之间的“双亲－孩子”关系改为“双亲－左孩子”关系，且将各结点按层次排列，形成二叉树
  1. 在兄弟结点之间加线
  2. 对每个节点，只保留他与第一个儿子的连线，而与其他孩子的连线全部抹掉
  3. 以树根为核心，顺时针旋转45度

picture 12

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

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

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

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

森林转换为二叉树

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

二叉树还原为森林

  • 抹线：抹掉二叉树根结点右链上所有结点之间的“双亲－右孩子”关系，分成若干个以右链上的结点为根结点的二叉树，设这些二叉树为bt1、bt2、…、btmbt_1、bt_2、…、bt_m
  • 转换：分别将bt1、bt2、…、btmbt_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为结点个数

图

图的基本概念

简单图与多重图

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

路径、路径长度与回路

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

简单路径和简单回路

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

连通图与强连通图

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

完全图

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

图的存储结构

picture 17

邻接矩阵

适合存储稠密图

邻接表

  • 对图中每个顶点i建立一个单链表，将顶点i的所有邻接点链起来
  • 每个单链表上添加一个表头结点（表示顶点信息）。并将所有表头结点构成一个数组，下标为i的元素表示顶点i的表头结点
特点
  • 邻接表表示不唯一
  • 对于有n个顶点和e条边的无向图，其邻接表有n个表头结点和2e个边结点；对于有n个顶点和e条边的有向图，其邻接表有n个表头结点和e个边结点
  • 用邻接表存储图时，确定任意两个顶点之间是否有边相连的时间为O(m)O(m)

十字链表

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

picture 14

picture 13

弧节点
  • tailvex：弧尾结点
  • headvex：弧头结点
  • hlink：弧头结点的下一个弧头结点
  • tlink：弧尾结点的下一个弧尾结点
  • info：弧的权值
顶点节点
  • data：顶点信息
  • firstin：指向第一个入弧结点
  • firstout：指向第一个出弧结点

邻接多重表

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

picture 15

  • 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的复杂度
存储方式 时间复杂度
邻接矩阵 O(∣V∣2)O(|V|^2)
邻接表 O(∣V∣+∣E∣)O(|V|+|E|)

深度优先遍历（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的复杂度
存储方式 时间复杂度
邻接矩阵 O(∣V∣2)O(|V|^2)
邻接表 O(∣V∣+∣E∣)O(|V|+|E|)

最小生成树

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;
            }
        }
    }
}

Prim算法的时间复杂度为O(∥V∥2)O(\|V\|^2)，适合稠密图

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;
        }
    }
}

Kruskal算法的时间复杂度为O(∥E∥log⁡∥E∥)O(\|E\| \log \|E\|)，适合稀疏图

最短路径

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});
                }
            }
        }
    }
}

Dijkstra算法的时间复杂度为O(∥V∥2)O(\|V\|^2)，适合稠密图
不适用于负权边的图

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]);
            }
        }
    }
}

Floyd-Warshall算法的时间复杂度为O(∥V∥3)O(\|V\|^3)，适合稠密图
不适用于负权回路的图，但是负权边是可以的

总结

picture 18

DAG描述表达式

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

手算方法：

  1. 把各个操作数不重复的排成一行
  2. 标出每个运算符的生效顺序（先后顺序有出入无所谓）
  3. 按顺序加入运算符，注意分层
  4. 从底向上逐层检查同层运算符是否可以合并

拓扑排序

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

手算方法：

  1. 从AOV网中找出入度为0的顶点，输出该顶点
  2. 删除该顶点和与之相连的所有边
  3. 重复步骤1和2，直到所有顶点都被输出

拓扑排序邻接表的时间复杂度为O(∥V∥+∥E∥)O(\|V\|+\|E\|)
拓扑排序邻接矩阵的时间复杂度为O(∥V∥2)O(\|V\|^2)

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

手算方法：

  1. 从AOV网中找出出度为0的顶点，输出该顶点
  2. 删除该顶点和与之相连的所有边
  3. 重复步骤1和2，直到所有顶点都被输出

关键路径

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

最早发生时间ve(K)v_e(K)

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

手算方法：
按照拓扑序列进行遍历

  1. ve(0)=0v_e(0)=0
  2. 对每个顶点K，ve(K)=max⁡ive(i)+w(i,K)v_e(K)=\max\limits_{i}v_e(i)+w(i,K)

最晚发生时间vl(K)v_l(K)

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

手算方法：
按照逆拓扑序列进行遍历

  1. vl(n)=ve(n)v_l(n)=v_e(n)
  2. 对每个顶点K，vl(K)=min⁡ivl(i)−w(K,i)v_l(K)=\min\limits_{i}v_l(i)-w(K,i)

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

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

手算方法：

  1. 若有<vk,vj><v_k,v_j>表示活动aia_i，则e(i)=ve(k)e(i)=v_e(k)
  2. 若有<vk,vj><v_k,v_j>表示活动aia_i，则l(i)=vl(j)−w(k,j)l(i)=v_l(j)-w(k,j)

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

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

关键路径的求法

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

  • 关键路径上的所有活动都是关键活动，缩短关键活动的时间可以缩短整个项目的完成时间，但是过度缩短关键活动的时间会导致其变成非关键活动
  • 网中的关键路径不止一条，只提高一条关键活动的速度，并不能缩短整个项目的完成时间

各种图算法的复杂度

picture 19

查找

查找的基本概念

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

顺序查找

  • ASL成功=∑i=0n−1pici=1n∑i=0n−1(i+1)=1n×n(n+1)2=n+12ASL_{成功}=\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不成功=∑i=0n−1qin=nASL_{不成功}=\sum\limits_{i=0}^{n-1}q_in=n
  • ASL=ASL成功+ASL不成功    (p+q=1)ASL=ASL_{成功}+ASL_{不成功}\ \ \ \ (p+q=1)

折半查找

  • ASL成功=∑i=0n−1pi×level(ki)ASL_{成功}=\sum\limits_{i=0}^{n-1}p_i\times level(k_i)
  • ASL不成功=∑i=−1n−1qi×(level(ui)−1)ASL_{不成功}=\sum\limits_{i=-1}^{n-1}q_i\times (level(u_i)-1)
  • 满二叉树：ASL成功=∑i=0n−1pici=1n∑j=1h2j−1×j=n+1nlog⁡2(n+1)≈log⁡2(n+1)−1ASL_{成功}=\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=⌈n/s⌉b=\lceil n/s \rceil））

  • 折半：ASLblk=ASLbn+ASLsq=log⁡2(b+1)−1+s+12≈log⁡2(ns+1)+s2ASL_{blk}=ASL_{bn}+ASL_{sq}=\log_2(b+1)-1+\frac{s+1}{2}\approx \log_2(\frac{n}{s}+1)+\frac{s}{2}
  • 顺序：ASLblk‘=ASLbn+ASLsq=b+12+s+12=12(ns+s)+1ASL^`_{blk}=ASL_{bn}+ASL_{sq}=\frac{b+1}{2}+\frac{s+1}{2}=\frac{1}{2}(\frac{n}{s}+s)+1

二叉排序树

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

哈希表

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

构造方法

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

哈希冲突解决方法

  • 装填因子α是指哈希表中已存入的元素数n与哈希地址空间大小m的比值，即α=nmα=\frac{n}{m}
开放定址法
  • 线性探测法d0=h(k), di=(di−1+1)%m    (1≤i≤m−1)d_0=h(k),\ d_i=(d_{i-1}+1)\% m \ \ \ \ (1≤i≤m-1)
  • 平方探测法d0=h(k), di=(d0±i2)%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)O(\log_2n)

自底向上的二路归并排序

平衡归并

  • 有清晰的趟数（同一趟产生的归并段优先归并）
  • 归并树高度h=⌊log⁡2n⌋+1h=\lfloor \log_2n\rfloor+1
  • 归并的趟数h−1h-1