• <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>
            posts - 297,  comments - 15,  trackbacks - 0
            Trie,又稱字典樹、單詞查找樹,是一種樹形結構,用于保存大量的字符串。它的優點是:利用字符串的公共前綴來節約存儲空間。
            相對來說,Trie樹是一種比較簡單的數據結構.理解起來比較簡單,正所謂簡單的東西也得付出代價.故Trie樹也有它的缺點,Trie樹的內存消耗非常大.當然,或許用左兒子右兄弟的方法建樹的話,可能會好點.

            其基本性質可以歸納為:
            1. 根節點不包含字符,除根節點外每一個節點都只包含一個字符。
            2. 從根節點到某一節點,路徑上經過的字符連接起來,為該節點對應的字符串。
            3. 每個節點的所有子節點包含的字符都不相同。

            其基本操作有:查找 插入和刪除,當然刪除操作比較少見.我在這里只是實現了對整個樹的刪除操作,至于單個word的刪除操作也很簡單.

            搜索字典項目的方法為:

            (1) 從根結點開始一次搜索;

            (2) 取得要查找關鍵詞的第一個字母,并根據該字母選擇對應的子樹并轉到該子樹繼續進行檢索;

            (3) 在相應的子樹上,取得要查找關鍵詞的第二個字母,并進一步選擇對應的子樹進行檢索。
            (4) 迭代過程……
            (5) 在某個結點處,關鍵詞的所有字母已被取出,則讀取附在該結點上的信息,即完成查找。
            其他操作類似處理.

             

            /*
            Name: Trie樹的基本實現 
            Author: MaiK 
            Description: Trie樹的基本實現 ,包括查找 插入和刪除操作
            */

            #include
            <algorithm>
            #include
            <iostream>
            using namespace std;

            const int sonnum=26,base='a';
            struct Trie
            {
                
            int num;//to remember how many word can reach here,that is to say,prefix
                bool terminal;//If terminal==true ,the current point has no following point
                struct Trie *son[sonnum];//the following point
            }
            ;
            Trie 
            *NewTrie()// create a new node
            {
                Trie 
            *temp=new Trie;
                temp
            ->num=1;temp->terminal=false;
                
            for(int i=0;i<sonnum;++i)temp->son[i]=NULL;
                
            return temp;
            }

            void Insert(Trie *pnt,char *s,int len)// insert a new word to Trie tree
            {
                Trie 
            *temp=pnt;
                
            for(int i=0;i<len;++i)
                
            {
                    
            if(temp->son[s[i]-base]==NULL)temp->son[s[i]-base]=NewTrie();
                    
            else temp->son[s[i]-base]->num++;
                    temp
            =temp->son[s[i]-base];
                }

                temp
            ->terminal=true;
            }

            void Delete(Trie *pnt)// delete the whole tree
            {
                
            if(pnt!=NULL)
                
            {
                    
            for(int i=0;i<sonnum;++i)if(pnt->son[i]!=NULL)Delete(pnt->son[i]);
                    delete pnt; 
                    pnt
            =NULL;
                }

            }

            Trie
            * Find(Trie *pnt,char *s,int len)//trie to find the current word
            {
                Trie 
            *temp=pnt;
                
            for(int i=0;i<len;++i)
                    
            if(temp->son[s[i]-base]!=NULL)temp=temp->son[s[i]-base];
                    
            else return NULL;
                
            return temp;
            }
             


            轉自:http://hi.baidu.com/luyade1987/blog/item/2667811631106657f2de320a.html
            posted on 2010-01-28 17:07 chatler 閱讀(568) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm
            <2010年1月>
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(10)

            隨筆分類(307)

            隨筆檔案(297)

            algorithm

            Books_Free_Online

            C++

            database

            Linux

            Linux shell

            linux socket

            misce

            • cloudward
            • 感覺這個博客還是不錯,雖然做的東西和我不大相關,覺得看看還是有好處的

            network

            OSS

            • Google Android
            • Android is a software stack for mobile devices that includes an operating system, middleware and key applications. This early look at the Android SDK provides the tools and APIs necessary to begin developing applications on the Android platform using the Java programming language.
            • os161 file list

            overall

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            青青青国产成人久久111网站| 亚洲AV无一区二区三区久久| 九九久久自然熟的香蕉图片| 久久精品无码一区二区日韩AV| 久久人人超碰精品CAOPOREN| 成人免费网站久久久| 偷偷做久久久久网站| 国产成人综合久久久久久| 亚洲人成网亚洲欧洲无码久久| 伊人丁香狠狠色综合久久| 性高湖久久久久久久久| 久久久久免费精品国产| 久久这里都是精品| 久久毛片一区二区| 91精品国产综合久久久久久| 久久亚洲精品国产精品婷婷| 99热精品久久只有精品| 色妞色综合久久夜夜| 久久精品无码专区免费青青| 精品久久久久成人码免费动漫| 国产精品久久久久久久久免费| 伊人色综合九久久天天蜜桃| 久久久www免费人成精品| 亚洲AV无码久久精品色欲| 久久国产三级无码一区二区| 久久久久久综合一区中文字幕| 亚洲综合熟女久久久30p| 亚洲欧美国产精品专区久久| 国产精品日韩深夜福利久久| 久久精品国内一区二区三区| 国产亚州精品女人久久久久久 | 国产精品毛片久久久久久久| 天天做夜夜做久久做狠狠| 久久精品人妻中文系列| 久久亚洲精品无码aⅴ大香| 久久亚洲天堂| 四虎国产精品成人免费久久| 久久精品国产免费观看| 蜜臀久久99精品久久久久久小说| 人妻少妇久久中文字幕一区二区 | 伊色综合久久之综合久久|