C语言 具有双向链表插入的优先级队列

Question

我正在使用双向链表实现优先级队列候补列表。我的方法创建一个新节点(优先级和学生 ID)。根据节点优先级，该方法会将节点排序到队列中。

what I get is                                what I should get
Waitlisted:             109 in 2123      |   Waitlisted:             109 in 2123
Current waitlist:       109              |   Current waitlist:       109
|
Waitlisted:             105 in 2123      |   Waitlisted:             105 in 2123
Current waitlist:       105              |   Current waitlist:       105 109
|
Waitlisted:             108 in 2123      |   Waitlisted:             108 in 2123
Current waitlist:       109 105          |   Current waitlist:       105 108 109
|
Waitlisted:             106 in 2123      |   Waitlisted:             106 in 2123
Current waitlist:       106              |   Current waitlist:       105 106 108 109
|
Waitlisted:             107 in 2123      |   Waitlisted:             107 in 2123
Current waitlist:       109 106          |   Current waitlist:       105 106 107 108 109

当第一个循环中的队列为空时，我可以插入一个新节点。从第二次运行开始，队列的返回值是错误的。

法典

void enqueue( PQNode** ppFront, WaitlistEntry info ){
/* create a new node to store the info */
PQNode *temp = (PQNode*)malloc(sizeof(PQNode)); //create a new node to store the info
temp->info = info;
temp->pNext = NULL;
temp->pPrev = NULL;
/* check if the LL is empty and add the new node to the front if it is */
if(*ppFront == NULL){
*ppFront = temp;
return;
}
/* check if the new node should come before the first node in the LL */
if(temp->info.iPriority > (*ppFront)->info.iPriority){
temp->pNext = *ppFront;
(*ppFront)->pPrev = temp;
*ppFront = temp;
return;
}   
/* walk back through the previous nodes in the LL until the correct insertion point is found */
/* remember to also check whether the previous node is NULL */
while((*ppFront)->pNext != NULL && temp->info.iPriority <= (*ppFront)->info.iPriority){
*ppFront = (*ppFront)->pNext;
}
/* insert the new node into the place you found with your loop */
/* note you may need a special case for when the previous node is NULL */
if((*ppFront)->pNext == NULL){
(*ppFront)->pNext = temp;
temp->pPrev = *ppFront;
return;
}
temp->pPrev = *ppFront;
temp->pNext = (*ppFront)->pNext;
(*ppFront)->pNext->pPrev = temp;
(*ppFront)->pNext = temp;
return;
}

结构体

typedef struct{
int iPriority;          /* Priority of the student to be enrolled */
int iStudentID;         /* ID of the student */
} WaitlistEntry;
typedef struct PQNode {
WaitlistEntry info;     /* WaitlistEntry stored in the node (sorted with largest priority first) */
struct PQNode* pNext;   /* Pointer to next node in the LL */
struct PQNode* pPrev;   /* Pointer to previous node in the LL */
} PQNode;
typedef struct{
int iCourseNumber;      /* Course number of the course */
int* iStudentIDs;       /* Array of IDs of students enrolled in the course */
int iNumEnrolled;       /* Number of Students currently enrolled in course */
int iMaxEnrolled;       /* Max number of Students that can enroll in the course */
PQNode* pFront;         /* Priority queue representing the waitlist for the course */
} Course;

我已经设法修复了一些代码，但我仍然卡住了。

Answer 1

正如 BLUEPIXY 所提到的，函数的最后一点有点错误(//edit 你在此期间更改了代码，我指的是你的原始代码)。当你浏览while块中的列表，然后你意识到curr是尾巴时，你无法检查你是否到达了那里，因为temp的优先级大于尾巴，或者你已经到达了列表的末尾，temp应该成为新的尾巴。

此外，您插入的最后一部分temp错误的一侧。

代码的最后一部分应该是这样的

编辑发布整个代码，我只更改了函数的最后一位和enqueue参数，为此编写测试代码要容易得多。

void print_queue(PQNode *queue)
{
if(queue == NULL)
{
puts("empty queue");
return;
}
for(;;)
{
printf("%d (priority %d)", queue->info.iStudentID, queue->info.iPriority);
queue = queue->pNext;
if(queue == NULL)
{
puts("");
return;
}
printf(" <--> ");
}
}

void enqueue( PQNode** ppFront, int id, int prio ){
/* create a new node to store the info */
PQNode *temp = (PQNode*)malloc(sizeof(PQNode)); //create a new node to store the info
temp->info.iStudentID = id;
temp->info.iPriority = prio;
temp->pNext = NULL;
temp->pPrev = NULL;
PQNode *curr = *ppFront;

/* check if the LL is empty and add the new node to the front if it is */
if(curr == NULL){
*ppFront = temp;
return;
}
/* check if the new node should come before the first node in the LL */
if(temp->info.iPriority > curr->info.iPriority){
temp->pNext = *ppFront;
(*ppFront)->pPrev = temp;
*ppFront = temp;
return;
}   
/* walk back through the previous nodes in the LL until the correct insertion point is found */
/* remember to also check whether the previous node is NULL */
while(curr->pNext != NULL && temp->info.iPriority <= curr->info.iPriority){
curr = curr->pNext;
}

/* insert the new node into the place you found with your loop */
/* note you may need a special case for when the previous node is NULL */
if(curr->pNext == NULL){
// we don't know whether the while stopped because it reached the
// final node or the priority was greater, we have to check it
if(temp->info.iPriority <= curr->info.iPriority)
{
// the priority is smaller, temp should be the tail
curr->pNext = temp;
temp->pPrev = curr;
return;
} else {
// the priority is bigger, curr should the the tail
// this case is handled by the next section
}
}
temp->pPrev = curr->pPrev;
temp->pNext = curr;
curr->pPrev->pNext = temp;
curr->pPrev = temp;
}
int main(void)
{
PQNode *queue = NULL;
enqueue(&queue, 109, 10);
enqueue(&queue, 105, 40);
enqueue(&queue, 108, 20);
enqueue(&queue, 110, 30);
enqueue(&queue, 911, 11);
enqueue(&queue, 219, 25);
print_queue(queue);
return 0;
}

我得到

105 (priority 40) <--> 110 (priority 30) <--> 219 (priority 25) <--> 108 (priority 20) <--> 911 (priority 11) <--> 109 (priority 10)