开发者

help with linked list template

I need some help with my linked list. I think the problem is in the copy constructor or the assignment overload. it keeps giving my segmentation fault when i call: (Queue test_int_copy(test_int);) Any other error or poor implementation that you can see would also be very helpful. the .h file

#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;
        //poin开发者_JAVA技巧ter 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

the .cpp file

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


Also don't include the source file like that. Or if you insist, make sure to put it inside the include guard. e.g.

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

Otherwise if the header is included multiple times (which happens all the time), you'll have a compilation error. (STuff will be defined multipled times).

Also, if you're going to include the "source" from the header -- make sure all functions are "inline" (implicitly or explicitly), otherwise you'll get linker errors


You should initialize your head pointer in your copy constructor (and also in your operator = function by the way). If you don't do so, head might end up with an undefined value and fail the IsEmpty test, witch may lead to a crash in enqeue.


One mistake I can see: in the dequeue() method, you do not set head to NULL after removing the last item.

Also, in the assignment overload:

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

... You do not need to set head = head->next, that has already been done by the dequeue() method.


  1. Your enqueue() function always inserts a node in the end. So it's better to maintain an extra member variable as: ListNode *tail;pointing to the last node of the list. So when you are adding a node you don't need to traverse through whole list and simply update the *tail. This will save lot of time.
  2. For whatsoever reason you return false from enqueu(), do NOT forget to delete newNode; otherwise it will leak memory.
  3. isEmpty() you can simplify as bool isEmpty() { return (0 != head); }.
  4. Instead of declaring & passing a raw object in dequeue(), you can simply return Object* if element is removed or return 0 (NULL) if it's empty; that's equivalent to true and false.
  5. Importantly, whenever you delete head; always do head = 0;. Because that's a member variable and should not be dangling.
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