狠狠色丁香久久婷婷综合图片 ,久久精品成人免费国产片小草,一本色道久久88加勒比

換了個(gè)地址：http://www.cnblogs.com/vizhen/

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

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

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

圖片示例

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

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

const int KIND=26;//26個(gè)小寫字母
struct Trie
{
     int count;//統(tǒng)計(jì)該字母出現(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 閱讀(789) 評(píng)論(0) 編輯收藏引用所屬分類: 算法學(xué)習(xí)

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

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

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

單鏈DNA

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

導(dǎo)航

統(tǒng)計(jì)

公告

隨筆分類(40)

隨筆檔案(48)

搜索

積分與排名

最新評(píng)論

評(píng)論排行榜