二次探測再散列散清單 源代碼（資料結構）

二次探測再散列 

/**********散清單**********/
#ifndef HashTable_
#define HashTable_
 
#include "Except.h"
 
template <class E,class K>
class HashTable
{
public:
HashTable(int divisor = 11);
~HashTable(){delete [] ht;delete []empty;}
bool Search(const K& k,E& e);
HashTable<E,K>& Insert(const E& e);
HashTable<E,K>& Delete(const K& k,E& e);
void Output() const;
private:
int hSearch(const K& k)const;
int D;//散列函數的除數
E* ht;//散列數組
bool *empty;//一維數組
 
};
 
template <class E,class K>
HashTable<E,K> ::HashTable(int divisor)
{
//構造函數
D = divisor;
//配置設定散列數組
ht = new E[D];
empty = new bool[D];
 
//将所有空桶置零
for(int i = 0;i < D;i++)
{
empty[i] = true;
}
}
template<class E,class K>
int HashTable<E,K>::hSearch(const K& k) const
{
   int i = k % D; // 起始桶
   int j = i;// 在起始桶處開始
   int n = 1,count=0;
   do {
if (empty[j] || ht[j] == k)
  return j;
  if( count  == 0)
  {
  j = (i + n*n) % D;
  count = 1;
  }
  else
  {
j = ((i - n*n) % D + D) % D; 
count = 0;
n++;
  }
} while (j !=i); // 傳回起始桶
  return j;  // 表已滿
}
 
template<class E, class K>
bool HashTable<E,K>::Search(const K& k, E& e) 
{ 
 
int b = hSearch(k);
if(empty[b] || ht[b] != k) 
return false;
e = ht[b];
return true;
}
 
template<class E, class K>
HashTable<E,K>& HashTable<E,K>::Insert(const E& e)
{
 
K k = e; 
int b = hSearch(k);
 
if(empty[b] )
{
empty[b] = false;
ht[b] = e;
return *this;
}
  
if(ht[b] == k) 
throw BadInput(); 
throw NoMem(); 
return *this;  
}
 
template<class E, class K>
HashTable<E,K>& HashTable<E,K>::Delete(const K& k,E& e)
{
 
int b = hSearch(k);
 
if(empty[b] || ht[b] != k)
throw OutOfBounds();
 
e = ht[b];
empty[b] = true;
 
return *this;  
}
template<class E, class K>
void HashTable<E,K>::Output() const
{
   for (int i = 0; i < D; i++) 
   if(empty[i])
   cout << "NULL" << " ";
   else
   cout  << ht[i] << " ";
}
 
 
#endif
 
//------------------------------------------
//.cpp
#include <iostream>
using namespace std;
#include "HashTable.h"
 
class element 
{
   friend int main();
   public:
        operator long() const {return key;}
 
/*bool operator < (const element other) const{
return (this->key < other.key);//translator element < element to K <K
}
bool operator == (const element other) const{
return (this->key == other.key);
}
bool operator < (const K other) const{
return (this->key < other);//translator elment < K to K < K
}
bool operator == (const K other) const{
return (this->key == other);
}
bool operator != (const K other) const{
return (this->key != other);
}
int operator % (int other) const{//support ht[e % P], P is int
return (this->key % other);
}*/
 
        element& operator =(long y)
         {key = y; return *this;}
   private:
      int data;
      long key;
};
 
HashTable<element, int> h(11);
element e;
 
int main()
{
e.key = 19;
h.Insert(e);
e.key = 01;
h.Insert(e);
e.key = 23;
h.Insert(e);
e.key = 14;
h.Insert(e);
e.key = 55;
h.Insert(e);
e.key = 68;
h.Insert(e);
e.key = 11;
h.Insert(e);
e.key = 82;
h.Insert(e);
e.key = 36;
h.Insert(e);
e.key = 12;
h.Insert(e);
 
h.Output();
cout << endl;
 
element x;
cout<<"查找元素:"<<endl;
if(h.Search(1,x))
cout<< "位置："<< x <<endl;
else
cout<<"元素不存在。"<< endl;
 
cout << endl;
e.key = 34;
cout<<"插入："<<endl;
h.Insert(e);
h.Output();
cout<<endl;
 
 return 0;