数据结构汇总(竞赛+笔试)(有待补全)

1.链表


1.1 单链表
(1) 笔试写法
 

struct Node
{
    int val;
    Node *next;
    Node(int _val) : val(_val), next(NULL){}
} *head;

// p 后插入新节点
void insert(Node *p , int x)
{
    Node *q = new Node(x);
    q->next = p->next;
    p->next = q;
}

// 删除节点p -> next
void remove(Node *p)
{
    auto q = p->next;
    p->next = q->next;
    delete(q);
}

//查找x节点
Node *find(int x)
{
    for(auto p = head ; p != NULL ; p = p->next)
    {
        if(p->val == x) return p;
    }
    return NULL;
}

//修改
void modify(int x , int y)
{
    Node *p = find(x);
    if(p) p->val = y;
}

(2)机试写法(链式前向星)
 

// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点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)
{
    ne[k] = ne[ne[k]];
}

1.2 双链表

1.3 循环链表

1.4 十字链表


栈与队列



3.3平衡树
(1) Splay

#include <bits/stdc++.h>

using namespace std;
const int N = 500010 , INF = 1e9;

int n , m;
struct Node
{
    int s[2] , p , v; // 左右子树下标、父节点下标、值
    int rev , same;   // 翻转和改变值的懒标记
    int size , sum , ms , ls , rs; // 子树大小、子树和、最大子段和、最大前缀和、最大后缀和
    
    void init(int _v , int _p)          
    {
        s[0] = s[1] = 0 , p = _p , v = _v;      // 0表示空
        rev = same = 0;
        size = 1 , sum = ms = v;
        ls = rs = max(0 , v);
    }
}tr[N];

int root , nodes[N] , idx;   // 根、下标分配站(因为数量很大,所以要循环利用删掉的点的下标)、分配站的idx
int w[N];                   // 存值的地方

void pushup(int x)
{
    auto &u = tr[x] , &l = tr[u.s[0]] , r = tr[u.s[1]];
    u.size = l.size + r.size + 1;
    u.sum = l.sum + r.sum + u.v;
    u.ls = max(l.ls , l.sum + u.v + r.ls);     // 最大前缀和是 左子树最大前缀和 和 左子树全部加上该节点加上右子树最大前缀和 的最大值
    u.rs = max(r.rs , r.sum + u.v + l.rs);     // 同理
    u.ms = max(max(l.ms , r.ms) , l.rs + u.v + r.ls );  
    // 最大子段和是 左子树的最大子段和 和 右子树的最大子段和 和 左子树最大后缀和加上该节点加上右子树的最大前缀和(因为子段和得连续) 中的最大值
}

void pushdown(int x)
{
    auto &u = tr[x] , &l = tr[u.s[0]] , &r = tr[u.s[1]];
    if(u.same)
    {
        u.same = u.rev = 0; // 懒标记消除
        if (u.s[0]) l.same = 1, l.v = u.v, l.sum = l.v * l.size;        // 懒标记下传
        if (u.s[1]) r.same = 1, r.v = u.v, r.sum = r.v * r.size;
        if (u.v > 0)
        {
            if (u.s[0]) l.ms = l.ls = l.rs = l.sum;
            if (u.s[1]) r.ms = r.ls = r.rs = r.sum;
        }
        else
        {
            if (u.s[0]) l.ms = l.v, l.ls = l.rs = 0;
            if (u.s[1]) r.ms = r.v, r.ls = r.rs = 0;
        }
    }
    else if(u.rev) // else 的原因是如果same了就没有必要旋转了,因为旋不旋转都一样
    {
        u.rev = 0, l.rev ^= 1, r.rev ^= 1;                   // 懒标记下传
        swap(l.ls, l.rs), swap(r.ls, r.rs);
        swap(l.s[0], l.s[1]), swap(r.s[0], r.s[1]);
    }
}

