数据结构的一些小结和板子

链表

//定义
int head=-1,e[N],ne[N],idx=0;
//头插
void add(int x)
{
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}
//在第k位后插入
void insert(int k,int x)
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}
//删除第k位
void del(int k)
{
    ne[k]=ne[ne[k]];
}

栈

后进先出

//定义
int q[N],tt;
//入栈
q[tt++]=x;
//取栈顶元素
q[tt]
//出栈
tt--;

队列

先进先出

//定义
int q[N],hh=0,tt=-1;
//入队
q[++tt]=x;
//出队
q[hh++]
//判断是否为空
tt-hh>=0

Trie数

字典树：高效地存储字符串

//定义
int son[N][26],idx=0,cnt[N];
//插入
void insert(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int x=str[i]-'a';
        if(!son[p][x]) son[p][x]=++idx;
        p=son[p][x];
    }
}
//查询
int query(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int x=str[i]-'a';
        if(!son[p][x]) return 0;
        p=son[p][x];
    }
    return cnt[p];
}

并查集

并查集的主要操作是合并和查找，这两个操作的核心是find根节点。

合并是将一个集合的根节点直接指向另一个集合的根节点。

查找是从当前结点开始往上，判断父节点是否为根节点，查找过程中进行路径压缩，将当前遍历到的结点直接指向根节点。

//初始化
for(int i=1;i<=n;i++) p[i]=i;

//find(带路径压缩)
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

//合并
int pu=find(u),pv=find(v);
if(pu!=pv) p[pu]=pv;

堆

以小根堆为例。

每插入一个数，需要堆堆进行down或up，down表示使大数往下，up表示使小数往上，通过这两个操作，可以维持小根堆堆顶元素最大的性质。

需要注意的是，当我们要删除堆中的某个元素时，并不是直接删去，因为删去数组中特定位置的数是非常困难的，而删去数组末尾的数非常容易，因此采用的方式是先将元素和堆尾元素互换，删去堆尾元素，再执行down或up。

//插入元素
heap[++idx]=x;
up(idx);

//删除元素
swap(heap[1],heap[idx--]);
down(1);

void down(int u)
{
    int t=u;
    if(2*u<=idx&&heap[2*u]<heap[t]) t=2*u;
    if(2*u+1<=idx&&heap[2*u+1]<heap[t]) t=2*u+1;
    if(u!=t) 
    {
        swap(heap[t],heap[u]);
        down(t);
    }
}

void up(int u)
{
    while(u/2&&heap[u/2]>heap[u])
    {
        swap(heap[u/2],heap[u]);
        u/=2;
    }
}