具有雙向鏈表插入的優先級隊列

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; 
} 

的Structs

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)