欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

字典树(数组版)入门级详细讲解加模拟

程序员文章站 2022-05-19 15:01:12
...

字典树是一种用于快速检索的多叉树结构,每个节点保存一个字符,一条枝干表示一个单词、电话等等信息。

具体每个节点如草图所示

字典树(数组版)入门级详细讲解加模拟

 结构体(节点)定义如下

struct Tree
{
    int point[30];
    int num;///这里维护的是单词前缀出现多少次,根据自己的需求定义结构体里面维护的值
    void init()
    {
        for(int i=0; i<=26; i++)
           point[i]=-1;
             num=0;
    }
} T[maxn];

每个节点下面的26条分支初始状态都是-1  按顺序0-25分别表示a到z字符。不是-1的位置代表这个位置可以继续往下索引。

比如 :(T[0]表示根节点)

T[0].point[0]=1;
T[1].point[1]=2;
T[2].point[2]=3;

这三个数组的意思就是表示存了一个abc字符串,如果T[2].point[0]=4;就表示还存了一个aba的串。从根开始通过T[0].point[0]可以找到T[1],通过T[1]里面point数组第二个位置的值(索引)可以找到T[2],T[2]的piont数组里面有第0个和第2个位置不为-1就表示有了aba和abc字符串。

另贴上三个常用函数

void Insert(char *str,int value)
{
    int cnt=0;///每次从根节点出发
    int len=strlen(str);
    for(int i=0; i<len; i++)
    {
        int x=str[i]-'a';
        if(!T[cnt].point[x])///如果下一个节点不存在就开一个新的节点,并且将当前节点的point指向下一个节点的下标cur
        {
            T[cur].init();
           
            T[cnt].point[x]=cur++;///cur代表字符数组开了多少了,因为不能重复一直自增
        }
        cnt=T[cnt].point[x];///意思是T=T->next 往下索引
        T[cnt].num+=value; ///维护前缀出现的次数
    }
}
void Delete(char *str,int value)
{
    int x,cnt=0;
    int len=strlen(str);
    for(int i=0; i<len; i++)
    {
        x=str[i]-'a';
        cnt=T[cnt].point[x];
        T[cnt].num-=value;
    }
}
int Query(char *str)
{
    int x,cnt=0;
    int len=strlen(str);
    for(int i=len-1; i>=0; i--)
    {
        x=str[i]-'a';
        if(T[cnt].point[x]==-1)
            return 0;
        cnt=T[cnt].point[x];
    }
    return T[cnt].num;
}

 

相关标签: 字典树