C++ 实现哈希表的实例

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

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

# C++ # 实现哈希表 # 哈希表的实现实例 # 详解哈希表 # C++数据结构哈希表详解 # C++深入探究哈希表如何封装出unordered_set和unordered_map # C++哈希表之线性探测法实现详解 # C++中使用哈希表(unordered_map)的一些常用操作方法 # C++基础算法基于哈希表的索引堆变形 # C++ 哈希表的基本用法及说明 # 都是 # 链表 # 如有 # 希望能 # 采用了 # 谢谢大家 # 疑问请 # num # nbsp # return # Getkey # friend # key # NULL # public # Hash # delete # void # Insert # GetLength

返回目录在线咨询

上一篇：如何使用社交媒体来提升SEO_SEO优化教程
下一篇：SEO中如何处理图像的Alt标签_SEO优化教程

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

C++ 实现哈希表的实例

您的项目需求