C Ошибка сегментации двусвязного списка - PullRequest
Новая
       25

C Ошибка сегментации двусвязного списка

1 голос
/ 12 июля 2010

Я написал свою собственную реализацию связанного списка на 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;
}

Ответы [ 5 ]

5 голосов
/ 12 июля 2010

Ваша функция 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 соответственно в этих случаях).

Было бы также неплохо, если бы ваши функции, использующие индекс, позаботились о том, чтобы они не выходили за пределы списка, если указанный индекс выходит за пределы..

5 голосов
/ 12 июля 2010

В этом разделе вашего кода: 

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.В общем, этот тип ошибки должен быть легко обнаружен с подключенным отладчиком.Просто постройте код построчно, и вы увидите, что в цикле, где вы печатаете значения, current-> next равно NULL.

3 голосов
/ 12 июля 2010

Непосредственные проблемы:

1 / При добавлении вы не устанавливаете следующий указатель текущего хвоста в качестве нового узла.

2 / При вставке вы не проверяете, что вы вышли за пределы своего списка.

3 / Аналогично, при удалении вы не проверяете, пытаетесь ли вы выйти за пределы своего списка.

4 / При удалении вы не проверяете крайние случаи. Например, удаление текущей головки приведет к тому, что вы попытаетесь установить (current->prev)->next на что-то, даже если current->prev равно NULL.

5 / Цикл в main, наряду с пунктом 1 выше, является причиной вашего segfault. Это потому, что head->next никогда не устанавливается на хвост, поэтому, даже если вы создаете предметы, они не тот список, о котором head знает.

На самом деле это странный подход, поскольку обычно вы делаете удаление на основе значения, а не индекса. Если вы собираетесь удалить (или распечатать или обработать любым способом) узел на основе индекса, вам следует обработать случай, когда указанный индекс выходит за пределы списка.

Я часто обнаруживал, что полезно составить текущий список с помощью бумаги и карандаша, а затем выполнить пробный запуск кода, чтобы убедиться, что он работает должным образом. Прекрасный пример этого см. здесь .

Объясняя, что не так с вашим кодом append (где ? представляет неизвестное значение, а ! означает неизвестный указатель, прямые ссылки вверху, обратные ссылки внизу): 

head
    \
     NULL
         \
          tail


Append (7):

# head = (node*) malloc(sizeof(node));
head   !
    \ /
     ?      NULL
    /           \
   !             tail


# head->prev = NULL;
head   !
    \ /
     ?
    /
NULL        NULL
                \
                 tail


# head->data = item;
head   !
    \ /
     7
    /
NULL        NULL
                \
                 tail


# head->next = NULL;
head   NULL
    \ /
     7
    /
NULL        NULL
                \
                 tail


# tail = head;
head   NULL
    \ /
     7
    / \
NULL   tail

Теперь, когда все выглядит хорошо. Вы можете пройти это вперед и назад без проблем. Теперь давайте добавим еще одно значение. 

# Initial state.
head   NULL
    \ /
     7
    / \
NULL   tail


Append (9):

# node *current = (node*) malloc(sizeof(node));
head   NULL          !
    \ /             /
     7             ? <- curr
    / \           /
NULL   tail      !


# current->prev = tail;
head   NULL          !
    \ /             /
     7             ? <- curr
    / \___________/
NULL   tail


# current->data = item;
head   NULL          !
    \ /             /
     7             9 <- curr
    / \___________/
NULL   tail


# current->next = NULL;
head   NULL          NULL
    \ /             /
     7             9 <- curr
    / \___________/
NULL   tail


# tail = current;
head   NULL          NULL
    \ /             /
     7             9 <- curr
    / \___________/ \
NULL                 tail

Теперь вы должны легко видеть, что там отсутствует. Нет ссылки от head на добавляемый нами узел.

Это означает, что любой цикл, начинающийся с заголовка, будет только когда-либо видеть один элемент в списке. Это также означает, что если вы попытаетесь разыменовать head->next (например, используя 10-итерационный цикл for), вы получите неопределенное поведение, которое и вызывает вашу ошибку.

Чтобы исправить это, сделайте резервную копию на один шаг и вставьте tail->next = current; перед tail = current;: 

# current->next = NULL; // Back up a bit.
head   NULL          NULL
    \ /             /
     7             9 <- curr
    / \___________/
NULL   tail


# tail->next = current; // This is the step we're adding.
head   ___________   NULL
    \ /           \ /
     7             9 <- curr
    / \___________/
NULL   tail


# tail = current;
head   ___________   NULL
    \ /           \ /
     7             9 <- curr
    / \___________/ \
NULL                 tail

И вот наш новый список, который можно перемещать в обоих направлениях. Вы можете добавить еще один, используя тот же метод, чтобы проверить правильность поведения.

0 голосов
/ 12 июля 2010 
for( ; index > 0; index--)
{
    current = current->next;
}

может попытаться найти следующее NULL, что приведет к ошибке сегментации.Если вы имели в виду получение элементов списка с помощью «прогонять», то есть.

0 голосов
/ 12 июля 2010

У вас сбой, потому что current-> data равен нулю: 

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

Вместо цикла for вы можете получить что-то вроде while (current). У вас все еще есть другая проблема, но это вызывает вашу ошибку сегмента.

Вы можете найти строку, вызывающую ошибку, с помощью gdb: 

> gcc -g list.c
> gdb a.out
(gdb) run
...