C++中的Trie机制
C++中的Trie机制
提问于 2020-11-13 21:07:50
我完全是个初学者，正在尝试创建一个拼写检查的trie结构。我已经阅读了很多文档，但在理解上仍有差距，如果有人解释，我将不胜感激。抱歉，我的问题看起来像菜鸟，但我基本上是菜鸟。
#include <stdio.h>
#include <stdlib.h>
#define LENGTH 45
#define N 27
char word[LENGTH + 1];
typedef struct trie
{
char data; //letter(character)
struct trie* child[N]; //array of pointers to the next trie
int leaf; //is word ending here
}trie;对于所有新的尝试，我将int leaf设置为0。当我完成插入单词时，我将int leaf更改为1，这样我就可以知道我正在检查的单词是否在那里。
如果我把那个leaf = 1换成了另一个单词呢？程序如何知道叶子对于其他单词是否为真？我应该创建一个指针数组，还是应该用一种不同的方法重新开始？提亚
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-11-13 23:15:10
我快速浏览了一下您的结构，并尝试实现了一个快速而肮脏的插入和查找。我把“叶子”的名字改成了“标志”，因为它不是叶子，而是一个标志，表明我们有一个单词，而不是一些前缀。
#define N 26
typedef struct trie {
char data;
struct trie* children[N];
int flag;
} trie;
// all zero data...
trie TRIE_TEMPLATE;
#define edge_idx(c) (c - 'a')
trie *next(trie *node, char c)
{
trie *n = node->children[edge_idx(c)];
if (!n) {
// no such edge yet...
n = malloc(sizeof *n);
if (!n) abort(); // error handling
*n = TRIE_TEMPLATE;
n->data = c;
node->children[edge_idx(c)] = n;
}
return n;
}
void insert(trie *root, char const *word)
{
trie *n = root;
for (char const *c = word; *c; c++) {
n = next(n, *c);
}
n->flag = 1; // tag final node as a word
}
int contains(trie *root, char const *word)
{
trie *n = root;
for (char const *c = word; *c; c++) {
n = n->children[edge_idx(*c)];
if (!n) return 0;
}
return n->flag;
}我没有很好地测试它，所以不要相信它，但正如您所看到的，我使用了一个全为零的模板节点(全局变量)来初始化新节点。这会将数据、子项和标志设置为零。(它不符合标准，因为NULL和零不一定是一回事，但它可能是一回事，对于快速原型来说，它是很好的)。
因此，节点最初将标志设置为零。在插入中，我在字符串的末尾将标志设置为1，因此只有最后一个节点才会获得标志。不是通向那里的任何节点。如果我们插入一个现有节点的前缀，我们不会创建新的节点，而是在适当的节点中设置标志。如果我们添加一个单词，其中trie已经有一个前缀，它将不会修改现有的节点。
至少，这是它应该是如何工作的，通过这个快速测试，它是我所看到的：
int main(void)
{
trie root = TRIE_TEMPLATE;
insert(&root, "foo");
insert(&root, "bar");
printf("fo %s in trie\n",
contains(&root, "fo") ? "is" : "is not");
printf("foo %s in trie\n",
contains(&root, "foo") ? "is" : "is not");
printf("ba %s in trie\n",
contains(&root, "ba") ? "is" : "is not");
printf("bar %s in trie\n",
contains(&root, "bar") ? "is" : "is not");
// bar and baz share a prefix, but that is fine...
printf("baz %s in trie\n",
contains(&root, "baz") ? "is" : "is not");
insert(&root, "baz");
printf("baz %s in trie\n",
contains(&root, "baz") ? "is" : "is not");
// after inserting ba, it is there, and bar and baz are
// also there. It doesn't matter that ba is a prefix
insert(&root, "ba");
printf("ba %s in trie\n",
contains(&root, "ba") ? "is" : "is not");
printf("bar %s in trie\n",
contains(&root, "bar") ? "is" : "is not");
printf("baz %s in trie\n",
contains(&root, "baz") ? "is" : "is not");
// foobar already has a prefix in the trie, foo,
// but when we insert it, that is not a problem.
printf("foobar %s in trie\n",
contains(&root, "foobar") ? "is" : "is not");
insert(&root, "foobar");
printf("foobar %s in trie\n",
contains(&root, "foobar") ? "is" : "is not");
return 0;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/64821476
复制相关文章
相似问题
腾讯云开发者
