1

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

如果列表是 [green, red, blue] 并且我尝试插入黄色，它会起作用，但新列表将是 [yellow, red, blue]。

节点类是：

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;
};

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

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();
}
4

1 回答 1

1

您的问题在于您的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())调用 where ，然后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 指向包含您的数据的新节点，它的 next 指针指向旧数据。

于 2012-12-03T03:31:26.190 回答