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.
- 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. - For whatsoever reason you return
false
fromenqueu()
, do NOT forget todelete newNode;
otherwise it will leak memory. isEmpty()
you can simplify asbool isEmpty() { return (0 != head); }
.- Instead of declaring & passing a raw object in
dequeue()
, you can simply returnObject*
if element is removed or return0 (NULL)
if it's empty; that's equivalent totrue
andfalse
. - Importantly, whenever you
delete head;
always dohead = 0;
. Because that's a member variable and should not be dangling.
精彩评论