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

gskbond

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.

gskbond

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..

Banfa

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.

gskbond

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??

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.

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

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

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

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

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

Similar C / C++ bytes

/bytes/development

/bytes/it

/bytes/about