来自北京大学NOIP金牌选手yxc的常用代码模板2——数据结构

清疚 2021-07-24 23:11 372阅读 0赞

### 目录 ###

*   *   *   *  1.单链表
             *  2.双链表
             *  3.栈
             *  4.队列
             *  5.单调栈
             *  6. 单调队列
             *  7.KMP
             *  8.Trie树
             *  9.并查集
             *  10.堆
             *  11.一般哈希
             *  12.字符串哈希
             *  13.C++ STL简介

#### 1.单链表 ####

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
    int head, e[N], ne[N], idx;
    
    // 初始化
    void init()
    { 
        head = -1;
        idx = 0;
    }
    
    // 在链表头插入一个数a
    void insert(int a)
    { 
        e[idx] = a, ne[idx] = head, head = idx ++ ;
    }
    
    // 将头结点删除，需要保证头结点存在
    void remove()
    { 
        head = ne[head];
    }

#### 2.双链表 ####

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
    int e[N], l[N], r[N], idx;
    
    // 初始化
    void init()
    { 
        //0是左端点，1是右端点
        r[0] = 1, l[1] = 0;
        idx = 2;
    }
    
    // 在节点a的右边插入一个数x
    void insert(int a, int x)
    { 
        e[idx] = x;
        l[idx] = a, r[idx] = r[a];
        l[r[a]] = idx, r[a] = idx ++ ;
    }
    
    // 删除节点a
    void remove(int a)
    { 
        l[r[a]] = l[a];
        r[l[a]] = r[a];
    }

#### 3.栈 ####

// tt表示栈顶
    int stk[N], tt = 0;
    
    // 向栈顶插入一个数
    stk[ ++ tt] = x;
    
    // 从栈顶弹出一个数
    tt -- ;
    
    // 栈顶的值
    stk[tt];
    
    // 判断栈是否为空
    if (tt > 0)
    { 
    
    }

#### 4.队列 ####

**(1). 普通队列：**

// hh 表示队头，tt表示队尾
    int q[N], hh = 0, tt = -1;
    
    // 向队尾插入一个数
    q[ ++ tt] = x;
    
    // 从队头弹出一个数
    hh ++ ;
    
    // 队头的值
    q[hh];
    
    // 判断队列是否为空
    if (hh <= tt)
    { 
    
    }

**(2). 循环队列**

// hh 表示队头，tt表示队尾的后一个位置
    int q[N], hh = 0, tt = 0;
    
    // 向队尾插入一个数
    q[tt ++ ] = x;
    if (tt == N) tt = 0;
    
    // 从队头弹出一个数
    hh ++ ;
    if (hh == N) hh = 0;
    
    // 队头的值
    q[hh];
    
    // 判断队列是否为空
    if (hh != tt)
    { 
    
    }

#### 5.单调栈 ####

**常见模型：找出每个数左边离它最近的比它大/小的数**

int tt = 0;
    for (int i = 1; i <= n; i ++ )
    { 
        while (tt && check(stk[tt], i)) tt -- ;
        stk[ ++ tt] = i;
    }

#### 6. 单调队列 ####

**常见模型：找出滑动窗口中的最大值/最小值**

int hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ )
    { 
        while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
        while (hh <= tt && check(q[tt], i)) tt -- ;
        q[ ++ tt] = i;
    }

#### 7.KMP ####

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
    求模式串的Next数组：
    for (int i = 2, j = 0; i <= m; i ++ )
    { 
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }
    
    // 匹配
    for (int i = 1, j = 0; i <= n; i ++ )
    { 
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == m)
        { 
            j = ne[j];
            // 匹配成功后的逻辑
        }
    }

#### 8.Trie树 ####

int son[N][26], cnt[N], idx;
    // 0号点既是根节点，又是空节点
    // son[][]存储树中每个节点的子节点
    // cnt[]存储以每个节点结尾的单词数量
    
    // 插入一个字符串
    void insert(char *str)
    { 
        int p = 0;
        for (int i = 0; str[i]; i ++ )
        { 
            int u = str[i] - 'a';
            if (!son[p][u]) son[p][u] = ++ idx;
            p = son[p][u];
        }
        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;
            p = son[p][u];
        }
        return cnt[p];
    }

#### 9.并查集 ####

**(1)朴素并查集：**

int p[N]; //存储每个点的祖宗节点
    
        // 返回x的祖宗节点
        int find(int x)
        { 
            if (p[x] != x) p[x] = find(p[x]);
            return p[x];
        }
    
        // 初始化，假定节点编号是1~n
        for (int i = 1; i <= n; i ++ ) p[i] = i;
    
        // 合并a和b所在的两个集合：
        p[find(a)] = find(b);

**(2)维护size的并查集：**

int p[N], size[N];
        //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
    
        // 返回x的祖宗节点
        int find(int x)
        { 
            if (p[x] != x) p[x] = find(p[x]);
            return p[x];
        }
    
        // 初始化，假定节点编号是1~n
        for (int i = 1; i <= n; i ++ )
        { 
            p[i] = i;
            size[i] = 1;
        }
    
        // 合并a和b所在的两个集合：
        size[find(b)] += size[find(a)];
        p[find(a)] = find(b);

**(3)维护到祖宗节点距离的并查集：**

int p[N], d[N];
        //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
    
        // 返回x的祖宗节点
        int find(int x)
        { 
            if (p[x] != x)
            { 
                int u = find(p[x]);
                d[x] += d[p[x]];
                p[x] = u;
            }
            return p[x];
        }
    
        // 初始化，假定节点编号是1~n
        for (int i = 1; i <= n; i ++ )
        { 
            p[i] = i;
            d[i] = 0;
        }
    
        // 合并a和b所在的两个集合：
        p[find(a)] = find(b);
        d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

