The objectives of this assignment are to write a program to implement a simple p
ID: 3746617 • Letter: T
Question
The objectives of this assignment are to write a program to implement a simple priority queue using a sorted, singularly linear linked list data structure. The priority queue code should be structured as if it were part of a software library to be used with other prog someone else. Small keys indicate higher priority. The software should implement the following interface rams written by 1. Use a typedef to define a data structure called Prioo, defined as a C struct representing the priority queue. The implementation of the data structure is not visible outside the library you are creating 2. Write a function with the prototype Priog *PO_create()i Create a new priority queue and return a pointer to it. The priority queue is initially empty, i.c., contains no elements. Return NULL if the operation failed, c.g., due to a lack of memory 3. Write a function with the prototype int PQ_insert(Prioo *PQ, double key, void "data); Insert the item pointed to by data into the priority queue PQ. The priority of this data item is key. Return NULL if the operation failed, or an arbitrary value not equal to NULL if it succeeded. The data type of the inserted item pointed to by data is defined by the caller, and is not visible to the priority queue library 4. Write a function with the prototype void *PQ_delete (Priog *PQ, double *key); Remove the data item from the priority queue PQ with the smallest key (priority). The function returns a pointer to the data item that was removed, or NULL if the queue was empty. The priority of the deleted item is returned in key 5. Write a function with the prototype Unsigned int PQ count (PrioQ *PQ) Returns the number of items crrently residing in the priority queue 6. Write a function with the prototype void *PQ free (struct PrioQ *PQ) Delete the priority queue Po by releasing all memory used by the contents of the data structure 7. Write a program to test your priority queue library. The test program should first create a priority queue, create 20 data elements, assign each a priority drawn from a random number generator and insert it into the queue. Then remove the elements one after another and verify that the priority of the removed items is in increasing order. Include print statements to demonstrate correct operation.Explanation / Answer
main.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "PrioQ.h"
#define PQ_TEST_LEN 20
int main(int argc, const char * argv[]) {
srand(time(NULL)); /* seed the random function */
/*************** variable declaration ****************/
int data[PQ_TEST_LEN]; /* 20 data element */
double* key = malloc(sizeof(double)); /* to save the key of removed item */
/*************** variable declaration ****************/
/********* create priority queue and check ***********/
PrioQ* PQ = PQ_create();
if (PQ == NULL) {
return 1;
}
/********* create priority queue and check ***********/
/************* create 20 data element ****************/
for (int i = 0; i<PQ_TEST_LEN; ++i) {
data[i] = i+1;
}
/************* create 20 data element ****************/
/* assign the data with random priority and insert into the queue */
for (int i = 0; i<PQ_TEST_LEN; ++i) {
/* check if it successfully allocate memory for new node */
if(!PQ_insert(PQ, (rand()/(double)RAND_MAX*10), &data[i])) /* random double key value from 0 to 10 */
return 1;
}
/* assign the data with random priority and insert into the queue */
/************* remove the elements *******************/
/* stop when the key pointer is null or data pointer is null or priority queue is empty */
while (PQ_delete(PQ, key) != NULL) {
printf("Remove the node with key %4.1f ",(*key));
}
/************* remove the elements *******************/
PQ_free(PQ);
return 0;
}
PrioQ.h
#ifndef PrioQ_h
#define PrioQ_h
#include <stdio.h>
#define LEN_Q sizeof(struct PrioQ)
#define LEN_N sizeof(struct Node)
/* Define a data stucture to implement Priority Queue */
typedef struct Node{
struct Node* next;
double key;
void* data;
}Node;
/* Define a data structure called PrioQ */
typedef struct PrioQ{
/* nodes content */
struct Node* head;
struct Node* tail;
int length;
}PrioQ;
/* Create a new priority queue and return a pointer to it */
PrioQ *PQ_create();
/* Insert the item pointed to by data into the priority queue PQ */
int PQ_insert(PrioQ *PQ, double key, void *data);
/* Remove the data item from the priority queue PQ with the smallest key (priority) */
void *PQ_delete(PrioQ *PQ, double *key);
/* Returns the number of items currently residing in the priority queue */
unsigned int PQ_count(PrioQ *PQ);
/* Delete the priority queue PQ by releasing all used memory */
void *PQ_free(struct PrioQ *PQ);
#endif /* PrioQ_h */
PrioQ.c
#include "PrioQ.h"
#include <stdlib.h>
/******* Create a new priority queue and return a pointer to it *********/
PrioQ *PQ_create(){
PrioQ* PQ = NULL;
PQ = malloc(LEN_Q);
/* If the request fails, malloc returns NULL and print error message to srceen */
if (PQ == NULL) {
printf("Error: Failed to allocate memory for Priority Queue ");
return NULL;
}
else{
/* initialization */
PQ->head = NULL;
PQ->tail = NULL;
PQ->length = 0;
return PQ;
}
}
/******* Create a new priority queue and return a pointer to it *********/
/***** Insert the item pointed to by data into the priority queue PQ ****/
int PQ_insert(PrioQ *PQ, double key, void *data){
Node* p1; /* the current node position */
Node* p2; /* the previous node position */
if (data == NULL) {
printf("Warning: Data is null ");
}
Node* new = malloc(LEN_N);
/* return NULL if the operation failed and print the error message */
if (new == NULL) {
printf("Error: Failed to allocate memory for new node ");
return 0;
}
else{
new->data = data;
new->key = key;
/* case 1: insert to an empty priority queue */
if (PQ->length == 0) {
new->next = NULL;
/* let the head and tail pointer both point to the new node */
PQ->head = new;
PQ->tail = new;
}
else{
p1 = PQ->head;
p2 = PQ->head;
/* case 2: insert at the front of the priority queue head */
if (p1->key > new->key) {
new->next = p1;
PQ->head = new;
}
else{
/* find the right place to insert the node according to its priority */
while (p1->next != NULL && p1->key <= new->key) {
p2 = p1;
p1 = p1->next;
}
/* case 3: insert at the end of the priority queue */
if (p1->next == NULL) {
new->next = NULL;
p1->next = new;
PQ->tail = new;
}
/* case 4: insert at the middle of the priority queue */
else{
new->next = p1;
p2->next = new;
}
}
}
}
/* increase the length of priority queue */
++PQ->length;
return 1;
}
/***** Insert the item pointed to by data into the priority queue PQ ****/
/* Remove the data item from the priority queue PQ with the smallest key (priority) */
void *PQ_delete(PrioQ *PQ, double *key){
if (key != NULL) {
Node* delete = PQ->head;
void* data;
/* parameter checks */
if (PQ->head == NULL) {
printf("This is an empty priority queue. No data to be removed. ");
return NULL;
}
/* remove the data item from the priority queue with the smallest key, which is the first element */
else{
PQ->head = PQ->head->next;
data = delete->data;
*key = delete->key;
/* free the corresponding memory */
free(delete);
}
/* decrease the length of priority queue */
--PQ->length;
if (data == NULL) {
printf("Warning: Data is null ");
}
return data;
}
/* parameter checks */
else{
printf("Error: The key pointer is NULL. BAD ACCESS. ");
return NULL;
}
}
/* Remove the data item from the priority queue PQ with the smallest key (priority) */
/*** Returns the number of items currently residing in the priority queue ***/
unsigned int PQ_count(PrioQ *PQ){
/* parameter checks */
if (PQ == NULL) {
printf("Error: Priority queue pointer equals to NULL. ");
return -1;
}
return PQ->length;
}
/*** Returns the number of items currently residing in the priority queue ***/
/********* Delete the priority queue PQ by releasing all used memory ********/
void *PQ_free(struct PrioQ *PQ){
/* parameter checks */
if (PQ == NULL) {
printf("Error: Priority queue pointer equals to NULL.");
return NULL;
}
Node* p = PQ->head;
/* empty queue */
if (PQ->length == 0) {
printf("It's already empty. ");
free(PQ);
return NULL;
}
/* free the node one by one */
while (PQ->length != 1) {
PQ->head = PQ->head->next;
free(p);
p = PQ->head;
--PQ->length;
}
/* free the last node and the entire priority queue */
if (PQ->length == 1) {
free(p);
free(PQ);
}
return NULL;
}
/********* Delete the priority queue PQ by releasing all used memory ********/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.