3

我正在寻找实现如下所示的多级数据结构。

object {
   object A {
          child {
               myChild;
          };
          child 1 {
               mychild;
          };
   };
   object B {
         child {
         };
   };
};

我的方法是使用如下所示的链表来实现这一点。

typedef struct node_s {
    struct node_s *next;
    struct node_s *first_child;
    struct node_s *parent;
    char *text;
} node_t;

将上述列表转换为 STAILQ (sys/queue.h linux) 将是

typedef struct node_s {
    char *text;
    ....;
} node_t;

typedef struct list_s {
    STAILQ_ENTRY(list_s) link;
    node_t *first_child;
    node_t *parent;
    node_t *next;
    int level;
} list_t;

typedef STAILQ_HEAD(list_head_s, list_s) list_head_t;

请建议除了链表或使用链表之外是否还有其他更好的方法来实现这一点？

4

1 回答 1

2

您所代表的结构更像是一棵树而不是链表 - 它是节点的集合，其中每个节点可能有零个或多个子节点，并且除根之外的每个节点都将只有一个父节点。

您使用的表示方案通常称为树的左子、右兄弟表示。它不是让每个节点都存储其子节点的显式列表，而是存储指向其子节点之一的指针，然后通过链表将子节点链接在一起。如链接的问答中所述，这在内存稀缺时具有一些优势，但会增加搜索给定节点的特定子节点所需的时间。

还有许多其他方式可以表示这个结构，这真的取决于你决定如何去做。一种选择是将子项存储在某种以子项名称为键的关联数组结构中（例如，哈希表或平衡二叉搜索树）。这样可以更快地找到给定其名称的特定子项，尽管它确实会增加内存使用量。另一种选择是使用所有子节点的显式数组，而不是通过每个节点的子节点线程化链表，这需要更多的分配，但更容易将子节点附加到给定节点。

希望这可以帮助！

于 2013-05-27T21:18:00.713 回答