學習字典樹一段時間 了，個人覺得字典樹比較容易掌握，但是ACM中題目變化多端，我們只有多練習，才能對字典樹的應用有更深的把握。
下面講解一下字典樹。
其實掌握字典樹，只需要寫過一個關於字典樹的程序，記住它的結構就可以了。先看看字典樹的定義
[cpp]
struct Trie
{
Trie *next[MAX];
bool isword;
};
struct Trie
{
Trie *next[MAX];
bool isword;
};
其實上面那個字典樹結點的定義只是來自我做的一個題目，裡面的元素視你做的題目而定，不過 Trie *next[] 這個數組就是一定的了，只不過他的大小也視你的題目而定。(可能是26個小寫字母，也可能是52個大小寫字母或者其他)
相信一個例子大家就都掌握了，建議一定先看看題目（自己敲完這一個題目之後，一定可以A掉其他許多關於字典樹的題目了）
題目的大概意思就是說給定一些單詞，要你從中找到某些單詞，而這個單詞是由另外兩個單詞組成的。
其實我們就是利用字符的ascii碼來給他對應的索引
這個題目就是把每個單詞拆成兩部分，看看是不是每一部分在字典樹中都是一個單詞
先來看看建樹的過程。（耐心一點，一步一步看懂程序，just one time）
必要的時候動手畫一畫圖
[cpp]
<SPAN style="FONT-SIZE: 18px">void createTrie(char str[])//傳進來輸入的字符串
{
int len = strlen(str);
Trie *p = root,*q = NULL;
for(int i=0;i<len;i++)
{
int id = str[i]-'a';
if(p->next[id]==NULL)
{
q = new Trie;
for(int j=0;j<MAX;j++)
q->next[j] = NULL;
q->isword = false;
p->next[id] = q;
}
if(i==len-1)
p->next[id]->isword = true;
p = p->next[id];
}
}</SPAN>
void createTrie(char str[])//傳進來輸入的字符串
{
int len = strlen(str);
Trie *p = root,*q = NULL;
for(int i=0;i<len;i++)
{
int id = str[i]-'a';
if(p->next[id]==NULL)
{
q = new Trie;
for(int j=0;j<MAX;j++)
q->next[j] = NULL;
q->isword = false;
p->next[id] = q;
}
if(i==len-1)
p->next[id]->isword = true;
p = p->next[id];
}
}再看看查找的過程
[cpp]
<SPAN style="FONT-SIZE: 18px">bool findTrie(char str[])
{
int len = strlen(str);
Trie *p = root;
for(int i=0;i<len;i++)
{
int id = str[i]-'a';
if(p->next[id]==NULL)
{
return false;
}
p = p->next[id];
}
if(p->isword)
return true;
else
return false;
}</SPAN>
bool findTrie(char str[])
{
int len = strlen(str);
Trie *p = root;
for(int i=0;i<len;i++)
{
int id = str[i]-'a';
if(p->next[id]==NULL)
{
return false;
}
p = p->next[id];
}
if(p->isword)
return true;
else
return false;
}
最後記得釋放掉這顆字典樹
[cpp]
<SPAN style="FONT-SIZE: 18px">void del(Trie *root)
{
for(int i=0;i<26;i++)
{
if(root->next[i]!=NULL)
{
del(root->next[i]);
}
}
delete root;
}</SPAN>
void del(Trie *root)
{
for(int i=0;i<26;i++)
{
if(root->next[i]!=NULL)
{
del(root->next[i]);
}
}
delete root;
}注意在建立樹的時候，先產生一個根節點 Trie *root = new Trie; //我幾乎每次都忘了先new出來一個
下面貼一下完整代碼
[cpp]
<SPAN style="FONT-SIZE: 18px">#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAX = 26;
struct Trie
{
Trie *next[MAX];
bool isword;
};
Trie *root = new Trie;
char word[50000][30];
void createTrie(char str[])
{
int len = strlen(str);
Trie *p = root,*q = NULL;
for(int i=0;i<len;i++)
{
int id = str[i]-'a';
if(p->next[id]==NULL)
{
q = new Trie;
for(int j=0;j<MAX;j++)
q->next[j] = NULL;
q->isword = false;
p->next[id] = q;
}
if(i==len-1)
p->next[id]->isword = true;
p = p->next[id];
}
}
bool findTrie(char str[])
{
int len = strlen(str);
Trie *p = root;
for(int i=0;i<len;i++)
{
int id = str[i]-'a';
if(p->next[id]==NULL)
{
return false;
}
p = p->next[id];
}
if(p->isword)
return true;
else
return false;
}
void del(Trie *root)
{
for(int i=0;i<MAX;i++)
{
if(root->next[i]!=NULL)
{
del(root->next[i]);
}
}
delete root;
}
int main()
{
int num=0;
char str1[30],str2[30];
for(int i=0;i<MAX;i++)
{
root->next[i] = NULL;
}
root->isword = false;
while(gets(word[num]))
{
createTrie(word[num]);
num++;
}
for(int i=0;i<num;i++)
{
int len = strlen(word[i]);
if(len==1)
continue;
for(int j=0;j<len;j++)//從每個單詞的各部分拆開
{
int k;
if(j==len-1) continue;
for(k=0;k<=j;k++)
{
str1[k] = word[i][k];
}
str1[k]='\0';
int k2=0;
for(int l=k;l<len;l++)
{
str2[k2++]=word[i][l];
}
str2[k2]='\0';
if(findTrie(str1)&&findTrie(str2))
{
cout<<word[i]<<endl;
break;//居然錯在這裡了(可能會重復輸出)
}
}
}
del(root);
return 0;
}
</SPAN>
