這種排序方法如何工作？

我正在從「The C Book」學習C語言。我認爲這是一本好書，我理解它的大部分內容，比如指針。但是我無法理解1個用鏈表結構排序的例子。這種排序方法如何工作？

如果我把它畫在紙上，我一直得知第二個對象的指針如果被切換的話不會被調整到第一個對象的指針。也許我在錯誤地思考結構中的這些指針。有人可以解釋這個交換很短，也許通過例子，如我在5,99和1的代碼中做的例子。我想了解這種用鏈表進行排序，因爲它看起來對於以後很有用。

這是代碼：的#include 的#include

struct list_ele{ 
    int data; 
    struct list_ele *pointer; 
}ar[3]; 

struct list_ele * 
sortfun(struct list_ele *list); 

int 
main(){ 
    struct list_ele *lp; 

    ar[0].data = 5; 
    ar[0].pointer = &ar[1]; 
    ar[1].data = 99; 
    ar[1].pointer = &ar[2]; 
    ar[2].data = 1; 
    ar[2].pointer = 0;/* mark end of list */ 

    /* sort list */ 
    lp = sortfun(ar); 
    /* follow pointers */ 
    while(lp){ 
     printf("contents %d\n", lp->data); 
     lp = lp->pointer; 
    } 
    exit(EXIT_SUCCESS); 
} 

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 = this->pointer->pointer; 
        thisp->pointer = nextp; 
       } 
      thisp = thisp->pointer; 
     } 
    }while(exchange); 

    return(dummy.pointer); 
}

來源

2014-01-16 Digihash

查找[「冒泡排序」]（http://en.wikipedia.org/wiki/Bubble_sort）。注：一本使用泡沫排序來教授排序的書不是我推薦的書。鏈表的高效排序通常通過[合併排序]（http://en.wikipedia.org/wiki/Merge_sort）來實現。 – user4815162342

「如果我把它畫在紙上，我會一直得到第二個物體的指針如果它們被切換不會被調整到第一個物體的指針」。我不確定你的意思。你能解釋更多嗎？（如果你對自己的想法更清楚，人們可能會更好地解釋你出錯的地方。） – starsplusplus

好的，我再次檢查了一遍，我認爲我找到了它，但是就像你說的我也來到這裏問題。第二個對象的指針不調整爲第一個。這就是爲什麼我執行它時功能會起作用的原因。 – Digihash

這是冒泡排序。它通過不按順序交換物品來工作，重複，直到沒有更多的物品失靈。如果沒有太多項目，這是有幫助的，否則需要其他一些方法。的tricki部分大概是這樣的：

   thisp->pointer = nextp->pointer; 
       nextp->pointer = this->pointer->pointer; 
       thisp->pointer = nextp;

，是爲了在交換鏈接的列表中有兩個元素的順序。

來源

2014-01-16 14:21:11

這種排序方法如何工作？

回答

相關問題