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