链表多个父和子节点 [英] 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），并且可具有多于一个previous节点
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
我的提问：是否有可能创建一个节点链表与一个以上的一个或一个以上的previous节点，如果是的话会怎么结构的样子
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的最previous 的节点（可以比之一，因为如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.
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
希望其明确的，请让我没怎么，我应该去实现它。
问候。
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屋！
