C中使用指向指针的指针更新链表

Question

我目前正在研究 K.N 的 C Programming A Modern Approach。大王，练习题之一是：

下面的函数应该将一个新节点插入到有序列表中的适当位置，返回指向修改列表中第一个节点的指针。不幸的是，该函数并非在所有情况下都正确表达。解释它有什么问题并展示如何修复它。假设节点结构是第 17.5 节中定义的那个。

struct node
{
    int value;
    struct node next;
};

struct node *insert_into_ordered_list(struct node *list, struct node *new_node)
{
    struct node *cur = list, *prev = NULL;
    while (cur->value <= new_node->value) {
        prev = cur;
        cur = cur->next;
    }
    prev->next = new_node;
    new_node->next = cur;
    return list;
}

在尝试理解这个问题一段时间并苦苦挣扎之后，我最终遇到了另一个 Whosebug 问题，有人发布了这个问题作为他们的答案。我目前没有足够的声望在那里询问它，所以我在这里问，试着解决这个问题。

struct node * insert_into_ordered_list( struct node *list, struct node *new_node )
{
    struct node **pp = &list;

    while ( *pp != NULL && !( new_node->value < ( *pp )->value ) ) 
    {
        pp = &( *pp )->next;
    }

    new_node->next = *pp;
    *pp = new_node;

    return list;
}

有人可以向我解释一下前一个节点，即插入的 new_node 之前的那个节点是如何更新为指向插入的 new_node 的吗？我猜 *pp = new_node; 行与它有关，但我不明白如何。谢谢。

Answer 1

pp 最初指向指针 head 或由于 while 循环指向某个节点 next 的数据成员

while ( *pp != NULL && !( new_node->value < ( *pp )->value ) ) 
{
    pp = &( *pp )->next;
}

例如，如果 pp 指向 head。如果 head 等于 NULL 或 new_node->value < head->value 那么这些语句

new_node->next = *pp;
*pp = new_node;

实际上等同于

new_node->next = head;
head = new_node

如果pp指向某个节点的数据成员next那么这些语句

new_node->next = *pp;
*pp = new_node;

将当前数据成员的值next更改为新节点的地址

*pp = new_node;

在此之前，新节点的数据成员next被设置为当前节点的数据成员next中存储的值。

至于这个功能

struct node *insert_into_ordered_list(struct node *list, struct node *new_node)
{
    struct node *cur = list, *prev = NULL;
    while (cur->value <= new_node->value) {
        prev = cur;
        cur = cur->next;
    }
    prev->next = new_node;
    new_node->next = cur;
    return list;
}

则不会检查指针 cur 是否变为（或最初）等于 NULL。其次，当新节点插入到 list 指向的节点之前时，指针 list 不会改变。

函数可以这样定义

struct node *insert_into_ordered_list(struct node *list, struct node *new_node)
{
    if ( list == NULL || new_node->value < list->value )
    {
        new_node->next = list;
        list = new_node;
    }
    else
    { 
        struct node *cur = list;
        while ( cur->next != NULL && cur->next->value <= new_node->value) 
        {
            cur = cur->next;
        }
    
        new_node->next = cur->next;
        cur->next = new_node;
    }

    return list;
}

Answer 2

如您所说，pp 是指向“列表中位置的当前节点”的指针——在文献中有时称为“处理程序”。名称 pp 来自“指向指针的指针”。

* 是“取消引用运算符”，具体意思是“数据在”，所以 *pp 意思是“内存位置 pp 处的数据”，在这种情况下是实际指针到当前节点。

当您使用带取消引用的赋值运算符时，您是说将内存位置 pp 的数据设置为 new_node （该数据恰好也是一个指针）。请记住，new_node 是指向新节点数据的指针。所以当你运行行：

new_node->next = *pp;

您将 new_node 处数据中的“下一个”条目设置为指向“当前”节点的指针。然后当你运行行：

*pp = new_node;

您正在更新位置 pp 处的指针以指向 new_node 处 struct node 格式的结构化数据。

有时在 C 中展开所有这些指针和取消引用时，它帮助我确保我理解每个表达式和子表达式的类型.

例如，上面的各种表达式及其类型，在现代 C 语言中使用 typeof 运算符表示为布尔运算。请注意，在实际程序中，在编译时这些将替换为值 1（C 中的“truthy”）:)

typeof(new_node) == struct node *;
typeof(pp) == struct node **;
typeof(*pp) == struct node *;
typeof(*new_node) = struct node;

请注意，由于在 C 中，= 运算符会导致内存被复制，从而导致表达式左侧在任何未来的计算中都等于右侧（通常称为 lvalue 和表达式的 rvalue）。因此，按照说法，在 = 之后，lvalue 的评估可能与之前不同。 rvalue用于计算lvalue的新值，但自身在赋值操作后保持不变。

重要的是要记住，无论何时您使用 =，您都会忽略 lvalue 中的任何数据。这常常令人困惑，因为 = 是 C 中导致“side-effects”的 ONLY 运算符（有时 () 也被认为是运算符，当然函数调用也可能导致 side-effects，如本例中使用指向函数的指针参数并在函数体内取消引用它）。

ALL 其他运算符只计算内部表达式（例如，*、&、+ 等），但是当您使用 = 它进行更改。例如，任何包含 lvalue 或依赖于 lvalue 的任何给定表达式在 = 操作前后可能会计算出不同的值。因为函数可以像本例中那样具有指针参数，所以函数调用也可能导致副作用。

您还可以更简单地将 * 视为从类型中“删除 *” 的运算符，将 & 视为“添加 *'s" 到类型 - 如上所述，它们被称为取消引用和引用运算符。

C中使用指向指针的指针更新链表

Using pointers to pointers to update linked lists in C

c

struct

pointers

linked-list

function-definition