實現跳躍列表在C++

Question

[解決]

所以我決定嘗試並創建一個排序的雙向鏈接跳轉列表...

我敢肯定，我有它的工作原理，把握好。當你插入x時，程序在基礎列表中查找放置x的適當位置（因爲它是排序的），（概念上）翻轉一個硬幣，如果「硬幣」落在一個然後該元素被添加到它上面的列表中（或者一個新的列表是由元素創建的），鏈接到它下面的元素，並且硬幣再次翻轉等。如果「硬幣」在任何時候落在b上，則插入結束。您還必須將每個列表中存儲的「無限」存儲爲起點，以便插入小於起始點的值（這意味着永遠不會找到該值），因此無法插入該值。

要搜索x，你從「左上角」（最高名單最低值）和「右移」到下一個元素開始。如果該值小於x，那麼繼續執行下一個元素，等等，直到您「走得太遠」並且該值大於x。在這種情況下，你回到最後一個元素並向下移動一層，繼續這個鏈，直到你找到x或x從未找到。

要刪除x，您只需搜索x並在列表中出現時將其刪除。

現在，我只是做一個存儲數字的跳過列表。我認爲STL中沒有任何東西可以幫助我，所以我需要創建一個List類，它包含一個整數值並具有成員函數，搜索，刪除和插入。

我遇到的問題是處理鏈接。我敢肯定，我可以創建一個類來處理「水平」鏈接，指向前一個元素和前面的元素，但我不知道如何處理「垂直」鏈接（指向相應的元素？在其他列表）

如果有我的邏輯是有缺陷的，請告訴我，但我的主要問題是：

1. 如何處理縱向聯繫，以及是否我的鏈接的想法是正確的現在
2. 我讀了我的班級列表的想法我在想列表應該持有一個整數向量而不是一個整數。事實上，我非常積極，但只是想驗證一下。
3. 我假設硬幣翻轉會簡單地調用int函數，其中rand（）％2返回0或1的值，如果它爲0，則值爲「levels up」，如果爲0，則插入結束。這是不正確的？
4. 如何存儲類似於-infinite的值？

編輯：我已經開始編寫一些代碼，並且正在考慮如何處理List構造函數....我猜測在構造時，「-infinite」值應該存儲在vectorname [ 0]元素，我可以在它創建後調用insert來將x放在適當的位置。

Answer 1

1. 只需存儲2個指針。一個叫上面，一個叫你下面的節點類。
2. 不確定你的意思。
3. 根據wikipedia你也可以做幾何分佈。我不確定發佈的類型對於完全隨機訪問是否重要，但如果您知道訪問模式，則顯然很重要。
4. 我不確定你的意思。你可以用浮點數來表示類似的東西。

Answer 2

http://msdn.microsoft.com/en-us/library/ms379573(VS.80).aspx#datastructures20_4_topic4

http://igoro.com/archive/skip-lists-are-fascinating/

上述跳躍列表在C＃實現的，但可以使用該代碼制定出一個C++實現。

Answer 3

「垂直」和「水平」太複雜了。他們都只是指針。你在紙上繪製線條的小盒子只是爲了在思考它們時幫助形象化。你可以調用一個指針「大象」，如果你願意，它會去下一個節點。

例如。 「下一個」和「前一個」指針與「上」/「下」指針完全相同。

無論如何，祝你的作業好運。在我的數據結構類中，我曾經做過同樣的功課。