数据结构-Trie树
[cpp]/**********************************************************
数据结构：
Trie树,又称单词查找树或字典树,是一种树形结构,是一种哈希树的变种;
基本原理：
Trie树的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的;
应用：
用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计;
优点：
最大限度地减少无谓的字符串比较,查询效率比哈希表高;
基本特性：
(1)根节点不包含字符,除根节点外每一个节点都只包含一个字符;
(2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串;
(3)每个节点的所有子节点包含的字符都不相同;
***********************************************************/
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<climits>
#include<algorithm>
using namespace std;
const int MAX=26;
struct Trie //Trie结点声明
{
bool isStr;//标记该结点处是否构成一个串
Trie *next[MAX];//一个指针数组，存放着指向各个儿子节点的指针
};
void insert(Trie *root,const char *s) //将单词s插入到字典树中
{
if(root==NULL||*s=='\0')
return;
Trie *p=root;
while(*s)
{
if(p->next[*s-'a']==NULL)//如果不存在存储该字符的节点，则建立结点
{
Trie *temp=new Trie;
for(int i=0; i<MAX; i++)
{
temp->next[i]=NULL;
}
temp->isStr=false;
p->next[*s-'a']=temp;
p=p->next[*s-'a'];
}
else
{
p=p->next[*s-'a'];
}
s++;//让指针s指向下一个字符
}
p->isStr=true;//单词结束的地方标记此处可以构成一个串
}
int search(Trie *root,const char *s)//查找某个单词s是否已经存在
{
Trie *p=root;
while(p&&*s)
{
p=p->next[*s-'a'];
s++;
}
return (p&&p->isStr); //在单词结束处的标记为true时，单词才存在
}
void del(Trie *root)//释放整个字典树占的堆区空间
{
for(int i=0; i<MAX; i++)
{
if(root->next[i]!=NULL)
{
del(root->next[i]);
}
}
delete root;
}
int main()
{
//freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
char s[100];
Trie * root = new Trie;
for(int i=0; i<MAX; i++)
{
root->next[i]=NULL;
}
root->isStr=false;
int n,m; //n为建立Trie树输入的单词数，m为要查找的单词数
scanf("%d",&n);
getchar();
for(int i=0; i<n; i++) //先建立字典树
{
scanf("%s",s);
insert(root,s);
}
while(~scanf("%d",&m))
{
if(!m)
break;
for(int i=0; i<m; i++) //查找
{
scanf("%s",s);
if(search(root,s))
printf("YES\n");
else
printf("NO\n");
}
printf("\n");
}
del(root); //释放空间很重要
return 0;
}
补充：软件开发 , C++ ,
