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 留给另一个词呢？程序如何知道叶子对于其他单词是否正确？我应该制作一个指针数组还是应该用不同的方法重新开始？ TIA

my trie node sketch

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 和零不一定是同一件事，但它可能是，并且对于快速原型来说很好）。

因此节点最初将标志设置为零。在插入中，我在字符串的末尾将标志设置为 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;
}

C中的Trie机制

Trie mechanism in C

c

data-structures

trie