数据结构

BraumAce2024年7月1日约 4090 字大约 14 分钟

数据结构

1. 数组模拟链表

1.1 单链表

也称静态链表（邻接表： $n$ 个链表，主要应用：存储图和树）单链表只能存储当前节点的值和指向下一节点的指针，无法存储上一节点

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1; //-1表示不存在，
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a,;
    ne[idx] = head,;
    head = idx ++ ;
}

// 将一个新的节点x插入下标是k的后面
void add(int k, int x){
    e[idx] = x;      // 1.先存值
    ne[idx] = ne[k]; // 2.新节点的下一节点指向 k 指向的下一节点
    ne[k] = idx;     // 3.k指向的下一节点指向新节点
    idx++;           // 4.index指向下一个指针
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

// 将下标是k的点后面的点删掉
void remove(int x){
    // 直接将其指向下下个节点，在算法竞赛中一般不需要考虑删除的那个节点该如何处理
    ne[k] = ne[ne[k]]; 
}

1.2 双链表

（主要用来优化某些问题）有两个指针，一个指向前，一个指向后。

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    // 0是左端点，1是右端点
    r[0] = 1;
    l[1] = 0;
    idx = 2; // 0和1都被占用了，所以idx从2开始
}

// 在节点k的右边插入一个数x
// 如果要插在k的左边，就把k改为l[k]
void insert(int k, int x)
{
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx++;
}

// 删除第k个点
void remove(int k)
{
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

2. 栈

先进后出

2.1 普通栈

// tt表示栈顶
int stk[N]; //栈数组从0开始
int tt = 0;

// 向栈顶插入一个数
stk[++tt] = x;

// 从栈顶弹出一个数
tt--;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0) not empty
{

}
else empty

2.1 单调栈

给定一个序列，找到每一个数左边离他最近的比它小的数。

性质：如果 $a_x \geq a_y, x < y$ ，那么 $a_x$ 永远不会被输出，可以删掉。比如 $a_3 \geq a_5$ ，那么 $a_3$ 永远不会被输出。

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i++)
{
    while (tt && check(stk[tt], i)) tt--;
    stk[++tt] = i;
}

3. 队列

先进先出，后进后出

3.1 普通队列

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[++tt] = x;

// 从队头弹出一个数
hh++;

// 队头的值
q[hh]; //同理队尾 q[tt]

// 判断队列是否为空
if (hh <= tt) not empty
{

}
else empty

3.2 单调队列

求滑动窗口里的最大值和最小值。用单调队列来优化。

步骤：

判断队头是否已经滑出窗口
判断当前元素与队尾元素是否满足单调性问题
若满足条件，弹出队尾元素，将当前元素加入队尾
如果窗口满足条件，则输出结果

【注意】队列里面存的是下标

常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i++)
{
    //判断队头是否滑出窗口
    if (hh <= tt && check_out(q[hh])) hh++; 
    
    //判断当前元素与队尾元素是否满足单调性问题
    while (hh <= tt && check(q[tt], i)) tt--;
    
    q[++tt] = i;    //将当前元素加入到队尾
    
    //如果满足条件再输出结果
    if()
}

4. KMP

关于为什么求 $next$ 数组和匹配的操作类似：
因为本质是一样的：对于 $S$ 串每一个特定的下标 $i$ ，在满足 s[i-j+1，i]=p[0，j] 的前提下，我们需要找出 $j$ 的最大值。
唯一不同的在于，求 $next$ 数组时，我们关心对于每个不同的下标 $i, j$ 能走多远；匹配时，我们只关心 $j$ 是否走到末尾.

非常有意思的说法是：
求 next 数组时，对于每个 i："j走到哪了呀？我用数组记录一下你的位置"
匹配时，对于每个 i："到终点和我说声，匹配完我输出一下，没事别叫我。"

#include <iostream>
using namespace std;
const int N = 100010, M = 10010; // N为模式串长度，M匹配串长度

int n, m;
int ne[M];        // next[]数组，避免和头文件next冲突
char s[N], p[M];  // s为模式串， p为匹配串

int main()
{
    cin >> n >> s+1;
    cin >> m >> p+1;  //下标从1开始

    // 求next[]数组
    for (int i = 2, j = 0; i <= m; i++)
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        
        if (p[i] == p[j + 1]) j++;
        
        ne[i] = j;
    }
    
    // 匹配操作
    for (int i = 1, j = 0; i <= n; i++)
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        
        if (s[i] == p[j + 1]) j++;
        
        if (j == m)  // 满足匹配条件，打印开头下标, 从0开始
        {
            // 匹配完成后的具体操作
            // 如：输出以0开始的匹配子串的首字母下标
            // printf("%d ", i - m); (若从1开始，加1)
            j = ne[j];            // 再次继续匹配
        }
    }

    return 0;
}

5. Trie树

Trie 树又称字典树、单词查找树。是一种能够高效存储和查找字符串集合的数据结构。

存储形式如下：

// son[][]存储树中每个节点的子节点，因为存的都是英文字母，最多有26个
int son[N][26];  
int cnt[N];  // cnt[]存储以每个节点结尾的单词数量
int idx;     // 存储当前用到的下标，0号点既是根节点，又是空节点

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    
    // 字符串以'0'结尾，所以可以用str[i]结束
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

6. 并查集

