泡沫分類雙向鏈表

我對雙向鏈表的氣泡排序功能有問題。它正在工作，當我以單向鏈接的方式排序節點（只有 - >下一個），但我不能使它與 - > prev指針一起工作。這裏是我使用的代碼：泡沫分類雙向鏈表

void sort(int count) 
{ 
    struct data *tmp,*current,*nextone; 
    int i,j; 
    for(i=0;i<count;i++) 
    { 
     current = first; 
     for(j=0;j<count-1-i;j++) 
     { 
      if(current->number > current->next->number) 
      { 
       nextone = current->next; 
       current->next = nextone->next; 
       nextone->next = current; 
       if(current == first) 
       { 
        first = nextone; 
        current = nextone; 
       } 
       else 
       { 
        current = nextone; 
        tmp->next = nextone; 
       } 
      } 
      tmp = current; 
      current = current->next; 
     } 
    } 
}

這是我使用的結構（與列表的第一個和最後一個元素的全局變量）：

struct data  
{ 
    int id; 
    char name[20]; 
    int number; 
    struct data *next; 
    struct data *prev; 
}; 

struct data *first = NULL; 
struct data *last = NULL;

來源

2014-01-16 user1630441

發佈使用雙鏈表節點移動時給您帶來麻煩的代碼。 – Buddha

下面的邏輯將工作。

我會遵循類似的算法...如果你想移動整個節點...

struct data *before, *after; 
if(current->number > current->next->number) 
{ 
    before = current->prev; 
    after = current->next; 
    if(before != NULL){ 
     before->next = after; 
    } 
    current->next = after->next; 
    current->prev = after; 
    after->next = current; 
    after->previous = before; 
}

或者，你可以簡單地在交換節點的數字，而不會打擾移動整個節點，如果排序的數據是目的。您可以擴展下面的邏輯以包括交換char數組和id。

if(current->number > current->next->number) 
{ 
    int tempNum = current->number; 
    current->number = current->next->number; 
    current->next->number = tempNum; 
}

來源

2014-01-16 02:04:53 Buddha

工作正常，但由於某種原因，最後一個節點在排序中丟失。當我添加新節點時，它取代了最後一個節點，並且當我閱讀它時，最後一個節點根本不顯示。 –

一更簡單的方法就是複製節點的數據，你可以交換數據，但是指向節點的指針。

if(current->number > current->next->number){ 
    swap(current->id,current->next->id); 
    swap(current->name,current->next->name); 
    swap(current->number,current->next->number); 
}

用你的方法，你永遠不會設置前一個指針。您可以將雙鏈表首先排序爲單列表，然後再次遍歷列表以設置所有prev指針。

當然，您可以一次對雙鏈表進行排序，但實現起來有點複雜。每步應該考慮4個節點，即current，current-> next，current-> prev和current-> next-> next。當你想交換電流和當前 - >下一個，你應該設置current->prev->next=current->next, current->next=current->next->next等等。

來源

2014-01-16 01:28:54

雖然的確如此，但我確實認爲這是一個不好的答案。鏈表的全部要點之一是避免移動大量數據。根本沒有理由爲鏈表做這樣的事情。 – klutt

你只需要坐下來思考一下。

先指定？那麼以前必須爲空。

分配最後？接下來必須爲空。

其他任何你需要與之前的&做交換跳舞的下一個要交換的元素。

一個更簡單的方法（對於較大的數組大小，它會快速變得更快）是分配一個指針數組，然後用指向這些元素的指針填充這些數組，然後再執行另一次通過重新連線指針並刪除臨時數組）。

來源

2014-01-16 01:35:15 LoztInSpace

泡沫分類雙向鏈表

回答

相關問題