排序單鏈表 - 我不明白

I'm望着例如6.7 http://publications.gbdirect.co.uk/c_book/chapter6/structures.html 排序單鏈表 - 我不明白

（粘貼在這裏爲方便起見）

struct list_ele * 
sortfun(struct list_ele *list) 
{ 

     int exchange; 
     struct list_ele *nextp, *thisp, dummy; 

     /* 
     * Algorithm is this: 
     * Repeatedly scan list. 
     * If two list items are out of order, 
     * link them in the other way round. 
     * Stop if a full pass is made and no 
     * exchanges are required. 
     * The whole business is confused by 
     * working one element behind the 
     * first one of interest. 
     * This is because of the simple mechanics of 
     * linking and unlinking elements. 
     */ 

     dummy.pointer = list; 
     do{ 
       exchange = 0; 
       thisp = &dummy; 
       while((nextp = thisp->pointer) 
         && nextp->pointer){ 
         if(nextp->data < nextp->pointer->data){ 
           /* exchange */ 
           exchange = 1; 
           thisp->pointer = nextp->pointer; 
           nextp->pointer = 
             thisp->pointer->pointer; 
           thisp->pointer->pointer = nextp; 
         } 
         thisp = thisp->pointer; 
       } 
     }while(exchange); 

     return(dummy.pointer); 
}

我得到的基本想法，但我真的不能解釋那裏發生了什麼。有人可以更深入地解釋，但以簡單的方式解釋這種功能正在發生什麼？

一些普遍問題：

爲什麼dummy.pointer = list;需要？ dummy然後在函數結束時返回，列表如何仍然排序？
評論The whole business is confused by working one element behind the first one of interest.是什麼意思？

來源

2012-06-09 Max

dummy是一個局部變量，它首先被設置爲列表的開始。臨時變量thisp設置爲指向dummy，因此更新時，dummy指向的內容也會更新。因此，dummy.pointer將最終指向排序列表的新開始元素。 list仍將指向列表的原始開始，所以返回該值以便更新頭指針。

我認爲他們的含義是我們感興趣的元素是nextp，而不是當前元素（或thisp）。也就是說，我們將列表中的下一個元素與當前元素進行比較，而不是將當前元素與前一個元素進行比較。我想這是混淆，但我真的不覺得它如此。

注意：這是Bubble Sort。一個更好的排序算法將是Merge Sort，實現在http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html。

來源

2012-06-09 20:06:34 tvanfosson

謝謝你的解釋，它使得它更清楚虛擬做什麼，特別是與thisp結合使用。我覺得很難理解：爲什麼需要do/while結構？在我天真的想法中，我只是遍歷列表並進行交換... – Max

@Max考慮列表c => b => a。經過內循環一次，你得到b => a => c（用c交換b，用c交換a）。您需要繼續瀏覽清單，直到您不進行任何交流。只有在那個時候你才知道整個清單是有序的。這就是外部循環所保證的。 – tvanfosson

該算法遍歷列表中的每個列表項和後面的列表項。如果他們失靈了，他們會轉過身來。然後重複該過程。最終沒有什麼不合適的地方，沒有任何東西可以切換;那時所有的工作都完成了（如exchanged表示剩餘零）。換句話說，通過列表的最後一次，沒有任何交換。

啞元用於跟蹤列表本身（如果前2個列表項目被切換）。它被使用（而不僅僅是一個簡單的指向列表的指針，因爲它也可以作爲虛假的第一項，這樣就有一些東西可以比較列表中的原始第一項，它不需要特殊情況下的結果列表第一個項目不同於原始列表的第一個項目

在紙上列出1,2,3和4個項目，然後您會看到它是如何工作的。然後在列表中交換2個項目並重新執行

關於整個業務的評論被混淆了，所有它指的是恕我直言的事實是你必須跟蹤單鏈表中的3個節點，以便交換其中的兩個節點。如果您有項目ACB在列表中（並且目標是列表爲A B C），當您交換B和C時，您還必須訪問A - 它的'下一個節點'指針必須從C更改爲B.

來源

2012-06-09 20:09:48

感謝您的回答！在紙上做一個例子是一個好主意。在另一面看來，我認爲最不直觀的部分是do/while（交換）爲什麼需要這樣做？不，我只是遍歷列表並交換值？ – Max

你不能只經歷一次。在最糟糕的情況下（即列表按降序排列，但您希望它按升序排序），需要多次迭代，直到每個項目都「落戶」到其最終位置。嘗試用5個項目（例如）手工排序列表，最初在最壞的情況下訂購;你會看到每次迭代如何不斷完善排序，直到最終實現目標。 –

排序單鏈表 - 我不明白

回答

相關問題