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