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 T> class DynamicSet { public: virtual ResultCode Search(T &x) = 0; virtual ResultCode Insert(T &x) = 0; virtual ResultCode Remove(T &x) = 0; /* data */ }; template <class T> class HashTable: public DynamicSet<T> { 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 <class T> void HashTable<T>::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 <class T> T HashTable<T>::h(T x) { return x % 11; } template <class T> HashTable<T>::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 <class T> ResultCode HashTable<T>::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 <class T> ResultCode HashTable<T>::Search(T &x) { int pos; if(Find(x, pos) == Success) return Success; return NotPresent; } template <class T> ResultCode HashTable<T>::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 <class T> ResultCode HashTable<T>::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<int> 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; } ~~~