在链表中使用双指针的目的

Question

我对这个旨在删除列表中给定整数的所有出现的函数有几个问题：

void deleteAllOcc (node**headRef,int d)
{   
    node*temp;
    if (*headRef==NULL)
        return;
       
    while (*headRef)
    {
        if ((*headRef)->data==d)
        {
            temp=*headRef;
            *headRef=(*headRef)->next;
            free(temp);        
        }
        else
        {  
            headRef=&((*headRef)->next);
        }
    }
}

首先为什么我们使用 **headRef 而不是 *head ？

其次，考虑到这一点：

if ((*headRef)->data==d)
{
    temp=*headRef;
    *headRef=(*headRef)->next;
    free(temp);               
}

我们不需要更新链接吗？

第三，考虑到这一点：

else
{
    headRef=&((*headRef)->next);
}

为什么我们没有做 *headRef=(*headRef)->next);在吗？

提前致谢

Answer 1

First why did we use **headRef instead of *head?

当您将链接列表的地址发送给函数时，您会在该列表的第一个元素上创建一个指针。它允许你在列表上迭代等。但是如果你想操作完整的列表（或编辑它），你必须在这个列表上创建一个指针，（这意味着通过发送链表

why we didnt do *headRef=(*headRef)->next); here?

你的方法可行，但我建议你创建一个指向临时节点的指针 *(node tmp) 以便分配它的价值并与之交换数据。它对每个人都更具可读性。

Answer 2

对于初学者来说，函数可以写得更简单

void deleteAllOcc( node **headRef, int d )
{   
    while ( *headRef != NULL )
    {
        if ( ( *headRef )->data == d )
        { 
            node *temp = *headRef;
            *headRef = ( *headRef )->next;
            free( temp );
        }                    
        else
        {  
            headRef = &( *headRef )->next;
        }
    }
}

这是对通过引用传递的指向头节点的指针的相等性的第一次检查是多余的。

First why did we use **headRef instead of *head?

这取决于函数是如何定义的。在您的问题中提供的函数定义的情况下，指向头节点的指针通过引用传递，即通过指向指针头的指针。在这种情况下，在函数内更改指针头就是在更改原始函数。

例如假设列表只包含一个节点，其数据成员 data 等于参数的指定值 d.

主要

node *head = malloc( sizeof( mode ) );
head->data = 1;
head->next = NULL;

deleteAllOcc( &head, 1 );

//...

在函数 deleteAllOcc 中你有

if((*headRef)->data==d)
{
    temp=*headRef;
    *headRef=(*headRef)->next;
    free(temp);
    
}

因为 *headRef 在 main 中产生原始指针 head 然后这个语句

*headRef=(*headRef)->next;

更改主 bot 中的原始指针 head 指针值的副本。

当指向头节点的指针不是按引用传递而是按值传递时，您可以用其他方式定义函数。但在这种情况下，您需要 return 指向 main 中头节点的指针的可能新值。

例如

node * deleteAllOcc( node *head, int d )
{
    while ( head != NULL && head->data == d )
    {
        node *temp = head;
        head = head->next;
        free( temp );
    }

    if ( head != NULL )
    {
        for ( node *current = head; current->next != NULL; )
        {
            if ( current->next->data == d )
            {
                node *temp = current->next;
                current->next = current->next->next;
                free( temp );
            }
            else
            {
                current = current->next;
            }
        }
    }

    return head;
}

并且在 main 中应该调用函数，例如

node *head = NULL;

//filling the list

head = deleteAllOcc( head, 1 );

正如您所见，当指向头节点的指针通过引用传递时，函数定义看起来更简单。

how are we updating the links between the nodes after deleting a node

你有一个指向当前节点的数据成员next的指针。当前节点的数据成员next指向的节点包含的值等于参数d的值。所以必须删除下一个节点。表示当前节点的数据成员next指向被删除节点之后的节点。那就是你需要写

*headRef = ( *headRef )->next;

当前时刻headRef指向当前时刻的数据成员next 节点。

|node1| next |  -> |node2| next | -> |node3| next |
         |            |
       headRef      node that must be deleted

所以在headRef指向的数据成员next中要写入被删除节点node2的数据成员next的值。

why we didnt do *headRef=(*headRef)->next); here?

在此代码段中

else
{
   headRef=&((*headRef)->next);
}

您正在重新分配指针 headRef 以指向下一个节点的下一个数据成员。如果你会写

*headRef = ( *headRef )->next;

那么你将丢失当前指向的节点，该节点由存储在当前指向的数据成员中的表达式 *headRef 中的值 next 将被更改，重写存储的指针。

在链表中使用双指针的目的

Purpose of Using a double pointer in Linked Lists

c

pointers

linked-list

pass-by-reference

singly-linked-list