0
정적 메모리 할당을 사용하여 주어진 해시 테이블을 동적으로 변경하여 프로그램 실행 중에 더 많은 메모리를 한도를 초과하여 할당 할 수있는 할당이 주어졌습니다. 나는 문제에 대한 해결책을 요구하는 것이 아니므로, 누군가가 시작하기 좋은 장소를 알고 있는지 또는 내가 해시 테이블과 약간 혼동되고 혼란스러워 할 때주의해야 할 코드의 측면을 묻는 것입니다. 열거 형을 알고 생성자를 변경해야하지만 다른 것들은 잘 모릅니다.정적 해시 테이블을 동적 해시 테이블로 변환
#ifndef TABLE1_H
#define TABLE1_H
#include <cstdlib> // Provides size_t
#include <cassert> // Provides assert
namespace main_savitch_12A
{
template <class RecordType>
class table
{
public:
enum { CAPACITY = 30 };
// CONSTRUCTOR
table();
// MODIFICATION MEMBER FUNCTIONS
void insert(const RecordType& entry);
void remove(int key);
// CONSTANT MEMBER FUNCTIONS
bool is_present(int key) const;
void find(int key, bool& found, RecordType& result) const;
size_t size() const { return used; }
private:
// MEMBER CONSTANTS -- These are used in the key field of special records.
enum { NEVER_USED = -1 };
enum { PREVIOUSLY_USED = -2 };
// MEMBER VARIABLES
RecordType data[CAPACITY];
size_t used;
// HELPER FUNCTIONS
size_t hash(int key) const;
size_t next_index(size_t index) const;
void find_index(int key, bool& found, size_t& index) const;
bool never_used(size_t index) const;
bool is_vacant(size_t index) const;
};
template <class RecordType>
table<RecordType>::table()
{
size_t i;
used = 0;
for (i = 0; i < CAPACITY; ++i)
data[i].key = NEVER_USED; // Indicates a spot that's never been 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)
{
assert(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;
}
template <class RecordType>
void table<RecordType>::remove(int key)
// Library facilities used: cassert
{
bool found; // True if key occurs somewhere in the table
size_t index; // Spot where data[index].key == key
assert(key >= 0);
find_index(key, found, index);
if (found)
{ // The key was found, so remove this record and reduce used by 1.
data[index].key = PREVIOUSLY_USED; // Indicates a spot that's no longer in use.
--used;
}
}
template <class RecordType>
bool table<RecordType>::is_present(int key) const
// Library facilities used: assert.h
{
bool found;
size_t index;
assert(key >= 0);
find_index(key, found, index);
return found;
}
template <class RecordType>
void table<RecordType>::find(int key, bool& found, RecordType& result) const
// Library facilities used: cassert.h
{
size_t index;
assert(key >= 0);
find_index(key, found, index);
if (found)
result = data[index];
}
template <class RecordType>
inline size_t table<RecordType>::hash(int key) const
{
return (key % CAPACITY);
}
template <class RecordType>
inline size_t table<RecordType>::next_index(size_t index) const
// Library facilities used: cstdlib
{
return ((index+1) % CAPACITY);
}
template <class RecordType>
void table<RecordType>::find_index(int key, bool& found, size_t& i) const
// Library facilities used: cstdlib
{
size_t count; // Number of entries that have been examined
count = 0;
i = hash(key);
while((count < CAPACITY) && (data[i].key != NEVER_USED) && (data[i].key != key))
{
++count;
i = next_index(i);
}
found = (data[i].key == key);
}
template <class RecordType>
inline bool table<RecordType>::never_used(size_t index) const
{
return (data[index].key == NEVER_USED);
}
template <class RecordType>
inline bool table<RecordType>::is_vacant(size_t index) const
{
return (data[index].key == NEVER_USED);// || (data[index].key == PREVIOUSLY_USED);
}
}
#endif