散列表ADT_HashTable
最后更新于：2022-04-01 20:51:48
M为除留余数法的模数, ht是指向动态生成的一维数组指针, empty是标志数组的指针.
成员函数Find()在散列表中搜索与x关键字相同的元素. 若表中存在与x关键字值相同的元素, 则将其复制给x, pos指示该位置, 函数返回Success. 若表已满, 函数返回Overflow. 若表未满, 函数返回NotPresent, pos指示首次遇到的空值位置.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int NeverUsed = -100;
enum ResultCode { Underflow, Overflow, Success, Duplicate, NotPresent };
template
class DynamicSet
{
public:
virtual ResultCode Search(T &x) = 0;
virtual ResultCode Insert(T &x) = 0;
virtual ResultCode Remove(T &x) = 0;
/* data */
};
template
class HashTable: public DynamicSet
{
public:
HashTable(int divisor = 11);
~HashTable() {
delete []ht;
delete []empty;
}
ResultCode Search(T &x);
ResultCode Insert(T &x);
ResultCode Remove(T &x);
void Output();
/* data */
private:
ResultCode Find(T &x, int &pos);
T h(T x);
int M;
T *ht;
bool *empty;
};
template
void HashTable::Output()
{
for(int i = 0; i < M; ++i)
cout << i << ' ';
cout << endl;
for(int i = 0; i < M; ++i)
if(ht[i] == NeverUsed) cout << "NU" << ' ';
else cout << ht[i] << ' ';
cout << endl;
for(int i = 0; i < M; ++i)
if(empty[i]) cout << "T " << ' ';
else cout << "F " << ' ';
cout << endl;
}
template
T HashTable::h(T x)
{
return x % 11;
}
template
HashTable::HashTable(int divisor)
{
M = divisor;
ht = new T[M];
empty = new bool[M];
for(int i = 0; i < M; ++i)
empty[i] = true;
for(int i = 0; i < M; ++i)
ht[i] = NeverUsed;
}
template
ResultCode HashTable::Find(T &x, int &pos)
{
pos = h(x); // h为散列函数, h(x) < M
int i = pos, j = -1;
do{
if(ht[pos] == NeverUsed && j == -1) j = pos; // 记录首次遇到空值的位置
if(empty[pos]) break; // 表中没有与x有相同关键字的元素
if(ht[pos] == x) { // ht[pos]的关键字与值与x的关键字值相同
x = ht[pos];
return Success; // 搜索成功, ht[pos]赋值给x
}
pos = (pos + 1) % M;
}while(pos != i); // 已搜索完整个散列表
if(j == -1) return Overflow; // 表已满
pos = j; // 记录首次遇到的空值位置
return NotPresent;
}
template
ResultCode HashTable::Search(T &x)
{
int pos;
if(Find(x, pos) == Success) return Success;
return NotPresent;
}
template
ResultCode HashTable::Insert(T &x)
{
int pos;
ResultCode reslt = Find(x, pos);
if(reslt == NotPresent) {
ht[pos] = x;
empty[pos] = false;
return Success;
}
if(reslt == Success) return Duplicate;
return Overflow;
}
template
ResultCode HashTable::Remove(T &x)
{
int pos;
if(Find(x, pos) == Success) {
ht[pos] = NeverUsed;
return Success;
}
return NotPresent;
}
int main(int argc, char const *argv[])
{
HashTable ht;
int x = 80; ht.Insert(x); ht.Output();
x = 80; ht.Insert(x); ht.Output();
x = 40; ht.Insert(x); ht.Output();
x = 65; ht.Insert(x); ht.Output();
x = 28; ht.Insert(x); ht.Output();
x = 24; ht.Insert(x); ht.Output();
x = 35; ht.Insert(x); ht.Output();
x = 58; ht.Insert(x); ht.Output();
return 0;
}
~~~
';