Implementing a Priority Queue as a Sorted Doubly Linked List (15 points) This is
ID: 3853253 • Letter: I
Question
Implementing a Priority Queue as a Sorted Doubly Linked List (15 points)
This is a program for simulating enrollment of students in a set of courses. Included in this is a waitlist which allows students to queue up for possible free space in the course. This free space may come from additional seats being added to the course or from students choosing to drop the course. The waitlist queue is a priority queue where some students are given a higher priority for being added to the course (e.g., seniors may be given a higher priority than freshman or majors given preference over non-majors). The priority queue is represented using a sorted doubly linked list. Higher numbers are associated with higher priorities. The higher the priority a student has the closer to the front of the queue they should be. In the case of students with the same priority, the one who entered the queue first should be given preference. There are two data files used for this assignment. The code for reading from these files has already been provided (see the main of the provided code). Students are specified by a 3 digit id and courses are specified by a 4 digit id. The “a3 EnrollData.txt” file specifies a sequence of three types of operations to be performed on the courses/students. You are responsible for implementing functions which execute these three operations: (1) enroll - Attempt to enroll the student in the course (2) addSeats - Add the specified number of seats to the course and adds students from the waitlist to fill these seats (3) drop - Drop the student from the course and fill the empty seat from the waitlist Some code has been provided for you to help in creating functions to execute the above three operations. In addition to the above you also need to implement your priority queue using a doubly linked list. Specifically, (1) enqueue - Add a new waitlist element to the priority queue. This element needs to be inserted in sorted order. (2) dequeue - Remove and return the front element from the LL.
Here is the code we were given that we have to use:
These are the extra files:
a3_CourseData.txt
a3_EnrollData.txt
Explanation / Answer
Here is the completed code with output. Please rate the answer if it helped. Thank you
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct{
int iPriority; /* Priority of the student to be enrolled */
int iStudentID; /* ID of the student */
} WaitlistEntry;
typedef struct PQNode {
WaitlistEntry info; /* WaitlistEntry stored in the node (sorted with largest priority first) */
struct PQNode* pNext; /* Pointer to next node in the LL */
struct PQNode* pPrev; /* Pointer to previous node in the LL */
} PQNode;
typedef struct{
int iCourseNumber; /* Course number of the course */
int* iStudentIDs; /* Array of IDs of students enrolled in the course */
int iNumEnrolled; /* Number of Students currently enrolled in course */
int iMaxEnrolled; /* Max number of Students that can enroll in the course */
PQNode* pFront; /* Priority queue representing the waitlist for the course */
} Course;
typedef enum { FALSE, TRUE } bool;
/* PQ function prototypes */
void printQueue( PQNode* pFront );
/* To be completed by you */
WaitlistEntry dequeue( PQNode** ppFront );
void enqueue( PQNode** ppFront, WaitlistEntry info );
/* function prototypes for course management */
void enrollStudent( Course* pCourse, int iStudentID );
void waitlistStudent( Course* pCourse, WaitlistEntry wl );
int searchCourses( Course* pCourses, int iNumCourses, int iCourseID );
int findStudent( Course* pCourse, int iStudentID );
/* To be completed by you */
void addSeats( Course* pCourse, int NumAdded );
void attemptEnrollment( Course* pCourse, int iStudentID, int iPriority );
void dropStudent( Course* pCourse, int iStudentID );
/* provided code - DO NOT CHANGE
* main simulates the waitlist for a number of courses by calling your functions
*/
int main( )
{
char courseFileName[] = "a3_CourseData.txt";
char enrollFileName[] = "a3_EnrollData.txt";
char szCommand[256];
FILE *in_file = fopen(courseFileName, "r");
Course *pCourses;
int i;
int iNumCourses;
int iCourseNumber;
int iCourse;
int iStudent;
int iPriority;
int iNumAdd;
printf("CS 2123 Assignment 3 ");
if (in_file == NULL)
{
printf("File %s not found. ", courseFileName);
return -1;
}
/* read the number of courses from file and allocate space to store them */
fscanf( in_file, "%d", &iNumCourses );
pCourses = (Course*) malloc( iNumCourses*sizeof(Course) );
/* initialize course data */
for( i=0 ; i<iNumCourses; i++){
if( fscanf( in_file, "%d %d", &pCourses[i].iCourseNumber, &pCourses[i].iMaxEnrolled )!=2 )
break;
pCourses[i].iStudentIDs = (int*) malloc( pCourses[i].iMaxEnrolled*sizeof(int) );
pCourses[i].iNumEnrolled = 0;
pCourses[i].pFront = NULL;
}
fclose(in_file);
/* open enrollment data file */
in_file = fopen(enrollFileName, "r");
if (in_file == NULL)
{
printf("File %s not found. ", enrollFileName);
return -1;
}
/* reads enrollment data and calls your functions to handle the commands */
while( !feof(in_file) ){
if(fscanf( in_file, "%s", szCommand)!=1 )
break;
if( strcmp(szCommand, "enroll")==0 ){
fscanf( in_file, "%d %d %d", &iCourse, &iStudent, &iPriority );
iCourseNumber = searchCourses( pCourses, iNumCourses, iCourse );
attemptEnrollment( &pCourses[iCourseNumber], iStudent, iPriority );
}
else if( strcmp(szCommand, "addSeats")==0 ){
fscanf( in_file, "%d %d", &iCourse, &iNumAdd);
iCourseNumber = searchCourses( pCourses, iNumCourses, iCourse );
addSeats( &pCourses[iCourseNumber], iNumAdd );
}
else if( strcmp(szCommand, "drop")==0 ){
fscanf( in_file, "%d %d", &iCourse, &iStudent);
iCourseNumber = searchCourses( pCourses, iNumCourses, iCourse );
dropStudent( &pCourses[iCourseNumber], iStudent );
}
printf(" " );
}
fclose(in_file);
/* Free course data */
for( i=0 ; i<iNumCourses; i++){
free( pCourses[i].iStudentIDs );
}
free( pCourses );
return 0;
}
/* provided code - DO NOT CHANGE
* search courses for one with iCourseNumber equal to iCourseID and return its index in the pCourses array
* returns -1 if the course is not found
*/
int searchCourses( Course* pCourses, int iNumCourses, int iCourseID ){
int i;
for( i=0; i<iNumCourses; i++ ){
if( pCourses[i].iCourseNumber==iCourseID )
return i;
}
return -1;
}
/* provided code - DO NOT CHANGE
* search the given course's iStudentIDs for an enrolled student.
* If the student is found it returns their index in the iStudentIDs array
* returns -1 if the iStudentID is not found
*/
int findStudent( Course* pCourse, int iStudentID ){
int i;
for( i=0; i<pCourse->iNumEnrolled; i++ ){
if( pCourse->iStudentIDs[i]==iStudentID )
return i;
}
return -1;
}
/*
* addSeats increases the maximum enrollment of the course by NumAdded.
* Use realloc to increase the number of student IDs which can be storexd in pCourse.
* dequeue students from the waitlist call enrollStudent on them to add them to the
* course until the course is full or the waitlist is empty.
*
* precondition: NumAdded > 0
*/
void addSeats( Course* pCourse, int NumAdded ){
WaitlistEntry entry;
/* increase the maximum enrollment of pCourse */
pCourse->iMaxEnrolled += NumAdded;
/*reallocate space since the size is increased*/
pCourse->iStudentIDs = (int *)realloc(pCourse->iStudentIDs, pCourse->iMaxEnrolled *sizeof(int));
/* Print that seats have been added to the course (no changes needed to this line) */
printf("Added Seats: %d seats added to the course %d ", NumAdded, pCourse->iCourseNumber );
/* add students to the course until it is full or the waitlist is empty */
while(pCourse->pFront != NULL && pCourse->iNumEnrolled < pCourse->iMaxEnrolled)
{
entry = dequeue(&pCourse->pFront);
enrollStudent(pCourse, entry.iStudentID);
}
}
/*
* attemptEnrollment attempts to enroll the given student in the course pCourse.
* If there is room left in the course call enrollStudent to add the student.
* Otherwise call waitlistStudent to add the student to the course's waitlist.
*/
void attemptEnrollment( Course* pCourse, int iStudentID, int iPriority ){
/*check if there is more space for another student*/
if(pCourse->iNumEnrolled < pCourse->iMaxEnrolled)
{
enrollStudent(pCourse, iStudentID);
}
else /*otherwise put the student in waitlist*/
{
WaitlistEntry entry;
entry.iStudentID = iStudentID;
entry.iPriority = iPriority;
waitlistStudent(pCourse, entry);
}
}
/* provided code - DO NOT CHANGE
* enrolls the given student in the given course
*
* precondition: the course has room left in it to enroll the student
*/
void enrollStudent( Course* pCourse, int iStudentID ){
if( pCourse->iMaxEnrolled <= pCourse->iNumEnrolled ){
printf("ERROR - enrollStudent called with a full course %d ", pCourse->iCourseNumber );
return;
}
pCourse->iStudentIDs[pCourse->iNumEnrolled] = iStudentID;
pCourse->iNumEnrolled++;
printf("Enrolled: %d in %d ", iStudentID, pCourse->iCourseNumber );
}
/* provided code - DO NOT CHANGE
* adds the given student to the courses waitlist
*
* precondition: the course is full
*/
void waitlistStudent( Course* pCourse, WaitlistEntry wl ){
if( pCourse->iMaxEnrolled > pCourse->iNumEnrolled ){
printf("ERROR - waitlistStudent called with a non-full course %d ", pCourse->iCourseNumber );
return;
}
enqueue( &pCourse->pFront, wl );
printf("Waitlisted: %d in %d ", wl.iStudentID, pCourse->iCourseNumber );
printf("Current waitlist: " );
printQueue( pCourse->pFront );
}
/*
* dropStudent drops the given student from the course.
* If the waitlist is not empty you should dequeue the first student and enroll them in the now non-full course.
* It should print an error if the student to be dropped is not enrolled in the course.
*/
void dropStudent( Course* pCourse, int iStudentID ){
/* Use findStudent to determine where student is in iStudentIDs array */
int index = findStudent(pCourse, iStudentID);
int i;
WaitlistEntry entry;
if( index == -1 ){
printf("ERROR - dropStudent called to drop non-enrolled student %d from %d ", iStudentID, pCourse->iCourseNumber );
return;
}
/* Use a loop to shift down students in iStudentIDs array and fill gap from the dropped student */
for(i = index+1; i < pCourse->iNumEnrolled; i++)
pCourse->iStudentIDs[i-1] = pCourse->iStudentIDs[i];
pCourse->iNumEnrolled--; /*reduce since a student is dropped*/
/* Print that student has been dropped from the course (no changes needed to this line) */
printf("Dropped: %d from %d ", iStudentID, pCourse->iCourseNumber );
/* Add student if the waitlist is not empty */
if(pCourse->pFront != NULL)
{
entry = dequeue(&pCourse->pFront);
enrollStudent(pCourse, entry.iStudentID);
}
}
/*
* insert a new node which contains info into the priority queue contained in the linked list pointed to by ppFront
*/
void enqueue( PQNode** ppFront, WaitlistEntry info ){
/* create a new node to store the info */
PQNode* newNode = (PQNode*)malloc(sizeof(PQNode));
newNode->info = info;
newNode->pNext = NULL;
newNode->pPrev = NULL;
/* check if the LL is empty and add the new node to the front if it is */
if(*ppFront == NULL)
{
*ppFront = newNode;
return;
}
/* check if the new node should come before the first node in the LL */
if(newNode->info.iPriority > (*ppFront)->info.iPriority)
{
(*ppFront)->pNext = newNode;
newNode->pPrev = *ppFront;
*ppFront = newNode;
return;
}
/* walk back through the previous nodes in the LL until the correct insertion point is found */
/* remember to also check whether the previous node is NULL */
PQNode *current = *ppFront;
while(current->info.iPriority >= newNode ->info.iPriority)
{
/*insertion at the end of LL */
if(current->pPrev == NULL)
{
newNode->pNext = current;
current->pPrev = newNode;
return;
}
current = current->pPrev;
}
/* insert the new node into the place you found with your loop */
/* note you may need a special case for when the previous node is NULL */
/*set up the 4 links , newNode is placed between 2 nodes*/
newNode->pNext = current->pNext;
current->pNext = newNode;
newNode->pPrev = current;
newNode->pNext->pPrev = newNode;
}
/*
* remove the node at the front of the priority queue and return its info
*
* precondition: the queue is not empty
*/
WaitlistEntry dequeue( PQNode** ppFront ){
WaitlistEntry ret;
/*check if queue is not empty*/
if(*ppFront != NULL)
{
ret = (*ppFront)->info;
*ppFront = (*ppFront)->pPrev;
}
return ret;
}
/* provided code - DO NOT CHANGE
* print the contents of the priority queue contained in the linked list pointed to by ppFront
*/
void printQueue( PQNode* pFront ){
while( pFront!=NULL ){
printf("%d ", pFront->info.iStudentID);
pFront = pFront->pPrev;
}
printf(" ");
}
output
CS 2123 Assignment 3
Enrolled: 100 in 2123
Enrolled: 101 in 2123
Enrolled: 102 in 2123
Enrolled: 103 in 2123
Enrolled: 104 in 2123
Waitlisted: 109 in 2123
Current waitlist: 109
Waitlisted: 105 in 2123
Current waitlist: 105 109
Waitlisted: 108 in 2123
Current waitlist: 105 108 109
Waitlisted: 106 in 2123
Current waitlist: 105 106 108 109
Waitlisted: 107 in 2123
Current waitlist: 105 106 107 108 109
Added Seats: 1 seats added to the course 2123
Enrolled: 105 in 2123
Added Seats: 2 seats added to the course 2123
Enrolled: 106 in 2123
Enrolled: 107 in 2123
Dropped: 101 from 2123
Enrolled: 108 in 2123
Dropped: 100 from 2123
Enrolled: 109 in 2123
Dropped: 103 from 2123
Waitlisted: 100 in 3343
Current waitlist: 100
Waitlisted: 101 in 3343
Current waitlist: 101 100
Waitlisted: 102 in 3343
Current waitlist: 101 102 100
Added Seats: 5 seats added to the course 3343
Enrolled: 101 in 3343
Enrolled: 102 in 3343
Enrolled: 100 in 3343
Enrolled: 103 in 3343
Added Seats: 2 seats added to the course 3343
Program ended with exit code: 0