学习了之前的树状结构,接下来就可以利用树状结构存储数据了。
首先什么是字典树?
字典树就是利用树的结构按照字典的原理进行存储的数据结构,树的结构我们了解了,字典是什么样的呢,我们通常去查英文单词的时候,往往都是英文字母a,b,c,d…x,y,z这样一个顺序,利用这样的原理我们知道有字典序这样的顺序。字典树也是如此,例如有两个单词application,apple,我们查字典时通常是按a->p->p->l->接着下去,然后先发现了apple,再发现了application,我们会发现这些有着相同前缀的单词查询时进行的方式是相同的,为了减少内存的使用,而且便于查找,它的优点很明显,有相同前缀的单词前缀部分只用存储一次。
这里给出字典树最常用的模板,当然不同的题目需要不同的删改变动灵活运用,需要注意的一点就是,我们知道一个树结构的分枝越多和深度越深,那么递归调用起来很可能爆栈,所以要适时进行改动,另外有些内存优化过的编译器更容易出现这样的情况。
和之前一样利用注释和代码结合,先给大家清晰直观的图示,了解一下。
insert函数过程:首先apple单词插入,char *s指向a字符,for循环遍历,遍历至root里next数组a结点时,也就是下标为0的数组值。它还是NULL,那么新建,将值赋进去,同理延伸至apple完成,e点时该单词结束标记此时的e结点为单词,isword=true。当application单词插入时,之前的appl都是已经建立好的了,只用在原来的基础上将prefix++即可,那么新的分枝出现了,也就是appli,与apple同理继续延伸下去。
struct node//树结构
{
char *s;//字符指针存储当前结点字符
int prefix;//出现多少以当前字符串为前缀的字符串,后面会进行深入解释
bool isword;//截止当前,该字符串是否为单词
node *next[26];//26个字母,从a的下标为0开始
node()//初始化函数,相当于构造函数初始化数据
{
s = NULL;//当前结点为空
prefix = 0;//0个单词以此段为前缀
isword = false;//不是单词
memset(next,0,sizeof(next));
}
}*root;
void insert(node *root,char *s)//插入函数
{
node *p = root;//将p赋值为我当前插入的结点
for(int i=0;s[i];i++)//遍历单词
{
int x = s[i] - 'a';//将单词顺序转化为下标存储
p->s=s+i;//p结点存储的字符指向char * s的第i位字,char * 结构需要通过调用指针+-来获取字符指针
if(p->next[x] == NULL)//很明显,如果没有指向下一个的就新建一个
p->next[x] = new node;
p = p->next[x];//接着p就会指向它,也就是指针向下一个字母前进
p->prefix++; //出现次数+1
}
p->isword=true;//遍历的最后,末尾p即为单词的结尾,所以它是一个完整的单词
}
bool del(node *root,char *s)//删除函数,这个函数通常很少使用,删除某个单词原理与插入相同
{
node *p = root;
for(int i=0;s[i];i++)
{
int x = s[i]-'a';
if(p->next[x]==NULL)
return false;
p = p->next[x];
}
if(p->isword)
p->isword=false;
else return false;
return true;
}
bool search(node *root,char *s)//查找单词
{
node *p=root;
for(int i=0;s[i];i++)
{
int x=s[i]-'a';
if(p->next[x]==NULL)//和insert中相同,只需要向下找到所需分枝即可,如果不存在,则说明不含有该单词返回false即可
return false;
p = p->next[x];
}
return p->isword;//如果到了末尾,返回当前分枝是否为单词,例如appl就不是一个单词,但是可以访问到达,返回appl的l结点的isword即可
}
int count(node *root,char *s)//记录以当前字符串为前缀的单词个数
{
node *p= root;
for(int i=0;s[i];i++)
{
int x=s[i]-'a';
if(p->next[x]==NULL)
return 0;
p = p->next[x];
}//遍历找到当前字符串的最后一个分枝返回出现次数即可,也就是prefix的值
return p->prefix;
}
char word[11];//单词长度,利用char 数组存储
char pre[11];
int main()
{
root = new node;
while(gets(word))
{
if(strcmp(word,"")==0) break;
insert(root,word);
// cout<<word<<endl;
}
// cout<<"next"<<endl;
while(gets(pre))
{
if(strcmp(pre,"")==0) break;
cout<<count(root,pre)<<endl;
}
}
很多人可能对char * s和char s[]之间产生疑问,c++中字符串的存储方式实际上是利用char数组进行的,指针实际上就相当于一个数组,只是他没有固定的大小,就好比如果我需要存1000000的字符串和10的字符串,如果char数组那我只能开一个1000000大小的,相对于10大小的,会造成浪费,所以char *没有固定大小是在内存上提供了遍历,本质上与char数组对字符串的处理是相同的。
main函数里的操作时,先进行插入单词,然后输入一些测试查询以此为前缀的单词数量
通常对于字典树的操作,在建树完成后,我们需要知道以下几个问题:
- 该字符串是否为单词
- 以此字符串为前缀的单词数量
- 有多少单词经过该分枝节点
- 最长的公共前缀,prefix为n的所有节点最深的那个,它的深度即为所求
想要求出这些问题的解,只需要对上述模板进行变形即可,熟练使用后,便很容易操作起来。
字典树学会了的话,不妨看看字典树的延伸——AC自动机,难度过大的话可以先收藏起来以后再学哦!