I am looking to implement a multi level data structure which looks like as shown below.
我希望实现一个多层次的数据结构，如下所示。
object {
object A {
child {
myChild;
};
child 1 {
mychild;
};
};
object B {
child {
};
};
};
My approach is to implement this using a linked list as shown below.
我的方法是使用一个链接列表来实现它，如下所示。
typedef struct node_s {
struct node_s *next;
struct node_s *first_child;
struct node_s *parent;
char *text;
} node_t;
Converting above list to STAILQ (sys/queue.h linux) will be
将上述列表转换为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;
Please suggest if there is any other better way of implementing this other than a linked list or using linked list?
除了链表或使用链表之外，还有什么更好的实现方法吗?
1 个解决方案
#1
2
The structure that you're representing is more of a tree than a linked list - it's a collection of nodes where each node may have zero or more children, and every node except the root will have exactly one parent.
您所表示的结构更像是一个树而不是一个链表——它是节点的集合，每个节点可能有0或更多的子节点，除了根节点之外的每个节点都有一个父节点。
The representation scheme that you are using is typically referred to as the left-child, right-sibling representation of a tree. Rather than having each node store an explicit list of its children, it stores a pointer to one of its children, and the children are then linked together through a linked list. As mentioned in the linked question and answer, this has some advantages when memory is scarce, but it increases the amount of time required to search for a particular child of a given node.
您正在使用的表示方案通常被称为树的左-子、右-兄弟表示。它不是让每个节点存储其子节点的显式列表，而是存储指向它的一个子节点的指针，然后通过链接列表将子节点链接在一起。正如在链接的问题和答案中提到的，当内存不足时，这有一些好处，但是它增加了搜索给定节点的特定子节点所需的时间。
There are many other ways that you could represent this structure, and it's really up to you do determine how to do it. One option would be to store the children in some sort of associative array structure keyed by the name of the child (for example, a hash table or balanced binary search tree). This would make it much faster to find a specific child given its name, though it does increase the memory usage a bit. Another option would be to use an explicit array of all the children rather than threading a linked list through the children of each node, which requires more allocations but makes it easier to append children to a given node.
你可以用很多其他的方式来表示这个结构，这取决于你怎么做。一种选择是将孩子存储在某种关联数组结构中，以孩子的名字(例如，哈希表或平衡的二叉搜索树)为键。这将使查找给定其名称的特定子节点快得多，尽管它确实增加了一点内存使用。另一种选择是使用所有子节点的显式数组，而不是通过每个节点的子节点对链表进行线程化，这需要更多的分配，但更容易将子节点附加到给定节点。
Hope this helps!
希望这可以帮助!
#1
2
The structure that you're representing is more of a tree than a linked list - it's a collection of nodes where each node may have zero or more children, and every node except the root will have exactly one parent.
您所表示的结构更像是一个树而不是一个链表——它是节点的集合，每个节点可能有0或更多的子节点，除了根节点之外的每个节点都有一个父节点。
The representation scheme that you are using is typically referred to as the left-child, right-sibling representation of a tree. Rather than having each node store an explicit list of its children, it stores a pointer to one of its children, and the children are then linked together through a linked list. As mentioned in the linked question and answer, this has some advantages when memory is scarce, but it increases the amount of time required to search for a particular child of a given node.
您正在使用的表示方案通常被称为树的左-子、右-兄弟表示。它不是让每个节点存储其子节点的显式列表，而是存储指向它的一个子节点的指针，然后通过链接列表将子节点链接在一起。正如在链接的问题和答案中提到的，当内存不足时，这有一些好处，但是它增加了搜索给定节点的特定子节点所需的时间。
There are many other ways that you could represent this structure, and it's really up to you do determine how to do it. One option would be to store the children in some sort of associative array structure keyed by the name of the child (for example, a hash table or balanced binary search tree). This would make it much faster to find a specific child given its name, though it does increase the memory usage a bit. Another option would be to use an explicit array of all the children rather than threading a linked list through the children of each node, which requires more allocations but makes it easier to append children to a given node.
你可以用很多其他的方式来表示这个结构，这取决于你怎么做。一种选择是将孩子存储在某种关联数组结构中，以孩子的名字(例如，哈希表或平衡的二叉搜索树)为键。这将使查找给定其名称的特定子节点快得多，尽管它确实增加了一点内存使用。另一种选择是使用所有子节点的显式数组，而不是通过每个节点的子节点对链表进行线程化，这需要更多的分配，但更容易将子节点附加到给定节点。
Hope this helps!
希望这可以帮助!