数据结构

297次阅读
没有评论

共计 4386 个字符,预计需要花费 11 分钟才能阅读完成。

内容目录

链表

单链表

// e[]存储的是节点的值
// ne[]存储节点的next指针
// idx表示当前用到哪个节点
// head存储链表头
int e[N],ne[N],head,idx,m;

// 链表初始化
void init(){
    head = -1;
    idx = 0;
}
// 向头节点插入元素x
void add_to_head(int x){
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}
// 删除第k个节点后的节点
void removeofK(int k){
    ne[k] = ne[ne[k]];
}
// 在第k个节点之后添加元素x
void add(int k,int x){
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}
// 删除头节点
void removeHead(){
    head = ne[head];
}
// 遍历链表
void display(){
    for(int i=head;i!=-1;i = ne[i]){
        printf("%d ",e[i]);
    }
    printf("\n");
}

双链表


// e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点
int e[N],l[N],r[N],idx;

// 初始化
void init(){
    //0是左端点,1是右端点
    r[0] = 1,l[1] = 0;
    idx = 2;
}

// 在下标是k的点的右边插入元素k
void add_to_right(int k,int x){
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

// 删除第k个点
void remove(int k){
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

// 遍历
void display(){
    for(int i=r[0];i!=1;i=r[i]){
        printf("%d ",e[i]);
    }
    printf("\n");
}

模拟栈

// tt栈顶指针
int a[N],tt;

// 初始化
void init(){
    tt = 0;
}

// 入栈
void push(int x){
    a[++tt] = x;
}
// 出栈
void pop(){
    tt--;
}
// 栈顶元素
int top(){
    return a[tt];
}
// 判空
bool isEmpty(){
    if(tt > 0) return false;
    else return true;
}

单调栈

常见模型:找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

队列

模拟队列

// hh:队头 tt:队尾 
int a[N],hh,tt;

// 队列初始化
void init(){
    hh = 0;
    tt = -1;
}

// 入队
void push(int x){
    a[++tt] = x;
}
// 出队
void pop(){
    hh++;
}
// 取队头元素
int front(){
    return a[hh]; 
}
// 判空
bool isEmpty(){
    if(hh <= tt) return false;
    return true;
}

单调队列

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;
}

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];
        // 匹配成功后的逻辑
    }
}

trie树(字典树)

int son[N][26],cnt[N],idx;
char str[N];

// 插入字符串
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];
}

并查集

// p[x]:x的祖先
int p[N];
int n,m;

// find
int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

// unionn
void unionn(int x, int y){
    p[find(x)] = find(y);
}

// 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);

哈希表


int h[N],e[N],ne[N],idx;

// insert 插入元素
void insert(int x){
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++;
}

// find 查找元素是否在集合中
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;
}

字符串哈希

核心思想:将字符串看成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];
}

STL简介


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

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

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

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

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

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

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

set, map, multiset, multimap, 基于平衡二叉树(红黑树),动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继,时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x,删除所有x   O(k + logn)
            (2) 输入一个迭代器,删除这个迭代器
        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()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似,增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound(), 迭代器的++,--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反
正文完
 
PG Thinker
版权声明:本站原创文章,由 PG Thinker 2023-09-15发表,共计4386字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
热评文章