Генерация списка ссылок с помощью malloc ()

Question

Как malloc используется при создании связанного списка?Я не вижу, как он используется для создания новых связанных списков, а не резервирует память для связанных списков

Совет: нажмите Ctrl + F и найдите «(***)» (безкавычки), чтобы найти точное местоположение кода

Пример 1:

#include <stdio.h>
#include <stdlib.h>

struct LinkedList {
    int data;                   /* The data part of the linked list */
    struct LinkedList *next;    /* The pointer part of the linked list */
};  

int main(void) {

    /* Generate the 1st node ("head")  */
    struct LinkedList *head     /* I am not sure what this pointer */  
    head = NULL;                /* is doing to the struct*/
    head = malloc(sizeof(struct LinkedList));   /* Head points to null. Now
                                                 * malloc() is being called  
                                                 * and is assigned to head. 
                                                 * Next line implies head is 
                                                 * already pointing to a 
                                                 * linked list, which means 
                                                 * malloc() is making a new 
                                                 * strucuture (***) */

    /* Generate the second node */
    head -> data = 1; // This implies head is already pointing to a linked list
    head -> next = malloc(sizeof(struct LinkedList));

    /* Generate the third node */
    head -> next -> data = 2;
    head -> next -> next = malloc(sizeof(struct LinkedList));

    /* Generate the fourth node */

    head -> next -> next -> data = 3;
    head -> next -> next -> next = NULL;

    return 0;
}

Пример 2:

#include<stdio.h>
#include<stdlib.h>

struct LinkedList {
    int data;
    struct LinkedList *next;
}; // notice the semi-colon!


int main(void) {

    struct LinkedList *head = NULL;     /* why is it doing this? */
    struct LinkedList *second = NULL;
    struct LinkedList *third = NULL;

    // Generate the node structure:
    /* how does (struct LinkedList*) affect malloc? (***) */
    head = (struct LinkedList*)malloc(sizeof(struct LinkedList));
    second = (struct LinkedList*)malloc(sizeof(struct LinkedList));
    third = (struct LinkedList*)malloc(sizeof(struct LinkedList));

    // Now fill the first node with info:
    head->data = 1;         /* assign data to the first node */
    head->next = second;    /* Link the first node ("head") with the second 
                             * node ("second") */

    // Now fill the second node with info:
    second->data = 2;       /* assign data to the second node */
    second->next = third;   /* Link the second node to the third node */

    // Now fill the second node with info:
    third->data = 3;        /* assign data to the second node */
    third->next = NULL;     /* Since node 3 is our last node to the link list, 
                             * we give it the value of NULL */

    return 0;
}

В учебнике описан список ссылок как цепочечная структура.Malloc () используется для динамического управления памятью.Однако malloc используется для объявления новой структуры в этих примерах, и я не понимаю, почему.Я думал, что он только резервирует память

Например, в примере 1 malloc () резервирует пространство для структуры, но не «создает» его (struct LinkedList var создаст новый связанный список и сохранит его вvar)

Например, в примере 2 похоже, что на malloc () влияет (struct LinkedList*) (то есть (struct LinkedList*)malloc(sizeof(struct LinkedList));), но я не уверен

Answer 1

Вы можете посмотреть на связанный список, как на коробках, связанных друг с другом:

 ______        ______        ______
| data |      | data |      | data |
|______|      |______|      |______|
| next |      | next |      | next |
|______|----->|______|----->|______|----->NULL

Где каждая коробка ваша:

struct LinkedList
{
    int data; /* The data part of the linked list */
    struct LinkedList *next; /* The pointer part of the linked list */

};

Размер ваших "коробок" (зависитпо арке) давайте возьмем x64 машинку Linux равную 16 байтам.Для создания типа данных связанного списка вам необходимо сохранить эти поля в памяти (стек / куча) и соединить их.

