什麼是四鏈表？

我目前正致力於在工作中實現列表式結構，並且我需要它變得瘋狂有效。在尋找有效的數據結構時，我偶然發現了一個四方喜歡列表的專利，這引起了我的興趣，足以讓我忘記當前的任務，並開始調查四列表。不幸的是，互聯網對整個事情非常隱祕，谷歌在可用結果方面產生的不多。我得到的唯一解釋是所述的專利說明：什麼是四鏈表？

一個四鏈接數據結構，爲單個記錄中的多個相關字段提供雙向搜索功能。通過以N個數據條目的間隔提供指針集合來搜索數據庫，以適應指針的二進制搜索，隨後對結果範圍進行線性搜索以定位感興趣的項目及其相關字段。

不幸的是，這讓我更加困惑，因爲我無法將頭圍繞非外行的解釋。因此，我希望你們能向我解釋這個四連鎖歷史究竟是什麼，因爲我知道不知道會不會很快地把我推上去。

你知道四鏈表是什麼嗎？

來源

2009-04-28 Mia Clarke

與您的問題的主要內容無關，但如果您需要「瘋狂有效」的列表式結構，則需要將盡可能多的數據項一起存儲在內存中，哪個普通鏈表不太適合。一種方法是製作頁面，將1000個數據項目保存爲數組，並將它們建立鏈接列表。 – 2009-04-28 12:57:24

是的，我知道，但我要實現這個目標的系統要求它是一個鏈表，所以當我寫'瘋狂有效'時，我的意思就是'儘可能有效，當它被限制時到一個喜歡的名單「。 – 2009-04-28 13:01:56

這個怎麼樣：http://www.codeproject.com/KB/recipes/4-Way_LinkedList.aspx – 2009-04-29 05:36:26

我還沒有遇到術語正式之前，但是從專利說明書，我可以讓一個受過教育的猜測。

鏈表是一個其中每個節點有一個鏈接到下一個...

a -->-- b -->-- c -->-- d -->-- null

雙向鏈表意味着每個節點擁有一個鏈接到它的前身爲好。

--<-- --<-- --<-- 
|  |  |  | 
a -->-- b -->-- c -->-- d -->-- null

我們假設列表已經排序。如果我想執行二分搜索，我通常會在列表中間找到中間節點，然後進入適當的時間間隔並重復。但是，鏈表遍歷總是O（n） - 我必須遵循所有鏈接。從描述中，我認爲他們只是從節點添加其他鏈接，以「跳過」列表中前面的固定數量的節點。喜歡的東西...

--<-- --<-- --<-- 
|  |  |  | 
a -->-- b -->-- c -->-- d -->-- null 
|      | 
|----------->-----------| 
-----------<-----------

現在我可以更加迅速地遍歷表，尤其是如果我選擇了仔細額外的鏈接目標（即確保他們總是去，他們從指向該項目的偏移後退/前進一半列表長度）。然後我找到了我想要的這些鏈接的粗略間隔，並使用普通鏈接來查找該項目。

這是我討厭軟件專利的一個很好的例子。這是非常明顯的東西，用華麗的散文包裹着迷惑人們。

來源

2009-04-28 12:50:32

是的。軟件專利通常很糟糕。紐約地鐵系統在幾年前實施。 :) – 2009-04-28 12:58:32

這仍然是O（n）這個二元列表thingie（更快，但仍然與n成正比）。在我看來，一個更好的結構是一個平衡的二叉樹，它是搜索的O（log n）時間複雜度。 – paxdiablo 2009-04-28 13:42:41

的複雜性將取決於附加的鏈接結構 - 如果它們隔開，並且保持正確的，它可以使搜索O（LN N），但我認爲，如果他們被固定在列表中，他們「跳躍」的量，這是在O（n）上只是一個更好的常數。 – 2009-04-28 14:58:18

我不能確定，但聽起來有點像skip list。

即使這並非如此，您也可以方便地找到跳過列表。（據我所知，他們是單向的，但是。）

來源

2009-04-28 12:47:38

