算法-自定义数据结构全览

内容纲要

数据结构全览

本篇将综合所使用过的全部数据结构

字符串

字符串哈希

struct StringHash{
    ull seed = 131,n,hash[100005],base[100005];
    void init(char *s,ull _len,ull _seed){
        //这样处理之后,对于s的所有子串都可以在o(1)的时间内求出Hash值
        n = _len; seed = _seed;
        base[0] = 1; hash[n] = 0;
        for(int i = 1;i < n;i++){
            base[i] = base[i-1] * seed;
        }
        for(int i = n-1;i >= 0;i--){
            hash[i] = hash[i+1] * seed + (s[i]-'a'+1);
        }
        return ;
    }
    //返回hash[s[i]~s[j]]即返回从i开始到j的子串的hash值
    ull get_hash(int i,int j){
        return hash[i] - hash[i+j]*base[j];
    }
};

KMP算法

void getPMT(char *p,int *f)
{
    int m = static_cast<int>(strlen(p));
    f[0] = f[1] = 0;    //f[0]肯定为0,f[1] = 0是由于右移
    for(int i = 1; i < m; ++i){
        //判断j的起点
        int j = f[i];
        //向前回溯,直到 无公共长度 或 再次找到部分匹配
        while(j && p[i] != p[j]) j = f[j];
        f[i + 1] = (p[i] == p[j]) ? j+1 : 0;
    }
}
//kmp算法,时间复杂度O(n+m)
void kmp(char *s,char *p,int *f)
{
    getPMT(p,f);
    int n = static_cast<int>(strlen(s));
    int m = static_cast<int>(strlen(p));
    int j = 0,cnt = 0;  //cnt计匹配数
    for(int i = 0;i < n;i++){
        //向前回溯,直到 无公共长度 或 再次找到部分匹配
        while(j && s[i] != p[j]) j = f[j];
        if(s[i] == p[j]) j++;
        if(j == m){     //找到匹配
            cnt++;
            printf("KMP find %d match in sign %d\n",cnt,i-m+1);
            j = f[j];   //回溯,查找是否有更多匹配
        }
    }
}

字典树

指针实现

//字典树指针实现
struct trieTree_p{
    //成员变量:子节点数组,必要时可以用map
    int tot,root,child[maxn][letter];
    bool flag[maxn];
    //构造函数,以1为起点
    trieTree_p(){
        memset(child[1],0,sizeof(child[1]));
        flag[1]=true;
        root = tot = 1;
    }
    void insert(const char *s)
    {
        int *cur = &root;
        for(const char*p = s; *p; p++){
            cur = &child[*cur][*p-'a'];
            if(!*cur){  //如果没有该节点,创建
                *cur = ++tot;   //child[][] = 新建节点序号tot
                memset(child[tot],0,sizeof(child[tot]));    //初始化子节点值为0(表示空)
                flag[tot] = false;  //非终止节点,标记flag
                printf("new create char %c\n",*p);
            }
        }
        flag[*cur] = true;  //遍历结束,标记终止节点
    }

    bool query(char *s)
    {
        int n = static_cast<int>(strlen(s));
        int *cur = &root;
        for(char i = 0; i < n; ++i){
            cur = &child[*cur][s[i]-'a'];
        }
        return (*cur) && flag[*cur];
    }
};

数组实现

//字典树数组实现
struct trieTree{
    //成员变量:子节点数组,必要时可以用map
    int tot,pos,child[maxn][letter];
    bool flag[maxn];
    //构造函数
    trieTree(){
        memset(child[0],0,sizeof(child[0]));
        flag[1]=true;
        pos = 1;
    }
    int idx(char c){
        return c - 'a';
    }
    void insert(char *s)
    {
        int n = strlen(s);
        int tot = 0;
        //bool mark = false;
        for(int i = 0; i < n; ++i){
            int c = idx(s[i]);
            if(!child[tot][c]){ //tot = 0,从0开始建trie树
                //mark = true;
                //新节点说明该串开辟了新的位置,肯定不是之前某个串的前缀
                memset(child[pos],0,sizeof(child[pos]));
                flag[pos] = false;
                child[tot][c] = pos++;
                printf("new create char %c\n",s[i]);
            }
            tot = child[tot][c];    //找到下一个字符的位置
        }
        flag[tot] = true;
    }
    bool query(char *s){
        int n = static_cast<int>(strlen(s));
        int tot = 0;
        for(char i = 0; i < n; ++i){
            int c = idx(s[i]);
            tot = child[tot][c]; //子节点
        }
        return tot && flag[tot];
    }
};

AC自动机

struct ACAutoMationTire{    //数值范围太大,可以在全局创建对象
    int trie[maxn_p][letter]; //字典树
    int f[maxn_p];     //失败时的回溯指针
    int end[maxn_p];    //记录终止的信息(模式串可能有重复,用int而不用bool)
    int root,tot;

