国产免费久久精品99re丫y,无码AV中文字幕久久专区,无码AV中文字幕久久专区

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

【數(shù)據(jù)結構】字典樹

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

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

圖片示例

單詞：abcd，bcd，efg，hii構建的字典樹示例

結構體定義

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

操作函數(shù)

void InsertNode(TreeNode *&root,char *word)//向root根節(jié)點插入字符串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++;
            //如果該字符存在，串數(shù)量加1
        }
        else
        {
            //不存在則建立新節(jié)點
            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) 評論(0) 編輯收藏引用所屬分類: 算法學習

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

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

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

單鏈DNA

【數(shù)據(jù)結構】字典樹

導航

統(tǒng)計

公告

隨筆分類(40)

隨筆檔案(48)

搜索

積分與排名

最新評論

評論排行榜