字典樹的建立和基本查找
一.字典樹的定義
字典樹又叫做前綴樹，任意一個或多個字串可以構建一棵字典樹用于存盤多個串的公共前綴
二.構建字典樹的兩種方法
（1）字典樹的鏈表構建及查找
在用鏈表構造的字典樹中每一個節點有著一個資料域來存放該點代表的字符和26個指標分別指向a(A)~z(Z)26個可能出現的子字符，在尋找某個字串是否出現時，從根節點出發不斷向下查找配對，如果到了最后一個字符都存在則表示該前綴存在
（2）字典樹的二維陣列構建及查找
用二維陣列tree[i][j]來標識一顆字典樹，其中i為父節點，j為子節點，程式開始時父節點為root節點，tree[i][j]表示節點i第j個兒子的編號【這里我們規定root的編號為0】
1） 字典樹的二維陣列構建
2）字典樹的二維陣列查找
三.代碼模板
（1） 字典樹的鏈表模板
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 5 const int SIZE=10; 6 struct Trie 7 { 8 int count;//前綴出現的次數 9 struct Trie *next[SIZE];//孩子節點的數目 10 bool isEnd; //判斷到這個位置是否是一個單詞 11 string name; 12 Trie()//建構式 13 { 14 count=0; 15 memset(next,0,sizeof(next)); 16 isEnd=false; 17 } 18 }; 19 struct Trie *root=new Trie;//建立根節點 20 void Insert(string s) 21 { 22 int len=s.length(); 23 int pos; 24 struct Trie *u=root; 25 for(int i=0;i<len;i++) 26 { 27 pos=s[i]-'0'; 28 if(u->next[pos]==NULL)//數字在邊上，或者說是以位置的方式體現，不需要存盤 29 u->next[pos]=new Trie; 30 u=u->next[pos]; 31 u->count++; 32 } 33 u->isEnd=true;//表明為一個單詞的節點 34 u->name=s;//同時存盤單詞 35 } 36 int Search(string s) 37 { 38 struct Trie *u=root; 39 int len=s.length(); 40 for(int i=0;i<len;i++) 41 { 42 int pos=s[i]-'0'; 43 if(u->next[pos]==NULL) 44 return 0; 45 else 46 u=u->next[pos]; 47 } 48 return u->count; 49 } 50 void del(struct Trie *u) 51 { 52 for(int i=0;i<SIZE;i++) 53 { 54 if(u->next[i]!=NULL) 55 del(u->next[i]); 56 } 57 delete(u); 58 } 59 void print(struct Trie *u) 60 { 61 if(u->isEnd) 62 cout<<u->name<<":"<<u->count<<endl; 63 for(int i=0;i<SIZE;i++) 64 if(u->next[i]!=NULL) 65 print(u->next[i]); 66 } 67 68 int main() 69 { 70 int n; 71 string s; 72 cin>>n; 73 while(n--) 74 { 75 cin>>s; 76 Insert(s); 77 } 78 print(root);//列印檢查下 79 del(root);//釋放樹，下次重新建立 80 return 0; 81 }
（2） 字典樹的二維陣列模板
1 const int maxn =2e6+5;//如果是64MB可以開到2e6+5，盡量開大 2 int tree[maxn][30];//tree[i][j]表示節點i的第j個兒子的節點編號 3 bool flagg[maxn];//表示以該節點結尾是一個單詞 4 int tot;//總節點數 5 void insert_(char *str) 6 { 7 int len=strlen(str); 8 int root=0; 9 for(int i=0;i<len;i++) 10 { 11 int id=str[i]-'0'; 12 if(!tree[root][id]) tree[root][id]=++tot; 13 root=tree[root][id]; 14 } 15 flagg[root]=true; 16 } 17 bool find_(char *str)//查詢操作，按具體要求改動 18 { 19 int len=strlen(str); 20 int root=0; 21 for(int i=0;i<len;i++) 22 { 23 int id=str[i]-'0'; 24 if(!tree[root][id]) return false; 25 root=tree[root][id]; 26 } 27 return true; 28 } 29 void init()//最后清空，節省時間 30 { 31 for(int i=0;i<=tot;i++) 32 { 33 flagg[i]=false; 34 for(int j=0;j<10;j++) 35 tree[i][j]=0; 36 } 37 tot=0; 38 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/110934.html
標籤：其他
上一篇：PAT乙級1008