常用代码模板2——数据结构 - AcWing

笔试用数组模拟而不是结构体

使用结构体指针，new Node() 非常慢，创建10万个节点就超时了，做笔试题不会用这种方式（优化是提前初始化好数组，但这样跟数组模拟没区别了，而且代码量很长）

单链表（数组）

使用两个数组，e存储val，ne存储next。空节点next用-1表示

826 ?

826. 单链表 - AcWing题库

第1个插入的点下标为0，第5个插入点下标为4，第k个插入点下标为k-1；

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

// head指向头结点，e[i]表示节点值，ne[i]表示节点next
// idx指向可用空间（当前可以用的最新点下标）
// 算法题不用考虑浪费的空间
int head, e[N], ne[N], idx;

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

// x 插到头结点后面
void add_to_head(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

// x 插到下标k的点后面
void add(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

// 将下标 k 后面点删掉
void remove(int k) {
    // if (ne[k] == -1) return; 题目保证合法不考虑边界情况
    ne[k] = ne[ne[k]];
}

int main() {
    int m;
    cin >> m;
    init();
    while (m--) {
        char c;
        int k, x;
        cin >> c;
        if (c == 'H') {
            cin >> x;
            add_to_head(x);
        } else if (c == 'D') {
            cin >> k;
            if (!k)
                head = ne[head];  // 特判删除头结点(链表第一个有效元素)
            else
                remove(k - 1);
        } else if (c == 'I') {
            cin >> k >> x;
            add(k - 1, x);
        }
    }
    for (int i = head; i != -1; i = ne[i]) {
        cout << e[i] << " ";
    }

    return 0;
}

邻接表

本质是一堆单链表，head[i]->x->x->-1 意思第i个点的邻边存起来了

最大用途：存储图、树 （内容在第三章）

双链表（数组）

用于优化某些题，每个节点有两个指针，一个指向前，一个指向后

需要3个数组，l 数组表示before，r 数组表示next，e 数组表示val，idx指向可用空间

下标0为head，指向头结点（左端点）；下标1为tail，指向尾结点（右端点）

827 ?

827. 双链表 - AcWing题库

因为提前用掉了数组中的两个，所以第k个插入元素下标是 k - 1 + 2

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int e[N], l[N], r[N], idx;

void init() {
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

// 在下标k点的右边插入x（可以转化成左边）
void add(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    r[k] = idx;
    l[r[idx]] = idx;
    idx++;
}

// 删除下标k的点
void remove(int k) {
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main() {
    int m;
    cin >> m;
    init();
    while (m--) {
        string s;
        int k, x;
        cin >> s;
        if (s == "L") {
            cin >> x;
            add(0, x);
        } else if (s == "R") {
            cin >> x;
            add(l[1], x);
        } else if (s == "D") {
            cin >> k;
            remove(k - 1 + 2);
        } else if (s == "IL") {
            cin >> k >> x;
            add(l[k - 1 + 2], x);
        } else if (s == "IR") {
            cin >> k >> x;
            add(k - 1 + 2, x);
        }
    }
    for (int i = r[0]; i != 1; i = r[i]) {
        cout << e[i] << " ";
    }
    return 0;
}

栈

830

828. 模拟栈 - AcWing题库

先进后出。数据存储区间为[1,M]，tt为栈顶指针

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int stk[N], tt;

int main() {
    int m;
    cin >> m;
    while (m--) {
        string s;
        int x;
        cin >> s;
        if (s == "push") {
            cin >> x;
            stk[++tt] = x;
        } else if (s == "pop") {
            tt--;
        } else if (s == "empty") {
            if (tt > 0)
                puts("NO");
            else
                puts("YES");
        } else if (s == "query") {
            cout << stk[tt] << endl;
        }
    }
    return 0;
}

3302 ??数组

3302. 表达式求值 - AcWing题库

中缀转后缀的重要规则（强行记忆）。转换与计算可以同步进行（各自需要一个栈）

• 当前运算符优先级<=栈顶元素，则栈顶元素依次输出直到不满足条件，并当前符号进栈
• 遇到右括号，则栈顶元素依次输出直到左括号
• 遍历完成后弹出栈内剩余运算符

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 1e5 + 10;

int op[N], num[N], opt = -1, numt = -1;

unordered_map<char, int> priority;

// 计算后缀表达式
void e