C中的免费链表

Question

嗨，我需要帮助在c中释放我的链表。当我运行此代码时，我得到一个段故障11。直到释放，一切都很完美。谢谢你的帮助!

#include <stdio.h>
#include <stdlib.h>
struct node{
    int x;
    struct node *next;
};
int main(void){
    struct node *root, *next;
    root = malloc(sizeof(struct node));
    root -> x = 0;
    root -> next = NULL;
    next = root;
    for (int i = 0; i <=10; i++){
        next -> next = malloc(sizeof(struct node));
        next -> x = i;
        next = next -> next;
    }
    next = root;
    for (int j = 0; j <= 10; j ++){
        printf("%i", next -> x);
        next = next -> next;
    }
        next = root;
    while(next != NULL){
        next = root;
        root = root -> next;
        free(next);
    }
    free(root);
}

Answer 1

原始代码有几个问题:

1) while(next != NULL)循环尝试使用已经释放的节点。

2)循环已经负责释放root (next = root;)，因此不需要单独释放root。

3)为了使while循环正常工作，列表的tail/head必须正确地终止NULL。(我在第一个for循环中添加了终止)

4)第二个循环应该打印所有的x值。但事实并非如此。计数器少了一个数字。

改进后的程序如下所示。请同时检查程序输出

#include <stdio.h>
#include <stdlib.h>
struct node{
    int x;
    struct node *next;
};
int main(void){
    struct node *root, *next, *to_free;
    root = malloc(sizeof(struct node));                   // 1 malloc
    root->x = 777;
    root->next = NULL;
    printf("allocating memory for root. root->x = %inn", root-> x);
    next = root; // next points to "head" (root)
    for (int i = 0; i <= 10; i++){
        next->next = malloc(sizeof(struct node));      // 11 mallocs
        printf("allocating memory for next. next->x = %in", i+1 );   
        next->next->x = i+1;                           //
        next = next->next;
        next->next = NULL;                             // list termination is needed!
    }
    printf("n");
    next = root; // next points to "head" (root)
    for (int j = 0; j <= 11; j ++){                   // 12 nodes has to be printed! 
        printf("Printing x = %in", next->x);
        next = next->next;
    }
    printf("n");
    next = root;   //  next points to "head" (root)
    while(next != NULL)         
    {   
        to_free = next;         // we will free `next` as `to_free` soon
        next = next->next;      // move to the next node   
        printf("deallocating node with x = %in", to_free->x);
       free(to_free);          // now free the remembered `next`
    }
 return 0;
}

输出:

allocating memory for root. root->x = 777
allocating memory for next. next->x = 1
allocating memory for next. next->x = 2
allocating memory for next. next->x = 3
allocating memory for next. next->x = 4
allocating memory for next. next->x = 5
allocating memory for next. next->x = 6
allocating memory for next. next->x = 7
allocating memory for next. next->x = 8
allocating memory for next. next->x = 9
allocating memory for next. next->x = 10
allocating memory for next. next->x = 11
Printing x = 777
Printing x = 1
Printing x = 2
Printing x = 3
Printing x = 4
Printing x = 5
Printing x = 6
Printing x = 7
Printing x = 8
Printing x = 9
Printing x = 10
Printing x = 11
deallocating node with x = 777
deallocating node with x = 1
deallocating node with x = 2
deallocating node with x = 3
deallocating node with x = 4
deallocating node with x = 5
deallocating node with x = 6
deallocating node with x = 7
deallocating node with x = 8
deallocating node with x = 9
deallocating node with x = 10
deallocating node with x = 11

Answer 2

释放节点的循环检查next是否为NULL 在调用free(next)之后。

Answer 3

正如另一个答案所述，下面的free()位于错误的位置，因为它释放了内存，然后在while循环的条件中进行检查。

while(next != NULL){
    root = root->next;
    next = root;
    free(next);
}

但是，如果将该块的第一个语句移动到块的末尾，正如您在评论中建议的那样，您的问题可能是这个循环本身完全足以释放整个列表的事实，因此循环后的语句free(root)可能是双自由的，这通常是一个错误。

Answer 4

你的代码中有几个问题，下面列出，最重要的是第1个。

1. 指针next在你的列表(根)的第一项不指向NULL，因为它将在第一个for循环改变。所以while(next != NULL)不能工作，因为链表中没有指向NULL的项。
2. malloc将返回类型为void *的指针，因此最好将其转换为next。
3. 分配内存后，应该检查分配成功与否的结果。另外，我建议您使用typedef来定义链表。

你的代码应该是这样的:

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
    int x;
    struct node *next, *temp;
} node_t;
int main(int argc, char *argv[]){
  node_t *root, *next, *temp;
  root = (node_t *) malloc(sizeof(node_t));
  if(root == NULL){
    /* Do somthing */
    fprintf(stderr, "unable to allocate memoryn");
    exit(1);
  }
  root -> x = 100;
  root -> next = NULL;
  for (int i = 0; i <= 10; i++){
    next = (node_t *) malloc(sizeof(node_t));
    if(next == NULL){
      /* Do somthing */
      fprintf(stderr, "unable to allocate memoryn");
      exit(1);
    }
    next -> x = i;
    next -> next = root;
    root = next;
  }
  temp = next;
  while(temp != NULL){
    printf("x value is: %dn", temp -> x);
    temp = temp -> next;
  }
  while(next != NULL){
    temp = next -> next;
    free(next);
    next = temp;
  }
}