使用3個數組的雙重鏈接列表

設L是存儲在長度爲n的數組key，prev和next中的長度爲m的雙向鏈表。假設這些數組是由ALLOCATE_OBJECT和FREE_OBJECT過程管理的，它們保留一個雙重鏈接的空閒列表F.進一步說，n個項目[可以由三個數組描述，正好m在列表L上，其他nm在自由列表F.編寫一個程序COMPACTIFY_LIST（L，F），用於移動L中的項目，以便它們佔用陣列位置1,2，...，m並調整所有陣列中的索引值，以便L列表保持相同的順序，並且F列表包含如前所述的nsame元素數目，現在佔據陣列中的位置m + 1，m + 1，...，n。使用3個數組的雙重鏈接列表

我只能想到一個O（n）程序，我保留兩個指針。我從數組鍵的開始處開始使用兩個指針。 Pointer1查找第一個可用的空白空間，然後指針2查找包含鏈接列表元素的該位置後的第一個索引。然後將這個元素移動到pointer1指向的位置，然後pointer1查找下一個空白處並繼續。但是如果我沒有錯，這個過程將花費O（n）次。我想不出O（m）算法。

P.S.是的，這是作業。但我卡住了，一些幫助將非常感激。

來源

2013-03-11 tanvi

將L的每個元素[i]放置在基本數組A的位置[i]上就足夠了。通過L讀取並交換找到的每個元素，而無論哪個元素已經佔據其在A中指定的位置。 O（m）複雜度。

來源

2013-03-11 21:31:46

通過將L的每個元素[i]放置在基本數組的位置[i]中，這是什麼意思？非常感謝您的回覆，但我無法理解您的解決方案。你能詳細說明一下嗎？ – tanvi 2013-03-11 21:38:58

有什麼不懂的？請更具體地說明什麼會給你帶來困難。 – 2013-03-11 21:50:38

@tanvi：兩者;這就是訣竅。通過與L或F的任何元素進行交易，L的元素[i]直接映射到A的元素[i]。 – 2013-03-11 22:02:56

使用3個數組的雙重鏈接列表

回答

相關問題