示例顯示爲圓形鏈表和跳過列表

我想問你的想法是什麼類型的程序，甚至我可以更好地解釋理論理論的有用性的技術圓形鏈表和跳過列表給我的同行。示例顯示爲圓形鏈表和跳過列表

我的編程觀念是，如果你給他們的例子和隱喻，人們可以更好地理解一個概念。

只是你的想法創建示例程序或解決方案（編程技術或算法）。

乾杯！

來源

2011-03-14 Panoy

你的意思是，你需要爲這些數據結構現實世界中的用例？或者你需要解釋他們如何使用範例和隱喻來工作？ – MAK 2011-03-14 05:34:07

是的，如果不是太多問的話。我的想法是創建一個使用循環和跳過列表的程序，以便他們知道它的目的以及它可以使用它的場景。 – Panoy 2011-03-14 05:37:49

循環鏈接列表的一個很好的用處是作業調度系統，其中每個作業都在給定資源（如簡單操作系統中的進程）上獲得一定的時間。

在這種情況下，具有特定的head是沒有意義的，因爲您總是在列表中循環，所需的全部是指針current。您可以在當前作業之後添加新作業，並使用current來找到要刪除的作業。推進到下一個工作是一個簡單的：

current = current->next

可能的跳躍列表以列表形式的字典。您保留一個指向第一個字a的指針，它包含一個指向aardvark的正常指針和一個指向baa^{* a}的跳轉指針。

^*一個：其實我不知道，如果他們是正確的話，但他們應該是接近，你會希望得到的想法。

來源

2011-03-14 05:53:07 paxdiablo

這可以是一個很好的。我會考慮這一點。謝謝！ – Panoy 2011-03-14 05:56:57

從Wikipedia：

圓鏈表可以代表陣列是自然圓形，例如天然選項多邊形的角落，緩衝區的池使用和釋放在先進先出順序，或應按時間輪循順序。在這些應用程序中，指向任何節點的指針將作爲整個列表的句柄。

一個容易想象的圓形列表如何工作的例子可能是想象一羣人站在一個圈子裏，每個人只知道左邊的人的名字。因此，爲了搜索組中的一個人，你從第一個人（在這種情況下是任意一個人）開始，然後轉移到他知道他的名字的人（即他的左邊），直到找到你要找的人或來再回到第一個人。在這個羣體中添加或刪除一個人只需要將一個人從圈子中拿走或者將人員知道的名字改爲他的右邊（如果他是一個添加的話，告訴他左邊那個人的名字）。我希望這個例子很有意義，它基本上是我在瞭解鏈表時的可視化方式。

跳過列表支持快速（O（log（n）））操作，可用作排序數據結構 - 非常像平衡二叉搜索樹。這使得他們有用的地方，我們需要快速的數據插入/刪除時間（如鏈表但不同於陣列），並且還具有快速訪問時間（如一個數組，但不像一個鏈表）。它們也是好的用於製造快速範圍查詢（例如發現的和（或在該結構的指數爲[I，J]的所有元素的最大值，最小值，產品，等等））。

我想不出一個足夠簡單真實世界的比喻爲一個跳躍列表，數據結構看起來相當比任何我可以期望看到在日常生活中的物體更加複雜。但是這個解釋很清楚，通過構建它的證明和算法來工作應該是一個很好的起點。這是一個鏈接到original paper這也是很可讀的國際海事組織。

來源

2011-03-14 05:55:24 MAK

謝謝。這是鴨，鴨，鵝遊戲嗎？ ;） – Panoy 2011-03-14 06:05:18

@Panoy：我不太確定這個遊戲被稱爲什麼。在我的世界兒童的一部分發揮，其中一個令牌（通常是一個枕頭）傳遞一個遊戲，而人誰不看說，開始在隨機時間間隔/停止（或播放/停止音樂）。拿着令牌的人被移除，遊戲再次開始，直到只有一個人離開。 – MAK 2011-03-14 06:10:21

我很欣賞跳過列表主題的更新。乾杯! – Panoy 2011-03-14 07:02:52

跳錶基本上都是一組額外的清單（或真鏈接）放在一個正規有序鏈表的頂部，以協助在列表中搜索的。

跳躍列表創建正規鏈表的頂部二叉搜索樹是一種-，使搜索操作都爲O（log n）的時間，而不是O（N），使其速度更快。您可以在任何想要使用常規鏈接列表的地方使用它們，但需要更快的訪問。

下頁有跳躍列表一個非常好的，易於後續討論： http://igoro.com/archive/skip-lists-are-fascinating/

來源

2011-03-14 06:05:53 shreddd

示例顯示爲圓形鏈表和跳過列表

回答

相關問題