大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
字典树
字典树（又叫单词查找树、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.net/196388.html原文链接：https://javaforall.net
