日韩视频精品在线,欧美一区日本一区韩国一区,亚洲精品日韩欧美

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

【數據結構】字典樹

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

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

圖片示例

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

結構體定義

const int KIND=26;//26個小寫字母
struct Trie
{
     int count;//統計該字母出現次數
     Trie *next[KIND];//子節點
     Trie()
     {
        count=0;
        for(int i=0;i<KIND;i++)
            next[i]=NULL;
     }
}

操作函數

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

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

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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

單鏈DNA

【數據結構】字典樹

導航

統計

公告

隨筆分類(40)

隨筆檔案(48)

搜索

積分與排名

最新評論

評論排行榜