按升序對鏈表進行排序C++

所以我有一個單獨的鏈表。新項目被添加到鏈的前端，所以如果你添加了8,4,10，那麼列表將是10,4,8。無論如何，現在我想在插入完成後對列表進行排序，除非我無法弄清楚如何循環這些數字並按升序重新排列它們。我可能會在這裏休息一下，稍微回來，希望這會幫助我弄清楚這一點。按升序對鏈表進行排序C++

*這是一個學校項目，所以建議我使用其他容器在我的情況下沒有幫助，除了信息豐富，因爲我無法改變我正在使用的內容。

佈局列表

struct Node 
    { 
     int Item;  // User data item 
     Node * Succ; // Link to the node's successor 
    }; 

unsigned Num //number of items in the list 
Node * Head //pointer to the first node

我的插入函數看起來像這樣

Node * newOne; 
newOne = new (nothrow) Node; 
newOne->Item = X; 
newOne->Succ = NULL; 

if(Head == NULL) 
{ 
     Head = newOne; 
} 
else 
{ 
     newOne->Succ = Head; 
     Head = newOne; 
} 
Num++;

來源

2012-11-15 sharkman

該作業還有其他限制嗎？你可以將內容複製到另一個容器進行分類嗎？ – Chad

這真的很難。我懷疑即使在休息之後，正確的解決方案也會來臨（儘管你可能是一個天才，誰知道呢）。看看這裏的最佳解決方案http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html – john

也許你應該在插入時對它進行排序？即把元素放在正確的位置... – Caribou

這可以通過兩種方式完成，我不會發布代碼，但希望這會對您有所幫助。

1插入

這涉及以升序總是添加元素中排列按升序排列。例如，如果鏈接列表是

  | 1 |

，並添加5新的鏈接列表是

  |1|--->|5|

，如果你加3下一個應該是

  |1| ---> |3| ----> |5|

這涉及到的比較直到你找到正確的位置爲止的新元素。

2.等到所有元素都插入後，按升序排列。

這將涉及使用排序算法，如合併排序，插入排序，冒泡排序等鏈接列表的元素。

完成數字排序後，按正確的順序重寫鏈接列表。

實施例：

如果鏈接列表包含

 3 2 5 1 6

通過鏈路列表通過算法

1 2 3 5 6 (stored in an array)

排序現在環路之後並替換以正確的順序的元素。

要小心如果節點包含其他元素，那些其他元素也需要被替換。

注意：這需要額外的內存，另一種方式是交換需要更長時間的節點。除非鏈接列表包含大量節點（從而使內存很重要）或者具有其他元素，否則使用數組會更簡單。

來源

2012-11-15 17:05:15

謝謝，這很有道理。我結束了方法2，因爲沒有其他信息除了該int。所以我做了一個矢量，對它進行排序，然後根據矢量的順序更新節點！謝謝！ – sharkman

排序單鏈表是討厭的代碼（除非你喜歡的線性排序，如冒泡排序或插入排序）。將內容複製到矢量中，對矢量進行排序，然後重新構建列表就簡單多了。

來源

2012-11-15 17:01:23

按升序對鏈表進行排序C++

回答

相關問題