c++ - 替换链表头时出现问题

编写函数以在链表上进行头插入。将对象插入头并重新附加列表已完成了一半，但是我以某种方式丢失了列表中的原始头节点。

如果列表为[绿色，红色，蓝色]，而我尝试插入黄色，则可以使用，但新列表为[黄色，红色，蓝色]。

节点类为:

template<class T>
class Node
{
public:
    Node(T theData, Node<T>* theLink) : data(theData), link(theLink){}
    Node<T>* getLink( ) const { return link; }

    const T& getData( ) const { return data; }

    void setData(const T& theData) { data = theData; }
    void setLink(Node<T>* pointer) { link = pointer; }

private:
    T data;
    Node<T> *link;
};

列表存储在队列中，因此头插入是该类的方法。队列的前后都有私有(private)变量，它们指向列表的相应位置。

template<class T>
void Queue<T>::headInsert(T& theData)
{
   Node<T> *temp;
   temp = front->getLink();
   front->setLink(new Node<T>(theData, temp->getLink() ));
   front = front->getLink();
}

最佳答案

您的问题出在setLink调用中:

template<class T>
void Queue<T>::headInsert(T& theData)
{
   Node<T> *temp;
   temp = front->getLink();
   front->setLink(new Node<T>(theData, temp->getLink() )); // Right here
   front = front->getLink();
}

您实际上有很多问题。首先，让我们假设我们有以下测试列表:
front = Red -> Green -> Blue -> NULL
调用temp = front->getLink()产生以下输出:
temp = Green -> Blue -> NULL。
new Node<T>(theData, temp->getLink())调用，其中theData = Yellow产生:
new Node<T>(theData, temp->getLink()) = Yellow -> Blue -> NULL。

调用front->setLink(new(...)会给您:
front = Red -> Yellow -> Blue -> NULL
最后，front = front->getLink():
front = Yellow -> Blue -> NULL。

这不是您想要的。您只想获取yellow并将其弹出列表的前面:

template<class T>
void Queue<T>::headInsert(T& theData)
{
   front = new Node<T>(theData, front);
}

无需修改内部指针。只需将front指向包含数据的新节点，下一个指向旧数据的指针即可。

关于c++ - 替换链表头时出现问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13676746/