我正在尝试设计一个从文件中获取数据的程序,然后为唯一数据编号,链表还包含父列表和子列表。
数据结构:
____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
希望它清楚,请告诉我应该如何实现它。 问候。
最佳答案
是的,所以这叫做有向图。并且有大约一千种方法可以实现它。 “正确”的方式完全取决于你将如何使用它,你没有描述过。由于您似乎确实将其限制为链表或双向链表,所以我只使用双向链表。
转发声明你的数据类型
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。我几乎想不出我会在实践中实现它的原因,但它仅使用双链表实现。做双向链接环(将列表的头部和尾部连接在一起)可能会使列表管理更容易,但更难以文本形式显示。 :)
关于c - 具有多个父节点和子节点的链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18140460/