Hash线性探测法C++实现
#include <iostream> #include <iomanip> #define DefaultSize 10 using namespace std; enum KindOfStatus{Active,Empty,Deleted}; template<typename T> class HashTable { public: HashTable(int d,int sz=DefaultSize) { _D = d; TableSize=sz; CurrentSize=0; _A = new T[TableSize]; info = new KindOfStatus[TableSize]; for(int _I=0;_I<TableSize;_I++) { info[_I]=Empty; } } HashTable(const HashTable& ht) { _D=ht._D; TableSize=ht.TableSize; CurrentSize=ht.CurrentSize; _A=new T[TableSize]; info = new KindOfStatus[TableSize]; for(int _I=0;_I<TableSize;_I++) { info[_I]=ht.info[_I]; _A[_I] = ht._A[_I]; } } HashTable& operator=(const HashTable& ht) { if(this!=&ht) { if(_A!=NULL && info!=NULL) { delete []_A; delete []info; _D=ht._D; TableSize=ht.TableSize; CurrentSize=ht.CurrentSize; _A=new T[TableSize]; info = new KindOfStatus[TableSize]; for(int _I=0;_I<TableSize;_I++) { info[_I]=ht.info[_I]; _A[_I] = ht._A[_I]; } } } } bool operator!=(const HashTable& ht) { if(_D!=ht._D || TableSize!=ht.TableSize || CurrentSize!=ht.CurrentSize) { return false; } for(int _I=0;_I<TableSize;_I++) { if(info[_I]!=ht.info[_I] || _A[_I]!=ht._A[_I]) return false; } return true; } int Hash(int x) { int dex = x%_D; int _I=dex; if(info[_I]==Empty || info[_I]==Deleted) return _I; do { if(info[_I]==Active && _A[_I]!=x) _I=(_I+1)%TableSize; if(info[_I]==Empty || (info[_I]==Active && _A[_I]==x) || info[_I]==Deleted) return _I; }while(_I!=dex); return _I; } int FindPos(int x) { int dex = x%_D; int _I=dex; do { if(info[_I]==Active && _A[_I]==x) { #ifdef _YES cout<<"找到该元素，它的位置是:"<<(_I)%TableSize+1<<endl; #endif return _I; } _I=(_I+1)%TableSize; }while(dex!=_I); if(dex==_I) {cout<<"没有找到该元素"<<endl;return -1;}; } void Insert(int x) { int dex=Hash(x); if(info[dex]==Active && _A[dex]==x) {cout<<"已经存在的值，不能插入!!"<<endl;return ;} if(info[dex]==Active && dex==(x%TableSize)) {cout<<"表满!!"<<endl;return ;} if(info[dex]==Empty || info[dex]==Deleted) _A[dex] = x; info[dex]=Active; CurrentSize++; } ~HashTable() { delete []_A; delete []info; for(int _I=0;_I<TableSize;_I++) { info[_I]=Empty; } } void Show() { cout<<"状态:"; for(int _I=0;_I<TableSize;_I++) { cout<<setw(4)<<info[_I]; } cout<<endl; cout<<"内容:"; for(int _J=0;_J<TableSize;_J++) { cout<<setw(4)<<_A[_J]; } cout<<endl; } void Remove(int x) { int dex = FindPos(x)-1; info[dex]=Deleted; _A[dex]=0; } private: int _D; int CurrentSize; int TableSize; KindOfStatus *info; T *_A; }; int main() { HashTable<int> ht(7,10); ht.Insert(1); ht.Insert(8); ht.Insert(15); ht.Insert(22); ht.Insert(29); ht.Insert(36); ht.Insert(43); ht.Insert(50); ht.Insert(57); ht.Insert(64); HashTable<int> hz(ht); hz.Remove(8); hz.Show(); return 0; }