关于Trie树的模板

Trie树又称单词查找树,Trie树,是一种树形结构。是一种哈希树的变种。典型应用是用于统计。排序和保存大量的字符串(但不仅限于字符串),所以常常被搜索引擎系统用于文本词频统计。

它的长处是:利用字符串的公共前缀来降低查询时间,最大限度地降低无谓的字符串比較。查询效率比哈希树高。 ——-百度百科

详细给出代码,这也是依据大牛们的一些代码整的。,还是太渣了。。。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
using namespace std;
const int maxn = 26;
struct Trie//结点声明
{
struct Trie *next[maxn];//孩子分支
bool isStr;//标记是否构成单词
}; void Insert(Trie *root,const char *s)//将单词s插入Trie树
{
if(root==NULL || *s=='\0')
return;
//int i;
Trie *p = root;
while(*s != '\0')
{
if(p->next[*s-'a'] == NULL) //假设不存在,则建立结点
{
Trie *tmp = (Trie*)malloc(sizeof(Trie));
for(int i=0; i<maxn; i++)
tmp->next[i] = NULL;
tmp->isStr = false;
p->next[*s-'a'] = tmp;
p = p->next[*s-'a'];
}
else
p = p->next[*s-'a'];
s++;
}
p->isStr = true;//单词结束的地方标记此处能够构成一个单词
} int Find(Trie *root, const char *s)
{
Trie *p = root;
while(p!=NULL && *s!='\0')
{
p = p->next[*s-'a'];
s++;
}
return (p!=NULL && p->isStr==true);//在单词结束处的标记为true时,单词才存在
} void Del(Trie *root)//释放整个Trie树的空间
{
for(int i=0; i<maxn; i++)
{
if(root->next[i] != NULL)
Del(root->next[i]);
}
free(root);
} char s[100];
int main()
{
int m,n; //n为建立Trie树输入的单词数,m为要查找的单词数
Trie *root = (Trie *)malloc(sizeof(Trie));
for(int i=0; i<maxn; i++)
root->next[i] = NULL;
root->isStr = false;
scanf("%d",&n);
getchar();
for(int i=0; i<n; i++)//建立Trie树
{
scanf("%s",s);
Insert(root,s );
} while(~scanf("%d",&m))
{
for(int i=0; i<m; i++)
{
scanf("%s",s);
if(Find(root, s) == 1)
puts("Yes");
else
puts("No");
}
puts("");
}
Del(root);
return 0;
}
上一篇:Jungle Roads(最小生成树)


下一篇:selenium+python,解决selenium弹出新页面,无法定位元素的问题(报错:Unable to locate element:元素)