C++ 实现哈希表的实例

C++ 实现哈希表的实例

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

实现代码：

linkNode.h

#include 
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!"<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->keynext; 
      } 
    } 
    return 0; 
  } 
  int Search(int num) 
  { 
    linkNode* p=head; 
    while(p) 
    { 
      if(p->key==num) 
      { 
 return num; 
      } 
      else if(p->keynext; 
      } 
      else 
      { 
 return 0; 
      } 
    } 
    return 0; 
  } 
  bool IsEmpty() 
  { 
    if(head==NULL) 
    { 
      return 1; 
    } 
    else 
      return 0; 
  } 
  void Print(int num) 
  { 
    if(head==NULL) 
    { 
      cout<<"the"<key<<" "; 
      p=p->next; 
    } 
    cout<

 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

 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<

以上就是C++实现哈希表的实例，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！