將新節點插入到已排序的鏈接列表中時出現問題

Question

我試圖將新節點插入已排序的整數鏈表中，但嘗試添加到長度超過兩個節點的列表時遇到問題。我使用下面的代碼來做到這一點

// Initialise place-holder pointers at first and second nodes 
TempPrevious = Head; 
TempNext = Head -> Next; 

do // Iterate until the right spot is found 
{  
    // Does the new node fit between the currently selected nodes? 
    if ((NewNode -> Element > TempPrevious -> Element) && 
      (NewNode -> Element < TempNext -> Element)) 
    { 
     NewNode -> Next = TempNext; 
     TempPrevious -> Next = NewNode; 
     return true; 
    } 

    // Does the new node fit in further along the list? 
    else if (NewNode -> Element > TempNext -> Element) 
    { 
     // Has the end of the list already been reached? 
     if (TempNext -> Next == NULL) 
     { 
      TempNext -> Next = NewNode; 
      return true; 
     } 

     // Or are there still more nodes to come? 
     else if (TempNext -> Next != NULL) 
     { 
      TempPrevious = TempNext; 
      TempNext = TempNext -> Next; 
     } 
    } 
} while (TempNext -> Next != NULL); 

我已經佔了一個空列表，單個節點列表，以及一個兩節點列表，以及在列表的開始插入新節點多於兩個元素，所有這些部分都可以正常工作。我已將問題確定爲所提供的代碼中的最後一個else if，因爲似乎指針TempNext和TempPrevious未與每個迭代的do-while循環一起移動。我得出這個結論構建包含以下元素列表和觀察PrintList()函數的輸出後：

Input: 1,2,3,4,5 
Output: 1,2,0 

Input; 5,4,3,2,1 
Output: 1,2,3,4,5 

我看過了我的代碼和運行這些測試，但無法找到在邏輯的任何故障。任何人都可以看到我要去哪裏嗎？

全list :: Insert()功能

// Insert new element 
template <class Type> 
bool list<Type> :: Insert (const Type& NewElement) 
{ 
    Node *NewNode; 
    Node *TempNext; 
    Node *TempPrevious; 
    NewNode = new Node; 
    NewNode -> Element = NewElement; 

    if (Empty()) // If the list is empty 
    { 
     Head = NewNode; 
     return true; 
    } 

    else if (Head -> Next == NULL) // If there is only a single node in the list 
    { 
     // If the element is less than or equal to the new one 
     if (Head -> Element <= NewNode -> Element) 
     { 
      Head -> Next = NewNode; 
      return true; 
     } 
     // If the element is greater than the new one 
     else if (Head -> Element > NewNode -> Element) 
     { 
      NewNode -> Next = Head; 
      Head = NewNode; 
      return true; 
     } 
    } 

    // Multi-node lists - the list has at least two existing nodes 

    // Initialise place-holder pointers at first and second nodes 
    TempPrevious = Head; 
    TempNext = Head -> Next; 

    // Does the new node go at the start? 
    if (NewNode -> Element < TempPrevious -> Element) 
    { 
     NewNode -> Next = TempPrevious; 
     Head = NewNode; 
     return true; 
    } 

    do // Iterate until the right spot is found 
    {  
     // Does the new node fit between the currently selected nodes? 
     if ((NewNode -> Element > TempPrevious -> Element) && 
       (NewNode -> Element < TempNext -> Element)) 
     { 
      NewNode -> Next = TempNext; 
      TempPrevious -> Next = NewNode; 
      return true; 
     } 

     // Does the new node fit in further along the list? 
     else if (NewNode -> Element > TempNext -> Element) 
     { 
      // Has the end of the list already been reached? 
      if (TempNext -> Next == NULL) 
      { 
       TempNext -> Next = NewNode; 
       return true; 
      } 

      // Or are there still more nodes to come? 
      else if (TempNext -> Next != NULL) 
      { 
       TempPrevious = TempNext; 
       TempNext = TempNext -> Next; 
      } 
     } 
    } while (NewNode -> Next != NULL); 

    delete TempNext, TempPrevious; 
} 

Answer 1

我認爲這個問題是你的，而條件下，它應該是：

while(TmpNext != NULL) 

如果你已經測試空或者一個元素列表，你可以將所有的其他情況下減少：

TempPrevious = Head; 
TempNext = Head->Next; 

while(TempNext != NULL) 
{ 
    if (TempNext->Element > NewNode->Element) 
    { 
     NewNode->Next = TempNext; 
     TempPrevious->Next = NewNode; 
     return true; 
    } 
    TempPrevious = TempNext; 
    TempNext = TempNext->Next; 
} 

// At this point we are sure that we did not inserted the element 
// anywhere in the list so we can safely added to the end 
TempPrevious->Next = NewNode; 

Answer 2

你是在不必要過分複雜的問題。有幾件事情是不完全正確的代碼：

1. 循環不應該是一個do ... while - 你想碰到任何東西（來處理一個空表）之前檢查是否Current == NULL。
2. 在循環內部，你有一個測試「我在看NewNode的最終位置？」。你不需要任何其他條件，因爲如果你是而不是看着最後的位置，是時候繼續循環。

你能做到那麼容易，因爲：

Previous = NULL; 
for (Current = Head; Current != NULL; Previous = Current, Current = Current->Next) { 
    if (NewNode->Element >= Current->Element) { 
     continue; 
    } 

    // Perform the insertion  
    NewNode->Next = Current; 
    if (Current == Head) { 
     Head = NewNode; 
    } 
    else { 
     Previous->Next = NewNode; 
    } 
    return; 
} 

// We haven't inserted yet after going through all the list 
// Previous now points to the last item, or NULL if the list was empty, so: 
NewNode->Next = NULL; 
if (Previous = NULL) { 
    Head = NewNode; 
} 
else { 
    Previous->Next = NewNode; 
} 
return; 

Answer 3

NewNode -> Next != NULL永遠是假的，所以你只有一次一次循環。

事實上，該循環應該繼續，直到插入節點。如果通過條件結束循環，則意味着您沒有插入節點。

delete TempNext, TempPrevious最後在您的示例列表之一中負責0。當你通過這些變量刪除時，你會銷燬它們指向的列表的實際元素。