[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; }