6.1 朴素并查集

    int p[N];     // 存储每个点的祖宗节点
    int rank[N];  // 树的高度

    // 初始化，假定节点编号是1~n
    void init(int n)
    {
        for (int i = 1; i <= n; i++){
            p[i] = i;
            rank[i] = 0;
        }
    }

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 合并x和y所在的两个集合：
    void union(int x, int y)
    {
        int px = find(x), py = find(y);
        if (rank[px] < rank[py]){
            p[px] = py;
            rank[py] += rank[px];
        }
        else {
            p[py] = px;
            rank[px] += rank[py];
        }
    }

6.2 维护size的并查集

    int p[N], size[N];
    // p[]存储每个点的祖宗节点
    // size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

6.3 维护到祖宗节点距离的并查集

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

7. 堆

1、作用：维护一个数组集合

2、堆是一棵（完全）二叉树，长得非常平衡，除最后一层节点，所有节点均不为空，最后一层节点从左向右排列，根节点小于等于左右两个子节点，即小根堆。

3、存储：用一个一维数组存储树，下标从 $1$ 开始。其中元素 $x$ 的左儿子为 $2x$ ， $x$ 的右儿子为 $2x + 1$ .

4、5个基本操作

heap 表示堆，size 表示大小

1. 插入一个数 heap[++size] = x; up(size);
2. 求集合当中的最小值 heap[1];
3. 删除最小值 heap[1] = heap[size]; size--; down(1);
4. 删除任意一个元素 heap[k] = heap[size]; size--; down(k); up(k); //down和up只会执行其中一个
5. 修改任意一个元素 heap[K] = x; down(k); up(k);

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)  // 跟两个儿子比较大小
{
    // t表示该元素与它的左、右儿子相比最小的元素，初始化为它自身
    int t = u;
    
    // 若左二子小于它，则最小的数为左二子
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    
    // 若右儿子小于它，则最小的数为右儿子
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    
    // 如果它本身不是最小的数，则往下沉，继续down()操作
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)  //只需要跟一个父亲比较大小就行
{
    // 如果比父节点大，就交换位置，上浮
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1; //x /= 2
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

8. 哈希表

8.1 拉链法

int h[N], e[N], ne[N], idx;

// 向哈希表中插入一个数
void insert(int x)
{
    //哈希函数离散化
    int k = (x % N + N) % N; 
    
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++ ;
}

// 在哈希表中查询某个数是否存在
bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x)
            return true;
    
    return false;
}

8.2 开放寻址法

int h[N];

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
    // 哈希函数
    int k = (x % N + N) % N;
    
    while (h[k] != null && h[k] != x)
    {
        k++;
        
        // 如果到了末尾，那么再从头开始查找
        if (k == N) k = 0;
    }
    
    return k;
}

8.3 字符串哈希

核心思想：将字符串看成 P 进制数，P 的经验值是 131 或 13331，取这两个值的冲突概率低
小技巧：取模的数用 2^64，这样直接用 unsigned long long 存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;

ULL h[N]; // h[k]存储字符串前k个字母的哈希值
ULL p[N]; // p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

9. C++ STL简介

vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string, 字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列，本身就是有序的，默认按 key 排序
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数 没找到则返回end()
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
            (3) 例如：s.erase(unique(s.begin(), d.end()), s,end()) 将一个容器中重复的元素删除，对字符串也适用
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        用 first 和 second 查找每个键值对的元素
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 都可以是‘哈希表’
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

10. 常用库函数

1. reverse 翻转

翻转一个 vector ：

reverse(a.begin(), a.end());

翻转一个数组，元素存放在下标 1 ~ n ：

reverse(a + 1, a + n + 1);

2. unique 去重

返回去重（只去掉相邻的相同元素）之后的尾迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。

把一个 vector 去重：

int m = unique(a.begin(), a.end()) – a.begin();

把一个数组去重，元素存放在下标 1 ~ n：

int m = unique(a + 1, a + n + 1) – (a + 1);

3. random_shuffle 随机打乱：
用法与 reverse 相同。

4. sort 排序：

对两个迭代器（或指针）指定的部分进行快速排序。可以在第三个参数传入定义大小比较的函数，或者重载 “小于号” 运算符。

把一个 int 数组（元素存放在下标 1 ~ n ）从大到小排序，传入比较函数：

int a[MAX_SIZE];
bool cmp(int a, int b)
{
    return a > b;
}
sort(a + 1, a + n + 1, cmp);

从大到小排序需要加入第三个参数：

sort(a.begin(), a.end(), greater<int>());

对自定义的结构体 vector 排序，重载 "小于号" 运算符：

struct node
{
    int id, x, y;
};

vector<node> a;

bool operator < (const node &a, const node &b)
{
        return a.x < b.x || a.x == b.x && a.y < b.y;
}

sort(a.begin(), a.end());

5. lower_bound / upper_bound 二分：

lower_bound 的第三个参数传入一个元素 x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于 x 的元素的位置的迭代器（指针）。

upper_bound 的用法和 lower_bound 大致相同，唯一的区别是查找第一个大于 x 的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。

在有序 int 数组（元素存放在下标 1 ~ n ）中查找大于等于 x 的最小整数的下标：

int i = lower_bound(a + 1, a + 1 + n, x) - a;

在有序 vector<int> 中查找小于等于 x 的最大整数（假设一定存在）：

int y = *--upper_bound(a.begin(), a.end(), x);

找不到则返回最后一个元素的下标+1，是越界的。