C++实现哈希表的实例

C++ 实现哈希表的实例

创新互联是一家以成都网站建设、网页设计、品牌设计、软件运维、成都网站推广、小程序App开发等移动开发为一体互联网公司。已累计为成都湿喷机等众行业中小客户提供优质的互联网建站和软件开发服务。

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

实现代码：

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++实现哈希表的实例，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

标题名称：C++实现哈希表的实例
网页链接：http://scyanting.com/article/gochjo.html

C++实现哈希表的实例

其他资讯