Проблема удаления главного узла в двусвязном списке в C - PullRequest
1 голос
/ 13 марта 2019

Я пытаюсь реализовать двусвязный список в C. При кодировании я столкнулся с проблемой при попытке удалить первый элемент списка.

Вот игрушечный пример, иллюстрирующий проблему:

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

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


 Node* create_dll(int array[], int arrSize){
     Node *current = (Node*)malloc(sizeof(Node));
     current->next = NULL;
     current->data = array[0];
     for(int i = 1; i < arrSize; i++){
         Node *temp = (Node*)malloc(sizeof(Node));
         temp->data = array[i];
         temp->next = current;
         current->previous  = temp;
         current = temp;
     }
     current->previous = NULL; 
     return current;
 }
 void print_dll(Node *head){
     if(head != NULL){
         Node *current = head;
         while(current!=NULL){
         printf("%d \t", current ->data);
             current = current->next;
         }
     }
     puts(" ");
 }

 void delete_head(Node *head){
     Node *current = head;
     head = head->next;
     //head ->previous = NULL;
     free(current);
 }
 void kill(Node *head){
     Node *current = head;
     while (current != NULL){
         Node *previous = current;
         current = current ->next;
         free(previous);
     }
 }

 int main(){
     int array [] = {1, 2, 3, 4, 5};
     int arrSize = 5;

     Node *head;

     head = create_dll(array, 5);

     print_dll(head);

     delete_head(head);
     print_dll(head);

     kill(head);
     return 0;

}

Всякий раз, когда я пытаюсь запустить код в main, который создает DLL, затем печатает то, что в ней, затем пытается удалить первый узел, затем снова печатает список, я получаю следующий результат:

    5   4   3   2   1    
    5    

Теперь я знаю, что одним из решений было бы сделать head глобальной переменной, но это будет проблематично в других разделах кода, плюс я не очень хочу идти по этому пути. Я также не хочу изменять какие-либо заголовки функций или что-либо в основном.

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

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

Любая помощь очень ценится! Спасибо!

Ответы [ 2 ]

2 голосов
/ 13 марта 2019

Проблема в том, что когда вы вызываете delete_head, передача параметра C происходит по значению, поэтому head не изменяется при возврате. Вам нужно реализовать это так:

void delete_head(Node **head){
            Node *current = *head;
            *head = current->next;
            //head ->previous = NULL;
            free(current);
}

И назовите это так: delete_head(&head);

1 голос
/ 13 марта 2019

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

Я бы решил эту проблему, добавив дополнительную структуру.

typedef struct DLL{
    struct Node * head;
} DLL;

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

...