0

基本的に、バイナリ ヒープとリニア プロービング ハッシュテーブルをマージして、ヒープの機能とハッシュテーブルの並べ替え機能を備えた「複合」データ構造を作成する必要があります。

私がする必要があるのは、データ構造 (バイナリ ヒープとハッシュ) ごとに 2 つの 2 次元配列を作成し、ポインターを使用してそれらを相互にリンクし、バイナリ ヒープの値を削除するなどの変更を行うと、それも取得されるようにすることです。ハッシュ テーブルから削除されます。

したがって、ヒープから Hastable を指すヒープ配列の 1 行と、ハッシュテーブルからヒープを指すハッシュテーブル配列の 1 行が必要です。

4

2 に答える 2

1

アルゴリズムに必要なすべての操作を実行するアクセサー関数/メソッド (実装言語に応じて) を使用して、両方を含むコンテナーを作成します。

IE: コンテナから削除: バイナリとハッシュから削除します。

コンテナーに追加: バイナリーとハッシュに追加します。

編集: ああ、割り当て - 楽しい! :)

私はこれを行います：まだコンテナを実装しています。ただし、btree/hash の標準ライブラリを使用する代わりに、次のように実装します。BTree ノードとデータ要素が存在する Hashtable ノードへのポインターを持つデータ メンバーに配置できる型を作成します。

データ要素を削除するには、データ要素へのポインターを指定すると、btree (ノード ポインターから親に移動、子 (左または右) を削除、ツリーを再構築) およびハッシュ テーブル (ハッシュ リストから削除) に対して削除アルゴリズムを実行できます。 ）。値を追加するときは、btree とハッシュに対して追加アルゴリズムを実行しますが、戻る前に必ずデータ内のノード ポインターを更新してください。

いくつかの疑似コード (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

リンクを気にする必要はありません。

2つの連想構造があり、一方の操作をもう一方の操作に複製するだけです（1つの操作を除いて、全体をクラッシュさせるか、オブジェクトを有効な状態のままにしておく必要があります）

一方の構造を他方の構造に役立てることができない限り (そして、どの変更操作でも内部状態を完全に再配置できるため、どのようにできるかわかりません)、これは同じくらい効果的で、はるかに簡単です。

もちろん、これは、変更操作の O() コストが最も高価なコストであり、メモリ コストが 2 倍になることを意味しますが、それは、私が見逃しているトリックでない限り、元の計画に当てはまります。

于 2009-04-22T00:04:59.080 に答える