静态单链表

      四个变量：head, e[N], ne[N], idx 
      四个函数：init(), add_to_head(x), add(k, x), remove(k) 
      一个遍历 for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';

head 表示头指针，指向头节点，存储头结点的下标

e[i] 表示第 i 个结点存储的值

ne[i] 表示第 i 个结点指向的下一个结点，存储下一个结点的下标

idx 表示已经存储了多少个数，存储下一个可以用的结点下标,

从0开始，也就是意味着第一个插入的结点下标为0，第二个为1，第三个为2

下标为-1的结点为空结点

静态双链表

       四个变量 e[i], l[i], r[i], idx
       三个函数 init(), add(k, x), remove(k)
       开局初始化牢记！！！

e[i] 表示第i个结点存储的值

l[i] 表示第i个结点左边的结点的下标

r[i] 表示第i个结点右边的结点的下标

idx 表达当前可以用的下标，从0开始。 01,已经用，0 是 头节点的下标， 1是尾结点的下标，初始从2开始

栈

        两个变量 stk[N], tt;
        四个操作 插入， 弹出， 判栈空， 取栈顶。

stk[] 模拟栈存储数据，只能取栈顶元素

tt 下标从1开始插入元素，且时刻指向栈顶，tt 初始为 0 表示栈为空

队列

          三个变量q[N], hh, tt
          四个操作插入， 弹出， 判栈空， 取队头

KMP

kmp算法，能快速地求出模板串 P 在模式串 S 中所有出现的位置的起始下标，终点下标

          四个变量S[M], P[N], m, n
          两个操作求ne数组，kmp匹配过程

s[]是长文本，p[]是模式串，m是s的长度，n是p的长度

求ne数组, ne[1] = 0, 不需要匹配。

    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j]; //当j不为0 且下一个字符不匹配时，j回到与它匹配的位置，求次长，
                                //若一直不匹配则j = 0跳出循环，另一种跳出循环的情况就是下一个字符匹配成功。
        if (p[i] == p[j + 1]) j ++ ; //来到这里j有两种情况（0和非0），当j==0, 意味接下来用模式串的第一个字符来匹配，成功就加1，失败不加
                //当j!=0, 意味着模式串已经成功匹配j个长度了，而且从上面的循环跳出条件看，下一个字符一定是匹配的，j一定加1
        ne[i] = j; //当j!=0,j已经加1，ne[i]成功匹配的长度就为j。若上面j == 0,下个字符相同，ne[i]匹配长度就为1，否则为0
    }

    //kmp过程，和求ne数组大同小异，求ne数组相当于自己与自己匹配，kmp是两个不同的字符串模式匹配
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++;
        if (j == n)//成功匹配
        {
            printf("%d ",i - n);//返回起始地点，终点是i，长度是n，起点是i - n + 1, 因为s下标从1开始的，所以我们要-1，i-n+1-1=i-n
            j = ne[j]; //再次缩短长度进行下一次的匹配
        }
    }

Trie

Trie字典树:高效地存储和查找字符串的数据结构

            三个变量 son[N][26], cnt[N], idx
            三个操作，初始化，insert(char str[]), query(char str[])

son[N][26] 表示 最多有N个结点，从0到N - 1，N的大小由字符串长度决定。

0既代表根结点又代表空结点，每个结点最多有26个子节点（随题目而变，这时表示字符串仅包含小写英文字母）

cnt[i] 表示 以下标为i的结点为末尾的字符串的个数

idx 指向最后生成的结点下标，0已经被根结点和空结点共同用了，所以初始化idx = 0

//插入一个字符串，也是代表存储一个字符串
void insert(char str[])
{
    int p = 0; // 从根结点开始
    for (int i = 0; str[i]; i ++ ) // 字符串以\0结尾，而\0 的ascll 为 0;
    {
        int u = str[i] - 'a';// 0..25 映射 a-z
        if (!son[p][u]) son[p][u] = ++ idx;//son[p][u] == 0 意味着空结点。代表没有这个字符，所以分配一个结点给它
        p = son[p][u];//到下一个结点，不管上一步分配与否，只要没走到字符串末尾，就一直走下去。
    }
    // 走完意味着str[i] == 0 ，p指向最后一个结点 ,那么这个结点+1，这个字符串的个数加一
    cnt[p] ++ ;
}

//查询一个字符串，从根结点走到最后结点p，返回其个数cnt[p]
int query(char str[])
{
    int p = 0;// 从根结点开始
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0; // 如果中道崩殂，意味着没有这个字符串，返回个数0
        p = son[p][u]; // 走到着，意味着 上面的if没执行，存在下p到u的路线。就走到u这个结点
    }
    return cnt[p]; // 走到最后一个结点了，不管它之前有没有以这里为末尾插入结点，返回cnt[p] 也就是到这个结点的字符串的个数。
}

并查集

并查集:每个集合用一棵树来表示，树根的编号就是整个集合的编号。每个结点存储它的父节点，p[x]表示x的父节点

            一个变量：p[N];
            六个操作：初始化，查找父结点，查找根结点，合并集合，查询关系，判断根结点

