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

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>
            亚洲天堂久久| 欧美激情日韩| 香蕉成人伊视频在线观看| 国产精品久久久久久久久久免费看| 国产精品99久久99久久久二8| 一本到12不卡视频在线dvd| 欧美午夜一区二区| 午夜在线视频观看日韩17c| 亚洲嫩草精品久久| 亚洲二区免费| 亚洲精品欧美精品| 国产伦精品一区二区三区| 久久婷婷丁香| 欧美日韩精品| 久久久久久久久一区二区| 卡一卡二国产精品| 亚洲小说欧美另类婷婷| 欧美一区二区三区四区夜夜大片| 在线国产精品播放| 一本色道88久久加勒比精品| 国产日韩在线看| 亚洲国产欧美在线人成| 欧美日韩在线观看视频| 久久精品国产精品亚洲精品| 欧美sm视频| 一区二区三区我不卡| 国产日韩欧美二区| 欧美成人高清视频| 国产精品毛片| 亚洲欧洲日产国产网站| 国产麻豆综合| 99精品欧美| 亚洲国产裸拍裸体视频在线观看乱了中文 | 久久久久久69| 亚洲欧美日韩在线| 免费日韩精品中文字幕视频在线| 先锋影音网一区二区| 欧美精品一区二区三区一线天视频 | 久久婷婷色综合| 欧美午夜不卡视频| 欧美成人一区二免费视频软件| 国产精品都在这里| 亚洲精品国精品久久99热| 狠狠色狠狠色综合日日tαg| 亚洲视频观看| 亚洲一本大道在线| 欧美激情亚洲视频| 欧美激情片在线观看| 国产一区99| 亚洲在线网站| 亚洲欧美日韩成人| 欧美日韩午夜剧场| 亚洲精品欧美精品| 日韩视频免费观看高清完整版| 久久精品久久综合| 久久久91精品国产| 国产视频久久| 欧美专区在线观看一区| 久久本道综合色狠狠五月| 国产精品久久久久av| 夜夜嗨av一区二区三区四季av| 亚洲精品偷拍| 欧美精品高清视频| 亚洲美女少妇无套啪啪呻吟| 日韩一区二区免费高清| 欧美精品免费在线| 日韩视频亚洲视频| 亚洲一区二区三区在线视频| 国产精品第三页| 午夜精品久久久久久久99樱桃| 欧美一级欧美一级在线播放| 国产精品午夜视频| 欧美亚洲三区| 媚黑女一区二区| 亚洲精选视频免费看| 欧美精品一区二区三区一线天视频 | 亚洲国产欧美在线| 欧美金8天国| 亚洲新中文字幕| 狠狠色2019综合网| 一本色道久久加勒比88综合| 亚洲一区二区三区免费视频| 国产精品日韩欧美| 久久影音先锋| 99pao成人国产永久免费视频| 亚洲在线视频免费观看| 国产欧美日韩在线观看| 噜噜噜91成人网| 99精品国产在热久久| 久久精品国产精品亚洲| 亚洲国产成人在线播放| 欧美日韩在线一区| 久久精品欧洲| 99这里只有精品| 两个人的视频www国产精品| 亚洲日本aⅴ片在线观看香蕉| 欧美日韩国产999| 欧美在线播放| 亚洲欧洲精品一区二区三区不卡 | 日韩一级片网址| 久久久www成人免费精品| 亚洲精选一区| 国内精品久久久久影院色| 欧美激情一区二区| 午夜精品久久久久久久久| 欧美激情精品久久久六区热门| 亚洲永久免费av| 亚洲高清视频的网址| 国产麻豆日韩| 欧美三日本三级少妇三2023| 久久久久久久久久久一区 | 亚洲精品之草原avav久久| 久久精品系列| 亚洲综合电影| 亚洲美女啪啪| 亚洲国产精品一区制服丝袜| 国产精品一区视频网站| 欧美剧在线免费观看网站| 久久久99爱| 欧美一区二区三区在线观看视频| aa级大片欧美| 亚洲精品日韩欧美| 欧美成人免费小视频| 久久精品国产成人| 香蕉乱码成人久久天堂爱免费| 亚洲免费大片| 亚洲美女区一区| 亚洲激情影视| 亚洲国产合集| 亚洲国产人成综合网站| 永久免费精品影视网站| 国产一区日韩一区| 国产婷婷成人久久av免费高清 | 精品成人在线视频| 国产亚洲欧美日韩在线一区| 国产精品日韩一区| 国产精品magnet| 国产精品免费视频xxxx| 国产精品麻豆成人av电影艾秋| 欧美日韩一级片在线观看| 欧美—级a级欧美特级ar全黄| 男同欧美伦乱| 欧美精品在线极品| 欧美日韩国产综合视频在线观看| 欧美顶级大胆免费视频| 国产精品成人观看视频免费| 亚洲一二区在线| 亚洲免费视频在线观看| 亚洲影院色在线观看免费| 亚洲综合激情| 久久精品99无色码中文字幕| 欧美在线视屏| 鲁大师成人一区二区三区| 欧美va日韩va| 亚洲人成网站精品片在线观看| 亚洲精品自在在线观看| 在线一区二区日韩| 香蕉乱码成人久久天堂爱免费 | 国产日韩在线看片| 一区二区三区亚洲| 亚洲国产欧美日韩精品| 一区二区三区视频在线播放| 亚洲欧美日韩国产精品| 久久精品人人做人人综合| 欧美成人精品影院| 亚洲美女视频在线观看| 亚洲欧美韩国| 男人的天堂亚洲| 国产精品久久久久天堂| 狠狠色狠狠色综合| 中文在线一区| 美国成人直播| 一区二区日韩| 久久久久综合网| 欧美午夜免费影院| 亚洲福利国产精品| 亚洲欧美大片| 欧美国产先锋| 午夜国产精品视频免费体验区| 久久免费视频网站| 国产精品成人va在线观看| 在线看片一区| 欧美一区二区精品在线| 亚洲国产精品视频一区| 亚洲一区日韩在线| 欧美不卡高清| 精品88久久久久88久久久| 一区二区三区免费观看| 你懂的视频欧美| 亚洲专区一区| 欧美三级中文字幕在线观看| 好男人免费精品视频| 亚洲综合日韩在线| 亚洲高清免费在线| 久久久久久久999| 国产女同一区二区| 亚洲免费视频在线观看| 亚洲激情专区| 欧美阿v一级看视频| 极品尤物av久久免费看|