冒泡排序鏈表

我有這兩個結構正在構建一個鏈表：冒泡排序鏈表

struct Element { 
    int value; 
    struct Element *next; 
}; 

struct List { 
    struct Element *first; 
};

現在我想用排序冒泡排序的鏈表。我實現了sortList方法，它比較當前元素的值和下一個元素的值。如果下一個元素的值大於當前元素的值，則必須交換。但在這一刻它不能正常工作。

void sortList(List *list) { 
    Element *current = malloc(sizeof(Element)); 
    current = list->first; 
    Element *nextElement = malloc(sizeof(Element)); 
    nextElement = current->next; 
    Element *tmp = malloc(sizeof(Element)); 
    tmp = NULL; 

    int changed = 1; 
    while (changed) { 
     changed = 0; 
     for (current; (current != NULL) && (nextElement != NULL);) { 
      if (current->value > nextElement->value) { 
       tmp = current->next; 
       current->next = nextElement->next; 
       nextElement->next = tmp; 
       changed = 1; 
      } 
      current = current->next; 
      nextElement = nextElement->next; 
     } 
    } 
}

來源

2014-12-03 torhoehn

什麼是不工作？基本的方法似乎是有效的;不過我建議將交換操作移至單獨的函數。 – Codor 2014-12-03 14:53:09

該列表未正確排序。輸入：1 4 3 2 6 輸出：1 4 2 6 3 – torhoehn 2014-12-03 15:20:45

實現是否能夠按錯誤順序對兩個元素進行排序？ – Codor 2014-12-03 15:21:30

之後，在重新開始之前，你必須設置current和nextElement指向列表的開始！或者他們不改變，立即失敗的測試條件。另外，mallocs有什麼意義？你使用current，next和temp僅作爲指向節點的指針，而不是真正的節點，我認爲你可以刪除它們。你可以用condtion重寫一下，它更具可讀性。對不起，我的英語。

編輯：如寫在問題下，你需要改變列表中的指針。我認爲最簡單的方法是立即將較低的元素移動到列表的開頭，並將列表的頭部改爲指向這個元素。之後，對列表的其餘部分進行分類。

來源

2014-12-03 15:38:15 GiuMaz

Now我改變了你在第一段中所說的話。現在函數看起來像這樣：http://pastie.org/9758554 我不明白你的編輯部分的一切。你能改變代碼嗎？ – torhoehn 2014-12-03 17:16:05

好的我更改了代碼。重點是更新列表 - >第一個值以指向REAL第一個值。在5 2清單的例子中，你可以看到不這樣做的問題，清單被排序，併成爲2 5但是列表 - >第一點指向5，所以5之前的東西丟失了！ – GiuMaz 2014-12-04 15:36:49

鏈接http://pastie.org/9760695 – GiuMaz 2014-12-04 16:06:11

假設程序正在對現有列表進行排序，沒有理由在sortList中分配節點，它應該只是操縱指向現有節點的指針。

交換節點時，指向當前節點的指針需要更新，可能是list.first或Element.next。使用指向指針的指針可以讓它更容易一些。

struct Element **ppcur; /* pointer to list->first or element->next */ 
/* ... */ 
    if(list == NULL || list->first == NULL) 
     return NULL; 
    for(ppcur = &(list->first); pnxt = (pcur = *ppcur)->next; 
     ppcur = &((*ppcur)->next)){ 
    /* ... */

來源

2014-12-03 16:41:26 rcgldr

冒泡排序鏈表

回答

相關問題