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

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

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

            搜索字典項目的方法為:

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

            (2) 取得要查找關(guān)鍵詞的第一個字母,并根據(jù)該字母選擇對應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進行檢索;

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

             

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

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


            轉(zhuǎn)自:http://hi.baidu.com/luyade1987/blog/item/2667811631106657f2de320a.html
            posted on 2010-01-28 17:07 chatler 閱讀(567) 評論(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
            • 感覺這個博客還是不錯,雖然做的東西和我不大相關(guān),覺得看看還是有好處的

            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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            色婷婷久久久SWAG精品| 9191精品国产免费久久| 久久国产劲爆AV内射—百度| 午夜肉伦伦影院久久精品免费看国产一区二区三区 | 女同久久| 欧美激情精品久久久久| 久久综合五月丁香久久激情| 久久婷婷色香五月综合激情| 久久精品国产亚洲av水果派| 久久国产一片免费观看| 国产成人无码精品久久久性色| 国产精品岛国久久久久| 中文精品99久久国产 | www.久久热.com| 国产精品99久久久精品无码| 国产午夜久久影院| 超级97碰碰碰碰久久久久最新| 青青草国产精品久久| 久久人人爽爽爽人久久久| 欧美色综合久久久久久| 99久久免费国产精品| 色偷偷偷久久伊人大杳蕉| 久久成人小视频| 久久久久九国产精品| 亚洲国产精品人久久| 久久精品国产亚洲av高清漫画| 亚洲国产婷婷香蕉久久久久久| 国产精品成人久久久久三级午夜电影| 国产成人精品综合久久久久| 亚洲欧洲中文日韩久久AV乱码| 丁香久久婷婷国产午夜视频| 91久久精品91久久性色| 色综合久久无码五十路人妻| 久久精品国产亚洲AV影院| 伊人久久一区二区三区无码| 日日狠狠久久偷偷色综合0| 91精品国产乱码久久久久久| a级成人毛片久久| 国产女人aaa级久久久级| 久久91这里精品国产2020| 久久乐国产精品亚洲综合|