私のソート機能に問題があります

Question

このソート機能が動作しない理由を理解するのに苦労しています。ノードはソート順に配置されますが、最初のノードは常にプロセスで失われます。ここに私のコードは、（head変数がグローバルである）である：

void medianscore() { 
    int i, j=0; 
    int counter=0; 
    struct student *curr=head; 
    struct student *trail=head; 
    struct student *temp=NULL; 

    while (curr !=NULL) 
    { 
     curr=curr->next; //couting the number of items I have in my list. 
     counter++;   //this works fine. 
    } 

    curr=head->next;   // reseting the curr value for the 2nd position. 

    for (i=0; i<counter; i++) 
    { 
     while (curr != NULL) 
     { 
      if (trail->grade > curr->grade) 
      { 
      temp=curr->next;  //bubble sort for the pointers. 
      curr->next=trail; 
      trail->next=temp; 

      temp=curr;   //reseting trail and curr. curr gets back to be infront. 
      curr=trail; 
      trail=temp; 

      if (j==0) //i'm using j to determine the start of the loop so i won't loose the head pointer. 
      { 
       head=trail; 
      } 
      } 
      j++; 
      trail=curr; 
      curr=curr->next; //traversing thru the list. nested loop. 
     } 

     trail=head; 
     curr=trail->next; 
     curr->next=trail->next->next; //traversing thru the list. outer loop. 
     j=0; 
    } 
} 

私が間違って何をしているのですか？

Answer 1

ノードのカウントと変数の使用iとjはソートを制御するために悪いコードの匂いがあります。これらは必要ではありません。

私はjとあなたの頭のリストの扱いについては後で扱います。 iを超える外側ループに関しては、外側ループの各反復に対してフラグを維持して、その反復の最後にスワップが行われたかどうかを判断することができます。そうでなければ、別の反復を実行する必要はありません。この方法は、現在のテクニックより多くの反復を実行することはありません。

しかし、あなたのコードに見られる主な問題は、ノードスワップを正しく実行しないことです。

prev --> trail --> curr --> Z 

は....あなたは trailと currが交換する必要があるかどうかを質問して、そしてあなたは、彼らがしなければならないことを決定したと...あなたはこのような状況で開始したとします。 - の連鎖を

その時点で

prev ----V 
     trail --> Z 
curr ----^ 

、currが効果的に失われた：その場合、あなたはこのように見えるリンクで終わる、trailのnextポインタとcurrのではなく、prev年代を更新しますリストの先頭からZへのリンクはもう通過しません。

頭のノードが特別なケースであるため、この問題が発生している可能性があります。しかし、そうである必要はありません。リンクリストは、コードの他の場所で使用されているかについては何も変更せずに、あなたが頭を指すmedianscore()にローカルダミーノードを作成することができます。

struct student dummy; 

dummy->next = head; 

あなたは、その後で、外側のループの各反復を開始することができます。.. 。

trail = &dummy; 

...とtrail->nextはtrail->next->nextと交換する必要があるかどうかを内部ループ試験です。あなたのループ終了条件とスワップは少し異なりますが、スワップする最初のペアの前にあるノードへのポインタを持っている必要があります。そのため、nextポインタを更新できます。

このようにすると、もう1つの利点があります。ヘッドノードはソートループ内で特別な処理を必要としなくなりました。代わりに、最後にhead = dummy->next;と設定するだけです。