0

だから私は現在、ハッシュテーブルについてもっと教えてくれることを目的としたプロジェクトに取り組んでいます

ただし、KeyValuePair 型のテンプレート リンク リストの配列であると想定される HashTable のデータ メンバーを実装するのは非常に困難です。

プログラムの要件の 1 つは、連鎖アドレッシングを実装することと、ユーザーがデータ配列の長さを初期化できることです。そのため、リンク リストの配列を使用することを余儀なくされています。

Data メンバーへの挿入に問題があるため、Data メンバーの宣言 (次のコード セグメントの下部) に何か問題があるのではないかと推測しました。

template <typename DATA_TYPE>
class HashTable
{
    typedef pair<const int, DATA_TYPE> KeyValuePair;

private:
    int Size;
    int Keys;
    list<KeyValuePair>* Data;

私が理解しているように、これにより、リンクされたリストの配列の要素を指すことができるはずです。

しかし、配列の初期化 (および配列への挿入。これについては後で説明します) に関しては、何が問題なのかよくわかりません。

これは私のコンストラクタとデストラクタです:

public:
HashTable(const int& size = INITIAL_SIZE)
{
    assert( size > 0 );
    Keys = 0;
    Size = size;
    Data = new list<KeyValuePair>[Size];
    /*for(int i = 0; i<Capacity; i++)
        Data[i] = new list<DATA_TYPE>;*/
}

~HashTable()
{
    delete[] Data;
}

これは私の挿入関数で、std::list でブレークポイントが発生します。これは、list.merge() で NULL の ".Next" ポインターにアクセスしようとしているために発生したと思います。確信はないけど：

void Insert(const DATA_TYPE& value)
{
    int hashIndex;
    hashIndex = HashCode(value);

    KeyValuePair* newPair = new KeyValuePair(hashIndex, value);
    list<KeyValuePair>* newHash = new  list<KeyValuePair>;

    newHash->push_back(*newPair);
    while(hashIndex>Size)
    {
        hashIndex-=Size;
    }
    //Data[hashIndex]->push_back(value);
    Data[hashIndex].merge(*newHash);
}

私はここ数日間これに取り組んできたばかりで、私がしていることを見て、私の考えを肯定または支援するために、本当に新鮮な目が必要です...

4

2 に答える 2

0

理解した！

したがって、これに関する最も困難な問題の 1 つは、デバッグ ウィンドウで配列ポインターのデータ要素を表示する方法がないことです。これは、配列ポインターが常に先頭または配列内のある点のみを指しているためです。

しかし、とにかく、(元のコードにあったメモリ リークを修正する以外に)主な問題は、 (思ったとおり) 初期化されたリンク リストを初期化されていないリストとマージしようとしたことでした。

これを解決するために、以下のコード スニペットで std::list.push_back() 関数を使用しました。リストを初期化し、そのハッシュインデックスに既に存在する可能性のある値を上書きしません。

実際に値をハッシュしていることを確認するために、(データ値を指定して) インデックスを検索し、そのインデックスに保存されている文字列を出力する検索関数を作成しました。

void Insert(const DATA_TYPE& value)
{
    int hashIndex;
    hashIndex = HashCode(value);

    KeyValuePair newPair = KeyValuePair(hashIndex, value);

    while(hashIndex>Size)
    {
        hashIndex-=Size;
    }

    Data[hashIndex].push_back(newPair);
}

（悲しいことに、答えを投稿する前に待たなければなりませんでした）

于 2013-04-22T16:00:38.350 に答える
0

コンストラクターでデータを削除するのはなぜですか

HashTable(const int& size = INITIAL_SIZE)
{
    Keys = 0;
    Size = size;
    if(size!=INITIAL_SIZE)
    {
        delete[] Data;  <------------
        Data = new list<KeyValuePair>[Size];
    }
}

削除するものは何もありません。 

 HashTable( int size = INITIAL_SIZE)
{
    assert ( size > 0 );
    Keys = 0;
    Size = size;
    Data = new list<KeyValuePair>[Size];
}

また

while(hashIndex>Size)
{
    hashIndex-=Size;
}
//Data[hashIndex]->push_back(value);
Data[hashIndex].merge(*newHash);

の場合hashIndex == Size、範囲外の要素にアクセスすることになります。

于 2013-04-19T19:37:33.280 に答える