void rotate(int x)                      // 左旋右旋合并函数
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x, int k)                // splay 操作 将x转到k的右子树上
{
    while (tr[x].p != k)
    {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if (!k) root = x;
}


int get_k(int k)                            // 找到第k排名的下标
{
    int u = root;
    while (u)
    {
        pushdown(u);
        if (tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
        else if (tr[tr[u].s[0]].size + 1 == k) return u;
        else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
    }
}

int build(int l, int r, int p)      // 建树
{
    int mid = l + r >> 1;
    int u = nodes[idx -- ];
    tr[u].init(w[mid], p);
    if (l < mid) tr[u].s[0] = build(l, mid - 1, u);
    if (mid < r) tr[u].s[1] = build(mid + 1, r, u);
    pushup(u);
    return u;
}

void del(int u)                             // 递归删树
{
    if(tr[u].s[0]) del(tr[u].s[0]);         
    if(tr[u].s[1]) del(tr[u].s[1]);
    nodes[ ++ idx] = u;                     // 空间回收利用
}

int main()
{
    for(int i = 1 ; i < N ; i ++) nodes[++ idx] = i;    // 给分配站一些初始空间
    scanf("%d%d", &n, &m);
    tr[0].ms = w[0] = w[n + 1] = -INF; // 空和哨兵(为了方便删除结点)
    for(int i = 1 ; i <= n ; i ++) scanf("%d", &w[i]);
    root = build(0 , n + 1 , 0);                        // 别忘了建树时把哨兵带上
    
    char op[20]; // 读指令
    while (m -- )
    {
        scanf("%s", op);
        if(!strcmp(op , "INSERT"))
        {
            int posi , tot;
            scanf("%d%d", &posi, &tot);
            for(int i = 0 ; i < tot ; i ++) scanf("%d", &w[i]);
            int l = get_k(posi + 1) , r = get_k(posi + 2); // +1 是因为有哨兵 , +2 是因为要插到两个之间
            splay(l , 0) , splay(r , l); // 现将l转到0的右子树,再将r转到l的右子树,这样r的左子树就是在l到r之间了
            int u = build(0 , tot - 1 , r);
            tr[r].s[0] = u;                 //插入到r的左子树
            pushup(r) , pushup(l);          // 因为r是l的子树,所以先pushup(r),再pushup(l)
        }
        else if(!strcmp(op , "DELETE"))
        {
            int posi , tot;
            scanf("%d%d", &posi, &tot);
            int l = get_k(posi) , r = get_k(posi + tot + 1) ; // 左边的向左一个,右边的向右一个,这样r的左子树就是这段序列了
            splay(l , 0) , splay(r,  l);
            del(tr[r].s[0]);            // 删除子树
            tr[r].s[0] = 0;             // 指向空
            pushup(r) , pushup(l);
        }
        else if(!strcmp(op , "MAKE-SAME"))
        {
            int posi , tot , c;
            scanf("%d%d%d", &posi, &tot ,&c);
            int l = get_k(posi) , r = get_k(posi + tot + 1);
            splay(l , 0) , splay(r , l);
            auto &son = tr[tr[r].s[0]];
            son.same = 1 , son.v = c , son.sum = c * son.size;
            if(c > 0) son.ms = son.ls = son.rs = son.sum;
            else son.ms = c , son.ls = son.rs = 0;
            pushup(r) , pushup(l);
        }
        else if (!strcmp(op, "REVERSE"))
        {
            int posi, tot;
            scanf("%d%d", &posi, &tot);
            int l = get_k(posi) , r = get_k(posi + tot + 1);
            splay(l , 0) , splay(r , l);
            auto &son = tr[tr[r].s[0]];
            son.rev ^= 1;
            swap(son.ls , son.rs);          // 旋转之后最大前缀和和最大后缀和对调
            swap(son.s[0] , son.s[1]);       // 左右子树对调
            pushup(r) , pushup(l);
        }
        else if (!strcmp(op, "GET-SUM"))
        {
            int posi, tot;
            scanf("%d%d", &posi, &tot);
            int l = get_k(posi), r = get_k(posi + tot + 1);
            splay(l, 0), splay(r, l);
            printf("%d\n", tr[tr[r].s[0]].sum);
        }
        else printf("%d\n", tr[root].ms);
    }
    
    return 0;
    
}


(2) FHQ

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

const int N = 500010, INF = 1e9;


int n, m;
struct FHQ
{
    int l, r;            // 左右子树下标
    int size;            // 子树大小
    int val, key;        // 结点值和维护堆性质的k
    int sum, ls, rs, ms; // 子树总和、最大前缀和、最大后缀和、最大子段和
    int same, rev;       // 懒标记

    void init(int _v) // 初始化函数
    {
        l = r = 0;
        size = 1;
        sum = val = ms = _v;
        key = rand();
        ls = rs = max(_v, 0);
        same = rev = 0;
    }
} tr[N];

int root, nodes[N], idx; // 根、下标分配站(因为数量很大,所以要循环利用删掉的点的下标)、分配站的idx
int w[N];                // 存值的地方

int addNode(int x) // 增加节点
{
    int id = nodes[idx--]; // 发配节点下标
    tr[id].init(x);
    return id;
}

void reverse(int p) // rev处理函数
{
    if (!p) // 如果是哨兵就跳过
        return;
    tr[p].rev ^= 1;           // 标记下传
    swap(tr[p].ls, tr[p].rs); // 旋转之后最大前缀和和最大后缀和对调
    swap(tr[p].l, tr[p].r);   // 左右子树对调
}

void cover(int p, int c) // same处理函数
{
    if (!p) // 如果是哨兵就跳过
        return;
    tr[p].same = 1;                            // 标记下传
    tr[p].val = c, tr[p].sum = c * tr[p].size; // 修改结点信息
    if (c >= 0)
        tr[p].ms = tr[p].ls = tr[p].rs = tr[p].sum;
    else
        tr[p].ms = c, tr[p].ls = tr[p].rs = 0;
}

void pushdown(int p)
{
    if (!p) // 如果是哨兵就跳过
        return;
    if (tr[p].same) // 如果有same标记
    {
        cover(tr[p].l, tr[p].val);
        cover(tr[p].r, tr[p].val);
        tr[p].same = 0; // 去除标记
    }
    if (tr[p].rev) // 如果有rev标记
    {
        if (tr[p].l)
            reverse(tr[p].l);
        if (tr[p].r)
            reverse(tr[p].r);
        tr[p].rev = 0; // 去除标记
    }
}

void pushup(int p)
{
    tr[p].sum = tr[p].val + tr[tr[p].l].sum + tr[tr[p].r].sum;
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1;
    tr[p].ls = max(tr[tr[p].l].ls, tr[tr[p].l].sum + tr[p].val + tr[tr[p].r].ls);                     // 最大前缀和是 左子树最大前缀和 和 左子树全部加上该节点加上右子树最大前缀和 的最大值
    tr[p].rs = max(tr[tr[p].r].rs, tr[tr[p].r].sum + tr[p].val + tr[tr[p].l].rs);                     // 同理
    tr[p].ms = max(tr[tr[p].l].rs + tr[p].val + tr[tr[p].r].ls, max(tr[tr[p].l].ms, tr[tr[p].r].ms)); // 最大子段和是 左子树的最大子段和 和 右子树的最大子段和 和 左子树最大后缀和加上该节点加上右子树的最大前缀和(因为子段和得连续) 中的最大值
}

// FHQ基本操作,合并x,y子树,其中x子树的值<=y子树的值
int merge(int x, int y)
{
    if (!x || !y)
        return x + y;          // x = 0答案是y,y = 0答案是x,也就是如果有一个子树为空则返回另一个子树
    if (tr[x].key > tr[y].key) // x在堆中是在y的上方,而值小于y,故在y的左上方
    {
        pushdown(x);                 // 合并谁的子树就pushdown谁
        tr[x].r = merge(tr[x].r, y); // 让x的右子树和y合并
        pushup(x);
        return x;
    }
    else // x在y的左下方
    {
        pushdown(y);
        tr[y].l = merge(x, tr[y].l); // x和y的左子树合并
        // 不能写成merge(tr[y].l,x) 必须满足x < y
        pushup(y);
        return y;
    }
}

// FHQ基本操作,按size分裂,找到第k个
// 将p子树以按k拆成x和y子树,其中x的大小<=k,y的大小大于k
void split(int p, int k, int &x, int &y)
{
    if (!p)
    {
        x = y = 0;
        return;
    }
    pushdown(p);               // 分裂前要pushdown标记
    if (k <= tr[tr[p].l].size) // 这里和以前不一样,因为本题是按照排名分裂,所以不比较val的大小,而是看左子树的大小来决定分裂哪棵
    {
        y = p;
        split(tr[p].l, k, x, tr[y].l);
        pushup(y);
    }
    else
    {
        x = p;
        split(tr[p].r, k - tr[tr[p].l].size - 1, tr[x].r, y);
        pushup(x);
    }
}

void del(int p)
{
    nodes[++idx] = p; // 空间回收利用
    if (tr[p].l)
        del(tr[p].l);
    if (tr[p].r)
        del(tr[p].r);
}

int build(int l, int r) // 建树
{
    if (l > r)
        return 0;
    if (l == r)
        return addNode(w[l]);
    int mid = (l + r) >> 1, p = addNode(w[mid]);
    tr[p].l = build(l, mid - 1);
    tr[p].r = build(mid + 1, r);
    pushup(p);
    return p;
}

int main()
{
    tr[0].ms = tr[0].val = w[0] = w[n + 1] = -INF; // 空和哨兵(为了方便删除结点)
    int X, Y, Z;                                   // 建三个空树,方便后序split和merge
    scanf("%d%d", &n, &m);
    for (int i = 1; i < N; i++)
        nodes[++idx] = i;
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    root = build(1, n);

    char op[20];
    while (m--)
    {
        scanf("%s", op);
        if (!strcmp(op, "INSERT"))
        {
            int posi, tot;
            scanf("%d%d", &posi, &tot);
            split(root, posi, X, Y);
            for (int i = 1; i <= tot; i++)
                scanf("%d", &w[i]);
            root = merge(X, merge(build(1, tot), Y));
        }
        else if (!strcmp(op, "DELETE"))
        {
            int posi, tot;
            scanf("%d%d", &posi, &tot);
            split(root, posi - 1, X, Y);
            split(Y, tot, Y, Z);
            del(Y);
            root = merge(X, Z);
        }
        else if (!strcmp(op, "MAKE-SAME"))
        {
            int posi, tot, c;
            scanf("%d%d%d", &posi, &tot, &c);
            split(root, posi - 1, X, Y);
            split(Y, tot, Y, Z);
            cover(Y, c);
            root = merge(X, merge(Y, Z));
        }
        else if (!strcmp(op, "REVERSE"))
        {
            int posi, tot;
            scanf("%d%d", &posi, &tot);
            split(root, posi - 1, X, Y);
            split(Y, tot, Y, Z);
            reverse(Y);
            root = merge(X, merge(Y, Z));
        }
        else if (!strcmp(op, "GET-SUM"))
        {
            int posi, tot;
            scanf("%d%d", &posi, &tot);
            split(root, posi - 1, X, Y);
            split(Y, tot, Y, Z);
            printf("%d\n", tr[Y].sum);
            root = merge(X, merge(Y, Z));
        }
        else
            printf("%d\n", tr[root].ms);
    }
    return 0;
}


(3) Treap(下标写法)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010 , INF = 1e8;

int n;

struct Node
{
    int l , r; //表示左右子树的下标
    int key , val; //表示键值和维护大根堆性质的随机数
    int cnt , size; // 该key的个数和该节点及其子树包含的数字总个数
}tr[N];

int root , idx;

void pushup(int p) //更新节点的size
{
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}

int get_node(int key) //创造新的节点
{
    tr[++ idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 1;
    return idx;
}

void zig(int &p) //右旋拎左右挂左
{
    int q = tr[p].l;
    tr[p].l = tr[q].r , tr[q].r = p , p = q;
    pushup(tr[p].r) , pushup(p);
}

void zag(int &p)//左旋拎右左挂右
{
    int q = tr[p].r;
    tr[p].r = tr[q].l , tr[q].l = p , p = q;
    pushup(tr[p].l) , pushup(p);
}

void build() //初始化
{
    get_node(-INF) , get_node(INF); // 哨兵
    root = 1 , tr[root].r = 2;
    pushup(root);

    if(tr[root].val < tr[tr[root].r].val) zag(root);
}

void insert(int &p , int key)
{
    if(!p) p = get_node(key);
    else if(tr[p].key == key) tr[p].cnt ++;
    else if(tr[p].key > key)
    {
        insert(tr[p].l , key);
        if(tr[tr[p].l].val > tr[p].val) zig(p);
    }
    else 
    {
        insert(tr[p].r , key);  
        if(tr[tr[p].r].val > tr[p].val ) zag(p);
    }
    pushup(p);//别忘了插入之后一定要更新该节点的信息
}

void _delete(int &p , int key)
{
    if(!p) return ;
    if(tr[p].key == key) //找到这个数了
    {
        if(tr[p].cnt > 1) tr[p].cnt --;
        else if( tr[p].l || tr[p].r ) //至少存在一个子树
        {
            if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) //右子树不存在或都存在但是左子树是大根,最终结果都是要右旋
            {
                zig(p);
                _delete(tr[p].r , key); //注意右旋之后要删除的点就是之前点的右儿子
            }
            else
            {
                zag(p);
                _delete(tr[p].l , key);
            }
        }
        else p = 0; //叶子节点,直接删除
    }
    else if (tr[p].key > key) _delete(tr[p].l , key);
    else _delete(tr[p].r , key);

    pushup(p);  //别忘了删除之后一定要更新该节点的信息
}

int get_rank_by_key(int p, int key) // 通过数字找排名
{
    if(!p) return 0;
    if(tr[p].key == key) return tr[tr[p].l].size + 1; 
    if(tr[p].key > key) return get_rank_by_key(tr[p].l , key);
    return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r , key);
}

int get_key_by_rank(int p , int rank) // 通过排名找数字
{
    if(!p) return INF;
    if(tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l , rank);
    if(tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
    return get_key_by_rank(tr[p].r , rank - tr[p].cnt - tr[tr[p].l].size);
}

int get_prev(int p , int key) //找前驱(小于key的最大数)
{
    if(!p) return -INF;
    if(tr[p].key >= key) return get_prev(tr[p].l , key);
    return max(tr[p].key , get_prev(tr[p].r , key));
}

int get_next(int p , int key) //找后继(大于key的最小数)
{
    if(!p) return INF;
    if(tr[p].key <= key) return get_next(tr[p].r , key);
    return min(tr[p].key , get_next(tr[p].l , key));
}

int main()
{
    build(); //初始化

    scanf("%d", &n);
    while (n -- )
    {
        int opt , x;
        scanf("%d%d", &opt, &x);
        if(opt == 1) insert(root , x);
        else if(opt == 2) _delete(root , x);
        else if(opt == 3) printf("%d\n" , get_rank_by_key(root , x) - 1); //减1是因为有哨兵(-INF)
        else if(opt == 4) printf("%d\n" , get_key_by_rank(root , x + 1)); //加1也是因为有哨兵(-INF)
        else if(opt == 5) printf("%d\n" , get_prev(root , x));
        else printf("%d\n" , get_next(root , x));
    }

    return 0;
}


(4)Treap(指针写法)

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

struct Node
{
    int key;
    int priority;
    Node *left;
    Node *right;
    Node(int k, int p) : key(k), priority(p), left(nullptr), right(nullptr) {}
};
Node *rightRotate(Node *t)
{
    Node *s = t->left;
    t->left = s->right;
    s->right = t;
    return s;
}
Node *leftRotate(Node *t)
{
    Node *s = t->right;
    t->right = s->left;
    s->left = t;
    return s;
}
Node *insert(Node *t, int key, int priority)
{
    if (t == nullptr)
    {
        return new Node(key, priority);
    }
    if (key == t->key)
    {
        return t;
    }
    if (key < t->key)
    {
        t->left = insert(t->left, key, priority);
        if (t->priority < t->left->priority)
        {
            t = rightRotate(t);
        }
    }
    else
    {
        t->right = insert(t->right, key, priority);
        if (t->priority < t->right->priority)
        {
            t = leftRotate(t);
        }
    }
    return t;
}
Node *find(Node *t, int key)
{
    if (t == nullptr)
    {
        return nullptr;
    }
    if (key == t->key)
    {
        return t;
    }
    if (key < t->key)
    {
        return find(t->left, key);
    }
    else
    {
        return find(t->right, key);
    }
}
Node *_delete(Node *t, int key);
Node *deleteNode(Node *t, int key)
{
    if (t == nullptr)
    {
        return nullptr;
    }
    if (key < t->key)
    {
        t->left = deleteNode(t->left, key);
    }
    else if (key > t->key)
    {
        t->right = deleteNode(t->right, key);
    }
    else
    {
        return _delete(t, key);
    }
    return t;
}
Node *_delete(Node *t, int key)
{
    if (t->left == nullptr && t->right == nullptr)
    {
        return nullptr;
    }
    else if (t->left == nullptr)
    {
        t = leftRotate(t);
    }
    else if (t->right == nullptr)
    {
        t = rightRotate(t);
    }
    else
    {
        if (t->left->priority > t->right->priority)
        {
            t = rightRotate(t);
        }
        else
        {
            t = leftRotate(t);
        }
    }
    return deleteNode(t, key);
}

void inorder(Node *t, vector<int> &v)
{
    if (t == nullptr)
    {
        return;
    }
    inorder(t->left, v);
    v.push_back(t->key);
    inorder(t->right, v);
}
void preorder(Node *t, vector<int> &v)
{
    if (t == nullptr)
    {
        return;
    }
    v.push_back(t->key);
    preorder(t->left, v);
    preorder(t->right, v);
}
int main()
{
    int m;
    cin >> m;
    Node *root = nullptr;
    while (m--)
    {
        string cmd;
        cin >> cmd;
        if (cmd == "insert")
        {
            int key, priority;
            cin >> key >> priority;
            root = insert(root, key, priority);
        }
        else if (cmd == "find")
        {
            int key;
            cin >> key;
            if (find(root, key) != nullptr)
            {
                cout << "yes" << endl;
            }
            else
            {
                cout << "no" << endl;
            }
        }
        else if (cmd == "delete")
        {
            int key;
            cin >> key;
            root = deleteNode(root, key);
        }
        else
        {
            vector<int> res;
            inorder(root, res);
            for (auto t : res)
                cout << t << ' ';
            cout << '\n';
            res.clear();
            preorder(root, res);
            for (auto t : res)
                cout << t << ' ';
            cout << '\n';
        }
    }
    //system("pause");
    return 0;
}