二重リンクリストを挿入したプライオリティキュー

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回目の実行から、キューの戻り値が間違っています。

コード

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)