在C中删除双向链表中的头节点时出现问题

Question

我正在尝试在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成为一个全局变量，但这在代码的其他部分会有问题，而且我真的不想走那条路。我也不想修改任何函数头或main中的任何东西。

我确实通过使用head总是指向的虚拟节点实现DLL来实现这一点，但我确信这个实现有一个简单的解决方法可以避免所有这些。

基本上，如果我可以在head函数中更改delete_head指向的内容并将此更改反映在main函数中，那将是一个解决方案。否则，我很高兴只是理解为什么这段代码无法按我的意愿行事。

很感谢任何形式的帮助！谢谢！

Answer 1

问题是当你调用delete_head时，C参数传递是按值，因此返回时不会更改head。你需要像这样实现它：

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

并称之为：delete_head(&head);

Answer 2

诀窍是，所有外部指针都指向各个节点。因此，当您从列表的其余部分中删除头部时，所有指向head的指针都会指向它 - 您自己获得单个节点，而不是列表的其余部分。

我会通过添加一个额外的结构来解决这个问题

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

如果要创建列表，请创建指向头部的DLL，而不是返回头部本身。现在，当您想要更改头部时，请更改DLL结构内的指针。所有对DLL本身的引用都可以保持不变，但现在它内部的head已经改变了，所有这些引用都将在它们寻找时看到新的head！