在C中创建链接列表，遇到分段错误

2024-05-09 • 问答

我需要创建一个节点链接列表，以便主要功能能够正常工作；我无法在主要功能中进行任何更改。我是C语言的新手，所以我可能犯了一个或两个简单的错误，并且在尝试运行代码时遇到分段错误。我缺少明显的东西吗？

分段错误发生在标记的行上

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

typedef struct Node{
    char *value;
    struct Node *next;
}Node;
typedef struct Node** List;

Node *new_node(char *input);
void delete_node(Node *input);
void push(List list,char *value);
List new_list();

Node *new_node(char *input) {
  Node *new;
  new = malloc(sizeof(Node));
  new->value = input;
  return new;
}

void delete_node(Node *input) {
  free(input);
}

void push(List head,char *input) {
  if (*head == NULL) {  
    *head = new_node(input);
  }
  else {
    Node *new = new_node(input);
    while ((*head)->next != NULL) {
      *head = (*head)->next;
    }
    (*head)->next = new;    
  } 
}

List new_list() {
  List list = malloc(sizeof(List));
  *list = NULL;
  return list;
}

int main( void ) {
  List list = new_list();
  push(list,"First!\n");
  push(list,"Second!\n");
  push(list,"Third!\n");
  push(list,"Fourth!");

  printf("%s",(*list)->value);
  printf("%s",(*list)->next->value);
  printf("%s",(*list)->next->next->value);       //Segmentation fault
  printf("%s",(*list)->next->next->next->value);

  return 0;
}

当我用gdb运行它时，我收到消息：

Third!                                                                                                               

Program received signal SIGSEGV,Segmentation fault.                                                                 
0x0000000000400752 in main () at main.c:54                                                                           
54        printf("%s",(*list)->next->next->value);

创建新节点时，永远不要设置新创建节点的next成员。这将使它保持未初始化状态，从而在取消引用指针时导致未定义行为。

修复很简单。添加

new->next = NULL;

在分配new_node之后进入value函数。

链接列表可以有一个或两个指针。单链表具有指向下一个元素的指针，双链表具有指向下一个元素和上一个元素的指针。您选择了一个链接列表。

您要添加到列表末尾的函数必须遍历每个追加到列表操作的整个列表。这意味着添加到列表是O（n）复杂度操作。链表的主要优点是实现该功能后的O（1）添加和删除操作。

将列表声明为指向（列表的）头和尾（列表的）的指针，

typedef struct {
    Node* head;
    Node* tail;
} List;

而不是将list声明为指向节点的指针，

typedef struct Node** List;

现在，添加到列表以及从列表中删除的复杂性是O（1）（恒定）时间操作...

//enqueue to tail of list (not push)
void enqueue(List* list,char *input) {
  if( !list ) return; //no list
  Node* new = new_node(input); //new node
  if( NULL == list->head ) { //list empty
    list->head = new; //add at tail,tail equals head
  }
  else {
    list->tail->next = new; //list not empty,add at tail
  }
  list->tail = new;
}

//dequeue from head of list
Node* dequeue(List* list) {
    if( !list ) return NULL; //no list
    if( NULL == list->head ) return NULL; //list empty
    Node* node = list->head; //node at head of list
    list->head = list->head->next; //remove from list
    if( NULL == list->head ) list->tail = NULL; //empty now
    //oh,should also: node->next = NULL;
    return node;
}

而且，正如其他人所说的，您应该在“构造函数”中初始化所有指针，

Node *new_node(char *input) {
  Node *new;
  if( ! (new = malloc(sizeof(Node))) ) return NULL;
  //new = calloc(sizeof(Node)); //calloc fills allocated memory with zero bytes
  //initialize all values in Node structure
  new->value = input;
  new->next = NULL; //either use calloc or init the individual elements
  return new;
}

在C中创建链接列表，遇到分段错误

loveldj13ldj 回答：在C中创建链接列表，遇到分段错误

大家都在问