数据结构汇总（竞赛+笔试）（有待补全）
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;
}