特里樹結構聲明

所以我這一段代碼（這不是我），我無法理解我的生活是什麼這些結構的樣子。有人可以解釋嗎？在第二結構特里樹結構聲明

typedef struct trie_node trie_node_t; 
struct trie_node 
{ 
    int value; 
    trie_node_t *children[ALPHABET_SIZE]; 
}; 

// trie ADT 
typedef struct trie trie_t; 
struct trie 
{ 
    trie_node_t *root; 
    int count; 
};

詮釋計數是用於計數把樹中的所有的話，但我想知道每一個字，多少次擺在那裏，而且除了修改代碼的其餘部分，應該如何我修改結構來實現這一目標？

休息代碼：http://pastebin.com/9zQuCBjb

來源

2014-01-18 deviance

我想你所熟悉的一個線索，在那裏你步行（或爬行，用代碼鏈接的話）查找單詞和單詞的前綴的概念下降根據您找到的字母，樹中包含單詞的字母並在每個節點處分支。每個節點有許多孩子; 26如果你使用不區分大小寫的拉丁字母。

這個詞是在編碼上你到達那裏的路徑：

root->[f]->[i]->[s]->[h] --> "fish"

現在，你需要知道當前節點是否代表一個字。 "fish"是一個詞，但"fis"不是。您不能使用節點是沒有子節點的事實，因爲"fishbone"可能在字典中。這就是value條目的用途：零表示當前節點不表示一個單詞，否則該值是當前單詞的基於一個單詞的索引。

當您創建一個新條目時，您只需向下爬行即可，隨時可以創建新節點，並將當前計數的最後一個節點標記爲值。如果"fishbode"已經在特里和添加"fish"，你不創造新的節點，只標出一個新值"h"節點。

trie struct只是包含trie的根節點和計數的幫助器。

如果要跟蹤出現次數，請將count字段添加到節點，並在設置爲value時增加該字段。（原始代碼不檢查前面的值是否已經存在於樹中，並無條件地添加單詞，從而覆蓋任何舊值。）

您還可以保留以當前節點的前綴開頭的所有單詞的計數通過有一個prefix_count字段並在插入密鑰時通過節點時增加該字段。

當你想取回次出現，你必須走的所有子樹。

嘗試從用戶輸入或T9風格的打字系統的第一個字母中自動展開單詞很有用，但它們相當記憶貪婪。如果您只是想計算單詞的出現次數（不利用單詞樹的好處），使用單個單詞哈希映射來計算單詞可能會更容易。

來源

2014-01-18 07:19:52

謝謝，你介意我問2個問題嗎？首先，void插入函數和「trie_node_t * pCrawl; pCrawl = pTrie-> root;」那是什麼意思？然後在最後，pCrawl-> value = pTrie-> count;我不明白pCrawl在什麼時候成爲我們的樹 – deviance

只有一個特里，但是有許多節點。開始時，trie中有一個節點，在'initialize（）'中創建。然後你沿着trie樹走，「level」是下降的等級（不包括根），這也是你的字符串的索引。走下來是通過'pCrawl = pCrawl-> children [index];'完成的。它就像鏈接列表中的「p = p-> next」，只有在這裏，每個節點有26個子節點，其中一些節點爲NULL。這就是我在括號內的草圖中顯示的內容。（代碼不檢查'CHAR_TO_INDEX'轉換的範圍，並假定char是一個大寫字母。） –

謝謝，我想我現在明白了。所以要添加我想要的，我應該添加「int計數器」typedef結構trie_node trie_node_t;並在void插入結束時，在循環之後和最後一行之前插入「if（pCrawl-> value！= 0）」pCrawl-> counter ++ else將其設置爲1;「對？編輯：它的工作原理：D現在我必須弄清楚其他一些事情，比如如何按字母順序打印所有這些單詞，並找到100個重複次數最多的單詞。 – deviance

特里樹結構聲明

回答

相關問題