• <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)論排行榜

            久久综合中文字幕| 一日本道伊人久久综合影| 蜜臀av性久久久久蜜臀aⅴ| 蜜臀久久99精品久久久久久小说| 精品国产乱码久久久久久1区2区 | 97视频久久久| 久久综合给合久久狠狠狠97色69| 88久久精品无码一区二区毛片 | 国产亚洲精久久久久久无码77777| 伊人久久大香线蕉av不变影院 | 久久久国产精品亚洲一区| 久久婷婷国产麻豆91天堂| 国产成人综合久久精品红| 99久久精品国产毛片| 一本色道久久综合亚洲精品| 国产99久久久久久免费看 | 久久亚洲国产午夜精品理论片| 亚洲午夜无码AV毛片久久| 国产精品久久成人影院| 成人午夜精品无码区久久| 久久综合日本熟妇| 久久精品无码一区二区三区日韩 | 久久不见久久见免费视频7| 伊人久久大香线蕉AV一区二区| 丁香久久婷婷国产午夜视频| 人妻精品久久久久中文字幕一冢本| 色偷偷88欧美精品久久久| 国产免费久久久久久无码| 国产精品久久久久国产A级| 日本五月天婷久久网站| 欧美性猛交xxxx免费看久久久| 婷婷久久综合九色综合98| 久久久亚洲欧洲日产国码aⅴ| 亚洲成av人片不卡无码久久| 国产精品欧美久久久久天天影视 | 99久久99这里只有免费的精品| 欧美亚洲国产精品久久久久| 激情综合色综合久久综合| 久久精品成人影院| 亚洲精品高清一二区久久| 久久久久久免费视频|