特里树结构声明

所以我这一段代码（这不是我），我无法理解我的生活是什么这些结构的样子。有人可以解释吗？在第二结构特里树结构声明

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

特里树结构声明

回答

相关问题