青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

Trie樹|字典樹的簡介及實現(轉)

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 2009-04-21 12:08 abilitytao 閱讀(26790) 評論(12)  編輯 收藏 引用

評論

# re: Trie樹|字典樹的簡介及實現(轉) 2010-08-25 13:16 renenglish

強,子樹查找的時候不用遍歷,我的就需要遍歷比較…你是咋想到的?  回復  更多評論   

# re: Trie樹|字典樹的簡介及實現(轉)[未登錄] 2010-08-25 14:00 abilitytao

@renenglish
這個是經典的東西。。。  回復  更多評論   

# re: Trie樹|字典樹的簡介及實現(轉)[未登錄] 2010-10-30 00:15 Michael

好東西,轉了  回復  更多評論   

# re: Trie樹|字典樹的簡介及實現(轉) 2011-09-13 17:05 明樣

把26個字母的指針都存掉冗余太大了,浪費這么多空間只換了一點點性能不值得- -@renenglish
  回復  更多評論   

# re: Trie樹|字典樹的簡介及實現(轉) 2012-07-11 14:40 noah

to 博主:
感覺你的代碼實現有點問題,我不知道您測試過沒有。
在節點定義中,terminal 為ture的時候,不能有子節點。但是遇到這種單詞怎么處理啊。
單詞一:blackberry
單詞二:black
如果先存儲black,然后terminal之后,那blackberry豈不是要又要創建一個子樹。這樣顯然違背trie樹的原則。
而且你的插入方法中,只要插入就terminal。
如有問題,可找我討論。我的mail是nklizhongnan@gmail.com.  回復  更多評論   

# re: Trie樹|字典樹的簡介及實現(轉) 2013-01-23 12:05 msa

恩,代碼有問題啊  回復  更多評論   

# re: Trie樹|字典樹的簡介及實現(轉)[未登錄] 2013-03-26 14:49 長風

@明樣
同意明樣,這樣的冗余度非常非常大。  回復  更多評論   

# re: Trie樹|字典樹的簡介及實現(轉) 2013-04-22 08:39 ptolemy

而且查找的話,如果已經插入單詞blackberry,那么它所有的前綴如black等也都查得出,即使這些單詞并沒有被插入過?  回復  更多評論   

# re: Trie樹|字典樹的簡介及實現(轉) 2013-05-31 17:06 fully

@ptolemy
應該在find到最后一個字符時,判斷terminal==true?  回復  更多評論   

# re: Trie樹|字典樹的簡介及實現(轉) 2013-11-16 10:12 dellenzhang

所以sonnum應該寫為27,其中有一個為空,再terminal=true。相當于結束標記。  回復  更多評論   

# re: Trie樹|字典樹的簡介及實現(轉) 2014-01-06 13:31 aa88kk

搜索過來, 大概看了下, 覺得有問題.
trie會多用一些空間,但不是很多. 因為每個節點只是一個字符(或最小的字符組合).
26個子節點只是極端情況.  回復  更多評論   

# re: Trie樹|字典樹的簡介及實現(轉) 2014-03-18 16:40

