大家好,又见面了,我是你们的朋友全栈君。
字典树
字典树(又叫单词查找树、TrieTree),是一种树形结构,典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串)。主要思想是利用字符串的公共前缀来节约存储空间。很好地利用了串的公共前缀,节约了存储空间。字典树主要包含两种操作,插入和查找
是一种哈希树的变种,常用于,统计,排序,保存大量字符串(但不仅限于字符串),主要实现方法是利用串的公共前缀来减少查询时间,减少了不必要的比较,不仅节约了存储空间,而且检索的效率比哈希表要高。
下面我们先理解一下字典树的结构
如图
节点代表放入的字符,绿色为公共前缀,我们可以把字典树看成一个连续的有很多分叉口的路,而单词的结尾相当于你要到的目的地,如果没有到达目的地的路就新建一条,如果有就只需要走建好的(公共前缀).并且只要有一个分叉口,即使公共前缀相同,也不会到达同一个目的地, 所以字典树不存在重复问题.
下面介绍字典树的实现及代码(数组模拟)
建树操作;
const int maxn=10000;//提前估计好可能会开的节点的个数
int tot; //节点编号,模拟申请新节点,静态申请
int trie[10000][26]; //假设每个节点的分支有26个(如果是数字0-9)
bool vis[10000]; //判断该节点是不是单词结尾,也可以开int纪录出现次数
插入操作
void insert(char *s,int rt)//参数是字符串和节点数,建立字典树
{
for(int i=0; s[i]; i++)
{
int x=s[i]-‘a’;//假设单词都是小写字母组成(这里我们用26个字母顺序编号表示插入字符)
if(trie[rt][x]==0) //若不存在该节点,开新节点
{
trie[rt][x]=++tot;//表示字符的编号
}
rt=trie[rt][x]; //代表该字符在rt层节点
}
vis[rt]=true;//整个字符串读完后,在vis数组中记录第rt层为单词结尾
}
查询
bool find(char *s,int rt)
{
for(int i=0; s[i]; i++)
{
int x=s[i]-‘a’;//假设单词都是小写字母组成
if(trie[rt][x]==0)
{
return false;//节点不存在,说明单词不存在,直接返回
}
rt=trie[rt][x];
}
return vis[rt]; //如果是被标记的,则说明该串在树中
}
初始化
tot=0;//一开始没有节点
int rt=++tot;//申请一个根节点
memset(trie[rt],0,sizeof(trie[rt]));//初始化根节点
memset(isw,false,sizeof(isw));//初期化标记数组
模板
#include <stdio.h>
#include <string.h>
const int maxn=10000;//提前估计好可能会开的节点的个数
int tot; //节点编号,模拟申请新节点,静态申请
int trie[10000][26]; //假设每个节点的分支有26个
bool isw[10000]; //判断该节点是不是单词结尾
void insert(char *s,int rt)//参数是字符串和节点数,建立字典树
{
for(int i=0; s[i]; i++)
{
int x=s[i]-'a';//假设单词都是小写字母组成
if(trie[rt][x]==0) //若不存在该节点,申请新节点
{
trie[rt][x]=++tot;//每个字符的编号
}
rt=trie[rt][x]; //代表该字符在rt层节点
}
isw[rt]=true;//整个字符串读完后,在isw数组中记录第rt层为单词结尾
}
bool find(char *s,int rt)
{
for(int i=0; s[i]; i++)
{
int x=s[i]-'a';//假设单词都是小写字母组成
if(trie[rt][x]==0)
{
return false;//节点不存在,说明单词不存在,直接返回
}
rt=trie[rt][x];
}
return isw[rt]; //如果是被标记的,则说明该串在树中
}
char s[22];//单词读入
int main()
{
tot=0;//一开始没有节点
int rt=++tot;//申请一个根节点
memset(trie[rt],0,sizeof(trie[rt]));//初始化根节点
memset(isw,false,sizeof(isw));//初期化标记数组
while(scanf("%s",s),s[0]!='#') //新建字典,以一个'#'结束
{
insert(s,rt);
}
while(scanf("%s",s),s[0]!='#') //查单词,以一个'#'结束
{
if(find(s,rt))//从字典中查找单词
printf("%s 在字典中\n",s);
else
printf("%s 不在字典中\n",s);
}
return 0;
}
谢谢观看。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/196388.html原文链接:https://javaforall.cn