字典树模板（数组实现和指针实现）

落日映苍穹つ 2022-06-10 08:46 99阅读 0赞

字典树的指针实现：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 64 
 65 
 66 
 67 
 68 
 69 
 70 
 71 
 72 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 ///这里以输入字符串后，查询字符串出现的次数为例 
 #include&lt;bits/stdc++.h&gt; 
 
 #define&nbsp;MAX&nbsp; 
 26 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 typedef&nbsp; 
 struct&nbsp;TrieNode&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///Trie节点声明 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;&nbsp;num;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///数据域，可根据需要进行改变 &nbsp;&nbsp;&nbsp;&nbsp; 
 struct&nbsp;TrieNode&nbsp;*next[MAX];&nbsp;&nbsp;&nbsp; 
 ///儿子分支 }&nbsp;Trie; 
 
 int&nbsp;ans&nbsp;=&nbsp;- 
 1; 
 
 char&nbsp;b[ 
 15]; 
 
 void&nbsp;insert1(Trie&nbsp;*root,&nbsp; 
 char&nbsp;*s) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(root&nbsp;==&nbsp; 
 NULL&nbsp;||&nbsp;*s&nbsp;==&nbsp; 
 '\0') 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;; 
 &nbsp;&nbsp;&nbsp;&nbsp;Trie&nbsp;*p&nbsp;=&nbsp;root; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(*s&nbsp;!=&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(p-&gt;next[*s&nbsp;-&nbsp; 
 'a']&nbsp;==&nbsp; 
 NULL) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///如果当前节点还不存在，就建立新的节点 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Trie&nbsp;*temp&nbsp;=&nbsp;(Trie&nbsp;*)malloc( 
 sizeof(Trie)); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;MAX;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp-&gt;next[i]&nbsp;=&nbsp; 
 NULL; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp-&gt;num&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p-&gt;next[*s&nbsp;-&nbsp; 
 'a']&nbsp;=&nbsp;temp; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;p-&gt;next[*s&nbsp;-&nbsp; 
 'a']; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;p-&gt;next[*s&nbsp;-&nbsp; 
 'a']; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s++; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;p-&gt;num++; 
 } 
 
 
 bool&nbsp;Find(Trie&nbsp;*rt,&nbsp; 
 char&nbsp;*s) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;len&nbsp;=&nbsp;strlen(s); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;len;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;c&nbsp;=&nbsp;s[i]&nbsp;-&nbsp; 
 'a'; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(!rt-&gt;next[c]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 false; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;rt&nbsp;=&nbsp;rt-&gt;next[c]; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(rt-&gt;num) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 true; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 false; 
 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;n; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 char&nbsp;a[ 
 15]; 
 &nbsp;&nbsp;&nbsp;&nbsp;Trie&nbsp;*root&nbsp;=&nbsp;(Trie&nbsp;*)malloc( 
 sizeof(Trie)); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;MAX;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;root-&gt;next[i]&nbsp;=&nbsp; 
 NULL; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;n); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;n;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%s",&nbsp;a); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;insert1(root,&nbsp;a); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(~scanf( 
 "%s",&nbsp;a)) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(Find(root,&nbsp;a)) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;puts( 
 "exist"); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;puts( 
 "none"); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

字典树的数组实现：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 64 
 65 
 66 
 67 
 68 
 69 
 70 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 ///这里以输入字符串后，查询字符串出现的次数为例 
 #include&nbsp;&lt;bits/stdc++.h&gt; 
 
 #define&nbsp;maxn&nbsp; 
 1000000 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 
 struct&nbsp;Trie 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;next[ 
 26]; 
 ///表示下一个节点是否存在， &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;val; 
 ///节点的数据域,可根据需要进行改变 }&nbsp;tree[maxn]; 
 
 int&nbsp;nxt; 
 ///nxt表示节点的编号 
 char&nbsp;str[ 
 26]; 
 ///存储输入的字符串 
 int&nbsp;add() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///建立新的节点 &nbsp;&nbsp;&nbsp;&nbsp;memset(&amp;tree[nxt],&nbsp; 
 0,&nbsp; 
 sizeof(Trie)); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;nxt++; 
 } 
 
 void&nbsp;Insert( 
 char&nbsp;*s) 
 ///插入以及建树 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;rt&nbsp;=&nbsp; 
 0,&nbsp;len&nbsp;=&nbsp;strlen(s); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;len;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;c&nbsp;=&nbsp;s[i]&nbsp;-&nbsp; 
 'a'; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(!tree[rt].next[c]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///如果树中还不存在这个节点，就开辟新的节点 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tree[rt].next[c]&nbsp;=&nbsp;add(); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;rt&nbsp;=&nbsp;tree[rt].next[c]; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;tree[rt].val++; 
 ///维护数据域（这个表示出现的次数） } 
 
 
 bool&nbsp;Find( 
 char&nbsp;*s) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///查找字符串是否存在 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;rt&nbsp;=&nbsp; 
 0,&nbsp;len&nbsp;=&nbsp;strlen(s); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;len;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;c&nbsp;=&nbsp;s[i]&nbsp;-&nbsp; 
 'a'; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(!tree[rt].next[c]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 false; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;rt&nbsp;=&nbsp;tree[rt].next[c]; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(tree[rt].val) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 true; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 false; 
 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;T; 
 &nbsp;&nbsp;&nbsp;&nbsp;memset(&amp;tree[ 
 0],&nbsp; 
 0,&nbsp; 
 sizeof(Trie)); 
 &nbsp;&nbsp;&nbsp;&nbsp;nxt&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;T); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(T--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%s",&nbsp;str); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Insert(str); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(~scanf( 
 "%s",&nbsp;str)) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(Find(str)) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;puts( 
 "exist"); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;puts( 
 "none"); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>