c - C 中的优先级队列链表实现 - enqueue() 操作失败

Question

将节点正确插入队列的enqueue()操作包含我的程序的核心逻辑。我已经使用递归实现了相同的优先级队列，并且我知道程序的其余部分工作正常。现在我想使用公共(public)迭代来实现优先级队列。 enqueue() 操作应该按照我下面的计划草案进行。

但是，当我运行该程序时，它失败了，没有任何错误(在 VS 和 gcc 中测试)。我就是不明白我的逻辑在哪里失败了，这让我发疯。帮助将不胜感激!

代码如下。

// The PQ is sorted according to its value
// Descending order sorted insertion (bigger first -> smaller last)
void enqueue(pqType val, PriorityQueue *PQ)
{
if (!isFull(PQ)) {
    PQ->count++;

    Node *currentNode = PQ->headNode;   // Iterate through PQ using currentNode
    Node *prevNode = NULL;              // the previous Node of our current iteration
    Node *newNode = (Node*) malloc(sizeof(Node)); // The new Node that will be inserted into the Queue

    int i = 0;
    while (i < MAX_QUEUE_SIZE) {
        // if PQ is empty, or if val is larger than the currentNode's value then insert the new Node before the currentNode
        if ((currentNode == NULL) || (val >= currentNode->value)) {
            newNode->value = val;
            newNode->link = currentNode;
            prevNode->link = newNode;
            break;
        }
        else {
            prevNode = currentNode;
            currentNode = currentNode->link;
        }
        i++;
    }
    //free(currentNode);
    //free(prevNode);
}
else
    printf("Priority Queue is full.\n");
}

Answer 1

我认为问题出在第一个入队(当 PQ 为空时)，在这种情况下，您应该更改 PQ->headNode = newNode 而不是 prevnode->link = newNode，第一次入队后我认为你的代码会正常工作。

if(prevNode == NULL)
{
    PQ->headNode = newNode;
}
else
{
    prevNode->link = newNode;
}