449,007 Members | 1,033 Online
Need help? Post your question and get tips & solutions from a community of 449,007 IT Pros & Developers. It's quick & easy.

# Queue using a linked list in c++ which stores a mway tree node

 P: 18 Below is the node for m way tree Expand|Select|Wrap|Line Numbers class Node {     public: Node(int imway);             ~Node();             int noofKeys;             int *keys;             Node **childPointer;       private:             int Nodemway;   };   Below is the node for the queue . struct QueueNode {             Node *storedNode;             struct QueueNode *next;             QueueNode(int mway)             {                 storedNode = new Node(mway);                 storedNode = NULL;             } };   Below is the queue class which will implement enqueue and dequeue methods which will enqueue / dequeue QueueNodes  which will have a single mway tree node stored in it. class Dq {     public:             Dq(int mway);             ~Dq();             void Enqueue(Node *root);             Node* Dequeue(void);             bool isEmpty(void);     private:             int Nodemway;             struct QueueNode *front,*rear; };   Dq::Dq(int mway) {     front = rear = NULL;     Nodemway = mway; }   Dq::~Dq() {     front = rear = NULL; }   void Dq::Enqueue(Node *root) {     struct QueueNode *ptr;       ptr->storedNode = root; /*     ptr->next = NULL;       if(front == NULL)     {         cout<<"NULL FRONT";         front = ptr;     }     else         rear->next = ptr;     rear = ptr;     */ }   Node* Dq::Dequeue(void) {     if(!isEmpty())     {         struct QueueNode *tmp;         tmp = front;         front = front->next;         return tmp->storedNode;     }     else         return NULL; }   bool Dq::isEmpty() {     if(front == NULL)         return true;     else         return false; }   Here I am facing problem at ptr->storedNode = root; in Enqueue function and I am getting segmentation fault.......... Can anybody please clarify where I am going wrong?? Or is it not possible to create a queue which will store a node as a data in it.? Other suggestions are also welcome. Oct 24 '09 #1

In Dq::Enqueue you are creating QueueNodes (Dq is the queue manager). However your current code does not create the, it uses a pointer without creating them. You should be using new to allocate QueueNodes.

If you are allocating QueueNodes with new then you need to be deallocating them with delete. This needs to be node in Dq::Dequeue and Dq::~Dq.

4 Replies

 P: 18 What I am trying to do is to have a queue implemented for level by level traverse of tree..... I want to push the node for tree on queue as data ....But I am getting error in above implementation.... please suggest where its going wrong.. Oct 24 '09 #2

 Expert Mod 5K+ P: 8,916 Fistly 21 storedNode = new Node(mway); 22 storedNode = NULL; is an instant memory leak every time you allocate a Node. You allocate memory and store in in a pointer the immediately clear the pointer without deallocating the memory. Line 21 is not required. Are you aware that the whole of your Dq and QueueNode classes could be simple replaced with an STL or class, for example #include std::dequequeue; Hwever assuming that you are writing this for an exercise and can't use the stl then void Dq::Enqueue(Node *root) causes a segment fault because you de-reference (use * or -> operators) ptr when it does not point anywhere. You never initialise ptr before using it. Presumable you needed to allocate memory for it. Assuming you did allocate memory for your Dq QueueNodes then in # # Node* Dq::Dequeue(void) you would get a memory leak because you never deallocate the memory allocated to the QueueNode you remove from the list. Oct 24 '09 #3

 P: 18 I am aware of stl...can not use it....have to implement my own queue.... I still did not get what exactly needs to be done and where??? Is it at destructor?? Oct 24 '09 #4

 Expert Mod 5K+ P: 8,916 In Dq::Enqueue you are creating QueueNodes (Dq is the queue manager). However your current code does not create the, it uses a pointer without creating them. You should be using new to allocate QueueNodes. If you are allocating QueueNodes with new then you need to be deallocating them with delete. This needs to be node in Dq::Dequeue and Dq::~Dq. Oct 24 '09 #5