好的，所以我正在研究“使用 C++ 第 4 版的数据结构和其他对象”一书。我正在制作一个哈希表，它接受密钥并使用开放寻址将它们哈希到正确的位置以解决冲突。下面的代码是我目前拥有的。
头文件
#ifndef TABLE1_H
#define TABLE1_H
#include <cstdlib> // Provides size_t
{
template <class RecordType>
class table
{
public:
// MEMBER CONSTANT -- See Appendix E if this fails to compile.
static const std::size_t CAPACITY = 811;
// 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;
std::size_t size( ) const { return used; }
private:
// MEMBER CONSTANTS -- These are used in the key field of special records.
static const int NEVER_USED = -1;
static const int PREVIOUSLY_USED = -2;
// MEMBER VARIABLES
RecordType data[CAPACITY];
std::size_t used;
// HELPER FUNCTIONS
std::size_t hash(int key) const;
std::size_t next_index(std::size_t index) const;
void find_index(int key, bool& found, std::size_t& index) const;
bool never_used(std::size_t index) const;
bool is_vacant(std::size_t index) const;
};
}
#include "table1.template" // Include the implementation.
#endif
和模板类
template <class RecordType>
const std::size_t table<RecordType>::CAPACITY;
template <class RecordType>
const int table<RecordType>::NEVER_USED;
template <class RecordType>
const int table<RecordType>::PREVIOUSLY_USED;
template <class RecordType>
table<RecordType>::table( )
{
std::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
std::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;
}
template <class RecordType>
void table<RecordType>::remove(int key)
// Library facilities used: cassert
{
bool found; // True if key occurs somewhere in the table
std::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;
std::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
{
std::size_t index;
assert(key >= 0);
find_index(key, found, index);
if (found)
result = data[index];
}
template <class RecordType>
inline std::size_t table<RecordType>::hash(int key) const
{
return (key % CAPACITY);
}
template <class RecordType>
inline std::size_t table<RecordType>::next_index(std::size_t index) const
// Library facilities used: cstdlib
{
return ((index+1) % CAPACITY);
}
template <class RecordType>
void table<RecordType>::find_index(int key, bool& found, std::size_t& i) const
// Library facilities used: cstdlib
{
std::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);
// Tried adding Counter = Counter +1.
// Failed, reason in comments.
}
template <class RecordType>
inline bool table<RecordType>::never_used(std::size_t index) const
{
return (data[index].key == NEVER_USED);
}
template <class RecordType>
inline bool table<RecordType>::is_vacant(std::size_t index) const
{
return (data[index].key == NEVER_USED) || (data[index].key == PREVIOUSLY_USED);
}
我希望我能得到一些帮助的问题是，我将如何跟踪为查找表中的每个值而进行的比较次数？
到目前为止，我尝试创建一个私有成员变量并通过 find_index 循环为每次迭代增加它，但这不起作用。我的总体目标是最终绘制平均比较次数 Vs。表密度。