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