将新节点插入已排序链表时出现问题

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

你不必要地将问题复杂化了。您的代码中有几处不太正确：

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 2

我认为问题出在你的 while 条件上，应该是：

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 3

新节点 -> Next != NULL 始终为 false，因此您只能通过循环一次。

事实上，该循环应该继续下去，直到插入节点为止。如果通过条件结束循环，则意味着尚未插入节点。

最后的 delete TempNext, TempPrevious 负责示例列表之一中的 0 。当您删除这些变量时，您会销毁它们所指向的列表的实际元素。