有序雙向鏈表搜索

假設我們有雙重鏈接的整數值排序列表：有序雙向鏈表搜索

struct ListItem 
{ 
    int value; 
    ListItem *prev, *next; 
}; 

struct List 
{ 
    ListItem *first, *last; 
    int count; 
};

我們可以用更快的搜索算法，如二進制搜索來查找ListItem內List又如何呢？

來源

2011-07-10 Muhammad Aladdin

聽起來像作業。請在標題中添加作業標籤和/或單詞「家庭作業」。 –

不，它不是作業 –

編寫多語言源文件很難。我建議你堅持使用C或C++之一。 – pmg

對於大多數實際目的，沒有。如果你想要更快的搜索，鏈接列表是一個糟糕的數據結構選擇。考慮一個vector，deque，set或multiset。

編輯：或許最好提供一些指導，說明哪些是有意義的。如果您有兩個基本上單獨的階段，則矢量最有意義：要麼按順序插入所有數據，要麼插入並排序，然後在數據排序後，數據保持靜態，並且只需在其中搜索即可。一個deque幾乎是一樣的，除了你可以在任何一端插入，所以如果你可能會按順序獲取數據，但新數據總是屬於集合的一端或另一端，那麼它可能是一個不錯的選擇。

A set或multiset如果您打算將插入/刪除與查找混合，效果會更好。它始終保持排序狀態，因此搜索總是相當快速。在兩者之間（set與multiset）的選擇非常簡單：如果您需要確保集合中的每個項目都是唯一的，那麼您需要設置。如果您可能有多個具有相同密鑰的項目，則需要多重集。

來源

2011-07-10 16:10:46

我正在爲大數據集寫一個哈希表，哈希表使用單獨的鏈式方法，並且使用向量將是一個不好的選擇，因爲內存重新分配 –

@Muhammad：我不確定我遵循內存重新分配應該如何做在這種情況下差別很大。無論如何，對於一個散列表，你的搜索碰撞鏈的方法應該很少有很大的區別。缺少病態散列函數或對整體大小的猜測很不準確，您應該很少搜索超過幾個項目（通常是〜3）。對於要搜索的這個小集合，線性搜索和二分搜索幾乎沒有任何區別。 –

那麼，你仍然需要循環所有元素直到中間元素。我不確定二進制搜索是否會加快通過鏈接列表搜索的速度，或者是否因此而加快搜索速度。例如，您的元素位於中間元素之前，從邏輯上看，只是在這些元素之間循環顯得更快。否則，你只是要去中間，看看你的元素是在哪裏，然後再循環，然後......騎自行車是真正會殺死這個的。我想這也取決於你的元素在列表中的確切位置。

來源

2011-07-10 15:50:53 MGZero

如果您只需執行幾次搜索，我懷疑從頭到尾搜索列表將是最佳選擇。可能有一些算法可以更高效，但它只會稍好一些。

但是，如果您必須多次執行搜索，則需要將列表複製到支持二分搜索的有序隨機訪問容器中。

來源

2011-07-10 16:17:06 Nubcase

如果節點之間沒有基於這些值的排序，則不會有其他選擇，只能單獨檢查所有節點。因此O（n）。

來源

2011-07-10 16:26:13

是的，你可以，但除非「比較值」的操作比「移動指針」花費更高，否則完全沒有意義。因爲通常「移動」大約是成本高，因爲「比較」，用普通的搜索：

O（N）移動
O（N）的比較

二進制：

O（N）移動到確定列表
O（N）移動到定位元件
O（日誌（N））的共同大小mparisons。

在你的例子中，值是「int」，這意味着比較比運動更便宜，所以二進制算法將會更加昂貴。

如果知道列表的大小，二進制可能會（可以說）變得更便宜，但是增加的雙向邏輯移動和元素計數的複雜性將會減少數值比較的減少帶來的好處。

當然，如果您需要多次搜索，最簡單的方法是將鏈表轉換爲數組或創建一個索引 - 一個指針數組。如果這個值比int複雜得多並且比較難以比較，那麼更快的算法當然是最合適的。

來源

2011-07-11 07:38:53

有序雙向鏈表搜索

回答

相關問題