C中的Trie机制

Question

我完全是初学者，并试图为拼写检查创建一个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留给另一个词怎么办？程序如何知道叶子对于其他单词是否为真？我应该制作一个指针数组还是应该用不同的方法重新开始？蒂亚

我的Trie节点草图

Answer 1

我快速浏览了您的结构，并尝试实现快速而肮脏的插入和查找。我将名称"leaf"改为"flag"，因为它不是叶子，而是一个标志，表明我们有一个单词，而不是一些前缀。

#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 和 0 不一定是一回事，但它可能是，对于快速原型来说，它很好)。

因此，节点最初将标志设置为零。在插入中，我将字符串末尾的标志设置为 1，因此只有最终节点才能获得标志。不是通往那里的任何节点。如果我们插入现有节点的前缀，我们不会创建新节点，而是在适当的节点中设置标志。如果我们添加一个单词，其中trie已经有前缀，它不会修改现有节点。

至少，这就是它应该工作的方式，通过这个快速测试，这就是我所看到的：

int main(void)
{
trie root = TRIE_TEMPLATE;
insert(&root, "foo");
insert(&root, "bar");
printf("fo %s in trien",
contains(&root, "fo") ? "is" : "is not");
printf("foo %s in trien",
contains(&root, "foo") ? "is" : "is not");
printf("ba %s in trien",
contains(&root, "ba") ? "is" : "is not");
printf("bar %s in trien",
contains(&root, "bar") ? "is" : "is not");
// bar and baz share a prefix, but that is fine...
printf("baz %s in trien",
contains(&root, "baz") ? "is" : "is not");
insert(&root, "baz");
printf("baz %s in trien",
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 trien",
contains(&root, "ba") ? "is" : "is not");
printf("bar %s in trien",
contains(&root, "bar") ? "is" : "is not");
printf("baz %s in trien",
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 trien",
contains(&root, "foobar") ? "is" : "is not");
insert(&root, "foobar");
printf("foobar %s in trien",
contains(&root, "foobar") ? "is" : "is not");
return 0;
}