By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,007 Members | 1,033 Online
Bytes IT Community
+ Ask a Question
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
  1. class Node
  2. {
  3.     public: Node(int imway);
  4.             ~Node();
  5.             int noofKeys;
  6.             int *keys;
  7.             Node **childPointer;
  8.  
  9.     private:
  10.             int Nodemway;
  11.  
  12. };
  13.  
  14. Below is the node for the queue .
  15. struct QueueNode
  16. {
  17.             Node *storedNode;
  18.             struct QueueNode *next;
  19.             QueueNode(int mway)
  20.             {
  21.                 storedNode = new Node(mway);
  22.                 storedNode = NULL;
  23.             }
  24. };
  25.  
  26. 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.
  27. class Dq
  28. {
  29.     public:
  30.             Dq(int mway);
  31.             ~Dq();
  32.             void Enqueue(Node *root);
  33.             Node* Dequeue(void);
  34.             bool isEmpty(void);
  35.     private:
  36.             int Nodemway;
  37.             struct QueueNode *front,*rear;
  38. };
  39.  
  40. Dq::Dq(int mway)
  41. {
  42.     front = rear = NULL;
  43.     Nodemway = mway;
  44. }
  45.  
  46. Dq::~Dq()
  47. {
  48.     front = rear = NULL;
  49. }
  50.  
  51. void Dq::Enqueue(Node *root)
  52. {
  53.     struct QueueNode *ptr;
  54.  
  55.     ptr->storedNode = root;
  56. /*
  57.     ptr->next = NULL;
  58.  
  59.     if(front == NULL)
  60.     {
  61.         cout<<"NULL FRONT";
  62.         front = ptr;
  63.     }
  64.     else
  65.         rear->next = ptr;
  66.     rear = ptr;
  67.     */
  68. }
  69.  
  70. Node* Dq::Dequeue(void)
  71. {
  72.     if(!isEmpty())
  73.     {
  74.         struct QueueNode *tmp;
  75.         tmp = front;
  76.         front = front->next;
  77.         return tmp->storedNode;
  78.     }
  79.     else
  80.         return NULL;
  81. }
  82.  
  83. bool Dq::isEmpty()
  84. {
  85.     if(front == NULL)
  86.         return true;
  87.     else
  88.         return false;
  89. }
  90.  
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

✓ answered by Banfa

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.

Share this Question
Share on Google+
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

Banfa
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 <deque> or <list> class, for example

#include <deque>
std::deque<Node *>queue;

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

Banfa
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

Post your reply

Sign in to post your reply or Sign up for a free account.