typedef struct node
{
int cnt;
node *next[26];
};
node root;
void CreateTrie(char *str) // 创建Trie树
{
int len=strlen(str);
node *p=&root;
node *q;;
for (int i=0;i< len;i++)
{
int id=str-'a';
if (p->next[id]==NULL)
{
q=(node*)malloc(sizeof(node));
q->cnt=1;
for (int j=0;jnext[j]=NULL;
p->next[id]=q;
p=p->next[id];
}
else
{
p->next[id]->cnt++;
p=p->next[id];
}
}
}
int FindTire(char *str) // 查询
{
int len=strlen(str);
node *p=&root;
for (int i=0;i< len;i++)
{
int id=str-'a';
p=p->next[id];
if (p==NULL)
return 0;
}
return p->cnt;
}
void DeleteTire(node *root) // Trie树的销毁
{
for (int i=0;inext!=NULL)
DeleteTire(root->next);
free(root);
}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
下图是对单词hat、hap、my、new、npc建立的一个字典树
很容易明确,如果有两个单词拥有相同的前缀,比方hat、hap,”ha”只需新建一次。
(2)数组实现:
int chara[200001][26];
int vis[200001]; // 用来标记前缀出现的次数
int e=1; // 出现的新节点的个数
void Insert(char *str) // 建立Trie树
{
int len=strlen(str);
int i,p=1;
for (int i=0;i