C双链表分段故障

Question

我在C中编写了自己的链表实现,它可以很好地存储值,但每当我尝试运行列表时,我都会遇到分段错误.我不确定为什么会出现这个问题,而且我花了相当多的时间试图自己完成程序,但无济于事.你能帮我找一下错误的原因吗？这是我的代码:

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

// A double linkd list node
struct list
{
    struct list * prev;
    int data;
    struct list * next;
};
typedef struct list node;
node *head = NULL;
node *tail = NULL;

// Adds an item to the end of the list
void append(int item);
// Adds an item at the given index
int insert(int item, int index);
// Removes and returns an item at the specified index
int remove_node(int index);
// Gets an item at the specified index
int get(int index);
// Returns the node at the specified index
node* get_node(int idex);


// Adds an item to the end of the list
void append(int item)
{
    // If no items have been added to the list yet   
    if(head == NULL)
    {
        head = (node*) malloc(sizeof(node));
        head->prev = NULL;
        head->data = item;
        head->next = NULL;
        tail = head;
        printf("Successfully added the head\n");
    }
    // If items have previously been added to the list
    else
    {
        node *current = (node*) malloc(sizeof(node));
        printf("Successfully allocated memory for the next item\n");
        current->prev = tail;
        printf("Assigned current previous link to tail\n");
        current->data = item;
        printf("Assignd current's data value: %d\n", item);
        current->next = NULL;
        printf("Assigned current's next value to NULL\n");
        tail = current;
        printf("Assigned tail to current\n\n\n");
    }
}


// Adds an item at the given index
// Returns an int. Nonzero means there was an error
int insert(int item, int index)
{
    node *current, *new;
    current = head;

    for( ; index > 0; index--)
    {
        current = current->next;
    }

    // Make a new node and properly connect it
    new = (node*) malloc(sizeof(node));
    new->prev = current->prev;
    new->data = item;
    new->next = current;
    current->prev = new;

    return 0;
}


// Removes and returns an item at the specified index
int remove_node(int index)
{
    int ret;
    node *current = head;

    for( ; index > 0; index--)
    {
        current = current->next;
    }
    ret = current->data;

    // Connect the nodes on both sides of current
    (current->prev)->next = current->next;
    (current->next)->prev = current->prev;

    free(current);
    return ret;
}


// Gets an item at the specified index
int get(int index)
{
    return (get_node(index))->data;
}

// Returns the node at the specified index
node* get_node(int index)
{
    node *current = head;
    for( ; index > 0; index--)
    {
        current = current->next;
    }
    return current;
}


int main(void)
{
    int i;
    for(i = 0; i < 10; i++)
    {
        append(i);
    }

    node *current = head;
    for(i = 0; i < 10; i++)
    {
        printf("%d\n", current->data);
        current = current->next;
    }

    return 0;
}

Answer 1

在代码的这一部分:

else
{
    node *current = (node*) malloc(sizeof(node));
    printf("Successfully allocated memory for the next item\n");
    current->prev = tail;
    printf("Assigned current previous link to tail\n");
    current->data = item;
    printf("Assignd current's data value: %d\n", item);
    current->next = NULL;
    printf("Assigned current's next value to NULL\n");
    tail = current;
    printf("Assigned tail to current\n\n\n");
}

您没有设置tail->next为current任何位置,因此next将始终为NULL.一般来说,附加调试器应该很容易发现这种bug.只需逐行执行代码,您将看到在您打印输出值的循环中,current-> next为NULL.

Answer 2

您的append()功能不正确 - 它还需要设置tail->next = current;(更改前tail).

你的insert()功能同样需要设置,current->prev->next = new;如果current->prev不是NULL; 否则需要设置head = new;.它还需要处理current存在NULL.

您的remove_node()函数需要处理current->prev和/或current->next存在的情况NULL(它应该更新head并tail分别在这些情况下).

如果给定索引的函数注意不要在列表的末尾运行,如果给定的索引超出范围,那么这也是一个好主意.