I wrote a priority queue in C that accepts passenger info of a flight by using their priorities. There are three main ticket classes (Business, Economy, Standard) and Business has a special class as 'diplomat' and Economy has too as 'veteran'. Here is a list of input info with their corresponding priorities in parentheses:
Input: bus_1(1), eco_1(3), bus_2(1), eco_2(3), std_1(4), eco_3(3), eco_4(3), bus_3(0), bus_4(1), eco_6(2), eco_7(2)
Output: bus_3, bus_1, bus_4, bus_2, eco_7, eco_6, eco_4, eco_3, eco_2, eco_1, std_1
What it should be: bus_3, bus_1, bus_2, bus_4, eco_6, eco_7, eco_1, eco_2, eco_3, eco_4, std_1
0 is the highest priority and 4 is the least. I know my code is not correct but I can't figure out the correct way to write an algorithm to push the same priority item after the one already in the queue. Here is my function:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
enum classes
{
business,
economy,
standard
};
struct flight
{
char flightName[8];
//for priority queue
struct queueNode *rootNode;
int hasRoot;
int businessQueueCount, economyQueueCount, standardQueueCount;
int totalPassengerCount;
};
struct passenger
{
char passengerName[15];
char flightName[8];
};
struct queueNode
{
struct passenger passenger;
int priority;
struct queueNode *next;
};
struct queueNode *newQueueNode(char flightName[8], char passengerName[15], int priority)
{
struct queueNode *temp = malloc(sizeof(struct queueNode));
temp->priority = priority;
temp->next = NULL;
strcpy(temp->passenger.flightName, flightName);
strcpy(temp->passenger.passengerName, passengerName);
return temp;
}
void pushQueue(struct queueNode **head, char *flightName, char *passengerName, int priority)
{
struct queueNode *start = (*head);
struct queueNode *temp = newQueueNode(flightName, passengerName, priority);
if ((*head)->priority > priority)
{
temp->next = *head;
(*head) = temp;
}
else
{
if (start->next != NULL && start->next->priority == priority)
{
temp->next = start->next->next;
start->next->next = temp;
}
else
{
while (start->next != NULL && start->next->priority < priority)
{
start = start->next;
}
temp->next = start->next;
start->next = temp;
}
}
}
struct passenger peekQueue(struct queueNode **head)
{
return (*head)->passenger;
}
void popQueue(struct queueNode **head)
{
struct queueNode *temp = *head;
(*head) = (*head)->next;
free(temp);
}
int main(){
struct flight flight_temp;
strcpy(flight_temp.flightName, "flight1");
flight_temp.rootNode = newQueueNode(flight_temp.flightName, "bus_1", 1);
pushQueue(&(flight_temp.rootNode), flight_temp.flightName, "eco_1", 3);
pushQueue(&(flight_temp.rootNode), flight_temp.flightName, "bus_2", 1);
pushQueue(&(flight_temp.rootNode), flight_temp.flightName, "std_1", 4);
pushQueue(&(flight_temp.rootNode), flight_temp.flightName, "eco_3", 3);
pushQueue(&(flight_temp.rootNode), flight_temp.flightName, "bus_3", 0);
pushQueue(&(flight_temp.rootNode), flight_temp.flightName, "bus_4", 1);
pushQueue(&(flight_temp.rootNode), flight_temp.flightName, "eco_4", 3);
for (size_t i = 0; i < 6; i++)
{
printf("%s\n", peekQueue(&(flight_temp.rootNode)).passengerName);
popQueue(&(flight_temp.rootNode));
}
}
Thanks in advance for your help.
Essentially, your pushQueue function is trying to insert into a sorted list, making sure that if an equal item is already there, the new item goes after it. But you have a couple of problems in your code that make it fail. I've added some comments to your code to show you where the errors are.
void pushQueue(struct queueNode **head, char *flightName, char *passengerName, int priority)
{
struct queueNode *start = (*head);
struct queueNode *temp = newQueueNode(flightName, passengerName, priority);
if ((*head)->priority > priority)
{
temp->next = *head;
(*head) = temp;
// if you put a return statement here, then you can get rid of
// the else. It reduces nesting and makes your code cleaner.
}
else
{
// If the new item has the same priority as what's already in the list,
// then you insert the new item right after it. What if there were two
// or more items with the same priority? The new one wouldn't go
// to the end of the list.
// This code really is just a broken special case for the else below.
if (start->next != NULL && start->next->priority == priority)
{
temp->next = start->next->next;
start->next->next = temp;
}
else
{
// You want to insert the new item after any existing items that
// have the same priority. But your logic will stop when it finds
// the first node that has the same priority. So the new item
// gets inserted at the front. You need to change '<' to '<='
while (start->next != NULL && start->next->priority < priority)
{
start = start->next;
}
temp->next = start->next;
start->next = temp;
}
}
}
You can simplify your code quite a bit by combining your cases. And also get away from brain-bending expressions like start->next->next that are hard to reason about and easy to get wrong, resulting in trying to dereference a NULL pointer.
void pushQueue(struct queueNode **head, char *flightName, char *passengerName, int priority)
{
struct queueNode *currentNode = (*head);
struct queueNode *nextNode;
struct queueNode *newNode = newQueueNode(flightName, passengerName, priority);
// if the new node's priority is less than the head node's priority,
// then the new node becomes the head.
if ((*head)->priority > priority)
{
newNode->next = *head;
(*head) = newNode;
return;
}
// Traverse the list looking for the first node whose priority
// is greater than the new node's priority.
nextNode = currentNode->next;
while (nextNode != NULL && nextNode->priority <= priority)
{
currentNode = nextNode;
nextNode = currentNode->next;
}
// at this point, you want to insert your new node between
// currentNode and nextNode
currentNode->next = newNode;
newNode->next = nextNode;
}
You'll want to test that, of course. I didn't really change your algorithm: just combined your two special cases into one.