排序的雙鏈表的搜索算法

Question

作爲學習練習，我剛剛嘗試實現我自己的「合併排序」算法。我在一個std :: list上做了這個，它顯然已經內置了函數sort（）和merge（）。但是，我打算把它移到我自己製作的鏈表上，所以實現不是特別重要。

問題在於，std :: list沒有訪問隨機節點的功能，只能訪問前臺/後臺並單步執行。我原本計劃以某種方式在這個列表中執行簡單的二進制搜索，並在幾個步驟中找到我的答案。

事實上，在std :: list中已經內置函數來執行這些類型的排序，這讓我相信有一種同樣簡單的方法來以我想要的方式訪問列表。

無論如何，感謝您的幫助提前！

Answer 1

鏈接列表的工作方式是逐步瀏覽列表中的項目。根據定義，無法訪問列表中的「隨機」元素。您引用的Sort方法實際上是通過逐個瀏覽每個節點並將項目放置在正確的位置來創建一個全新的列表。

如果您想隨機訪問數據，則需要以不同的方式存儲數據。也許是你正在存儲的元素的數組。

上鍊表的更多信息：http://en.wikipedia.org/wiki/Linked_list

Answer 2

合併排序並不需要訪問隨機元素，只能從列表的一端元素。