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

A Za, A Za, Fighting...

堅信:勤能補拙

[zz] Trie樹|字典樹的簡介及實現


Trie,又稱字典樹、單詞查找樹,是一種樹形結構,用于保存大量的字符串。它的優點是:利用字符串的公共前綴來節約存儲空間。
相對來說,Trie樹是一種比較簡單的數據結構.理解起來比較簡單,正所謂簡單的東西也得付出代價.故Trie樹也有它的缺點,Trie樹的內存消耗非常大.當然,或許用左兒子右兄弟的方法建樹的話,可能會好點.

其基本性質可以歸納為:
1. 根節點不包含字符,除根節點外每一個節點都只包含一個字符。
2. 從根節點到某一節點,路徑上經過的字符連接起來,為該節點對應的字符串。
3. 每個節點的所有子節點包含的字符都不相同。

其基本操作有:查找 插入和刪除,當然刪除操作比較少見.我在這里只是實現了對整個樹的刪除操作,至于單個word的刪除操作也很簡單.

搜索字典項目的方法為:

(1) 從根結點開始一次搜索;

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



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

 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 閱讀(236) 評論(0)  編輯 收藏 引用 所屬分類: G_其他

導航

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

統計

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            宅男噜噜噜66一区二区66| 99re亚洲国产精品| 久久久福利视频| 欧美在线短视频| 亚洲国产成人久久综合| 亚洲黄色一区| 国产精品久久久久久妇女6080| 欧美一区91| 久久综合伊人77777蜜臀| 一区二区三区日韩欧美精品| 亚洲一区二区3| 在线视频成人| 99热精品在线| 今天的高清视频免费播放成人| 欧美国产日韩在线| 欧美日韩中文在线观看| 久久久国产一区二区| 欧美电影在线观看完整版| 亚洲午夜精品一区二区| 久久国产日本精品| 亚洲视频在线二区| 久久激情五月激情| 亚洲图片欧洲图片av| 久久久中精品2020中文| 亚洲自拍偷拍一区| 久久人人爽人人| 亚洲欧美在线看| 欧美国产在线观看| 久久手机免费观看| 国产精品久久久久77777| 欧美激情亚洲另类| 国产欧美韩日| 一区二区三区蜜桃网| 在线观看欧美日韩国产| 亚洲欧美日韩在线播放| 99成人在线| 久热精品视频在线| 久久久久久97三级| 国产精品久久久久久久免费软件| 欧美成人免费小视频| 国产视频在线一区二区| 亚洲无线视频| 亚洲欧美不卡| 欧美日韩极品在线观看一区| 欧美二区乱c少妇| 好吊成人免视频| 午夜精品久久久久久久99水蜜桃 | 免播放器亚洲| 久久精品欧美日韩| 国产精品午夜av在线| 99pao成人国产永久免费视频| 亚洲国产一区视频| 久久亚洲精品伦理| 欧美成人亚洲| 亚洲国产欧美一区二区三区同亚洲| 欧美一区二区成人| 篠田优中文在线播放第一区| 欧美日韩亚洲一区在线观看| 日韩一二三区视频| 亚洲视频999| 欧美网站在线| 中文国产一区| 亚洲欧美一区二区三区极速播放| 欧美日韩在线一区二区| 99精品视频免费全部在线| 亚洲视频综合| 国产精品久久久久久亚洲毛片| 99精品国产福利在线观看免费| 亚洲天堂av在线免费| 国产精品久久国产愉拍| 亚洲欧美日韩网| 久久夜色精品| 亚洲片在线观看| 欧美日韩一卡| 亚洲欧美激情视频在线观看一区二区三区 | 亚洲一区视频在线观看视频| 欧美一区二区三区日韩| 国产一区二区三区在线观看免费视频| 午夜精品国产更新| 欧美二区在线看| 亚洲午夜未删减在线观看| 国产精品永久入口久久久| 亚洲欧美日韩国产精品| 女女同性精品视频| 99www免费人成精品| 国产精品中文字幕欧美| 久久久久国色av免费看影院| 亚洲精品久久久久久久久| 亚洲欧美综合网| 伊人色综合久久天天五月婷| 欧美电影免费观看高清完整版| 一区二区三区视频在线看| 久久久999精品视频| 最新亚洲视频| 国产精品综合久久久| 久久久久久91香蕉国产| 一二三区精品| 欧美成人r级一区二区三区| 亚洲一区二区三区三| 雨宫琴音一区二区在线| 国产精品v欧美精品v日韩精品| 久久久久五月天| 亚洲深爱激情| 亚洲国产精品毛片| 久久精品99国产精品日本| 99pao成人国产永久免费视频| 国产麻豆91精品| 欧美精品日韩综合在线| 久久精品视频99| 一本色道久久综合狠狠躁的推荐| 久久综合九色综合网站| 亚洲欧美国产日韩天堂区| 亚洲韩日在线| 国产一区日韩一区| 国产精品日日做人人爱| 欧美精品日日鲁夜夜添| 久久五月激情| 欧美一区午夜精品| 亚洲午夜在线观看| 91久久夜色精品国产九色| 美女脱光内衣内裤视频久久影院 | 亚洲欧洲日产国产网站| 国产一区二区三区高清| 国产精品美女午夜av| 欧美区一区二| 欧美激情精品久久久久| 久久中文字幕导航| 久久视频在线看| 久久成人亚洲| 久久精品国产精品亚洲综合| 亚洲性色视频| 亚洲综合色网站| 亚洲综合欧美日韩| 亚洲一区在线播放| 亚洲欧美日韩网| 亚洲欧美日韩国产成人精品影院| 亚洲视屏在线播放| 亚洲一区二区免费| 亚洲综合色自拍一区| 亚洲一区欧美激情| 欧美一级片在线播放| 欧美一区二区视频在线观看| 欧美一区亚洲二区| 久久精品一区蜜桃臀影院| 久久久久国产精品厨房| 久久亚洲捆绑美女| 免费在线观看成人av| 欧美日本一区二区三区| 欧美新色视频| 国产欧美亚洲精品| 激情久久久久久久| 亚洲国产精品久久91精品| 亚洲国产精品成人一区二区| 亚洲精品久久久久久久久久久| 99视频国产精品免费观看| 亚洲午夜精品网| 久久9热精品视频| 麻豆乱码国产一区二区三区| 欧美韩日精品| 一道本一区二区| 欧美中文日韩| 欧美激情中文不卡| 国产精品人成在线观看免费| 国产有码在线一区二区视频| 在线观看视频免费一区二区三区 | 狠狠色综合网站久久久久久久| 在线观看中文字幕不卡| 亚洲精品一区中文| 久久er精品视频| 欧美护士18xxxxhd| 亚洲网站在线播放| 久久综合九色九九| 欧美亚日韩国产aⅴ精品中极品| 国产一区二区三区最好精华液| **网站欧美大片在线观看| 亚洲午夜久久久久久久久电影网| 久久精品噜噜噜成人av农村| 91久久综合| 久久精品中文字幕一区二区三区| 欧美精品成人一区二区在线观看 | 香蕉成人久久| 亚洲电影在线| 亚洲欧美在线一区| 欧美激情精品久久久久久蜜臀 | 一区二区在线观看av| 一区二区三区欧美在线观看| 久久久精品视频成人| 一本久久知道综合久久| 久久天天躁狠狠躁夜夜av| 国产精品你懂的在线欣赏| 亚洲三级电影全部在线观看高清| 欧美制服丝袜第一页| 亚洲精品一区久久久久久| 久久精品99国产精品酒店日本| 国产精品成人国产乱一区| 91久久亚洲| 久久夜精品va视频免费观看| 亚洲自拍另类| 欧美亚洲成人网| 一区二区三区欧美在线观看|