C++實現(xiàn)哈希表的實例

C++ 實現(xiàn)哈希表的實例

創(chuàng)新互聯(lián)是一家以成都網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計、品牌設(shè)計、軟件運維、成都網(wǎng)站推廣、小程序App開發(fā)等移動開發(fā)為一體互聯(lián)網(wǎng)公司。已累計為成都濕噴機(jī)等眾行業(yè)中小客戶提供優(yōu)質(zhì)的互聯(lián)網(wǎng)建站和軟件開發(fā)服務(wù)。

該散列表的散列函數(shù)采用了除法散列函數(shù)、乘法散列函數(shù)、全域散列函數(shù)，每一個槽都是使用有序單向鏈表實現(xiàn)。

實現(xiàn)代碼：

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++實現(xiàn)哈希表的實例，如有疑問請留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

分享標(biāo)題：C++實現(xiàn)哈希表的實例
網(wǎng)頁URL：http://bm7419.com/article20/gochjo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、電子商務(wù)、App設(shè)計、網(wǎng)站設(shè)計、域名注冊、手機(jī)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都app開發(fā)公司