将相同优先级的项目添加到 C 问题中的优先级队列

Question

我在 C 中写了一个优先级队列，它通过使用他们的优先级来接受航班的乘客信息。共有三种主要机票 classes（商务舱、经济舱、标准舱），商务舱有一个特殊的 class 和 'diplomat'，经济舱也有 'veteran'。以下是括号中相应优先级的输入信息列表：

输入： 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)

输出： bus_3, bus_1, bus_4, bus_2, eco_7, eco_6, eco_4, eco_3, eco_2, eco_1, std_1

应该是什么： bus_3, bus_1, bus_2, bus_4, eco_6, eco_7、eco_1、eco_2、eco_3、eco_4、std_1

0 是最高优先级，4 是最低优先级。我知道我的代码不正确，但我想不出正确的方法来编写算法以将相同优先级的项目推送到已在队列中的项目之后。这是我的功能：

#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));
    }






}

在此先感谢您的帮助。

Answer 1

本质上，您的 pushQueue 函数试图插入到排序列表中，确保如果已经存在相同的项目，则新项目会在它之后。但是您的代码中有几个问题导致它失败。我已经在您的代码中添加了一些注释，以向您展示错误所在。

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;
        }
    }
}

您可以通过组合案例来大大简化您的代码。还要避免像 start->next->next 这样难以推理且容易出错的令人费解的表达式，导致试图取消引用 NULL 指针。

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;
}

当然，您需要测试一下。我并没有真正改变你的算法：只是将你的两个特殊情况合并为一个。

将相同优先级的项目添加到 C 问题中的优先级队列

Adding same priority items to a priority queue in C problem

c

priority-queue