实现直接地址表

Question

我被作为家庭作业的算法导入练习11.1-3,如下:

建议如何实现直接访问表,其中存储元素的键不需要是不同的,并且元素可以具有卫星数据.所有三个字典操作(插入,删除和搜索)都应该在O(1)时间内运行.不要忘记Delete将一个指向要删除的对象的指针作为参数,而不是键.

好吧,Insert没有问题,因为它只是意味着在表中的适当位置创建一个链表(如果它还不存在)并向其添加元素.给定键的搜索可以返回与键匹配的任何元素,因此它只是意味着我们需要返回表中匹配列表的头部.

我的问题是删除操作.如果我修改对象添加到链接列表中指向其节点的指针,那么我可以在O(1)中删除,但我不确定我是否可以更改对象.有没有办法在不改变给定对象的情况下这样做？

Answer 1

这是Cormen书中的一个问题吗？据我了解,通过阅读该书中的前几段,您存储在直接访问表中的对象是"您的"对象.因此,您可以按照建议将指针存储到表中的双向链表,每个列表元素都有一个指向用户对象的指针.然后,字典SEARCH操作返回一个列表元素,用户必须使用另一个步骤来获取他的对象.同样,DELETE操作采用指向列表元素的指针.

那有意义吗？我不想破坏你的作业!

Answer 2

哈希表在一定程度上可以为您工作。一旦开始发生冲突，就会变成 O(1+k/n)，其中 k 是键的数量，n 是表的大小。如果您执行计划的哈希大小调整和重新哈希，那么您可能能够摆脱这种情况。不知道这是否会影响您的效率评级，因为在插入、删除或搜索期间不会发生这种情况。

只需将散列引用指针设置为空即可实现不改变对象的删除。不会对对象进行直接更改，但会对对象容器进行更改。

我认为对于您给出的大多数限制，可以通过某些方式实现哈希表来绕过它们。有关如何实现哈希表的更多信息，请访问http://en.wikipedia.org/wiki/Hash_table#Performance_analysis 。