C语言用一个链表实现链队列按优先级顺序入队代码

在C语言中，要实现一个链队列（Priority Queue），其中元素按照优先级排序，可以结合链表结构（通常使用双向链表）和堆数据结构来完成。这里我会给出一个简单的示例，假设我们有一个自定义节点结构，包含优先级值以及实际的数据。

首先，创建一个节点结构（Node）：

typedef struct Node {
    int priority; // 优先级
    void *data;    // 数据指针
    struct Node *prev, *next;
} PriorityQueueNode;

然后，我们可以创建一个双向链表头结点（PriorityQueueHead）：

struct PriorityQueueHead {
    PriorityQueueNode *min; // 指向最小优先级的节点
    PriorityQueueNode *max; // 指向最大优先级的节点（用于删除操作）
};

接下来，定义队列的基本操作：

1. 初始化队列：

void initPriorityQueue(PriorityQueueHead *pq) {
    pq->min = pq->max = NULL;
}

2. 插入元素（堆化操作）：

void insert(PriorityQueueHead *pq, int priority, void *data) {
    PriorityQueueNode *newNode = malloc(sizeof(PriorityQueueNode));
    newNode->priority = priority;
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = pq->min;

    if (pq->min != NULL) {
        newNode->prev->next = newNode;
    } else {
        pq->max = newNode;
    }

    if (priority < pq->min->priority) {
        pq->min = newNode;
    } else if (priority > pq->max->priority) {
        pq->max = newNode;
    }
    // 堆化操作
    siftDown(pq, newNode);
}

3. 堆化函数（siftDown）：

void siftDown(PriorityQueueHead *pq, PriorityQueueNode *node) {
    while (node->prev && node->priority < node->prev->priority) {
        PriorityQueueNode temp = *node->prev;
        *node->prev = *node;
        *node = temp;

        node = node->prev;
    }
}

4. 出队操作：

void* dequeue(PriorityQueueHead *pq) {
    if (pq->min == NULL) return NULL; // 空队列

    PriorityQueueNode *temp = pq->min;
    pq->min = pq->min->next;

    if (pq->min == NULL) {
        pq->max = NULL;
    } else {
        pq->min->prev = NULL;
        siftUp(pq, pq->min); // 重新调整堆顶
    }

    free(temp);
    return temp->data;
}

// siftUp函数对上移操作的堆化处理
void siftUp(PriorityQueueHead *pq, PriorityQueueNode *node) {
    while (node->next != pq->max && node->priority > node->next->priority) {
        PriorityQueueNode temp = *node;
        *node = *node->next;
        *node->next = temp;

        node = node->next;
    }
}