常用数据结构模板

并查集

时间复杂度O(1)

朴素并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int p[N]; //存储每个点的祖宗节点

// 返回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;

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

维护集合中点的数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
int p[N], size[N];

// 返回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);

数组实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// tt表示栈顶
int stk[N], tt = 0;

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

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

// 栈顶的值
stk[tt];

// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)

数组实现队列

普通队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

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

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

// 队头的值
q[hh];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)

循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)

单调队列

时间复杂度O(n)

1
2
3
4
5
6
7
8
找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;  //保持队列单调
    q[ ++ tt] = i;
}

单调栈

时间复杂度O(n)

1
2
3
4
5
6
7
找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx从1开始对应第几个插入的数
int h = -1, e[N], ne[N], idx = 1;   

//头节点后面加
void add_to_head(int x)  
{
    e[idx] = x, ne[idx] = h, h = idx ++ ;
}

//第 k 个插入的数后面插入一个数 x
void add(int k, int x)  
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}

//删除第 k 个插入的数后面的数
void remove(int k)   
{
    ne[k] = ne[ne[k]];
}

双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

堆

时间复杂度O(logn)
模拟堆

  1. I x 插入一个数x
  2. PM 输出当前集合最小值
  3. DM 删除当前集合最小值
  4. D k 删除第k个插入的数
  5. C k x 修改第k个插入的数，将其变为x
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    #include <iostream>
    #include <algorithm>

    using namespace std;

    const int N = 100010;

    char op[4];
    int n, k, x, cnt, h[N], ph[N], hp[N], m;  //m:第几个插入  ph:p->h p表示第几个插入 hp:h->p
    //ph[i]:第i个插入的数在h中的下标是ph[i]   hp[i]:在h中下标是i的数是第hp[i]个插入的数

    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 up(int u)
    {
        while (u / 2 && h[u / 2] > h[u])
        {
            heap_swap(u / 2, u);
            u /= 2;
        }
    }

    void down(int u)
    {
        int t = u;
        if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
        if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
        if (u != t)
        {
            heap_swap(t, u);
            down(t);
        }
    }

    int main()
    {
        cin >> n;
        while (n -- )
        {
            scanf("%s", op);
            if (op[0] == 'I')
            {
                scanf("%d", &x);
                cnt ++ , m ++ ;
                h[cnt] = x, hp[cnt] = m, ph[m] = cnt;
                up(cnt);
            }
            else if (op[0] == 'P') printf("%d\n", h[1]);
            else if (op[0] == 'C')
            {
                scanf("%d%d", &k, &x);
                k = ph[k];
                h[k] = x;
                up(k), down(k);
            }
            else if (op[1] == 'M')
            {
                heap_swap(1, cnt);
                cnt -- ;
                down(1);
            }
            else
            {
                scanf("%d", &k);
                k = ph[k];
                heap_swap(k, cnt);
                cnt -- ;
                up(k), down(k);
            }
        }

        return 0;
    }

一般哈希

时间复杂度O(1)

拉链法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}

开放寻址法

1
2
3
4
5
6
7
8
9
10
11
12
13
int h[N];

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)
    {
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}