段错误 - C 中的链表

Question

我正在用 C 语言创建一个基本链表，但是在我的测试文件中调用添加到后台函数时出现段错误。它似乎有问题，因为列表的头部是 NULL，但我不明白为什么这是一个问题。当我使用 cgdb 工具时，它告诉我错误发生在行上：prev->next = new_node。我在下面附上了完整的代码，请让我知道我没有看到什么来解决这个问题。

头文件

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *create_node(int data);
void free_list(Node *head);
void add_to_front(struct Node **head, int data);
void print_list(struct Node *head);
void reverse_list(struct Node **head);
void add_to_back(Node **head, int data);

#endif // LINKED_LIST_H

.c 文件

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

/* returns a new node whose data is set to DATA and next is set to NULL */
Node *create_node(int data) {
    struct Node *new_node = malloc(sizeof(struct Node));
    if (new_node == NULL) {
        perror("Malloc failed\n");
    }
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}


/* Frees the list starting at HEAD */
void free_list(Node *head) {
    while (head != NULL) {
        Node *temp = head->next;
        free(head);
        head = temp;
    }
}

/* Creates a new node whose data is set to DATA and adds it to the front of the
   list pointed to by HEAD.
   */
void add_to_front(struct Node **head, int data) {
    /* Check if the head is NULL to make sure that we do not dereference a NULL pointer
    because that would result in a segfault */
    if (head == NULL) return;
    struct Node *new_node = create_node(data);
    if (*head != NULL) {
        /* The list is not empty */
        /* The new node's next should point to the head */
        new_node->next = *head;
    }
    /* We must set HEAD using the following line in order to change the original list */
    *head = new_node;
    /* The following line would not work because it would only change our local copy of HEAD */
    /* head = new_node */
}

/* Prints out a linked list starting at HEAD */
void print_list(struct Node *head) {
    struct Node *curr;
    for (curr = head; curr != NULL; curr = curr->next) {
        printf("%d->", curr->data);
    }
    printf("NULL\n");
}

/* Iteratively reverses a linked list whose first node is HEAD */
void reverse_list(struct Node **head) {
    if (head == NULL || *head == NULL) {
        return;
    }
    struct Node *curr = *head;
    struct Node *next = (*head)->next;
    curr->next = NULL;
    while (next != NULL) {
        struct Node *temp = next->next;
        next->next = curr;
        curr = next;
        next = temp;
    }
    *head = curr;
}

/* Creates a new node with a data field set to DATA and adds the node
   to the back of the list pointed to by HEAD */
void add_to_back(Node **head, int data) {
    if (head == NULL || *head == NULL) {
        return;
    }
    Node *new_node = create_node(data);
    Node *prev;
    for (Node *curr = *head; curr != NULL; curr = curr->next) {
        prev = curr;
    }
    prev->next = new_node;
}

测试文件

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "linked_list.h"

int main(int argc, char **argv) {
    printf("Running tests...\n\n");

    Node *head = NULL;

    /*********** reverse_list test ***********/
    reverse_list(&head);
    for (int i = 0; i < 5; ++i) {
        add_to_front(&head, i);
        reverse_list(&head);
    }

    int expected_values[] = {3, 1, 0, 2, 4};
    Node *curr = head;
    for (int i = 0; i < 5; ++i) {
        assert(curr->data == expected_values[i]);
        curr = curr->next;
    }
    free_list(head);

    printf("Congrats! You have passed the reverse_list test!\n\n");

    /************ add_to_back test ***********/
    Node *head_2 = NULL;
    add_to_back(&head_2, 15);
    add_to_back(&head_2, 12);
    add_to_back(&head_2, 18);
    int expected_values_2[] = {15, 12, 18};
    Node *curr_2 = head_2;
    for (int i = 0; i < 3; ++i) {
        assert(curr_2->data == expected_values_2[i]);
        curr_2 = curr_2->next;
    }
    free_list(head_2);

    printf("Congrats! All of the test cases passed!\n");
    return 0;
}

Answer 1

函数中的if语句add_to_back

if (head == NULL || *head == NULL) {
    return;
}

没有意义，因为它不允许将节点附加到空列表。

函数可以这样定义，例如

void add_to_back( Node **head, int data ) 
{
    if ( head == NULL ) return;

    Node *new_node = create_node(data);

    while ( *head ) head = &( *head )->next;

    *head = new_node;
}

或者使用你的方法

void add_to_back( Node **head, int data ) 
{
    if ( head == NULL ) return;

    Node *new_node = create_node(data);

    Node *prev = NULL;

    for ( Node *curr = *head; curr != NULL; curr = curr->next ) 
    {
        prev = curr;
    }

    prev == NULL ? ( *head = new_node ) : ( prev->next = new_node );
}

总的来说这个说法

if ( head == NULL ) return;

也是多余的。如果用户将传递一个空指针，那么该函数将具有未定义的行为。

另一方面，函数create_node应该写成下面的方式

Node * create_node( int data ) 
{
    struct Node *new_node = malloc(sizeof(struct Node));

    if ( new_node != NULL )
    {
        new_node->data = data;
        new_node->next = NULL;
    }

    return new_node;
}

相应地例如函数add_to_back可以写成

int add_to_back( Node **head, int data ) 
{
    Node *new_node = create_node( data );
    int success = new_node != NULL;

    if ( success )
    {
        Node *prev = NULL;

        for ( Node *curr = *head; curr != NULL; curr = curr->next ) 
        {
            prev = curr;
        }

        prev == NULL ? ( *head = new_node ) : ( prev->next = new_node );
    }

    return success;
}

Answer 2

问题出在 add_to_back() 函数中。由于该函数的第一行 if (head == NULL || *head == NULL) { return; }，它将继续返回而不执行其余代码。因此，如果您在调用 add_to_back 函数三次后打印您的列表，您的列表将只有 NULL，这就是您遇到分段错误的原因。我做了以下更改，您的代码运行良好 ` void add_to_back(Node **head, int data) {

Node *new_node = create_node(data);
if (*head == NULL){
    *head =  new_node;
    return;
}
Node *prev;
for (Node *curr = *head; curr != NULL; curr = curr->next) {
    prev = curr;
}
prev->next = new_node;

} `

段错误 - C 中的链表

Segment Fault - Linked List in C

c

linked-list

append

data-structures

singly-linked-list