带有双向链表插入的优先级队列

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

当队列在第一个循环中为空时，我能够插入一个新节点。从第 2 个运行开始，队列的 return 值是错误的。

代码

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 块中的列表，然后你意识到 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)

带有双向链表插入的优先级队列

Priority Queue with Doubly Linked List Insertion

c

priority-queue

doubly-linked-list