0

我正在尝试编写自己的模板队列类来学习如何使用模板。我看到这种类型的问题经常被问到，并且我已经阅读了很多回复，但我仍然没有看到我做错了什么。

template <class type>
struct Node{
    type data;
    Node *next;
};

template <class type>
class LinkedListQueue{
public:
    LinkedListQueue();
    void push(type new_data);
    void pop();
    type front();
    void print();

private:
    Node<type> *head;
    Node<type> *tail;
};

template <class type>
LinkedListQueue<type>::LinkedListQueue(){
    this->head = NULL;
    this->tail = NULL;
}

template <class type>
void LinkedListQueue<type>::push(type new_data){
    Node<type> *newNode;
    newNode->data = new_data;
    newNode->next = NULL;

    if(this->head == NULL){
        this->head = newNode;
        this->tail = newNode;
    }else{
        this->tail->next = newNode;
        this->tail = newNode;
    }
}

template <class type>
void LinkedListQueue<type>::pop(){
    if(this->head != NULL){
        this->head = this->head->next;
        if(this->head == NULL){
            this->tail == NULL;
        }
    }else{
    cout << "Queue is Empty" << endl;
    }
}

template <class type>
type LinkedListQueue<type>::front(){
    return(this->head->data);
}

int main() {
    LinkedListQueue<int> newQueue;
    newQueue.push(5);
    newQueue.push(4);
    cout << newQueue.front() << endl;
    newQueue.pop();
    cout << newQueue.front() << endl;
}

我无法确定问题出在哪里。如果我注释掉 pop 和 last front call，第一个 front() 调用会正确输出。但是，取消注释 pop 和 front 会破坏一切。当我尝试调试 pop() 时，列表中似乎只有一个节点。

任何帮助将不胜感激。

4

2 回答 2

0

您没有分配新节点。只是存储数据。

Node<type> *newNode; //<=== indeterminate pointer
newNode->data = new_data;
newNode->next = NULL;

不管怎样，你总是在推入一个新元素，所以分配它，设置它，然后弄清楚它的去向。此外，为您的节点创建一个构造函数，该构造函数接受数据的 const-ref，并将 next 设置为 NULL。这使您的代码更加直接（实际上更高效）：

Node<type> *newNode = new Node<type>(new_data);

随着节点模板变为：

template <class type>
struct Node
{
    Node(const type& value) 
        : data(value), next(NULL) {};
    type data;
    Node *next;
};

最后，您pop()并没有删除节点，只是在处理指针。您可能也想解决这个问题。

template <class type>
void LinkedListQueue<type>::pop()
{
    if(this->head != NULL)
    {
        Node<type>* victim = this->head;
        this->head = this->head->next;
        if(this->head == NULL)
            this->tail == NULL;
        delete victim; // <=== note: deleting node.
    }
    else
    {
        cout << "Queue is Empty" << endl;
    }
}
于 2013-01-29T10:11:19.477 回答
0

这是一个大问题：

Node<type> *newNode;
newNode->data = new_data;

您声明一个指针并开始直接访问它，而不为它分配内存。这意味着指针指向一个看似随机的位置。导致不确定的行为和奇怪的事情发生是可以预料的。

此外，如果您为节点分配内存，则会出现内存泄漏，因为您没有释放pop函数中的节点。

于 2013-01-29T10:11:33.727 回答