#### 10.堆 ####

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
    // ph[k]存储第k个插入的点在堆中的位置
    // hp[k]存储堆中下标是k的点是第几个插入的
    int h[N], ph[N], hp[N], size;
    
    // 交换两个点，及其映射关系
    void heap_swap(int a, int b)
    { 
        swap(ph[hp[a]],ph[hp[b]]);
        swap(hp[a], hp[b]);
        swap(h[a], h[b]);
    }
    
    void down(int u)
    { 
        int t = u;
        if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
        if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
        if (u != t)
        { 
            heap_swap(u, t);
            down(t);
        }
    }
    
    void up(int u)
    { 
        while (u / 2 && h[u] < h[u / 2])
        { 
            heap_swap(u, u / 2);
            u >>= 1;
        }
    }
    
    // O(n)建堆
    for (int i = n / 2; i; i -- ) down(i);

#### 11.一般哈希 ####

**(1) 拉链法**

int h[N], e[N], ne[N], idx;
    
        // 向哈希表中插入一个数
        void insert(int x)
        { 
            int k = (x % N + N) % N;
            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;
        }

**(2) 开放寻址法**

int h[N];
    
        // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
        int find(int x)
        { 
            int t = (x % N + N) % N;
            while (h[t] != null && h[t] != x)
            { 
                t ++ ;
                if (t == N) t = 0;
            }
            return t;
        }

#### 12.字符串哈希 ####

核心思想：将字符串看成`P`进制数，`P`的经验值是`131`或`13331`，取这两个值的冲突概率低  
小技巧：取模的数用`2^64`，这样直接用`unsigned long long`存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
    ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
    // 初始化
    p[0] = 1;
    for (int i = 1; i <= n; i ++ )
    { 
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }
    
    // 计算子串 str[l ~ r] 的哈希值
    ULL get(int l, int r)
    { 
        return h[r] - h[l - 1] * p[r - l + 1];
    }

#### 13.C++ STL简介 ####

**(1).`vector`, 变长数组，倍增的思想**  
`size()`返回元素个数  
`empty()` 返回是否为空  
`clear()`清空  
`front()/back()`  
`push_back()/pop_back()`  
`begin()/end()`  
`[]`  
支持比较运算，按字典序

**(2).`pair<int, int>`**  
`first`, 第一个元素  
`second`, 第二个元素  
支持比较运算，以`first`为第一关键字，以`second`为第二关键字（字典序）

**(3). `string`，字符串**  
`size()/length()` 返回字符串长度  
`empty()`  
`clear()`  
`substr`(起始下标，(子串长度)) 返回子串  
`c_str()` 返回字符串所在字符数组的起始地址

**(4). `queue`, 队列**  
`size()`  
`empty()`  
`push()` 向队尾插入一个元素  
`front()`返回队头元素  
`back()` 返回队尾元素  
`pop()` 弹出队头元素

**(5). `priority_queue`, 优先队列，默认是大根堆**  
`size()`  
`empty()`  
`push()` 插入一个元素  
`top()`返回堆顶元素  
`pop()`弹出堆顶元素  
定义成小根堆的方式：`priority_queue<int, vector<int>, greater<int>> q`;

**(6). `stack`, 栈**  
`size()`  
`empty()`  
`push()` 向栈顶插入一个元素  
`top()` 返回栈顶元素  
`pop()` 弹出栈顶元素

**(7). `deque`, 双端队列**  
`size()`  
`empty()`  
`clear()`  
`front()/back()`  
`push_back()/pop_back()`  
`push_front()/pop_front()`  
`begin()/end()`  
`[]`

**(8). `set`, `map`, `multiset`, `multimap`, 基于平衡二叉树（红黑树），动态维护有序序列**  
`size()`  
`empty()`  
`clear()`  
`begin()/end()`  
`++`,`--`返回前驱和后继，时间复杂度 `O(logn)`  
(1) 输入是一个数x，删除所有`x` `O(k + logn)`  
(2) 输入一个迭代器，删除这个迭代器  
**(9).`lower_bound()/upper_bound()`**  
`lower_bound(x)` 返回大于等于x的最小的数的迭代器  
`upper_bound(x)`返回大于x的最小的数的迭代器  
`map/multimap`  
`insert()`插入的数是一个pair  
`erase()` 输入的参数是pair或者迭代器  
`find()`  
`[]` 注意`multimap`不支持此操作。 时间复杂度是 `O(logn)`  
`lower_bound()/upper_bound()`

**(10).`unordered_set`,`unordered_map`, `unordered_multiset`, `unordered_multimap`, 哈希表**  
和上面类似，增删改查的时间复杂度是`O(1)`  
不支持 `lower_bound()/upper_bound()`， 迭代器的`++`，`--`  
**(11).其他**  
`bitset`, 圧位  
`bitset<10000> s`;  
`~`, `&`,`|`, `^`  
`>>`, `<<`  
`==`, `!=`  
`[]`  
`count()` 返回有多少个`1`  
`any()` 判断是否至少有一个`1`  
`none()`判断是否全为`0`  
`set()` 把所有位置成`1`  
`set(k, v)`将第k位变成`v`  
`reset()`把所有位变成`0`  
`flip()` 等价于`~`  
`flip(k)`把第`k`位取反