在C中使用指針泡泡排序單鏈表

Question

我想用C中的指針操作對單個鏈表進行泡沫排序。我已經看了一些其他在網站上使用泡沫排序的實現，但是我覺得我的代碼在這裏的邏輯應該是有道理的。即便如此，仍然進入無限循環。任何幫助將不勝感激！

int counter; 
struct node* current = head; 
struct node* previous = (struct node*) malloc(sizeof(struct node)); 
struct node* next = (struct node*) malloc(sizeof(struct node)); 

for (counter = 0; counter < num_nodes; counter++){ 
    current = head; 
    next = current->m_next; 

    while(next != NULL){ 
     int compare = strcmp(current->m_last_name, next->m_last_name); 
     if (compare > 0){ 
      if (current == head){ 
       head = next; 
      } 
      previous->m_next = next; 
      current->m_next = next->m_next; 
      next->m_next = current; 

      previous = next; 
      next = current->m_next; 
     } 
     else { 
      previous = current; 
      current = current->m_next; 
      next = current->m_next; 
     } 
    } 
} 
printf("Loop completely done\n"); 

}

Answer 1

這裏有幾個問題。首先，爲什麼要爲next和previous節點指針分配內存？你正在排序，沒有新的節點參與，你只是在混合現有節點之間的鏈接。更重要的是，你重新分配，你有malloc版內存指針，例如：

previous = current; 

這意味着，中previous價值，從而分配的內存IST丟失。

接下來，您的頭指針在排序後很可能不會相同。調用函數需要知道這個變化。因此，你應該傳遞一個指向你的排序函數的節點指針。 （我相信你的函數將ndes添加到列表中也是如此。）

對於你的指針previous也是如此。如果這是一個節點指針，那就是：指向同一個節點的另一個指針。當你更新它時，你更新一個指向列表結構的外部指針。因此，previous也應該是指向節點指針的指針。該指針與首先指向頭節點指針的指針相同，然後在遍歷列表時指向先前節點的指針。如果更新prev指向的指針，則更新列表結構中的指針，這就是你想要的。

此外，在代碼中明確使用num_nodes非常不像列表。您應該使用列表結構本身來編寫算法。

無限循環是由current交換後未正確更新造成的。鑑於malloc ed指針的錯誤概念，我沒有多少關注。

下面是工作的實施：

void list_bubble_sort(struct node **head) 
{ 
    int done = 0;   // True if no swaps were made in a pass 

    // Don't try to sort empty or single-node lists 
    if (*head == NULL || (*head)->m_next == NULL) return; 

    while (!done) { 
     struct node **pv = head;   // "source" of the pointer to the 
              // current node in the list struct 
     struct node *nd = *head;   // local iterator pointer 
     struct node *nx = (*head)->m_next; // local next pointer 

     done = 1; 

     while (nx) { 
      int cmp = strcmp(nd->m_last_name, nx->m_last_name); 

      if (cmp > 0) { 
       nd->m_next = nx->m_next; 
       nx->m_next = nd; 
       *pv = nx; 

       done = 0; 
      } 
      pv = &nd->m_next; 
      nd = nx; 
      nx = nx->m_next; 
     } 
    } 
} 

注意如何pv總是包含內部指針指向nd的來源，以及如何通過*head指向頭節點是沒有特例。

該算法重複從頭到尾傳遞列表，直到不需要進行任何更改。這有點粗糙，但畢竟是冒泡排序。

編輯在另一個答案中，aehrwyn解釋了爲什麼你得到一個無限循環。他的修復工作，但有不必要的分配內存的缺陷，永遠不會真正使用，更不用說釋放它。應用aehrwyn的發現，你的代碼應該是這樣的：

struct node *bubble (struct node *head) 
{ 
    int num_nodes = count(head); 
    int counter; 

    for (counter = 0; counter < num_nodes; counter++) { 
     struct node* current = head; 
     struct node* next = current->m_next; 
     struct node* previous = NULL; 

     while(next != NULL) { 
      int compare = strcmp(current->m_last_name, next->m_last_name); 
      if (compare > 0) { 
       if (current == head){ 
        head = next; 
       } else { 
        previous->m_next = next; 
       } 
       current->m_next = next->m_next; 
       next->m_next = current; 

       previous = next; 
       next = current->m_next; 
      } 
      else { 
       previous = current; 
       current = current->m_next; 
       next = current->m_next; 
      } 
     } 
    } 
    printf("Loop completely done\n"); 
    return head; 
} 

注意事項：

• 沒有必要對malloc什麼。指針next和previous只是沒有正確數據的「工作指針」他們指向現有的節點。

• 我已經移動了外循環內工作指針的定義。這反映了它們的範圍，並且在我看來，會讓錯誤更容易發現，比如忘記重新定位它們。

• 您指定previous->m_next。我認爲你害怕取消引用NULL指針，因此分配了一個虛擬節點。相反，您應該在取消引用前檢查NULL。在您的代碼中，條件previous != NULL等同於current == head，因此分配給previous->m_next可能發生在else子句中。事實上，if/else反映了兩個基本情況：頭節點和後續節點。我上面說過，我應該使用指向指向節點的指針，但那是因爲我認爲你的代碼來自一個單獨的函數。但它可能是main的一部分，所以使用簡單的struct node *是可以的。請注意，當您返回新的頭節點時，這也適用於單獨的函數。你必須調用你的功能：

  head = bubble(head); 
  

  這在我看來是容易出錯的，因爲忽略返回值是合法的。我更喜歡上面解釋的雙指針方法。 （注意：我在這裏看到很多代碼，這是一個很長的函數，學習將你的代碼分解成小的，自包含的函數，你可以重用它，起初可能看起來很乏味，但是在長時間運行這種編碼風格支付股息。）

Answer 2

除了其他人提到的不必要的mallocing之外，大部分代碼是正確的。

因爲在進入下一個循環迭代時沒有重置「previous」，所以您正在進入無限循環。所以，當你設置：

previous-> next = next;

以前可能是列表中倒數第二項，您在最後一次for循環迭代中的while循環中設置。對於一個快速砍死修復一看就知道這就是問題所在，以取代你的第三行：

struct node* previousDummy = (struct node*) malloc(sizeof(struct node)); 
struct node* previous; 

和while循環之前加入這一權利：

previous = previousDummy;