为什么在显式使用变量保存链表头部时删除链表中的节点失败？

Question

我正在使用此函数通过将新节点推到前面来创建列表。

void push(struct Node **head, int newValue)
{    
    if (*head == NULL)
    {
        puts("List is empty. The first node will be created now... ");
    }
    struct Node *new_node = malloc(sizeof(struct Node));
    new_node->data = newValue;
    new_node->next = (*head);
    (*head) = new_node;
}

我正在通过这样做来填充列表：

  push(&head, 10);
  push(&head, 20);
  push(&head, 30);
  push(&head, 40);

这给了我以下列表：40->30->20->10

现在，我想删除列表头部的元素。这是我的删除功能：

void delete (struct Node **head, int key)
{
    // struct Node *currentNode = (*head);
    
    if ((*head)->data == key)
    {
        struct Node *tmp = (*head);
        (*head) = (*head)->next;
        free(tmp);
    }
}

然后：

delete(&head, 40);
printList(head);

我得到了预期的输出（即 30->20->10）。

但是，如果我取消注释 struct Node *currentNode = (*head); 行并使用 currentNode 指针而不是 (*head) ，如下所示：

void delete (struct Node **head, int key)
{
    struct Node *currentNode = (*head);

    //if the key is at HEAD (the first node)
    if (currentNode->data == key)
    {
        struct Node *tmp = currentNode;
        currentNode = currentNode->next;
        free(tmp);
    }
}

，我再次调用 delete(&head, 40) 和 printList(&head)，我得到一些我认为是垃圾的值（即 0->1）。

我的printList是这样的：

void printList(struct Node *list)
{
    int index = 0;
    
    while (list != NULL)
    {
        index++;
        list = list->next;
    }
}

节点是这样的：

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

怎么回事？

更新

对于这个结构，

struct Test
{
    int x;
};

int main()
{
    struct Test *myPtr = malloc(sizeof(struct Test));
    myPtr->x = 111;
    printf("Before copyStructOne x is: %d\n", myPtr->x);

    copyStructOne(&myPtr);
    //would expect this print 111 and not 500
    printf("After copyStructOne x is: %d\n", myPtr->x); 
}
void copyStructOne(struct Test **testPtr)
{
 //doesn't this create a local copy like in my original question?
    struct Test *testStr = (*testPtr); 
    testStr->x = 500;
    printf("Inside copyStructOne x is: %d\n", testStr->x);
}

Answer 1

在您使用 currentNode 的情况下，它包含 *head 中内容的副本。但是，您只修改了副本，而不是 *head，因此列表的头部实际上并没有改变。所以在函数 returns 之后，head 现在指向已释放的内存，因此读取该指针会触发 undefined behavior.

传递pointer-to-pointer的原因是允许调用函数中的指针被被调用函数修改。

Answer 2

其实你修改后的函数和下面类似

int x = 10;
int y = x;
y = 0;

在此代码片段之后，变量 x 保持不变，因为最初由变量 x 的值初始化的变量 y 发生了变化。

函数内无需引入局部变量currentNode

我怀疑您想更改该函数，使其删除值等于参数键值的任何节点（不仅是第一个节点）。

在这种情况下，函数可以如下所示

int delete (struct Node **head, int key)
{
    while ( *head != NULL && ( *head )->data != key )
    {
        head = &( *head )->next;
    } 

    int success = *head != NULL;

    if ( success )
    {
        struct Node *tmp = *head;
        *head = ( *head )->next;
        free( tmp );
    }

    return success;
}

为什么在显式使用变量保存链表头部时删除链表中的节点失败？

Why deleting a node in linked list fails when explicitly using a variable to save the head of the list?

c

linked-list

pass-by-reference

singly-linked-list

function-definition