なぜこのCコードは無限ループに終わるのですか？

Question

私はこのコードで無限ループを修正しようとしています。しかし、なぜ無限ループが起こるのか理解できませんでした。このコードは、処理される前にジョブを最小から最大にソートしようとしています。

SortJobs() 
{ 
    linked_list ptr, h, temp, pptr; 
    int i, j; 

    pptr = ready_queue; 
    ptr = ready_queue->next; 
    h= ready_queue; 

    while(ptr != NULL) {  
     if ((ready_queue->pcb.job_length - ready_queue->pcb.run_time) > (ptr->pcb.job_length - ptr->pcb.run_time)) { 
      ready_queue = ptr; 
      pptr->next = ptr->next; 
      ptr->next = h->next;     
      h->next = pptr->next; 
      pptr->next = h; 
      ptr=h->next; 
      h=ready_queue; 
      pptr=ptr->next; 
     } else { 
      pptr = ptr; 
      ptr=ptr->next;   
     } 
    } 
} 

Answer 1

ptrは常にnullではないため？

Answer 2

gdbは、このような問題をデバッグするのにあなたの友人です。デバッガを使い始めてください！

OTOHは、これはcircular-(linked)-listです！

ヒント：SortJobs()を実行する前に、ready_queueを実行してすべての要素を印刷し、無限ループに入るかどうかを確認できますか？

リンクリスト内の最後のノードをNULLに設定していないため、無限ループの理由が考えられます。 addNode()の機能を確認できます。

Answer 3

目立つ問題は、この行ことである：間でpptr又はptrにない変更を

pptr->next = ptr->next; 

：

pptr=ptr->next; 

は時々、この行が続くことができます。これにより、1ノードの循環リンクリストが作成され、ptr->next->next == ptr->nextとなります。だからあなたはリンクされたリストから抜け出すことはできません。

全体的に、あなたのアルゴリズムは非常に混乱しています。実際には、各変数の単一の論理的意味を決定し、適切なループ不変量を考え出す必要があります。例えば、ループの反復の終わりには、ときどきptr == pptr->next（これは正しいと思います）がありますが、時にはpptr == ptr->next（これは私が間違っていると確信しています。

Answer 4

あなたのアルゴリズムは非常に混乱していますが、私も間違っていると思います。ループが何とか終了し、すべての結果が正しいとすれば、最初の要素はjob_length - run_timeの最小値ですが、リストの残りの部分は順序付けされません。

ruakhが指摘しているように、問題は、次のすべてのポインタを操作するとリストが壊れてしまうことです。私はノード全体を動かしているリスト自体の構造に触れず、むしろmemcpyを使い、ノードによって運ばれたデータだけを動かします。ここではサンプルfuncionです：

// I assume your linked list is made of nodes such as this 
typedef struct { 
    struct Node next; 
    struct Node prev;  // optional 
    struct Somewhat pcb; 
} Node; 

void swapData(Node *n1, Node *n2) 
{ 
    struct pcb temp; 

    memcpy(&temp, n1->pcb, sizeof(struct Somewhat)); 
    memcpy(n1->pcb, n2->pcb, sizeof(struct Somewhat)); 
    memcpy(n2->pcb, &temp, sizeof(struct Somewhat)); 
} 

今、私たちが正しくノード入れ替えることができるしていることを、私はあなたが見つけることができます。この方法は、より簡単に、次の役立つ、いくつかのよくテスト/有名なソートアルゴリズムを使用したいです誰があなたのコードを見て、自分自身を殺すように誘惑されることはありません（意図的な嫌悪はありません、私はただ冗談です）。 Selection sortやBubble sortのような簡単なアルゴリズムを提案しましょう。非常に高速ではありませんが実装が簡単です。