• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>


            如圖,每條路徑上保存一個字母,從根節點開始進行dfs,每遍歷到一個標記節點(圖中的紅點),從根節點到當前節點路徑上所有字母連起來即為一個單詞

            上圖中存儲了 abc, abcd, b, bcd, efg, hij.

            對于Trie樹主要有三種操作:

            1. 新建一個結點
            2. 插入一個單詞
            3. 在trie樹中查找單詞
            trie樹中每次插入一個結點的時間復雜度是 O( strlen( str ) )
            建立trie樹的時間復雜度為 O( ∑strlen( str[i] ) )
            對于每個單詞,查詢的時間復雜度為 O( strlen( str ) )

            Templates:

            Struct:

            struct node  
            {  
                
            int flag;     //The end of a word  
                node* next[26];  
            };  

            新建結點:

            node* newnode()  
            {  
                node* p = new node;  
              
                p->flag = 0;  
              
                
            forint i = 0; i < 26; i++ )  
                    p->next[i] = NULL;  
              
                
            return p;  
            }  

            插入單詞:

            void trie_insert( node* root, char* s )  
            {  
                node* p = root;  
                
            int len = strlen( s );  
              
                
            int tmp;  
                
            forint i = 0; i < len; i++ )  
                {  
                    tmp = s[i] - 'a';  
                    
            if( p->next[tmp] == NULL )  
                        p->next[tmp] = newnode();  
                    p = p->next[tmp];  
                }  
                p->flag = 1;  
            }  

            查詢:

            int trie_search( node* root, char* s )  
            {  
                node* p = root;  
                
            int len = strlen( s );  
              
                
            int tmp;  
                
            forint i = 0; i < len; i++ )  
                {  
                    tmp = s[i] - 'a';  
                    
            if( p->next[tmp] == NULL )         //not matched  
                        return 0;  
                    p = p->next[tmp];  
                }  
              
                
            if( p->flag )     //match && it is a word which has been stored  
                return 1;  
                
            return 0;  
            }  
            posted on 2016-08-31 09:35 Vontroy 閱讀(370) 評論(0)  編輯 收藏 引用 所屬分類: 字符串
            国内精品久久久久伊人av| 久久99精品国产自在现线小黄鸭 | 色综合久久天天综合| 无码国内精品久久人妻| AV狠狠色丁香婷婷综合久久| 精品久久久久久国产潘金莲| 国产成人无码精品久久久免费| 久久夜色撩人精品国产小说| 欧美精品九九99久久在观看| 久久天天躁狠狠躁夜夜avapp| 久久电影网一区| 美女久久久久久| 国内精品人妻无码久久久影院| 亚洲а∨天堂久久精品| 色欲av伊人久久大香线蕉影院| 超级碰久久免费公开视频| 性欧美大战久久久久久久久| 久久777国产线看观看精品| 欧美喷潮久久久XXXXx| 久久亚洲精品中文字幕三区| 无码国内精品久久人妻蜜桃| 久久久这里只有精品加勒比| 久久99国产精品久久99果冻传媒| 77777亚洲午夜久久多人| 久久影院亚洲一区| 人人狠狠综合久久亚洲婷婷| 精品无码久久久久国产动漫3d| 久久久久久亚洲精品不卡| 国产精品久久久久天天影视| 日本欧美久久久久免费播放网 | 伊人热人久久中文字幕| 精品国产青草久久久久福利| 亚洲国产精品无码久久久久久曰 | 久久久女人与动物群交毛片| 欧美久久久久久| 亚洲国产精品成人久久蜜臀| 热RE99久久精品国产66热| 久久精品国产清自在天天线| 久久久久亚洲精品无码网址 | 国产精品狼人久久久久影院| 精品国产91久久久久久久|