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

            堅(jiān)信:勤能補(bǔ)拙

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


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

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

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

            搜索字典項(xiàng)目的方法為:

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

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



             1/*
             2Name: Trie樹的基本實(shí)現(xiàn) 
             3Author: MaiK 
             4Description: Trie樹的基本實(shí)現(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) 評(píng)論(0)  編輯 收藏 引用 所屬分類: G_其他

            導(dǎo)航

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            統(tǒng)計(jì)

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久久青草久久久青草| 久久综合久久综合亚洲| 99热成人精品热久久669| 91久久精品电影| 狠狠色丁香婷婷久久综合| 久久亚洲AV成人无码国产| 91亚洲国产成人久久精品| 久久久国产视频| 91精品久久久久久无码| 少妇无套内谢久久久久| 嫩草影院久久99| 久久精品a亚洲国产v高清不卡| 国产精品九九久久免费视频 | 老司机国内精品久久久久| 久久国产福利免费| 久久精品aⅴ无码中文字字幕不卡| 国产2021久久精品| 久久夜色精品国产网站| 伊人久久无码精品中文字幕| 办公室久久精品| 7国产欧美日韩综合天堂中文久久久久 | 久久精品卫校国产小美女| 久久精品中文騷妇女内射| 久久久久无码精品| 91亚洲国产成人久久精品| 久久A级毛片免费观看| 久久久噜噜噜久久中文字幕色伊伊| 99久久国产亚洲高清观看2024 | 无码人妻少妇久久中文字幕蜜桃| 久久精品成人欧美大片| 色综合久久最新中文字幕| 99久久无码一区人妻a黑| 亚洲AV无一区二区三区久久| 久久国产AVJUST麻豆| 久久久久久毛片免费看| 99久久99久久精品国产片| 91久久婷婷国产综合精品青草| 无遮挡粉嫩小泬久久久久久久| 精品伊人久久大线蕉色首页| 久久精品国产亚洲av麻豆蜜芽 | 国产∨亚洲V天堂无码久久久|