0

我目前正在实施此处描述的算法（维基百科）。
本文描述了 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;
};

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

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

4

1 回答 1

1

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

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

说这个以防万一，也许它已经是这样了（不知道是什么SLIST_*）：因为你的结构很小，你应该将它用作值类型。也就是说，不是具有指向边缘结构的指针数组或边缘结构的链表，而是具有指向边缘结构值数组的指针。即使您需要调整小结构数组的大小，与通过指针数组保持链接列表或额外间接相比，现代处理器仍然更有效。

于 2012-12-10T09:16:19.307 回答