    int newNode() //节点信息包括 当前节点序号 和 终止信息
    {
        //初始化孩子节点值
        forl(i,0,letter) trie[tot][i] = -1;
        //终止信息
        end[tot] = 0;   //0表示该节点不存在终止情况
        //返回节点序号
        return tot++;   //tot在return后+1,表明有效节点数(序号)+1
    }
    //创建新节点,初始化孩子为-1,表明未创建
    void init()
    {
        tot = 0;    //初始化节点序号(0...n)
        root = newNode();   //创建根节点 
    }
    void insertWords(char *s){
        int len = strlen(s);
        int now = root;
        forl(i,0,len){
            int c = s[i] - 'a';
            if(trie[now][c] == -1){ //创建新节点
                trie[now][c] = newNode();
            }
            now = trie[now][c];
        }
        end[now]++;
    }
    void build(){
        std::queue<int> q;
        f[root] = root;
        //首先对根节点进行一次BFS
        forl(i,0,letter){
            if(trie[root][i] == -1){
                //如果为无效节点,根据父节点继续查找
                trie[root][i] = root;
            }else{  //如果节点有效
                f[trie[root][i]] = root;
                q.push(trie[root][i]);
            }
        }
        while(!q.empty()){
            int now = q.front();
            q.pop();
            forl(i,0,letter){
                if(trie[now][i] == -1){
                    //无效节点,根据父节点继续查找
                    trie[now][i] = trie[f[now]][i];
                }else{
                    //有效节点,设定失败指针并加入队列继续搜索 
                    f[trie[now][i]] = trie[f[now]][i];
                    q.push(trie[now][i]); 
                }
            }
        }
    }
    int query(char* s){
        int len = strlen(s);
        int now = root,ans = 0;
        forl(i,0,len){    //遍历文本串
            int c = s[i] - 'a';
            now = trie[now][c];  //从s[i]点开始寻找
            //每一个s[i],
            for(int j = now; j; j = f[j]){
                //一直向下寻找,直到匹配失败(失败指针指向根)
                ans += end[j];      //遇到终止标记则ans++
                end[j] = 0;    //如果只需要匹配一次模式串,则设为false
            }
        }
        return ans;
    }
};

数论

矩阵乘法及快速幂


struct Matrix{
    int r,c;
    int m[maxn][maxn];
    Matrix(int r = 0,int c = 0){
        init(r,c);
    }
    void init(int _r,int _c){
        this->r = _r;
        this->c = _c;
        memset_zero();
    }
    void memset_zero(){
        memset(m,0,sizeof(m));
    }
    void print(){
        forl(i,0,r){
            forl(j,0,c){
                printf("%5d ",m[i][j]);
            }
            printf("\n");
        }
    }
    friend Matrix operator* (const Matrix& A,const Matrix& B);
};

Matrix operator* (const Matrix& A,const Matrix& B)
{
    //定义并初始化临时矩阵
    Matrix temp(N,N);
    //构造相乘结果矩阵
    forl(i,0,N){
        forl(j,0,N){
            forl(k,0,N){
                temp.m[i][j] = (temp.m[i][j] + A.m[i][k]*B.m[k][j]%mod)%mod;
            }
        }
    }
    return temp;
}

Matrix mPow(Matrix& Mat,int n){
    Matrix ret(N,N);
    forl(i,0,N) forl(j,0,N) ret.m[i][i] = 1;
    while(n){
        if(n&1) ret = ret*Mat;
        Mat = Mat*Mat;
        n >>= 1;
    }
    return ret;
}

搜索

数据结构

简单并查集

struct UnionSet{
    int bb[maxn];
    UnionSet(int n){
        forl(i,0,n) bb[i] = i;
    }
    int getroot(int x){
        if(x != bb[x]) bb[x] = getroot(bb[x]);
        return bb[x];
    }
    void merge(int x,int y){
        x = getroot(x);
        y = getroot(y);
        if(x != y) bb[x] = bb[y];
    }
};

图论

邻接表

邻接表数据结构主体

struct AdjacencyList{
    int n,m;  //n个顶点,m条边
    int u[maxm],v[maxm],w[maxm];
    int first[maxn],next[maxn];
    AdjacencyList(int _n,int _m):n(_n),m(_m){};
    void readGraph_by_AdjacencyList();
    void traversal();
};

功能代码实现

void AdjacencyList::readGraph_by_AdjacencyList(){
    inPut_2(n,m);
    //初始化first数组下标1~n的值为-1,表示1~n顶点暂时都没有边
    fore(i,1,n) first[i] = -1;
    fore(i,1,m){
        inPut_3(u[i],v[i],w[i]);
        //next[i] 表示
        next[i]=first[u[i]];
        first[u[i]]=i;
    }
}

void AdjacencyList::traversal(){
    //遍历每个顶点,first[1] 表示 1号顶点其中的一条边的编号
    //也即该顶点最后读入的边,其余的边都可以在next数组中依次找到
    fore(i,1,n){
        //遍历每个顶点的所有边
        for(int k = first[i]; k != -1; k = next[k]){ 
            printf("%d %d %d\n",u[k],v[k],w[k]);
        }
    }
}

动态规划


发表评论