作業，鏈表冒泡排序

Question

我有一門功課，在那裏我有鏈表的工作有點問題，問題是排序功能，我選用了冒泡算法，這裏是一段代碼。

void BubbleSort(PrikazStruct **Seznam) { 
    int Prohozeno = NULL; 
    int Value_1, Value_2; 

    PrikazStruct *AktualniPrikaz = *Seznam; 
    PrikazStruct *Temp = AktualniPrikaz->Dalsi; 

    Value_1 = AktualniPrikaz->Jmeno[0]; 
    Value_2 = AktualniPrikaz->Dalsi->Jmeno[0]; 

    do { 
     Prohozeno = 1; 

     while (AktualniPrikaz->Dalsi != NULL) { 
      if (Value_1 < Value_2) { 
       ProhodCleny(AktualniPrikaz, AktualniPrikaz->Dalsi); 
       Prohozeno = 0; 
      } 

      Value_1 = AktualniPrikaz->Jmeno[0]; 
      AktualniPrikaz = AktualniPrikaz->Dalsi; 
      Value_2 = AktualniPrikaz->Jmeno[0]; 

     } 

    } while (!Prohozeno); 

    return; 
} 

我不能明白爲什麼，它並不在列表正確排序，這裏是結構交換功能

void ProhodCleny(PrikazStruct *S1, PrikazStruct *S2) { 
    PrikazStruct *Temp = (PrikazStruct *) malloc(sizeof(PrikazStruct)); 

    Temp->ID = S1->ID; 
    strcpy(Temp->Jmeno, S1->Jmeno); 
    strcpy(Temp->Prijmeni, S1->Prijmeni); 
    Temp->Castka = S1->Castka; 
    strcpy(Temp->Popis, S1->Popis); 
    Temp->Obdobi = S1->Obdobi; 
    strcpy(Temp->stringObdobi, S1->stringObdobi); 
    strcpy(Temp->JePlatba, S1->JePlatba); 

    S1->ID = S2->ID; 
    strcpy(S1->Jmeno, S2->Jmeno); 
    strcpy(S1->Prijmeni, S2->Prijmeni); 
    S1->Castka = S2->Castka; 
    strcpy(S1->Popis, S2->Popis); 
    S1->Obdobi = S2->Obdobi; 
    strcpy(S1->stringObdobi, S2->stringObdobi); 
    strcpy(S1->JePlatba, S2->JePlatba); 

    S2->ID = Temp->ID; 
    strcpy(S2->Jmeno, Temp->Jmeno); 
    strcpy(S2->Prijmeni, Temp->Prijmeni); 
    S2->Castka = Temp->Castka; 
    strcpy(S2->Popis, Temp->Popis); 
    S2->Obdobi = Temp->Obdobi; 
    strcpy(S2->stringObdobi, Temp->stringObdobi); 
    strcpy(S2->JePlatba, Temp->JePlatba); 

    free(Temp); 
    return; 
} 

Answer 1

您需要的工作指針重置每個外環：

Prohozeno = 1;    /* after this line */ 
    AktualniPrikaz = *Seznam; /* add this line */ 

此外代碼交換節點的內容，而不是更改節點鏈接來完成排序。我不確定這是否允許你上課。

如果您需要更改鏈接，而不是使用冒泡排序（通過鏈接交換節點是複雜的）這將是簡單的創建一個新的空單，如：

PrikazStruct *Sorted = NULL; /* this will be sorted list */ 

然後將其刪除節點將原始列表一次一個地按順序插入待排序列表中。其他方法，如自下而上合併排序會更快，但超出了您對此類類別分配的期望。

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

這將是快還是創建指針數組節點，指針數組排序，然後重新鏈接基於指針的有序陣列上的名單，但是這需要O（n）的空間，它不是一個鏈表列表。

Answer 2

你拔插功能複製節點的完整內容。這將非常低效，非常特定於節點的內容，任何持有指向這些節點的指針的人在內容發生變化時都會感到非常驚訝。一個好的排序算法只需要知道排序標準。

相反，它應該被單獨留下節點的內容和在列表中重新鏈接它們。正如您可能已經注意到的那樣，通過單個鏈接列表來「冒泡」，您需要兩個節點和前一個節點。相反，向上鼓起較小的物品，推下較大的物品。

這裏是基本的算法。

while(changed) { 
    changed = 0; 

    /* I believe you forgot this part */ 
    q = top; 
    p = top->next; 

    while(p->next != NULL) { 
     /* push bigger items down */ 
     if(p->data > p->next->data) { 
      q->next = list_switch(p, p->next); 
      changed = 1; 
     } 

     q = p; 

     if(p->next != NULL) { 
      p = p->next; 
     } 
    } 
} 

而交換功能非常簡單。

LIST *list_switch(LIST *l1, LIST *l2) 
{ 
    l1->next = l2->next; 
    l2->next = l1; 
    return l2; 
} 

欲瞭解更多信息，請參閱此Linked List Bubble Sort example。