c++ - 为什么会有单独的 "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(或其他数据结构，例如链表)只是一个想法，实现可能会有所不同。

例如，链表可以实现为数组(将下一项的索引保存为链接并为最后保存一个特殊数字)或节点类型和列表类型，其中列表类型包含指向头的指针。前一个实现可能易于理解、实现和调试，而后一个实现更好地利用动态分配。一种实现可能适用于一个目的，但可能不适用于其他目的。