使用鏈接列表排序

我有兩個字段，即ID和名稱。在鏈接列表中插入節點時，我想按ID降序排列它。假設不同的人可能有相同的ID。例使用鏈接列表排序

1001 CHARICE -> 1001 JUSTIN -> 1001 ANNA -> 1000 CHYNA -> 888 MIKEY -> NULL

的最終名單應該是這樣的：

1001 ANNA -> 1001 CHARICE -> 1001 JUSTINE -> 1000 CHYNA -> 888 MIKEY -> NULL

我而ID是按降序排列升序排列相同ID的名稱進行排序。這裏是我的代碼：

NODE* insert_std(NODE *head, NODE* std){ 
    NODE *prev, *cur; 
    if(head==NULL) return std; 
    cur = head; 
    while (cur != NULL && std->ID < cur->ID){ 
     prev = cur; 
     cur = cur->next; 
    } 
    if(std->ID == cur->ID){ 
     while (cur != NULL && strcmp(std->name, cur->name)>=0){ 
      prev = cur; 
      cur = cur->next; 
     } 
    }  
    if (head==cur){ 
     if(std->ID >= head->ID) { 
     std->next = head; 
     head = std; 
     } 
    } else { 
     std->next = cur; 
     prev->next = std; 
    } 
    return head; 
}

但就是不進行排序我想要的方式。我究竟做錯了什麼？

來源

2010-12-15 newbie

添加&& std->ID == cur->ID比較字符串使用'strcmp'（或POSIX'strcasecmp'）。 – pmg 2010-12-15 17:02:20

這一個將是有用的：http://en.wikipedia.org/wiki/Sentinel_node – ruslik 2010-12-15 17:38:58

請使用快速排序算法找到我的解決方案這個問題在http://stackoverflow.com/questions/11813696/sorting-a-鏈接列表中-C/15457283＃15457283> – user1596193 2013-03-17 03:47:40

在插入函數中，每當比較兩個節點時，首先比較兩個ID。如果一個比另一個小，這就告訴你哪個節點應該先到達。如果ID相同，則需要比較名稱以決定哪個節點先到達。

這相當於修改std->ID <= cur->ID和std->ID > head->ID。如果我是你，我會編寫一個幫助函數，它將採用指向NODE的兩個指針（稱之爲A和B），以上述方式比較它們，如果節點A位於節點B之前，則返回true。將此函數併入您的insert_std然後是微不足道的。

來源

2010-12-15 17:01:38 NPE

只需替換對ID值的比較，並在ID值相同時考慮名稱（例如使用strcmp）。最簡單的方法是編寫一個單獨的函數來比較執行此項工作的兩個記錄。

來源

2010-12-15 17:02:53

在while循環

while (cur != NULL && std->ID == cur->ID && strcmp(std->name, cur->name)>=0)

來源

2010-12-15 17:54:14 newbie

使用鏈接列表排序

回答

相關問題