Как я заметил, размер одного байта составляет 16 байт, и он должен храниться в памяти.Для управления памятью в пользовательском пространстве вы можете использовать malloc(), важная вещь здесь malloc() ничего не «объявляет» это выделять только часть памяти для вашего одного «ящика» в куче, и вы запрашиваете ровно 16 байтов для вашего «ящика» с помощью оператора sizeof().

struct LinkedList *head = malloc(sizeof(struct LinkedList));

Он выделяет память для вашего «ящика» итеперь это выглядит так:

 ______ 
| data |
|______|
| next |
|______|----->NULL

Когда вы делаете это:

head->next = malloc(sizeof(struct LinkedList));

Вы выделяете память для другой "коробки" и соединяете их:

 ______        ______  
| data |      | data |      
|______|      |______|      
| next |      | next |      
|______|----->|______|

Когда вы делаете это:

struct LinkedList *head = malloc(sizeof(struct LinkedList));     
struct LinkedList *second = malloc(sizeof(struct LinkedList));
struct LinkedList *third = malloc(sizeof(struct LinkedList));

Вы создаете три "коробки" где-то в памяти по 16 байт каждый.И они пока не подключены, они только расположены в памяти;

   head         second      third
  ______        ______      _____
 | data |      | data |    | data |
 |______|      |______|    |______|   
 | next |      | next |    | next |
 |______|      |______|    |______|

И вы подключили их, делая это:

head->next = second;
second->next = third;
third->next = NULL;

 head          second        third
 ______        ______        ______
| data |      | data |      | data |
|______|      |______|      |______|
| next |      | next |      | next |
|______|----->|______|----->|______|----->NULL

Обычно второй подход используется в функции, как для ex add_node_front()

void add_node_front(struct LinkedList **head_ref, int data) 
{ 
    /* 1. allocate node */
    struct LinkedList *new_node = malloc(sizeof(struct LinkedList)); 

    /* 2. put in the data  */
    new_node->a  = data; 

    /* 3. Make next of new node as head */
    new_node->next = (*head_ref); 

    /* 4. move the head to point to the new node */
    (*head_ref)    = new_node; 
} 

Answer 2

Как malloc используется при создании связанного списка?

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

Из примера 1:

head = malloc(sizeof(struct LinkedList));

Из примера 2:

head = (struct LinkedList*)malloc(sizeof(struct LinkedList));

Единственное отличие состоит в том, что в Примере 2 вы явно приводите результат malloc.Тип возврата malloc - void *, и void * может быть приведен к нужному типу, но в этом нет необходимости, поскольку он будет автоматически преобразован.Так что актерский состав не нужен.На самом деле, нежелательно разыгрывать malloc return.Проверьте это .

Функционально оба примера одинаковы, за исключением последовательности выделения памяти.В примере 1 вы выделяете память для указателя head, затем для указателя head -> next и затем для указателя head -> next -> next.

В примере 2 вы выделяете память для указателя head, second и third, а затем присваиваете second для head -> next и third для head -> next -> next.

---

Дополнительно:

Всегда проверяйте возвращение malloc, например:

head = malloc(sizeof(struct LinkedList));
if (NULL == head) {
    fprintf (stderr, "Failed to allocate memory");
    exit(EXIT_FAILURE);
}

Кроме того, убедитесь, что free динамически выделяется память, как только высделано с этим.Следуйте хорошей практике программирования.

Answer 3

Во втором примере вы также можете выделить память статически:

struct LinkedList head;
struct LinkedList second;
struct LinkedList third;

Затем вам нужно получить доступ с помощью оператора точки:

head.data = 1; //assign data to the first node
head.next = &second;

Вы также можете использовать массив

struct LinkedList nodes[3];
node[0].data = 1;
node[0].next = &node[1];

и т. Д.

Таким образом, команда malloc не является существенной для концепции связанного списка.Но для многих приложений вы не знаете, насколько велик будет ваш связанный список.И элементы и порядок будут меняться во время выполнения.Так что в этом случае динамическое распределение памяти с помощью malloc / free действительно полезно.