無法理解sortedlinklist功能

發現來自斯坦福大學的CS庫的一些問題，這是個問題如下無法理解sortedlinklist功能

寫SortedInsert（）函數給出了在遞增的順序排序的列表，以及一個單節點，將節點插入列表中正確的排序位置。雖然Push（）分配一個新節點添加到列表中，但SortedInsert（）需要一個現有節點，並且重新排列指針以將其插入到列表中。有很多可能的解決方案來解決這個問題。

我發現了一個有趣的解決方案，我有一個很難理解

void SortedInsert(struct node** headRef, struct node* newNode) { 
    struct node **pp, *curr; 

    pp = headRef; 
    while ((curr = *pp) != NULL && curr->data <= newNode->data) 
     pp = &curr->next; 
    *pp = newNode; 
    newNode->next = curr; 
}

有人可以給我解釋一下這是如何工作？我知道curr設置爲* pp（headRef），curr在while循環中設置爲* pp，然後檢查當前節點是否小於要插入的節點，然後將pp設置爲下一個節點當前的一個。什麼絆倒了我是當條件不滿足，自CURR在while循環*重置頁跳轉到

*pp = newNode; 
newNode -> next = curr;

，請問newNode得到由它後面的一個連接？還是我完全誤讀了這種解決方案

來源

2014-04-13 Apprentice Programmer

您不需要curr指針。另外一個for循環代替while循環會更具可讀性，恕我直言。空白也有幫助。 – wildplasser

而且你也不需要pp，因爲你可以使用headRef。 – wildplasser

pp是指針的指針，所以在這一行pp = &curr->next;分配指針（不是下一個元素它自身的地址）pp地址持有下一個元素的地址，所以稍後在這裏*pp = newNode;你'進入'存儲下一個元素的地址，並用newNode的地址替換它。

來源

2014-04-13 09:41:51 Dabo

簡體版：

void SortedInsert(struct node **headRef, struct node *newNode) { 

     for (; *headRef && (*headRef)->data <= newNode->data; headRef = &(*headRef)->next) 
      {;} 

      /* When we arrive here, headRef points to the ->next pointer 
      ** that points to the node that should come after the newNode 
      ** , OR it points to the terminal ->next pointer, 
      ** which will be NULL. 
      ** In the case of an empty list, *headRef will be NULL, and 
      ** the loop is never entered. 
      */ 
     newNode->next = *headRef; 
     *headRef = newNode; 
}

來源

2014-04-13 09:48:53 wildplasser

你提到：

「因爲CURR在while循環* PP復位，請問newNode獲得通過它背後的一個連接或者我完全誤解了這個解決方案......「

實際上，'curr'被保留在循環開始時分配給（新的，更新的）pp，就像你EE中的代碼：

while ((curr = *pp) != NULL && curr->data <= newNode->data) 
    pp = &curr->next;

的（CUR == * PP）不僅用於啓動，它是爲每個循環執行.. 和PP也保持被進展到下一個項目（PP = & curr-> next）直到列表結尾（* pp == NULL）

來源

2014-04-13 11:05:38 Ari

無法理解sortedlinklist功能

回答

相關問題