Write Code In C++ 5-1 Motivation: This project is to implement Priority Queue, u

Question

Write Code In C++

5-1 Motivation: This project is to implement Priority Queue, using array or a complete binary tree structure. Details about priority queue can be found from http://www.cse.cuhk.edu.hk/~taoyf/course/2100sum11/lec8.pdf

5-2 Requirements: You should name your Prority Queue class as PQ. The queue must be able to hold unlimited number of integers. It has two key operations: Push and Pop, which should have the time complexity of O(logn).

5-3 Files to turn in: You need to turn in four files: makefile, main.C, PQ.C, PQ.h. You should have a main.C that reads in or generates some integers, pushes them into the PQ one by one, and pops and prints them until the PQ is empty.

5-4 Grading The total points is 12, you will get full credit if you correctly implement it using tree structure, 6 points if you correctly implement it using array. No late turn in is acceptable, any late turn in will be given 0 point. Your code must be compilable on Linux/Unix, any code that cannot be compiled by g++ will automatically get ZERO point.

Use This Main File:

#include <iostream>

#include "PQ.h"

#include <stdlib.h> /* for random number generation */

#include <time.h> /* time for random seed*/

using namespace std;

int main(){

PQ pq;

/* initialize random seed: */

srand (time(NULL));

for (int i = 1; i < 10; ++i) pq.Push(rand() % 100 + 1);

Node * p = pq.tail;

while(p != pq.head){

cout << p->val << endl;

p = p->prev;

}

for (int i = 0; i < 10; i++) cout << pq.Pop() << ", ";

}

Explanation / Answer

#include <stdio.h>

#include <stdlib.h>

#define SIZE 5

struct node

{

int data;

struct node *right,*left;

};

struct Queue

{

int front, rear;

int size;

struct node* *array;

};

struct node* newNode(int data)

{

struct node* temp = (struct node*) malloc(sizeof( struct node ));

temp->data = data;

temp->left = temp->right = NULL;

return temp;

}

struct Queue* createQueue(int size)

{

struct Queue* queue = (struct Queue*) malloc(sizeof( struct Queue ));

queue->front = queue->rear = -1;

queue->size = size;

queue->array = (struct node**) malloc(queue->size * sizeof( struct node* ));

int i;

for (i = 0; i < size; ++i)

queue->array[i] = NULL;

return queue;

}

int isEmpty(struct Queue* queue)

{

return queue->front == -1;

}

int isFull(struct Queue* queue)

{ return queue->rear == queue->size - 1; }

int hasOnlyOneItem(struct Queue* queue)

{ return queue->front == queue->rear; }

void Enqueue(struct node *root, struct Queue* queue)

{

if (isFull(queue))

return;

queue->array[++queue->rear] = root;

if (isEmpty(queue))

++queue->front;

}

struct node* Dequeue(struct Queue* queue)

{

if (isEmpty(queue))

return NULL;

struct node* temp = queue->array[queue->front];

if (hasOnlyOneItem(queue))

queue->front = queue->rear = -1;

else

++queue->front;

return temp;

}

struct node* getFront(struct Queue* queue)

{ return queue->array[queue->front]; }

int hasBothChild(struct node* temp)

{

return temp && temp->left && temp->right;

}

void insert(struct node **root, int data, struct Queue* queue)

{

struct node *temp = newNode(data);

if (!*root)

*root = temp;

else

{

// get the front node of the queue.

struct node* front = getFront(queue);

// If the left child of this front node doesn’t exist, set the

// left child as the new node

if (!front->left)

front->left = temp;

// If the right child of this front node doesn’t exist, set the

// right child as the new node

else if (!front->right)

front->right = temp;

// If the front node has both the left child and right child,

// Dequeue() it.

if (hasBothChild(front))

Dequeue(queue);

}

// Enqueue() the new node for later insertions

Enqueue(temp, queue);

}

// Standard level order traversal to test above function

void levelOrder(struct node* root)

{

struct Queue* queue = createQueue(SIZE);

Enqueue(root, queue);

while (!isEmpty(queue))

{

struct node* temp = Dequeue(queue);

printf("%d ", temp->data);

if (temp->left)

Enqueue(temp->left, queue);

if (temp->right)

Enqueue(temp->right, queue);

}

}

// Driver program to test above functions

int main()

{

struct node* root = NULL;

struct Queue* queue = createQueue(SIZE);

int i;

for(i = 1; i <= 12; ++i)

insert(&root, i, queue);

levelOrder(root);

return 0

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.