c - C 中基本基数特里树的实现

Question

我目前正在实现 here 描述的算法(维基百科)。
文章描述了2个主要结构:

• 一个节点，包含边数组
• 一条边，包含指向目标节点的指针和标签

所以，目前我的 C 代码中有 2 个结构:radix_node_s 和 radix_edge_s

typedef struct radix_node_s radix_node_t;

typedef struct radix_edge_s {
    radix_node_t                *target_node;
    char                        *label;

    SLIST_ENTRY(radix_edge_s)   next;
} radix_edge_t;

struct radix_node_s {
    SLIST_HEAD(radix_edge_list_s, radix_edge_s) edges;
    void                                        *data;
};

我想知道是否可以使边缘结构消失并将其包含与其目标节点合并。因此，边缘标签将是节点的一个新字段。

这是一个很好的方法吗？还是我错过了什么？

Answer 1

好吧，如果边的标签与源节点或目标节点的标签相同，则只需将边结构更改为指向节点的指针，无需复制数据。

但如果它是边的名称，并且节点可能具有不同名称的边，那么您确实需要边的数据“元组”:目标和名称。使用 C 处理此问题的最佳方法是使用边缘结构。

这样说只是为了以防万一，也许它已经是这样了(不知道 SLIST_* 是什么):由于您的结构很小，因此您应该将其用作值类型。也就是说，不是具有指向边缘结构的指针数组或边缘结构的链接列表，而是具有指向边缘结构值数组的指针。即使您需要调整小结构数组的大小，对于现代处理器来说，它仍然比通过指针数组保留链表或额外的间接寻址要高效得多。