c-使用链表而不将优先级作为输入的降序优先级队列

Question

我尝试使用以下代码，以便在Descending Priority Queue中插入一个元素。我很无奈，因为这个问题有几个答案，人们把priority作为用户的输入。在这里，我试图用以下条件进行排序：

#include<stdio.h>
#include<stdlib.h>
struct qElem 
{
int ele;
int priority;
struct qElem *next;
};
struct queue
{
struct qElem *front, *rear;
int size;
};
void enQueue(struct queue *q, int ele)
{
struct qElem *temp;
temp = (struct qElem *) malloc (sizeof(struct qElem));
temp->ele = ele;
temp->next = NULL;
if (q->rear == NULL) {
q->rear = temp;
q->front = temp;
}
else if (q-> rear -> ele < temp->ele){
q-> rear  = temp;
temp->next = q->rear;
}
++ q->size;
}
void display_pqueue(struct queue *q)    {
if(q->front == NULL)
printf("nQueue is Empty!!!n");
else{
struct qElem *temp = q->front;
while(temp->next != NULL){
printf("%d--->",temp->ele);
temp = temp -> next;
}
printf("%d--->NULLn",temp->ele);
}
}

插入没有按照订单进行。请帮助我进行EnQueue和Display操作。

Answer 1

您的enQueue不会扫描插入点。

而且，您没有提供[单独的]优先级作为参数，因此无法正确插入。

为了便于说明，我使用了ele来设置ele和priority。

有多种插入情况需要处理：

1. 空列表
2. 后部插件
3. 插入中间
4. 在非空列表中的第一个元素之前插入

无论如何，这是代码。请注意，尽管它设置了rear，但这并没有经过测试：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
struct qElem {
int ele;
int priority;
struct qElem *next;
};
struct queue {
struct qElem *front, *rear;
int size;
};
#ifdef DEBUG
#define dbgprt(_fmt...) 
printf(_fmt)
#else
#define dbgprt(_fmt...) 
do { } while (0)
#endif
int
show(struct qElem *cur)
{
int val;
if (cur != NULL)
val = cur->priority;
else
val = -1;
return val;
}
void
enQueue(struct queue *q, int ele)
{
struct qElem *temp;
struct qElem *cur;
struct qElem *prev;
temp = malloc(sizeof(*temp));
temp->ele = ele;
#if 1
temp->priority = ele;
#endif
temp->next = NULL;
dbgprt("enQueue: ele=%dn",ele);
// find correct insertion point (place to insert _after_)
// NOTE: this is descending (e.g. 3->2->1). For ascending, use ">"
prev = NULL;
for (cur = q->front;  cur != NULL;  cur = cur->next) {
if (cur->priority < ele)
break;
prev = cur;
}
do {
dbgprt("prev=%dn",show(cur));
dbgprt("cur=%dn",show(cur));
dbgprt("front=%dn",show(q->front));
dbgprt("rear=%dn",show(q->rear));
// empty list
if (q->front == NULL) {
q->front = temp;
q->rear = temp;
break;
}
// insert at front
if (prev == NULL) {
temp->next = q->front;
q->front = temp;
break;
}
// insert in priority place
temp->next = prev->next;
prev->next = temp;
} while (0);
// new rear of list
if (prev == q->rear)
q->rear = temp;
// increase number of elements in list
q->size += 1;
}
void
display_pqueue(struct queue *q)
{
if (q->front == NULL)
printf("nQueue is Empty!!!n");
else {
struct qElem *temp = q->front;
while (temp->next != NULL) {
printf("%d--->", temp->ele);
temp = temp->next;
}
printf("%d--->NULLn", temp->ele);
}
}
void
dotest(struct queue *q,...)
{
va_list ap;
memset(q,0,sizeof(*q));
printf("n");
printf("dotest:");
va_start(ap,q);
while (1) {
int val = va_arg(ap,int);
if (val < 0)
break;
printf(" %d",val);
enQueue(q,val);
}
printf("n");
display_pqueue(q);
struct qElem *next;
for (struct qElem *temp = q->front;  temp != NULL;  temp = next) {
next = temp->next;
free(temp);
}
}
int
main(void)
{
struct queue q;
dotest(&q,5,1,3,4,12,99,18,19,20,-1);
return 0;
}