具有多个父节点和子节点的链表 [英] Linked list with multiple parent and child nodes

问题描述

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

I am trying to design a program that takes in data from a file, after which it gives numbering to unique data, linked list also contains parent and child lists.

数据结构:

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

节点可以有多个下一个节点(例如 A 和 C)，并且可以有多个前一个节点.

The nodes can have more than one next nodes (e.g. A and C), and can have more than one previous nodes.

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

The text file contains the data like this, i'll get the data from file and turn them into linked list:

                    A
                    B
                    E
                    I

                    A
                    C
                    E
                    F
                    J

                    A
                    C
                    G
                    K

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

My Question: Is it possible to create linked list with nodes with more than one next or more than one previous nodes, if so how would the struct look like?

我尝试过的:

我创建了一个结构体，其中包含一个由 4 个整数组成的数组，用于父子进程.

I made a struct which contains an array of 4 integers for parent and child.

struct abcd{
 char data;
 int nodeid;

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

 struct abcd *next;

}

所以父数组保存了大多数前一个节点的节点 ID(可以是多个，因为例如 E(B & C 指向它)-->(节点 ID - 1).

So the parent array holds node-id of most previous node (can be more than one since e.g. E (B & C are pointing to it) --> (node-id - 1).

子数组保存即时下一个节点的节点 ID(节点 ID +1).

Child array holds node-id of instant next node (node-id +1).

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

There are no duplicate nodes for A or any other.

输出:

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

希望它很清楚，请让我不知道我应该如何实施它.问候.

Hopefully its clear, please let me no how i should go about implementing it. Regards.

推荐答案

是的，所以这被称为有向图.大约有一千种方法可以实现它.正确"的方式完全取决于你将如何使用它，你没有描述过.由于您似乎确实将其限制为链接列表或双向链接列表，因此我只会使用双向链接列表.

Yes, so this is called a directed graph. And there are about a thousand ways you could implement it. The "right" way depends entirely on how you will use it, which you haven't described. Since you did seem to limit this to linked lists or doubly linked lists I'll just use nothing but doubly linked lists.

前向声明你的数据类型

typedef struct ItemInfo_s ItemInfo;
typedef struct DoubleLinkedListNode_s DoubleLinkedListNode;

像往常一样创建一个 ListNode:

Create a ListNode like you always do:

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

然后创建您的 ItemInfo:

Then create your ItemInfo:

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

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

Also, for sanity's sake create a list of all created nodes:

DoubleLinkedListNode *items;

现在，我不打算写所有的链表管理功能，但我相信你能弄明白.按照惯例，我将 (B) 写为指向项目 B 的节点(node.data = &B).我还将指示用="和-"链接在一起的任何两个节点作为未链接(空值)节点链接.我将写一个元素链 [ -(1)=(2)=(3)- ] 并且按照惯例，指向项目链的指针将始终指向链中的第一个节点(本例中的 (1)).您给定的图形在内存中如下所示:

Now, I'm not going to write all of the linked list management functions, but I'm sure you can figure it out. By convention I'll write (B) as a node pointing to item B (node.data = &B). I'll also indicate any two nodes linked together with an '=', and a '-' as an unlinked (null valued) node linkage. I'll write a chain of elements [ -(1)=(2)=(3)- ] and by convention pointers into a chain of items will always point to the first node in the chain (the (1) in this example). Your given graph looks like this in memory:

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

In total that is 9 ItemInfos and 27 DoubleLinkedListNodes. I can think of almost no reason I would ever implement this in practice, but it's implemented only using double linked lists. It might make the list management easier to do doubly linked rings (connecting the head and tail of the list together) but that's harder to show in text form. :)

这篇关于具有多个父节点和子节点的链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！