为什么有独立的"trie_node“和"trie”结构？

Question

我已经阅读了实现trie的以下实现。

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; 
};

我不明白为什么会有两个结构，而我们只能有一个具有指针数组和一个值类型的结构。请帮帮忙！

Answer 1

短答案

trie_node_t是(链接到一个) trie内部每个节点的类型。

trie_t是每个trie的类型。

使用

可能的用途是

trie_t tr1, tr2;  /* Create 2 tries */

addstring(&tr1, "baseball");   /* This adds multiple nodes to existing trie */
addstring(&tr1, "basketball");

addstring(&tr2, "rock");
addstring(&tr2, "rocket");
addstring(&tr2, "rob");

作者使用2种结构可能是因为它使事物更加模块化和易于管理，并简化了动态分配。

可视化

 +--------+
 |  tr2   |    trie_t
 +---+----+
     |
   +-+-+
   | r |       trie_node_t
   +-+-+
     |
   +-+-+
   | o |       trie_node_t
   +-+-+
    / \
   /   \
+-+-+ +-+-+
| b*| | c |    both trie_node_t
+---+ +-+-+
        |
      +-+-+
      | k*|    trie_node_t
      +-+-+
        |
      +-+-+
      | e |    trie_node_t
      +-+-+
        |
      +-+-+
      | t*|    trie_node_t
      +---+
(* means count is not zero)

终于

Trie (或其他数据结构，例如链接列表)只是一个想法，实现可能有所不同。

例如，链接列表可以实现为数组(将下一项的索引保持为链接并为最后保留一个特定的编号)，或者作为节点类型和列表类型实现，其中列表类型包含指向头的指针。前一个实现可能容易理解、实现和调试，而后面的实现更好地利用了动态分配。一个实现可能对一个目的是好的，而对于另一个目的则可能不那么合适。