帮助链接列表模板

Question

我的链接列表需要一些帮助。我认为问题出在复制构造函数或赋值重载中。当我打电话时，它总是给出分段错误： （队列test_int_copy（test_int）；） 您看到的任何其他错误或不良实施也会非常有帮助。 .h 文件

#ifndef QUEUE_H
#define QUEUE_H

template <class Object>
class Queue
{
 public:
     Queue();
     //initializes empty queue

     Queue(const Queue& a_queue);
     //copy constructor

     Queue& operator =(const Queue& rhs);
     //overload assignment operator

     bool enqueue(const Object& d);
     //insert object into queue,return true
     //return false if not

     bool dequeue(Object& d);
     //remove object from queue,return true
     //if empty return false

     bool isEmpty();
     //check if empty

     ~Queue();
     //destructor

private:
    struct ListNode
    {
        Object obj;
        //object that is in the list

        ListNode *next;
        //pointer to the next node

    };
    //struct of list

    ListNode *head;
    //pointer that points to head
};

#endif //Queue_H
#include "queue.cpp"  //include queue.cpp with file

.cpp 文件

     #include <iostream>
using namespace std;

template <class Object>
Queue<Object>::Queue()
{
    head = NULL;
}

template <class Object>
Queue<Object>::Queue(const Queue<Object> &a_queue)
{
    head = NULL;
  ListNode *nodePtr = a_queue.head;
    while (nodePtr){
      enqueue(nodePtr->obj);
      nodePtr = nodePtr->next;
    }

}

template <class Object>
Queue<Object>& Queue<Object>::operator =(const Queue<Object> &rhs)
{
    //head = NULL;
  ListNode *nodePtr = rhs.head;
  Object temp;
    while(head){
      dequeue(temp);
    }
    while (nodePtr){
      enqueue(nodePtr->obj);
      nodePtr = nodePtr->next;
    }
}

template <class Object>
bool Queue<Object>::enqueue (const Object& d) //Enqueue
{
    ListNode *newNode = new ListNode;
    newNode->obj = d;
    newNode->next = NULL;
    ListNode *nodePtr = NULL;
    ListNode *previousNode = NULL;

    if(isEmpty()){
        head = newNode;
        return true;
        }
    else{
        nodePtr = head;
        while(nodePtr != NULL){
            previousNode = nodePtr;
            nodePtr = nodePtr->next;
        }
        if(previousNode->next == NULL){
            previousNode->next = newNode;
            return true;
        }
        else
            return false;
    }
}

template <class Object>
bool Queue<Object>::dequeue (Object& d)  //Dequeue
{
    ListNode *nodePtr;

    if(!head)
        return false;
    else{
      if(head->next != NULL){
            nodePtr = head;
            d = nodePtr->obj;
            head = head->next;
            delete nodePtr;
            return true;
      }
      else{
        d = head->obj;
        head = NULL;
        return true;
      }
    }
}


template <class Object>
bool Queue<Object>::isEmpty() //Check if Empty
{
    if(!head)
        return true;
    else
        return false;
}

template <class Object>
Queue<Object>::~Queue()   //Destructor
{
    Object temp;
    while(head)
        dequeue (temp);
}

Answer 1

也不要像这样包含源文件。或者，如果您坚持，请确保将其放入包含防护中。例如

#include "queue.cpp"  //include queue.cpp with file
#endif //Queue_H

，否则，如果多次包含标头（这种情况经常发生），则会出现编译错误。 （STuff 将被定义多次）。

另外，如果您要包含标头中的“源”，请确保所有函数都是“内联”（隐式或显式），否则您将收到链接器错误

Answer 2

您应该在复制构造函数中初始化头指针（顺便说一下，也在您的运算符 = 函数中）。如果不这样做， head 可能会得到一个未定义的值并无法通过 IsEmpty 测试，这可能会导致排队崩溃。

Answer 3

我看到一个错误：在 dequeue() 方法中，删除最后一项后没有将 head 设置为 NULL。

另外，在赋值重载中：

while(head){
      dequeue(temp);
      head = head->next;
    }

...您不需要设置 head = head->next，这已经由 dequeue() 方法完成了。

Answer 4

1. 您的 enqueue() 函数始终在末尾插入一个节点。因此最好维护一个额外的成员变量：ListNode *tail;指向列表的最后一个节点。因此，当您添加节点时，无需遍历整个列表，只需更新 *tail 即可。这会节省很多时间。
2. 无论出于何种原因，您从 enqueu() 返回 false，都不要忘记 delete newNode; 否则会泄漏内存。
3. isEmpty() 你可以简化为 bool isEmpty() { return (0 != head); }。
4. 而不是声明 &在 dequeue() 中传递原始对象，如果元素被删除，您可以简单地返回 Object* ，或者如果元素为空，则返回 0 (NULL) ；这相当于 true 和 false。
5. 重要的是，每当您删除 head; 时，始终执行 head = 0;。因为这是一个成员变量，不应该是悬空的。