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;  
}  </pre>