c - c 中的链表和 MALLOC

Question

我试图理解下面的代码，但在理解为什么运行它时没有段错误时遇到了一些困难。我想我需要使用 malloc 在主函数的开头分配列表？有人可以解释一下列表的内存是如何分配的吗？

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

typedef struct DListElmt_ {

void               *data;
struct DListElmt_  *prev;
struct DListElmt_  *next;

} DListElmt;

typedef struct DList_ {

int                size;

int                (*match)(const void *key1, const void *key2);
void               (*destroy)(void *data);

DListElmt          *head;
DListElmt          *tail;

} DList;

void dlist_init(DList *list, void (*destroy)(void *data));

void dlist_destroy(DList *list);

int dlist_ins_next(DList *list, DListElmt *element, const void *data);

int dlist_ins_prev(DList *list, DListElmt *element, const void *data);

int dlist_remove(DList *list, DListElmt *element, void **data);

#define dlist_size(list) ((list)->size)

#define dlist_head(list) ((list)->head)

#define dlist_tail(list) ((list)->tail)

#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)

#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)

#define dlist_data(element) ((element)->data)

#define dlist_next(element) ((element)->next)

#define dlist_prev(element) ((element)->prev)

void dlist_init(DList *list, void (*destroy)(void *data)) {
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL;
    list->tail = NULL;

return;

}

void dlist_destroy(DList *list) {

    void    *data;

    while (dlist_size(list) > 0) {

        if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 && list->destroy != NULL) {

            list->destroy(data);
   }

}

    memset(list, 0, sizeof(DList));

    return;
}

int dlist_ins_next(DList *list, DListElmt *element, const void *data) {

DListElmt          *new_element;

if (element == NULL && dlist_size(list) != 0)
   return -1;

if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
   return -1;
new_element->data = (void *)data;

if (dlist_size(list) == 0) {
   list->head = new_element;
   list->head->prev = NULL;
   list->head->next = NULL;
   list->tail = new_element;

   }

else {
   new_element->next = element->next;
   new_element->prev = element;

   if (element->next == NULL)
      list->tail = new_element;
   else
      element->next->prev = new_element;

   element->next = new_element;

}
list->size++;

return 0;

}

int dlist_ins_prev(DList *list, DListElmt *element, const void *data) {

DListElmt          *new_element;

if (element == NULL && dlist_size(list) != 0)
   return -1;

if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
   return -1;

new_element->data = (void *)data;

if (dlist_size(list) == 0) {
   list->head = new_element;
   list->head->prev = NULL;
   list->head->next = NULL;
   list->tail = new_element;

   }


else {
   new_element->next = element; 
   new_element->prev = element->prev;

   if (element->prev == NULL)
      list->head = new_element;
   else
      element->prev->next = new_element;

   element->prev = new_element;

}

list->size++;

return 0;

}

int dlist_remove(DList *list, DListElmt *element, void **data) {

if (element == NULL || dlist_size(list) == 0)
   return -1;

*data = element->data;

if (element == list->head) {

   list->head = element->next;

   if (list->head == NULL)
      list->tail = NULL;
   else
      element->next->prev = NULL;

   }

else {
   element->prev->next = element->next;

   if (element->next == NULL)
      list->tail = element->prev;
   else
      element->next->prev = element->prev;

}

free(element);

list->size--;

return 0;

}

void print_list(const DList *list) {

DListElmt          *element;

int                *data,

fprintf(stdout, "List size is %d\n", dlist_size(list));

i = 0;
element = dlist_head(list);

while (1) {

   data = dlist_data(element);
   fprintf(stdout, "list[%03d]=%03d\n", i, *data);

   i++;

   if (dlist_is_tail(element))
      break;
   else
      element = dlist_next(element);

}

return;

}

int main(int argc, char **argv) {

DList              list;
DListElmt          *element;

int                *data, i;

dlist_init(&list, free);

element = dlist_head(&list);

for (i = 10; i > 0; i--) {

   if ((data = (int *)malloc(sizeof(int))) == NULL)
      return 1;

   *data = i;

   if (dlist_ins_prev(&list, dlist_head(&list), data) != 0)
      return 1;

}

print_list(&list);

element = dlist_head(&list);

for (i = 0; i < 8; i++)
   element = dlist_next(element);

data = dlist_data(element);
fprintf(stdout, "Removing an element after the one containing %03d\n", *data);

if (dlist_remove(&list, element, (void **)&data) != 0)
   return 1;

print_list(&list);

fprintf(stdout, "Inserting 011 at the tail of the list\n");

*data = 11;
if (dlist_ins_next(&list, dlist_tail(&list), data) != 0)
   return 1;

print_list(&list);

fprintf(stdout, "Removing an element at the tail of the list\n");

element = dlist_tail(&list);
if (dlist_remove(&list, element, (void **)&data) != 0)
   return 1;

print_list(&list);

fprintf(stdout, "Inserting 012 just before the tail of the list\n");

*data = 12;
if (dlist_ins_prev(&list, dlist_tail(&list), data) != 0)
   return 1;

print_list(&list);

fprintf(stdout, "Iterating and removing the fourth element\n");

element = dlist_head(&list);
element = dlist_next(element);
element = dlist_prev(element);
element = dlist_next(element);
element = dlist_prev(element);
element = dlist_next(element);
element = dlist_next(element);
element = dlist_next(element);

if (dlist_remove(&list, element, (void **)&data) != 0)
   return 1;

print_list(&list);

fprintf(stdout, "Inserting 013 before the first element\n");

*data = 13;
if (dlist_ins_prev(&list, dlist_head(&list), data) != 0)
   return 1;

print_list(&list);

fprintf(stdout, "Removing an element at the head of the list\n");

if (dlist_remove(&list, dlist_head(&list), (void **)&data) != 0)
   return 1;

print_list(&list);

fprintf(stdout, "Inserting 014 just after the head of the list\n");
*data = 14;

if (dlist_ins_next(&list, dlist_head(&list), data) != 0)
   return 1;

print_list(&list);

fprintf(stdout, "Inserting 015 two elements after the head of the list\n");

if ((data = (int *)malloc(sizeof(int))) == NULL)
   return 1;

*data = 15;
element = dlist_head(&list);
element = dlist_next(element);

if (dlist_ins_next(&list, element, data) != 0)
   return 1;

print_list(&list);

i = dlist_is_head(dlist_head(&list));
fprintf(stdout, "Testing dlist_is_head...Value=%d (1=OK)\n", i);
i = dlist_is_head(dlist_tail(&list));
fprintf(stdout, "Testing dlist_is_head...Value=%d (0=OK)\n", i);
i = dlist_is_tail(dlist_tail(&list));
fprintf(stdout, "Testing dlist_is_tail...Value=%d (1=OK)\n", i);
i = dlist_is_tail(dlist_head(&list));
fprintf(stdout, "Testing dlist_is_tail...Value=%d (0=OK)\n", i);

fprintf(stdout, "Destroying the list\n");
dlist_destroy(&list);

return 0;

}

感谢您的帮助。

Answer 1

线路

DList              list;

在堆栈上分配列表。然后在 dlist_ins_prev 中为每个元素在堆上分配空间。