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.

Please dont use high-level code! Im also trying to learn from this so please use low-moderate level code. Please clarify the seperate main/PQ.C/PQ.h. Thanks!

Explanation / Answer

/*---Program Name: PQ.C----*/

#include <stdio.h>
#include <conio.h>

#define MAX 5

struct Info
{
    char j[MAX] ;
    int prno ;
    int order ;
} ;

struct PQ
{
    struct Info d[MAX] ;
    int front ;
    int rear ;
} ;

void InitPQ ( struct PQ * ) ;
void Push ( struct PQ *, struct Info ) ;
struct Info Pop ( struct PQ * ) ;

void main( )
{
    struct PQ q ;
    struct Info dt, temp ;
    int i, j = 0 ;

    clrscr( ) ;

    InitPQ ( &q ) ;

    printf ( "Enter Job description (max 4 chars) and its priority " ) ;
    printf ( "Lower the priority number, higher the priority " ) ;
    printf ( "Job     Priority " ) ;

    for ( i = 0 ; i < MAX ; i++ )
    {
        scanf ( "%s %d", &dt.job, &dt.prno ) ;
        dt.order = j++ ;
        Push ( &q, dt ) ;
    }
    printf ( " " ) ;

    printf ( "Process jobs prioritywise " ) ;
    printf ( "Job Priority " ) ;

    for ( i = 0 ; i < MAX ; i++ )
    {
        temp = Pop ( &q ) ;
        printf ( "%s %d ", temp.job, temp.prno ) ;
    }
    printf ( " " ) ;

    getch( ) ;
}

/* initialises data members */
void InitPQ ( struct PQ *pq )
{
    int i ;

    pq -> front = pq -> rear = -1 ;
    for ( i = 0 ; i < MAX ; i++ )
    {
        strcpy ( pq -> d[i].job, '' ) ;
        pq -> d[i].prno = pq -> d[i].order = 0 ;
    }
}

/* adds item to the priority queue */
void Push ( struct PQ *pq, struct Info dt )
{
    struct Info temp ;
    int i, j ;

    if ( pq -> rear == MAX - 1 )
    {
        printf ( " Queue is full." ) ;
        return ;
    }

    pq -> rear++ ;
    pq -> d[pq -> rear] = dt ;

    if ( pq -> front == -1 )
        pq -> front = 0 ;

    for ( i = pq -> front ; i <= pq -> rear ; i++ )
    {
        for ( j = i + 1 ; j <= pq -> rear ; j++ )
        {
            if ( pq -> d[i].prno > pq -> d[j].prno )
            {
                temp = pq -> d[i] ;
                pq -> d[i] = pq -> d[j] ;
                pq -> d[j] = temp ;
            }
            else
            {
                if ( pq -> d[i].prno == pq -> d[j].prno )
                {
                    if ( pq -> d[i].ord > pq -> d[j].order )
                    {
                        temp = pq -> d[i] ;
                        pq -> d[i] = pq -> d[j] ;
                        pq -> d[j] = temp ;
                    }
                }
            }
        }
    }
}

/* removes item from priority queue */
struct Info Pop ( struct PQ *pq )
{
    struct Info t ;
    strcpy ( t.job, "" ) ;
    t.prno = 0 ;
    t.ord = 0 ;

    if ( pq -> front == -1 )
    {
        printf ( " Queue is Empty. " ) ;
        return t ;
    }

    t = pq -> d[pq -> front] ;
    pq -> d[pq -> front] = t ;
    if ( pq -> front == pq -> rear )
         pq -> front = pq -> rear = -1 ;
    else
         pq -> front++ ;

    return t ;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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