数据结构模拟

此篇是对数据结构模拟的代码总结，主要记录链表、栈、队列、单调栈、单调队列、并查集、堆、哈希表的模拟。

链表

单链表

单链表可以用 forward_list，但没必要，单链表能实现的东西双链表都可以，不需要对链表内部指针修改都可以用双链表。

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;

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

void init(){
    head = -1;
    idx = 0;
}

void insert_head(int x){ // 插入到头
    e[idx] = x, ne[idx] = head, head = idx ++;
}

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

void remove(int k){
    ne[k] = ne[ne[k]]; 
}

int main(){
    int n; cin >> n;
    
    init();
    while (n -- ){
        char a; cin >> a;
        if (a == 'H'){
            int x; cin >> x;
            insert_head(x);
        } else if (a == 'D'){
            int k; cin >> k;
            if (!k) head = ne[head];
            else remove(k - 1);
        } else {
            int k, x; cin >> k >> x;
            insert(k - 1, x); 
        }
    }
    
    for (int i = head; i != -1; i = ne[i]){
        cout << e[i] << ' ';
    }
    cout << endl;
}

双链表

双链表可以用 list 来实现。

栈

栈可以的用 vector 来实现。

单调栈

单调栈的意思是栈内元素递增或递减。 此图来源acwing的兄弟

队列

队列可以用 queue 来实现。

单调队列

并查集

并查集是一种集合数据结构，每个结点刚开始都是一个结点，指向本身，为一个集合。他有两个操作，把两个集合合并为一个集合，查询这个两个数是否在一个集合内。

#include <iostream>
using namespace std;
const int N = 100010;

int p[N];

int find(int x)
{
    // 看 x 是否是头节点，否则让 x 指向头节点。
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    while (m -- )
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'M') { // 将 a 的头节点，指向 b 的头节点。
            p[find(a)] = find(b);
        } else
        {
            // 查询 a 和 b 是否在同一个集合。
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

堆

堆模拟，简单一些，写个堆排序了。

堆是一个完美二叉树，父节点是左右子树的最小（大）值，它可以动态的维护一个集合的最值。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int h[N], sz;

void down(int u) {
    int t = u, l = u * 2, r = u * 2 + 1;
    if (l <= sz && h[t] > h[l]) t = l;
    if (r <= sz && h[t] > h[r]) t = r;
    if (t != u) {
        swap(h[u], h[t]);
        down(t);
    }
}

int main() {
    int n, m; cin >> n >> m;
    sz = n;
    for (int i = 1; i <= n; i ++) {
        cin >> h[i];
    }
    // n / 2 是最后一个结点的父节点，它也是第一个有叶子的结点，从它这里开始 down
    for (int i = n / 2;i; i --) down(i);

    while (m --) {
        cout << h[1] << " ";
        h[1] = h[sz];
        sz --;
        down(1);
    }
    cout << endl;
    return 0;
}

哈希表

哈希表模拟有两种办法，开放地址寻址法和拉链法，两种方法都用的很多，所以都模拟一下。

开放地址寻址法。

#include <bits/stdc++.h>
using namespace std;

const int N = 200003, null = 0x3f3f3f3f;
int h[N];

void insert(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null) {
        k ++;
    }
    h[k] = x;
}

bool find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null) {
        if (h[k] == x) {
            return true;
        }
        k ++;
    }
    return false;
}

int main() {
    memset(h, 0x3f, sizeof h);
    int t; cin >> t;
    while (t --) {
        char a; cin >> a;
        int b; cin >> b;
        if (a == 'I') {
            insert(b);
        } else {
            if (find(b)) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }
}

拉链法

#include <bits/stdc++.h>
using namespace std;

const int N = 100003;
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;
}

int main() {
    memset(h, -1, sizeof h);
    int t; cin >> t;
    while (t --) {
        char a; cin >> a;
        int b; cin >> b;
        if (a == 'I') {
            insert(b);
        } else {
            if (find(b)) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }
}