0

我需要基本上合并一个二进制堆和线性探测哈希表来制作一个“复合”数据结构，它具有堆的功能，具有哈希表的排序能力。

我需要做的是为每个数据结构（二进制堆和哈希）创建 2 个二维数组，然后用指针将它们相互链接，这样当我更改内容时，例如删除二进制堆中的值，它也会得到在哈希表中删除。

因此，我需要让 Heap 数组的一行从 Heap 指向 Hastable，而 hashtable 数组的一行从 hashtable 指向堆。

4

2 回答 2

1

创建一个包含两者的容器，以及执行算法所需的所有操作的访问器函数/方法（取决于您的实现语言）。

IE：从容器中删除：从二进制和哈希中删除。

添加到容器：添加到二进制和哈希。

编辑：哦，一个任务 - 有趣！:)

我会这样做：仍然实现一个容器。但是，不要为 btree/hash 使用标准库，而是像这样实现它们：创建一个可以放入数据成员中的类型，该类型具有指向数据元素所在的 BTree 节点和 Hashtable 节点的指针。

要删除一个数据元素，给定一个指向它的指针，您可以在 btree（从节点指针导航到父节点、删除子节点（左或右）、重构树）和哈希表（从哈希列表中删除）上执行删除算法）。添加值时，对 btree 和 hash 执行 add 算法，但请确保在返回之前更新数据中的节点指针。

一些伪代码（我将使用 C，但我不确定您使用的是什么语言）： typedef struct { BTreeNode* btree HashNode* hash } ContianerNode;

将数据放入容器中：

typedef struct
{
    ContainerNode node;
    void* data; /* whatever the data is */
} Data;

BTreeNode 有类似的东西：

typedef struct _BTreeNode
{
    struct _BTreeNode* parent;
    struct _BTreeNode* left;
    struct _BTreeNode* right;
} BTreeNode;

一个 HashNode 有类似的东西：

typedef struct _HashNode
{
    struct _HashNode* next;
} HashNode;
/* ala singly linked list */

并且您的 BTree 将是指向 BTreeNode 的指针，而您的 hastable 将是指向 HashNodes 的指针数组。像这样：

typedef struct
{
    BTreeNode* btree;
    HashNode* hashtable[HASHTABLESIZE];
} Container;

void delete(Container* c, ContainerNode* n)
{
    delete_btree_node(n->btree);
    delete_hashnode(n->hash);
}

ContainerNode* add(Container* c, void* data)
{
    ContainerNode* n = malloc(sizeof(ContainerNode));
    n->btree = add_to_btree(n);
    n->hash = add_to_hash(n);
}

我会让你完成那些其他功能（不能为你完成整个任务；））

于 2009-04-22T00:05:12.560 回答
0

为什么要打扰链接？

您有两个关联结构，只是将一个上的任何操作复制到另一个上（确保如果一个操作除外，您要么使整个事物崩溃，要么让对象处于有效状态，如果您关心这些事情）

除非您可以利用其中一个的结构来帮助您处理另一个（我不知道您如何做到这一点，因为任何一个都可以在任何修改操作中完全重新安排其内部状态），这同样有效且简单得多。

当然，这意味着任何修改操作的 O() 成本是最昂贵的成本，并且内存成本加倍，但原始计划确实如此，除非它们是我遗漏的一些技巧。

于 2009-04-22T00:04:59.080 回答