Segfault при доступе к следующему узлу в одиночном списке

Question

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

struct _Node 
{ 
    union 
    { 
     int n; 
     char c; 
    } val; 
    void *ptr; /* points to ptr variable in next node, not beginning */ 
    int var; 
}; 
typedef struct _Node Node; 

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

Node *reverse(Node *head) 
{ 
    Node * temp; 
    Node * prev = NULL; 
    while(head != NULL) 
    { 
     temp = head->ptr + 4; /* add 4 to pass union and get beginning of next node */ 
     head->ptr = prev; 
     prev = head; 
     head = temp; 
    } 
    return prev; 
} 

Даже если я пытаюсь и доступ head->ptr без добавления 4, я получаю Segfault.

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

Answer 1

Во-первых, я покажу вам главную проблему в коде:

while (head) // is shorter than while(head != NULL) 
    { 
     // Where does the 4 come from? 
     // And even if: You have to substract it. 
     // so, definitively a bug: 
     // temp = head->ptr + 4; /* add 4 to pass union and get beginning of next node */ 
     size_t offset_ptr = (char*)head->ptr - (char*)head; 
     // the line above should be moved out of the while loop. 
     temp = head->ptr - offset_ptr; 

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

1. сосчитать элементы, выделить массив, помните указатели в этом массиве, а затем переназначить следующие указатели.

2. создать временный двойной связанный список (на самом деле вам нужен только один единственный обратный список, поскольку оба списка вместе образуют двойной связанный список). Затем повторите попытку, чтобы скопировать следующий указатель из вашего временного списка в старый список. Не забудьте освободить временный список до возвращения.

Answer 2

Я пробовал ваш код и делал некоторые настройки, ну, на мой взгляд, у вашего кода была некоторая логическая ошибка. Ваши указатели были перезаписаны снова и снова (прыгая с одного узла на другой и обратно: 1-> 2, 2-> 1), которые приводили к подозрению в утечке памяти. Здесь рабочая версия вашего кода ...

Node *reverse(Node *head) 
{ 
    Node *temp = 0; 
    //Re-ordering of your assignment statements 
    while (head) //No need for explicit head != NULL 
    { 
     //Here this line ensures that pointers are not overwritten 
     Node *next = (Node *)head->ptr; //Type casting from void * to Node * 
     head->ptr = temp; 
     temp = head; 
     head = next; 
    } 
    return temp; 
}