打我3秒！ – Pesto 2009-04-28 12:48:00

的描述不是特別好，但最好我所知，這聽起來像一個效率低的skip list。

來源

2009-04-28 12:47:41 Pesto

我不知道這是不是完全是「四聯單」，但它聽起來就像是這樣的：

struct Person { 
    // Normal doubly-linked list. 
    Customer *nextCustomer; 
    Customer *prevCustomer; 

    std::string firstName; 

    Customer *nextByFirstName; 
    Customer *prevByFirstName; 

    std::string lastName; 

    Customer *nextByLastName; 
    Customer *prevByLastName; 
};

也就是說：您通過收集維護多個排序。您可以使用名字順序或姓氏順序輕鬆導航。保持鏈接的更新非常昂貴，但它使導航非常快捷。

當然，這可能是完全不同的東西。

來源

2009-04-28 12:47:42

我的它讀數是一個四鏈表是一個可以在O（n）的兩種不同的方式被遍歷（向後或向前），根據FieldX或FieldY即排序：

（ a）生成第一和第二組鏈接指針的，其特徵在於，所述第一組的鏈接指針指向組相關記錄的後繼元素時的記錄是有序相對於所述固定ID 字段，和第二套鏈接點ERS指向前任一組相關的記錄的元素時的記錄排序，對於固定ID字段;

（b）產生第三和第四組鏈接指針的，其特徵在於，所述第三組的鏈接指針指向組相關記錄的後繼元素時的記錄是有序相對於所述可變 ID字段和第四組鏈接指針指向相關記錄集合的前導元素當時記錄按關於變量ID字段排序;

所以，如果你有一個員工的四鏈表，你可以存儲它按名稱排序和按年齡排序，並在O（n）中枚舉。

來源

2009-04-28 12:50:32

該專利的一個來源是this。還有，它的出現，兩種說法，其中第二個是更接近相關：

用於組織和搜索一組相關的記錄，其中每個記錄包括一種計算機實現的方法，包括：

ⅰ）一個固定ID字段;和

ii）變量ID字段;所述方法包括以下步驟：（a）產生第一和第二組鏈接指針，其中當所述記錄相對於所述固定順序排序時，所述第一組鏈接指針指向所述組相關記錄的後繼元素ID字段，並且當記錄相對於固定ID字段排序時，第二組鏈接指針指向該組相關記錄的前趨元素; （b）生成第三和第四組鏈接指針，其中當記錄相對於變量ID字段排序時，第三組鏈接指針指向相關記錄組的後繼元素，並且第四組鏈接指針當相對於變量ID字段排序記錄時，鏈接指針指向該組相關記錄的前趨元素; （c）產生第一組字段指針和第二組字段指針，其中第一組字段指針包括當記錄相對於固定ID字段排序時指向每第N個固定ID字段的有序指針集合，並且第二組指針包括當記錄相對於變量ID字段排序時指向每個第N個變量ID字段的有序指針集合; （d）當通過參考其固定ID字段來搜索特定記錄時，對第一組字段指針進行二分搜索以確定初始指針和最終指針，該初始指針和最終指針定義特定記錄所在的範圍位於; （e）通過線性查找檢查步驟（d）中確定的範圍內的固定ID字段以定位特定記錄; （f）當通過參考其變量ID字段來搜索特定記錄時，對第二組字段指針進行二分搜索以確定初始指針和最終指針，所述初始指針和最終指針定義特定記錄所在的範圍位於; （g）通過線性搜索檢查在步驟（f）中確定的範圍內的變量ID字段以定位特定記錄。

當通過專利官樣文章工作，我認爲這意味着大致相同爲具有兩個跳躍表（一個用於前向搜索，一個用於向後搜索）上的每兩個鍵（因此總共4所列出的，併名稱「四列表」）。我不認爲這是一個非常好的專利 - 它看起來是一個明顯的跳過列表應用程序的數據集，你有兩個鍵搜索。

來源

2009-04-28 12:57:27

什麼是四鏈表？

回答

相關問題