Возникают проблемы с пониманием определения связанного списка

Question

У меня есть несколько вопросов относительно определения связанного списка, как он был определен в моем классе.

Вот что использовалось:

typedef struct node_t {
int x;
struct node_t *next;
} *Node;

Теперь я понимаю, что такмы создали более короткий способ использовать указатели на структуру node_t.Node будет использоваться как struct node_t*.

Теперь, скажем, мы хотим создать связанный список.Например:

Node node1 = malloc(sizeof(*node1));
Node node2 = malloc(sizeof(*node2));
Node node3 = malloc(sizeof(*node3));
node1->x = 1;
node1->next = node2;
node2->x = 4;
node2->next = node3;
node3->x = 9;
node3->next = NULL;

Это примерно так, как я себе представляю (круги обозначают структуры):

Теперь я знаю, что это неправильно, но яне могу понять почему.У нас есть указатель node1, который указывает на нашу структуру.Затем мы указываем на node2, который указывает на другую структуру и т. Д. И т. П.

Другое дело, я не могу понять, как можно иметь более длинные стрелки на рисунке.Разве мы не должны иметь возможность указывать только на структуру из каждой нижней части круга, а не указатель на структуру?Как это возможно?

Если бы кто-нибудь здесь мог немного прояснить ситуацию, это было бы очень признательно.Большое спасибо.

Answer 1

У вас есть три связанных узла и дополнительные локальные указатели, указывающие на них.
Тем не менее узлы ничего не знают об этих локальных указателях, даже если часто их имена используются для ссылки на узлы.
Вместо этого они знают следующий узел в последовательности, соответственно, последний узел не знает ни одного.

Другими словами, ваше изображение выровнено неправильно.

          +---+------+
node1 --> | 1 | next |
          +---+-|----+
                |
                v
          +---+------+
node2 --> | 4 | next |
          +---+-|----+
                |
                v
          +---+------+
node3 --> | 9 | NULL |
          +---+------+

Answer 2

Назначение является переходной операцией.Итак,

node1->next = node2;

будет означать, что node1->next указывает на то, на что node2 указывает.И, в частности, node1->next не указывает на node2.

Каждый из node1, node2 и node3 называет переменную, которая является указателем.

node1       node2       node3
+---+       +---+       +---+
| * |       | * |       | * |
+ | +       + | +       + | +
  v           v           v
+---+---+   +---+---+   +---+---+
| 1 | * --> | 4 | * --> | 9 | * --> NULL
+---+---+   +---+---+   +---+---+

Answer 3

typedef struct node_t {
    int x;
    struct node_t *next;
} *Node;                   /* <-- don't typedef pointers */

Просто используйте Node вместо Node * и выделите с помощью:

Node *node1 = malloc(sizeof(*node1));

Почему? Кто-то, глядя на ваш код на 100 строк ниже объявления вашего typedef, по сути не будет знать, является ли Node типом, или это указатель на тип . Этот тип путаницы будет только расти по мере увеличения размера вашего кода. Обзор: Это хорошая идея typedef указатели? .

( примечание: хорошая работа с использованием разыменованного указателя для установки размера в sizeof)

Связанный список

Связанный список - это просто умная структура данных, которая позволяет выполнять итерацию по нескольким независимо распределенным узлам. Каждый узел содержит некоторое значение data, а затем указатель на следующий узел в списке или NULL, если этот узел является последним узлом в списке.

(для двусвязного списка вы просто добавляете указатель prev, который также указывает на узел перед текущим узлом в списке. У вас также есть циклический список, куда последний узел указывает назад к первой разрешающей итерации от любого узла к любому другому узлу в списке независимо от того, с какого узла вы начинаете итерацию. Для двусвязного кругового списка вы можете перебирать весь список в обоих направлениях от любого узла)

В вашем случае ваш список просто:

     node1    +-> node2    +-> node3
    +------+  |  +------+  |  +------+
    | data |  |  | data |  |  | data |
    |------|  |  |------|  |  |------|
    | next |--+  | next |--+  | next |---> NULL
    +------+     +------+     +------+

Где ваш data представляет собой одно целочисленное значение, а указатель next просто содержит адрес следующего узла в вашем списке, или NULL, если это последний узел в списке. При добавлении ваших данных ваш список будет:

     node1    +-> node2    +-> node3
    +------+  |  +------+  |  +------+
    |   1  |  |  |   4  |  |  |   9  |
    |------|  |  |------|  |  |------|
    | next |--+  | next |--+  | next |---> NULL
    +------+     +------+     +------+

При создании списка первый узел обычно называется заголовком списка, а последний узел хвостом списка. Вы всегда должны сохранять указатель на заголовок вашего списка, так как этот указатель содержит начальный адрес списка. Для эффективной вставки в список также неплохо сохранить указатель на узел tail , чтобы вы могли просто вставить новый узел, не просматривая список, чтобы каждый раз находить последний узел, например:

Node *newnode = malloc(sizeof(*newnode));   /* allocate */
newnode->next = NULL;                       /* initialize next NULL */
tail->next = newnode;                       /* assign to tail */
tail = newnode;                             /* set new tail at newnode */

Списки являются фундаментальными для C, многие из них используются в самом ядре Linux. Потратьте время, чтобы понять их и как написать их в разных вариантах. Вы будете рады, что сделали. Наконец, не забудьте написать простую функцию, чтобы освободить ваш список, когда вы закончите (и освободите data также, если он выделен). Простая функция free_list:

void free_list (Node *list) 
{
    while (list) {
        Node *victim = list;    /* separate pointer to node to free    */
        list = list->next;      /* can you see why you iterate next... */
        free (victim);          /* before you free the victim node?    */
    }
}

Дайте мне знать, если у вас есть дополнительные вопросы.