Связанный список с несколькими родительскими и дочерними узлами

Да, это называется ориентированным графом. И есть около тысячи способов реализовать это. «Правильный» способ полностью зависит от того, как вы его будете использовать, чего вы не описали. Поскольку вы, похоже, ограничили это связанными списками или двусвязными списками, я просто буду использовать только двусвязные списки.

Вперед объявите ваши типы данных

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. Я не могу придумать почти никаких причин, по которым я когда-либо реализовал бы это на практике, но это реализовано только с использованием списков с двойной связью. Создание двусвязных колец (соединяющих начало и конец списка вместе) могло бы упростить управление списком, но это сложнее отобразить в текстовой форме. :)

У вас может быть такая структура:

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;, где вы можете иметь динамическое количество следующих / предыдущих узлов. Однако вам придется правильно распределить память.

Связанные и двусвязные списки - это особая разновидность направленных графов, которые можно оптимизировать до знакомой вам структуры head/tail, data/next/prev. Поскольку вы расширяете его возможности, вы теряете эту специфичность и хотите вернуться к общей структуре ориентированного графа и работать оттуда.

Ориентированный граф проще всего описать с помощью списка смежности:

Вы можете реализовать это как список списков, или массив списков, или зубчатый массив, или как угодно. Теперь справа я нарисовал двусвязный список в форме ориентированного графа. Поскольку указатели 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;

Или что-то подобное. Отказ от ответственности: я не тестировал это в компиляторе. И на всякий случай вот руководство о том, как читать некоторые из содержащихся там деклараций .

В качестве альтернативы вы можете создать два ориентированных графа: один движется вперед, а другой - назад. Однако для этого потребуется больше памяти, чем для этого «обратного» графика. Он также будет работать медленнее (больше промахов в кеш-памяти процессора), будет менее интуитивно понятным и будет более проблематичным для освобождения памяти.

Можно ли создать связанный список с узлами с более чем одним следующим или более чем одним предыдущим узлом, если да, то как будет выглядеть структура?

Да, это возможно. Вы должны задать себе вопрос: «как мне сохранить достаточно большой объем данных?», а краткий ответ: «вы должны использовать ADT» . Напомним, что ADT - это математическая модель для сбора данных.

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