字典树(数组版)入门级详细讲解加模拟
程序员文章站
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;
}
推荐阅读