具有多个父节点和子节点的链接列表

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;

}

因此,父数组保存最前一个节点的node-id (可以是多个,因为例如E(B&C指向它) - >(node-id-1).

子数组包含即时下一个节点(node-id +1)的node-id.

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

OUTPUT:

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个ItemInfos和27个DoubleLinkedListNodes.我几乎没有理由想在实践中实现这一点,但它只使用双链表实现.它可能使列表管理更容易做双链接环(将列表的头部和尾部连接在一起),但是更难以文本形式显示.:)