Find函數里的返回是不是有問題呢?不是不能返回局部對象的指針嗎  回復  更多評論   

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产欧美日韩一区| 欧美福利一区| 国产日韩欧美一区在线| 欧美在线|欧美| 欧美一区二区精品| 一区二区三区在线免费播放| 免费久久久一本精品久久区| 欧美暴力喷水在线| 在线视频欧美日韩精品| 亚洲一二三区在线观看| 国内精品国产成人| 亚洲第一视频网站| 欧美va天堂| 亚洲字幕一区二区| 久久精品国产一区二区电影| 亚洲韩国日本中文字幕| 日韩视频免费看| 国内外成人免费激情在线视频网站 | 欧美a级片网站| 亚洲视屏在线播放| 午夜久久久久久| 亚洲激情成人网| 亚洲天天影视| 一区二区在线视频播放| 亚洲欧洲一区二区在线观看| 国产精品夜色7777狼人| 欧美岛国激情| 国产免费观看久久| 亚洲第一色在线| 国产一区二区三区黄| 最新日韩在线视频| 国内精品久久久久影院色 | 妖精成人www高清在线观看| 国产人久久人人人人爽| 亚洲国产一成人久久精品| 国产九九精品视频| 亚洲国产裸拍裸体视频在线观看乱了中文| 欧美日韩中文字幕综合视频| 男人的天堂亚洲| 国产精品一区二区你懂得| 91久久在线| 136国产福利精品导航网址| 中文av字幕一区| 亚洲精品麻豆| 久久亚洲电影| 久久久久久久网站| 亚洲日本国产| 久久午夜电影网| 亚洲视频你懂的| 免费高清在线视频一区·| 香蕉成人伊视频在线观看| 欧美日韩精品免费观看| 欧美电影免费| 亚洲国内在线| 久久视频这里只有精品| 久久久综合网站| 国产亚洲成av人片在线观看桃 | 亚洲欧洲在线免费| 亚洲国产欧美一区二区三区丁香婷| 亚洲免费在线看| 性欧美长视频| 国产精品一区久久久| 亚洲午夜羞羞片| 亚洲欧美日韩另类精品一区二区三区| 欧美久久在线| 在线视频你懂得一区| 亚洲视频一区| 国产精品国产三级国产普通话99| 亚洲精品美女久久7777777| 日韩一级欧洲| 欧美三级电影网| 亚洲一区三区电影在线观看| 亚洲欧美日韩国产综合精品二区| 欧美四级电影网站| 亚洲——在线| 久久久99国产精品免费| 激情六月婷婷综合| 美女诱惑黄网站一区| 亚洲第一偷拍| 亚洲视频在线观看| 国产精品成人一区二区艾草| 亚洲一区二区视频| 久久躁狠狠躁夜夜爽| 在线观看精品| 欧美日韩成人免费| 亚洲午夜小视频| 看欧美日韩国产| 一本色道久久综合亚洲精品不卡| 欧美日韩免费一区二区三区| 亚洲综合色自拍一区| 久久久久国产精品厨房| 亚洲国产精品一区制服丝袜| 欧美了一区在线观看| 亚洲视频在线一区| 久久免费视频在线观看| 亚洲精品欧美一区二区三区| 国产精品欧美日韩| 美国十次了思思久久精品导航| 亚洲精选视频免费看| 欧美一区二区三区视频在线| 在线电影国产精品| 欧美日韩在线播放三区四区| 欧美一区二区三区在线观看视频| 亚洲国产99精品国自产| 欧美一区二区精品久久911| 亚洲高清av在线| 国产精品久久久久一区二区三区共 | 亚洲一区免费看| 亚洲第一黄网| 亚洲夜晚福利在线观看| 老司机精品视频网站| 国产精品99久久久久久久久久久久| 国产视频丨精品|在线观看| 欧美精品午夜| 久久久国产精品一区二区中文 | 亚洲国产精品久久91精品| 欧美专区亚洲专区| 在线视频亚洲一区| 亚洲国产欧美精品| 韩国成人理伦片免费播放| 国产精品久久久久99| 欧美高清成人| 久久久久久夜| 欧美一区二区视频在线观看| 中文在线不卡| 亚洲欧洲在线一区| 欧美h视频在线| 久久久天天操| 久久国产手机看片| 午夜精品久久久久久99热| 国产精品99久久久久久有的能看| 亚洲成色www8888| 一区二区三区自拍| 国产日韩欧美精品在线| 国产精品视频xxxx| 欧美视频一区在线观看| 欧美日本在线观看| 欧美黄在线观看| 欧美成人在线免费观看| 免费高清在线视频一区·| 久久偷看各类wc女厕嘘嘘偷窃| 久久xxxx精品视频| 欧美一区在线直播| 欧美一区二区三区视频免费| 销魂美女一区二区三区视频在线| 亚洲综合清纯丝袜自拍| 午夜精品久久| 久久国产毛片| 久久免费视频网| 免费短视频成人日韩| 欧美国产日本高清在线| 欧美精品一区三区| 欧美日韩不卡视频| 国产精品久久久久99| 国产伦精品一区二区| 国产一二三精品| 在线免费不卡视频| 亚洲黄页视频免费观看| 亚洲精品网站在线播放gif| 日韩视频在线免费观看| 国产精品99久久久久久宅男| 亚洲免费一在线| 久久成人免费视频| 免费不卡视频| 亚洲国产日韩欧美在线99| 日韩网站在线观看| 亚洲欧美一区在线| 快射av在线播放一区| 欧美日本不卡| 国产日韩精品一区二区三区| 伊人久久av导航| 一区二区高清视频| 欧美在线看片| 亚洲激情视频网| 亚洲欧美激情四射在线日| 久久米奇亚洲| 国产精品啊啊啊| 影音先锋中文字幕一区二区| 中文一区字幕| 久久亚洲精品伦理| 一区二区三区www| 狂野欧美激情性xxxx| 国产精品久久网| 亚洲人成啪啪网站| 欧美在线播放一区二区| 亚洲高清免费视频| 欧美一二三区精品| 欧美日韩国产小视频| 在线播放国产一区中文字幕剧情欧美| 日韩午夜中文字幕| 久久深夜福利免费观看| 午夜综合激情| 亚洲毛片在线看| 久久―日本道色综合久久| 国产精品区免费视频| 亚洲精品美女在线观看播放| 久久精品国产成人| 夜夜夜精品看看| 欧美国产日产韩国视频| 影音国产精品|