使用指向指標的指標來更新C中的鏈表-有解無憂

我目前正在研究 KN King 的 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;
}

在嘗試理解了一段時間并苦苦掙扎之后，我最終遇到了另一個 stackoverflow 問題，有人將其發布為他們的答案。我目前沒有足夠的聲譽在那里詢問它，所以我在這里要求嘗試解決這個問題。

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;與它有關，但我不明白如何。謝謝你。

uj5u.com熱心網友回復：

正如你所說，pp是一個指向“當前節點在串列中的位置”的指標——這在文獻中有時被稱為“處理程式”。該名稱pp來自“指向指標的指標”。

*是“取消參考運算子”，特別是它的意思是“資料在”，所以*pp意思是“記憶體位置 pp 的資料”，在這種情況下是指向當前節點的實際指標。

當您使用帶有取消參考的賦值運算子時，您是說將記憶體位置的資料設定pp為new_node（該資料恰好也是一個指標）。請記住，new_node是指向新節點資料的指標。因此，當您運行該行時：

new_node->next = *pp;

您正在將資料中的“下一個”條目設定為 new_node 等于指向“當前”節點的指標。然后，當您運行該行時：

*pp = new_node;

您正在更新位置 pp 處的指標以指向struct node格式為new_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 中，=運算子會導致記憶體被復制，以使運算式的左側在任何未來的評估中都等于右側（通常稱為運算式的 thelvalue和 the rvalue）。因此，按照說法，After an=的lvalue評估方式可能與之前不同。rvalue用于計算的新值，lvalue但其本身在賦值操作后保持不變。

重要的是要記住，無論何時使用，=您都會在lvalue. 這通常令人困惑，因為C=中唯一會導致“副作用”的運算子（有時()也被認為是運算子，當然函式呼叫也可能導致副作用，如在此示例中使用函式的指標引數和在函式體內取消參考它）。

所有其他運算子只計算內部運算式（例如，，*等&），但是當您使用=它時會進行更改。例如，任何包含 thelvalue或任何依賴于 the 的給定運算式lvalue可能在操作之前和之后計算為不同的值=。因為函式可以像本例中那樣具有指標引數，所以函式呼叫也會導致副作用。

您還可以更簡單地將其*視為從型別中“洗掉*'s”&的運算子，以及將“添加*'s”到型別的運算子 - 如上所述，它們被稱為解參考和參考運算子。

uj5u.com熱心網友回復：

pp要么最初指向指標head，要么由于 while 回圈指向next某個節點的資料成員

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

例如，如果pp指向head. ifhead等于NULLor new_node->value < head->valuethen 這些陳述句

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;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/439024.html

標籤：C 指针结构链表函数定义

上一篇：我如何解釋以下代碼行

下一篇：如何在C 中的動態分配陣列中正確插入和顯示資料？