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

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

数据结构：

____A / | BC | / \ E--> FG | | | IJK 

节点可以具有多个下一个节点（例如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; 

现在，我不打算编写所有链表管理function，但我相信你可以搞清楚。 按照惯例，我将（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。 我几乎没有理由想在实践中实现这一点，但它只使用双链表实现。 它可能使列表管理更容易做双重链接环（将列表的头部和尾部连接在一起），但是更难以文本forms显示。 🙂

Answer 2

你可以有这样的结构：

 struct abcd{ char data; struct abcd *next[10]; //array of next nodes struct abcd *prev[10]; //array of previous nodes } 

访问下一个节点时，您可以执行node->next[i]而不是node->next ，其中0<= i < 10 。 分配/创建节点时，将所有数组元素重置为NULL以便您不会为未初始化的节点提供垃圾。

因此，假设您为'A'添加了节点，那么您可以为'B'和'C'添加节点

 int idx; //find index for free element. for(idx = 0; nodeA->next[idx] && idx < 10; idx++) ; if(idx == 10) //dont have free space nodeA->next[idx] = nodeB; nodeB->prev[0] = nodeA; //similarly add for C, you may have to check for appropriate idx! nodeA->next[idx++]] = nodeC; nodeC->prev[0] = nodeA; 

基本上，您可以创建最多可包含10个下一个或上一个节点的节点。

数组是为了简单，你也可以做struct abcd **next; 您可以在其中拥有动态数量的next / prev节点。 你必须适当地分配内存。

Answer 3

链接和双向链表是一种特定的有向图 ，可以优化为您熟悉的head/tail ， data/next/prev结构。 由于您正在扩展其function，您将失去这种特异性，并希望回到通用有向图结构并从那里开始工作。

使用邻接列表最容易描述有向图：

您可以使用列表列表，列表数组或锯齿状数组，或者您喜欢的方式实现它。 现在，在右边，我以有向图forms绘制了一个双向链表。 由于next指针与prev指针不同，因此您的邻接列表需要将这些指针分开。 所以它实际上是双列表的列表：

 typedef struct _BPNode { // "Back-Pointing Node" void *data; struct _BPNode *nexts[]; struct _BPNode *prevs[]; } Node; typedef struct _BPGraph { // "Back-Pointing Graph" Node **allNodes; } BPGraph; 

或类似的东西。 免责声明：我没有在编译器中测试它。 为了以防万一， 这里有一个如何阅读那里的一些声明的指南 。

或者，您可以创建两个有向图，一个向前运行，一个向后运行。 但是，这将占用比这个“反向”图更多的内存。 它也会运行得更慢（更多的cpu缓存未命中），不太直观，并且释放内存会更麻烦。

Answer 4

是否可以使用具有多个下一个或多个先前节点的节点创建链接列表，如果是这样，结构将如何显示？

是的，这是可能的 – 你必须问自己的问题是“我如何存储大量数据？” ，简短的回答是“你必须使用ADT” 。 回想一下， ADT是数据集合的数学模型 。

您可以使用任何ADT实现它，特定ADT的选择取决于您计划最常使用的操作。 对于我的例子，我将使用动态数组。 结构将声明如下（省略节点的特定字段）：

 struct llnode { int item; struct llnode *children; int length; int capacity; }; 

…其中项是’A’，’B’，’C’等的ASCII码，而children是指向struct llnode数组的指针。 但是，您可以为动态数组创建一个单独的结构，使其不那么混乱，但这完全取决于您。 同样的想法将适用于父节点。

Answer 5

您可以尝试通过实现指向数据对象的指针列表来将数据与数据结构分开：

 struct data_item { unsigned char data; unsigned char id; unsigned int count; // Whatever other data you want. }; struct list_node { struct data_item *item; struct list_node *next; } 

现在，当我们遇到文件中的字符时，我们将它们插入到“存储库”数据结构中。 对于这个例子，我将使用一个简单的表，但如果你想节省空间，你可以使用一个列表，如果你想节省空间，同时保持快速搜索速度等。

 data_item data_table[UCHAR_MAX + 1] = {0}; ... unsigned char data = read_character_from_file(); struct data_item *di = data_table[data]; if (di == NULL) di = new_data_item(data); else ++di->count; 

并将它们附加到当前列表：

 struct list_node *list; if (first_item_in_list()) list = new_list(di) else list - add_list(list, di); 

现在你可以拥有任意数量的这样的列表（如果你事先不知道列表的数量，甚至是列表列表）。

Answer 6

你所描述的是一个图表 。

（双）链接列表实际上只是一维列表，并且是您想要的不恰当的术语。

实现图表有两种主要方式：

• 邻接列表。 每个节点/顶点都有一个传入和传出边的列表。 就像你描述的那个。
• 邻接矩阵。 n次n矩阵（其中n是节点/顶点的数量），如果节点a具有到b的边，则在[a][b]处具有条目。

使用其中哪些取决于您的使用案例。 根据经验法则：如果你有许多顶点（数万个）并且你可以平均限制每个顶点的边数量，那么你应该使用列表。 在其他用例中，您最好使用矩阵（主要是因为易于实现）。

我假设你的用例仅限于ASCII字母，所以我实际上在这里使用矩阵。 通过适当的优化（位域等），您可以非常快速地浏览它。

您的实现可能如下所示：

 char adj_matrix[0x80][0x80]; // I am assuming that you only have ASCII letters memset(adj_matrix, 0, sizeof(adj_matrix)); // initialise empty 

插入元素会像：

 adj_matrix['A']['C'] = 1; // edge from A --> C 

要确定’A’的所有传入边缘，您必须迭代矩阵：

 for (i = 'A'; i <= 'Z'; i++) if (adj_matrix[i]['A']) // A has an incoming edge from i 

反过来传出

 for (i = 'A'; i <= 'Z'; i++) if (adj_matrix['E'][i]) // E has an outgoing edge to i 

如上所述，您可以使用位域和位扫描指令（例如gcc __builtin_clzll ，icc _bit_scan_reverse ）显着提高空间和时间性能。