c - 具有多个父节点和子节点的链表

Question

我正在尝试设计一个从文件中获取数据的程序，然后为唯一数据编号，链表还包含父列表和子列表。

数据结构:

                   ____A
                  /    |     
                 B     C    
                 |  /    \  
                 E-->  F   G
                 |     |   |
                 I     J   K

节点可以有多个下一个节点(例如A和C)，也可以有多个前一个节点。

文本文件包含这样的数据，我将从文件中获取数据并将它们转换为链表:

                    A
                    B
                    E
                    I

                    A
                    C
                    E
                    F
                    J

                    A
                    C
                    G
                    K

我的问题:是否可以创建一个链表，其中的节点有多个下一个节点或多个前一个节点，如果可以的话，结构会是什么样子？

我尝试过的:

我创建了一个结构，其中包含一个由 4 个整数组成的数组，用于父项和子项。

struct abcd{
 char data;
 int nodeid;

 int parent[4];
 int child[4];

 struct abcd *next;

}

因此父数组包含最前节点的节点 ID(可以不止一个，因为例如 E(B 和 C 指向它)--> (node-id - 1) .

子数组包含即时下一个节点的节点ID(节点ID +1)。

A 或任何其他节点都没有重复的节点。

输出:

1 :  A <-- 
2 :  B <-- 1
3    E <-- 2,5
4 :  I <-- 3
5 :  C <-- 1
6 :  F <-- 3
7 :  J <-- 6
8 :  G <-- 5
9 :  K <-- 8

希望它清楚，请告诉我应该如何实现它。问候。

Answer 1

是的，所以这叫做有向图。并且有大约一千种方法可以实现它。 “正确”的方式完全取决于你将如何使用它，你没有描述过。由于您似乎确实将其限制为链表或双向链表，所以我只使用双向链表。

转发声明你的数据类型

typedef struct ItemInfo_s ItemInfo;
typedef struct DoubleLinkedListNode_s DoubleLinkedListNode;

像往常一样创建一个 ListNode:

struct DoubleLinkedListNode_s {
    DoubleLinkedListNode *next;
    DoubleLinkedListNode *prev;
    ItemInfo *data;
};

然后创建您的 ItemInfo:

struct ItemInfo_s {
    DoubleLinkedListNode *children;
    DoubleLinkedListNode *parents;
    ...  /* other item data */
};

此外，为了理智起见，创建一个包含所有已创建节点的列表:

DoubleLinkedListNode *items;

现在，我不会写出所有的链表管理函数，但我相信你能搞定。按照惯例，我将 (B) 写为指向项目 B 的节点 (node.data = &B)。我还将指示用“=”和“-”链接在一起的任何两个节点作为未链接(空值)节点链接。我将编写一个元素链 [ -(1)=(2)=(3)- ] 并且按照惯例，指向项目链的指针将始终指向链中的第一个节点(本例中的 (1) ).您给定的图表在内存中看起来像这样:

items = [ -(A)=(B)=(C)=(E)=(F)=(G)=(I)=(J)=(K)- ]

A.children = [ -(B)=(C)- ]
A.parents = []

B.children = [ -(E)- ]
B.parents = [ -(A)- ]

C.children = [ -(E)=(G)- ]
C.parents = [ -(A)- ]

E.children = [ -(I)=(F)- ]
E.parents = [ -(B)=(C)- ]

F.children = [ -(J)- ]
F.parents = [ -(E)- ]

G.children = [ -(K)- ]
G.parents = [ -(C)- ]

I.children = []
I.parents = [ -(E)- ]

J.children = []
J.parents = [ -(F)- ]

K.children = []
K.parents = [ -(G)- ]

总共有 9 个 ItemInfo 和 27 个 DoubleLinkedListNode。我几乎想不出我会在实践中实现它的原因，但它仅使用双链表实现。做双向链接环(将列表的头部和尾部连接在一起)可能会使列表管理更容易，但更难以文本形式显示。 :)