實現直接地址表

我給出的功課Introduction to Algorithms鍛鍊11.1-3肚裏如下：實現直接地址表

建議如何落實其中存儲的元素的按鍵並不需要是不同的直接訪問表並且元素可以具有衛星數據。所有三種字典操作（插入，刪除和搜索）應該在O（1）時間內運行。不要忘記，Delete將一個指向要刪除的對象的指針作爲參數，而不是一個鍵。

那麼，插入是沒有問題的，因爲它只是意味着在表中適當的位置創建一個鏈表（如果它尚不存在）並添加元素。 Search被賦予一個鍵，可以返回任何與鍵匹配的元素，因此它意味着我們需要返回表中匹配列表的頭部。

我的問題是刪除操作。如果我修改對象來添加一個指向其鏈接列表中節點的指針，那麼我可以在O（1）中刪除，但我不確定我是否允許更改該對象。有沒有辦法做到這一點，而不改變給定的對象？

來源

2010-01-03 CS n00b

+1用於發佈作業問題並披露並顯示您已嘗試過某些東西。歡迎來到SO – JoshJordan 2010-01-03 19:28:02

標準的香草鏈接列表不會給你O（1）的搜索性能。 – 2010-01-03 19:29:02

@GregS - 我說過我可以用匹配鍵返回任何元素，這意味着我可以返回列表的頭部，這是O（1）。 – 2010-01-03 19:55:37

哈希表將爲您工作到某一點。一旦你開始有collsions，那麼它變成O（1 + k/n），其中k是鍵的數量，n是你的表格大小。如果您執行預定的哈希大小調整並重新哈希，那麼您可能會擺脫這種情況。不知道這是否會影響您的效率等級，因爲它不會在插入，刪除或搜索過程中發生。

通過不改變對象的刪除可以通過簡單地將散列引用指針設置爲空來實現。不直接改變對象，但改變對象容器。

我認爲，對於大多數您提供的限制，可以通過某種方式實現哈希表來解決它們。 http://en.wikipedia.org/wiki/Hash_table#Performance_analysis有關如何實現散列表的更多信息。

來源

2010-01-04 02:01:20

這是來自Cormen書的問題嗎？據我所知，通過閱讀該書中的前幾段，您存儲在直接訪問表中的對象是「您的」對象。因此，您可以按照您的建議將指向雙向鏈表的指針存儲在表中，每個列表元素都有一個指向用戶對象的指針。然後，字典SEARCH操作返回一個列表元素，用戶必須使用更多的步驟來獲取他的對象。同樣的，DELETE操作需要一個指向list元素的指針。

這有道理嗎？我不想破壞你的功課！

來源

2010-01-04 19:16:06

如果您有n個重複項目的列表，該怎麼辦？那將是O（n）。 – 2017-07-14 16:25:24

「不要忘記，Delete作爲參數指向要刪除的對象的指針」 - 因此，您將獲得n-1個重複項目的列表。 – 2017-07-15 20:04:58

明白了。在這種情況下，你甚至不需要雙向鏈表。有一種方法可以刪除O（1）中的當前節點。現在不會破壞作業... – 2017-07-17 16:08:14

我認爲你可以利用衛星數據映射爲輔助鍵。然後它是一種2級哈希表。關心DELETE操作，首先我們使用主鍵。當有重複的主鍵時，我們使用輔助鍵來獲取對象。因此總時間仍然是O（1）。

來源

2012-06-22 09:12:54 Romi

最重要的部分。「實施，其中存儲元件的密鑰並不需要是不同的直接訪問表」和「爲O字典操作（1）的時間。

如果元素相等，插入在O（1）時間也是不可能的（因爲Q表示元素不需要是不同的）。

對於刪除部分，您必須採取密鑰以及對象才能到達特定對象並假設衛星數據的密鑰，以便覆蓋特定對象。

我認爲只有以上兩個想法對O（1）時間有意義。

來源

2013-01-06 10:30:50 Atiq

我們可以在直接地址表的每個索引處使用雙鏈表。插槽j將包含一個指向列表頭的指針，該指針包含所有具有鍵值j的元素，並且如果沒有這樣的元素槽j包含NIL。 INSERT - 在列表頭部插入x只需要O（1）次。 SEARCH-它可以返回任何匹配給定鍵的元素，因此返回列表頭只需要O（1）次。 DELETE-因爲我們已經使用了雙鏈表，所以我們可以使用指向上一節點和下一節點的指針來刪除O（1）時間中的一個元素。

來源

2014-05-27 08:04:54

實現直接地址表

回答

相關問題