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

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。