• <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>

            A Za, A Za, Fighting...

            堅信:勤能補拙

            [zz] Trie樹|字典樹的簡介及實現(xiàn)


            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é)點上的信息,即完成查找。
            其他操作類似處理.



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

             5#include<algorithm>
             6#include<iostream>
             7using namespace std;
             8
             9const int sonnum=26,base='a';
            10struct Trie
            11{
            12    int num;//to remember how many word can reach here,that is to say,prefix
            13    bool terminal;//If terminal==true ,the current point has no following point
            14    struct Trie *son[sonnum];//the following point
            15}
            ;
            16Trie *NewTrie()// create a new node
            17{
            18    Trie *temp=new Trie;
            19    temp->num=1;temp->terminal=false;
            20    for(int i=0;i<sonnum;++i)temp->son[i]=NULL;
            21    return temp;
            22}

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

            32    temp->terminal=true;
            33}

            34void Delete(Trie *pnt)// delete the whole tree
            35{
            36    if(pnt!=NULL)
            37    {
            38        for(int i=0;i<sonnum;++i)if(pnt->son[i]!=NULL)Delete(pnt->son[i]);
            39        delete pnt; 
            40        pnt=NULL;
            41    }

            42}

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

            posted on 2010-11-01 15:28 simplyzhao 閱讀(227) 評論(0)  編輯 收藏 引用 所屬分類: G_其他

            導(dǎo)航

            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            国产91色综合久久免费分享| 一本色道久久88—综合亚洲精品| 久久99国产精品久久99小说| 久久福利片| 久久久久国产| 久久久久亚洲国产| 2021最新久久久视精品爱| yy6080久久| 久久国产热精品波多野结衣AV| 色妞色综合久久夜夜| 久久er99热精品一区二区| 国产∨亚洲V天堂无码久久久| 亚洲国产精品高清久久久| 久久亚洲精品国产精品| 国产精品免费看久久久| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 99久久er这里只有精品18| 亚洲AV无码久久精品蜜桃| 久久AV高清无码| 久久高潮一级毛片免费| 国产成年无码久久久免费| 国产V亚洲V天堂无码久久久| 久久AAAA片一区二区| 2021久久精品免费观看| 久久99精品国产麻豆宅宅| 久久亚洲国产精品123区| 无码国内精品久久人妻| 精品水蜜桃久久久久久久| 久久精品国产亚洲av麻豆图片| 国产亚洲精久久久久久无码| 色婷婷综合久久久久中文字幕| 国产亚洲综合久久系列| 久久频这里精品99香蕉久| 青青草原综合久久| 日日噜噜夜夜狠狠久久丁香五月| 成人午夜精品久久久久久久小说 | 亚洲精品无码久久久久去q| 国产精品嫩草影院久久| 伊人久久大香线蕉综合影院首页| 国产精品成人99久久久久| 日日噜噜夜夜狠狠久久丁香五月 |