0

私はこのハッシュ テーブルの実装に取り​​組んできましたが、障害にぶつかりました。容量に達した場合に配列のサイズを変更できるようにコンストラクターと挿入関数を変更しましたが、サイズ変更に問題があります。現在、負のデータを無限に挿入しているようですが、その理由はわかりません。サイズ変更内にイテレータを実装する必要がありますか、それとももっと簡単な方法がありますか?

関数は次のとおりです。

サイズ変更:

template <class RecordType>
void table<RecordType>::resize( )
{

    RecordType *oldData = data;
    int oldSize = CAPACITY;
    int newSize = CAPACITY *2;

    //create a new table
    RecordType *newData;
    newData = new RecordType[CAPACITY];

    size_t i;
    used = 0;

    for (i = 0; i < CAPACITY; i++)
        newData[i].key = NEVER_USED;

    data = newData;
    delete[] newData;

    //place data from old table to new, larger table.
    for(int i = 0; i < oldSize; i++)
    {
            RecordType next = oldData[i];
            insert(next);
    }

    CAPACITY = newSize;
    delete[] oldData;
}

コンストラクタ:

template <class RecordType>
table<RecordType>::table( )
{
    CAPACITY = 30;
    data = new RecordType[CAPACITY];

    size_t i;

    used = 0;
    for (i = 0; i < CAPACITY; ++i)
        data[i].key = NEVER_USED;

}

入れる:

template <class RecordType>
void table<RecordType>::insert(const RecordType& entry)
// Library facilities used: cassert
{
    bool already_present;   // True if entry.key is already in the table
    size_t index;        // data[index] is location for the new entry

    assert(entry.key >= 0);

    // Set index so that data[index] is the spot to place the new entry.
    find_index(entry.key, already_present, index);

    // If the key wasn't already there, then find the location for the new entry.
    if (!already_present)
    {
        if (size( ) >= CAPACITY)
        {
            resize( ); // resize the table.

            insert(entry); // reinsert entry into new table.
        }
        else if (size( ) < CAPACITY)
        {
            index = hash(entry.key);

            while (!is_vacant(index))
                index = next_index(index);
            ++used;
        }
    }

    data[index] = entry;
    size_t i;
    for (i=0; i<CAPACITY; i++) cout << data[i].key << ' ';
    cout << endl;
}

助けてくれてありがとう!

4

1 に答える 1

0

にデータを入れているあなたresize()が呼んでいます。次に、空の (完全な)配列で上書きします。私の推測では、削除して代わりに使用したいだけです。insert()data[]resize()dataNEVER_USEDnewDatanewDatadata

CAPACITY *= CAPACITYこのコードを実際に使用しようとすると、これが爆発するので、おそらく再考する必要があります。

于 2013-06-08T04:09:18.830 に答える