亚洲激情第一区,国产日韩高清一区二区三区在线,国产精品jizz在线观看美国

換了個地址：http://www.cnblogs.com/vizhen/

【數(shù)據(jù)結(jié)構(gòu)】字典樹

字典樹概念   Trie，又稱單詞查找樹，是一種樹形結(jié)構(gòu)，是哈希樹的變種。
   典型應(yīng)用：于統(tǒng)計和排序大量的字符串（但不僅限于字符串），所以經(jīng)常用于搜索引擎系統(tǒng)用于文本詞頻的統(tǒng)計。
   優(yōu)點(diǎn)：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。

字典樹性質(zhì)1.根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個節(jié)點(diǎn)都只包含一個字符。
2.從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對應(yīng)的字符串。
3.每一個節(jié)點(diǎn)所包含的字符都不相同。

圖片示例

單詞：abcd，bcd，efg，hii構(gòu)建的字典樹示例

結(jié)構(gòu)體定義

const int KIND=26;//26個小寫字母
struct Trie
{
     int count;//統(tǒng)計該字母出現(xiàn)次數(shù)
     Trie *next[KIND];//子節(jié)點(diǎn)
     Trie()
     {
        count=0;
        for(int i=0;i<KIND;i++)
            next[i]=NULL;
     }
}

操作函數(shù)

void InsertNode(TreeNode *&root,char *word)//向root根節(jié)點(diǎn)插入字符串word
{
    TreeNode *location=root;
    int i=0,branch=0;

    if (location==NULL)
    {
        location=new TreeNode();
        root=location;
    }

    while(word[i])
    {
        branch=word[i]-'a';

        if (location->next[branch])
        {
            location->next[branch]->count++;
            //如果該字符存在，串?dāng)?shù)量加1
        }
        else
        {
            //不存在則建立新節(jié)點(diǎn)
            location->next[branch]=new TreeNode();
        }
        i++;
        location=location->next[branch];
    }
}

//查找  與插入類似
int SeacrhWord(TreeNode *root,char *word)
{
    TreeNode *location=root;
    int i=0,branch=0;
    int ans;

    if (location==NULL)
    {
        return 0;
    }

    while(word[i])
    {
        branch=word[i]-'a';
        if (!location->next[branch]) return 0;
        i++;
        location=location->next[branch];
        ans=location->count;
    }
    return ans;
}

posted on 2010-10-24 18:13 Geek.tan 閱讀(803) 評論(0) 編輯收藏引用所屬分類: 算法學(xué)習(xí)

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 【數(shù)據(jù)結(jié)構(gòu)】字典樹 [轉(zhuǎn)載]樹狀數(shù)組 ACM競賽菜鳥入門指南（四）--貪心算法 ACM菜鳥入門學(xué)習(xí)指南（三）--分治算法 0-1背包問題--動態(tài)規(guī)劃解法 ACM競賽學(xué)習(xí)菜鳥入門指南（一）：認(rèn)識OJ與熟悉語言頂點(diǎn)著色的Welch Powell方法

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

單鏈DNA

【數(shù)據(jù)結(jié)構(gòu)】字典樹

導(dǎo)航

統(tǒng)計

公告

隨筆分類(40)

隨筆檔案(48)

搜索

積分與排名

最新評論

評論排行榜