int find(int x) //查找根结点
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

堆

基本版

            两个变量：h[N], siz; 
            两个基本操作：down(),up()
            三个细节操作：插入，求最值，删最值

h[i] 表示第i个结点存储的值，i从1开始，2i是左子节点，2i + 1是右子节点

size 既表示堆里存储的元素个数，又表示最后一个结点的下标

加强版
五个变量：h[N], ph[N], hp[N], siz, idx;
三个基本操作：down(),up(),heah]p_swap()
五个细节操作：插入，求最值，删最值，改任意值，删任意值

h[i]存储第i个结点的下标

ph[i]存储插入数下标i的堆数组下标（堆中位置）

hp[i]存储堆数组下标i的插入数下标

siz 表示堆数组大小，而且时刻指向堆数组最后已用的下标

idx 表示插入数下标，而且时刻指向插入数最后已用的下标

void heap_swap(int a, int b) //要修改的两个堆数组下标，可得=> hp[a],hp[b] ,对应的插入数下标 => ph[hp[a]], ph[hp[b]] ,插入数对应的堆数组下标
{
    swap(h[a], h[b]); // 交换堆数组下标对应的值
    swap(hp[a], hp[b]);//插入数下标要跟着改变
    swap(ph[hp[a]], ph[hp[b]]); //堆数组下标是跟着插入数下标改变
}

void down(int u)// 下沉
{
    int t = u; // 存储值最小的结点的下标
    if (u * 2 <= siz && h[u * 2] < h[t]) t = u * 2;//比较左结点
    if (u * 2 + 1 <= siz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;//比较右结点
    if (t != u)//不同，以为着左右子节点的值有更小的，那就交换
    {
        heap_swap(t, u);
        down(t);
    }
}
void up(int u)// 上浮
{
    while (u / 2 && h[u / 2] > h[u])//父节点存在且大于当前结点
    {
        heap_swap(u / 2, u);
        u = u / 2; //指向父节点，继续操作
    }
}

哈希表(散列表)

两种结构：拉链法、开放寻址法
一种特殊哈希表：字符串哈希表

第一种结构-拉链法
四个变量：h[N], e[N], ne[N], idx;
三个操作：初始化，insert(int x)，find(int x)

初始化
const int N = 100003;//最多插入1e5个不同的数，所以把数组最大开到大于1e5的最近素数，素数有利于减少冲突

memset(h, -1, sizeof h);

h[i]= -1 表示下标为i的结点指向一个空结点

void insert(int x)
{
    int k = ( x % N + N ) % N; //把映射到1.. N - 1
    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;
}

第二种结构-开放寻址法

            一个变量：h[N];
            两个操作：初始化，find(int x)

初始化

const int N = 200003, null = 0x3f3f3f3f;//要比原有结点多2、3倍，且为素数

memset(h, 0x3f, sizeof h);//都为无穷大，代表指向空

int find(int x)
{
    int k = (x % N + N) % N;
    while(h[k] != null && h[k] != x)//当下标为k的值不为空也不是x, k向前走一位
    {
        k ++ ;
        if (k == N) k = 0;//超过数组范围，循环到0的位置，继续走
    }
    return k; //到了这里，要么h[k]==null，要么h[k]==x,前者返回这个值应该在的位置，后者返回这个值确实在的位置
}

一种特殊的哈希表-字符串哈希表

            两个变量：ULL h[N],p[N];
            两个操作：初始化，get(int l, int r)

p[i]预处理存储的是P的各种幂次P[1] == P^1 ,p[2] == P^2
h[i]预处理存储的是字符串前缀的hash值
get返回的是l..r之间子字符串的hash值

初始化
onst int N = 100010, P = 131;

typedef unsigned long long ULL;//每个数的hash值最后都要mod 2^64

小技巧就是把每个数的hash用ULL存储，这样机器会帮我们mod（溢出处理）

至于为什么要mod 2^64 因为大家发现mod这个数hash值冲突的概率会低

个人理解是，因为这个数是目前大部分机器能表示最大的整数了！当然你的电脑是128位的另说。

而P 为什么要取131，或者13331，因为emm..经验之谈！ 暂时没有逻辑hh

目的和mod 2^64 一样的也是降低hash值冲突的概率，可能它们是孤儿中的孤儿hh，（质数中的王牌个人战斗机！）

p[0] = 1; //这个很重要，如果不初始化，任意p[i]都为0 ,字符串哈希将会没有意义！ 
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = p[i - 1] * P; // 初始化p[i] 进制数 p^1..p^n
        h[i] = h[i - 1] * P + str[i];// 初始化 h[i] 字符串前缀的hash值 h[1]..h[n] h[n] 等于整个字符串在P进制下的hash值
    }

get(int l, int r)

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];//r比l-1 多了r - l + 1位，所以h[l-1] 要乘这么多位后再被h[r]减。错位相减后的值就是l..r之间的hash值 
}