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 提到的，函数的最后一位有点错误(//编辑您同时更改了代码，我指的是您的原始代码)。当您浏览 while block 中的列表，然后您意识到 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)