C++ 实现哈希表的实例分享

—-想了解C++ 实现哈希表的实例分享的全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>

C++ 实现哈希表的实例

该散列表的散列函数采用了除法散列函数、乘法散列函数、全域散列函数，每一个槽都是使用有序单向链表实现。

实现代码：

LinkNode.h

      #include<iostream>   using namespace std;   class Link;   class LinkNode   {   private:     int key;     LinkNode* next;     friend Link;   public:     LinkNode():key(-1),next(NULL){}     LinkNode(int num):key(num),next(NULL){}     int Getkey()     {       return key;     }      };     

 Link.h

  #include"LinkNode.h"   class Hash;   class Link   {   private:     friend Hash;     LinkNode* head;     int length;   public:     Link():head(NULL),length(0)     {}     Link(LinkNode* node):head(node)     {       length+=1;     }     ~Link()     {       MakeEmpty();     }     void MakeEmpty()     {       if(head==NULL)         return ;       LinkNode* p=head;       while(p)       {         head=head->next;         delete p;         p=head;       }     }     int GetLength()     {       return length;     }     void Insert(int num)     {       length++;       LinkNode* p=new LinkNode(num);       if(head==NULL)       {         head=p;         return ;       }       LinkNode* q=head,*t=head->next;       if(q->key>num)       {         head=p;         head->next=q;         return ;       }       while(t)       {         if(t->key>=num)         {           q->next=p;           p->next=t;           return ;         }         else         {           q=t;           t=t->next;         }       }       q->next=p;     }     bool Delete(int num)     {       if(head==NULL)       {         cout<<"the link is empty!"<<endl;         return 0;       }       LinkNode* p=head,*t=head->next;       if(p->key==num)       {         head=head->next;         delete p;         length--;         return 1;       }       while(t)       {         if(t->key==num)         {           p->next=t->next;           delete t;           length--;           return 1;         }         else if(t->key<num)         {           p=t;           t=t->next;         }       }       return 0;     }     int Search(int num)     {       LinkNode* p=head;       while(p)       {         if(p->key==num)         {           return num;         }         else if(p->key<num)         {           p=p->next;         }         else         {           return 0;         }       }       return 0;     }     bool IsEmpty()     {       if(head==NULL)       {         return 1;       }       else         return 0;     }     void Print(int num)     {       if(head==NULL)       {         cout<<"the"<<num<<"th link is null!"<<endl;       }       LinkNode* p=head;       while(p)       {         cout<<p->key<<" ";         p=p->next;       }       cout<<endl;     }   };     

 Hash.h

Hash表中每一个元素存储一个链表

  #include"Link.h"   class Hash   {   private:     Link*Table;   public:     Hash(int num):Table(new Link [num]){}     ~Hash()     {       delete [] Table;     }     //除法散列法     int H1(int num,int m)     {       return num%m;     }     //乘法散列法     int H2(int num,float A,int m)     {       float fnum=(float)num;       float re=((fnum*A)-(int)(fnum*A))*m;       return (int)re;     }     //全域散列     int H3(int num,int p,int m)     {       int a,b;       a=rand()%p;       b=rand()%p;       return ((a*num+b)%p)%m;     }     void Insert(int num,int n)     {       int key;              if(n==1)       {         key=H1(num,17);       }       else if(n==2)       {         key=H2(num,0.618033,17);       }       else       {         key=H3(num,701,17);       }       Table[key].Insert(num);     }     bool Delete(int num,int n)     {       int key;         if(n==1)       {         key=H1(num,17);       }       else if(n==2)       {         key=H2(num,0.618033,17);       }       else       {         key=H3(num,701,17);       }       return Table[key].Delete(num);     }     int Search(int num,int n)     {       int key;              if(n==1)       {         key=H1(num,17);       }       else if(n==2)       {         key=H2(num,0.618033,17);       }       else       {         key=H3(num,701,17);       }         if(Table[key].Search(num)!=0)         {           return key+1;         }         else           return -1;     }     void Print(int num)     {       int i;       for(i=0;i<num;i++)       {         if(Table[i].IsEmpty())           continue;         Table[i].Print(i);       }     }   };     

 main.h

  #include"Hash.h"   int main()   {     Hash hash(1000),ha(100),sh(100);     int a[15]={15,6,9,4,7,32,569,419,78,125,635,46,456,16,457};     int i;     for(i=0;i<15;i++)     {       hash.Insert(a[i],1);     }          for(i=0;i<15;i++)     {       ha.Insert(a[i],2);     }     cout<<endl;     for(i=0;i<15;i++)     {       sh.Insert(a[i],3);     }     hash.Print(1000);     cout<<endl;     ha.Print(100);     cout<<endl;     sh.Print(100);     cout<<endl;     cout<<hash.Search(46,1)<<endl;     if(hash.Delete(125,1))     {       cout<<hash.Search(125,1)<<endl;     }   }       

• 1
• 2
• 下一页