将新元素插入已排序的链接列表时的Segfault

Question

我使用以下函数将新节点插入到排序的整数链表中

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

    for (TempNext = Head; TempNext != NULL; TempPrevious = TempNext, TempNext = TempNext -> Next) 
    {
        NewNode -> Next = TempNext;
        if (TempNext == Head) Head = NewNode; // Check for empty list
        else if (NewNode -> Element >= TempNext -> Element) continue; // Check for correct point in list
        else TempPrevious -> Next = NewNode;
        return true;
    }

    // If execution reaches this point, then the new node goes at the end of the list    
    TempPrevious -> Next = NewNode;
    return true;
}

每当我尝试使用此算法将元素插入空列表时,程序将返回分段错误.使用GDB检查将最后TempPrevious -> Next = NewNode;一行标识为原因,但执行不应该到达那里,因为循环return true结束时for应该将控制权返回给调用函数,但由于某种原因它不是.有人能看到我在哪里错了吗？

Answer 1

请注意,如果列表为空,TempPrevious则会显示未初始化的指针.当您尝试for在空列表上运行循环时,TempNext将立即NULL执行该语句TempPrevious = TempNext.由于您从未设置TempPrevious为具有默认值,因此它将是未初始化的,因此代码也是如此

TempPrevious -> Next = NewNode;

将取消引用垃圾指针,从而导致崩溃.

要解决这个问题,您需要在列表为空时使用特殊情况,或使用其他方法列出插入(可能保留指向要重写的节点指针的指针),以便优雅地处理插入到空列表中.