大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
字典树又称单词查找树，Trie树，是一种树形结构。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。
之前在网上找的都是些用指针实现的，代码看起来很难懂，今天学习了一种用数组实现的。学习起来简单易懂
int ch[200010][27]; //节点编号
int sz; //字典树节点个数
int val[200010]; //节点的值
void init()
{
sz=1;
memset(ch,0,sizeof(ch));
memset(val,0,sizeof(val));
}
void insert(char *s)
{
int u=0,c;
for(int i=0;i<strlen(s);i++)
{
c=s[i]-'a';
if(!ch[u][c])
ch[u][c]=sz++;
u=ch[u][c];
val[u]++; //！！！
}
}
int query(char *s)
{
int u=0,c;
for(int i=0;i<strlen(s);i++)
{
c=s[i]-'a';
if(!ch[u][c])
return 0;
u=ch[u][c];
}
return val[u];
}说明一下代码中注释的部分，这个语句放在for循环外面有时也是很方便的，当遇到一些特殊的标记，比如1或-1，就代表着字符串的结束，而字符串的中间部分默认都为0。这在有些题中使用是很方便的。
这个数组实现和指针的版本也是有些区别的，数组的版本并不怎么直观，因为在数组中实现的树没有“层”的概念。代替的是节点的“编号”，通过这个编号可以向“下一层”去找节点，也可以通过编号获得字符串的一些其他信息，很多题都需要在结构体或是数组中记录或保存信息，当然这个下标利用的就是“编号”。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/197523.html原文链接：https://javaforall.net
