实现直接地址表

我给出的功课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

实现直接地址表

回答

相关问题