C++ 实现哈希表的实例
C++实现哈希表的实例
该散列表的散列函数采用了除法散列函数、乘法散列函数、全域散列函数，每一个槽都是使用有序单向链表实现。
实现代码：
LinkNode.h
#includeusingnamespacestd; classLink; classLinkNode { private: intkey; LinkNode*next; friendLink; public: LinkNode():key(-1),next(NULL){} LinkNode(intnum):key(num),next(NULL){} intGetkey() { returnkey; } };
Link.h
#include"LinkNode.h"
classHash;
classLink
{
private:
friendHash;
LinkNode*head;
intlength;
public:
Link():head(NULL),length(0)
{}
Link(LinkNode*node):head(node)
{
length+=1;
}
~Link()
{
MakeEmpty();
}
voidMakeEmpty()
{
if(head==NULL)
return;
LinkNode*p=head;
while(p)
{
head=head->next;
deletep;
p=head;
}
}
intGetLength()
{
returnlength;
}
voidInsert(intnum)
{
length++;
LinkNode*p=newLinkNode(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;
}
boolDelete(intnum)
{
if(head==NULL)
{
cout<<"thelinkisempty!"<next;
if(p->key==num)
{
head=head->next;
deletep;
length--;
return1;
}
while(t)
{
if(t->key==num)
{
p->next=t->next;
deletet;
length--;
return1;
}
elseif(t->keynext;
}
}
return0;
}
intSearch(intnum)
{
LinkNode*p=head;
while(p)
{
if(p->key==num)
{
returnnum;
}
elseif(p->keynext;
}
else
{
return0;
}
}
return0;
}
boolIsEmpty()
{
if(head==NULL)
{
return1;
}
else
return0;
}
voidPrint(intnum)
{
if(head==NULL)
{
cout<<"the"<key<<"";
p=p->next;
}
cout<
Hash.h
Hash表中每一个元素存储一个链表
#include"Link.h"
classHash
{
private:
Link*Table;
public:
Hash(intnum):Table(newLink[num]){}
~Hash()
{
delete[]Table;
}
//除法散列法
intH1(intnum,intm)
{
returnnum%m;
}
//乘法散列法
intH2(intnum,floatA,intm)
{
floatfnum=(float)num;
floatre=((fnum*A)-(int)(fnum*A))*m;
return(int)re;
}
//全域散列
intH3(intnum,intp,intm)
{
inta,b;
a=rand()%p;
b=rand()%p;
return((a*num+b)%p)%m;
}
voidInsert(intnum,intn)
{
intkey;
if(n==1)
{
key=H1(num,17);
}
elseif(n==2)
{
key=H2(num,0.618033,17);
}
else
{
key=H3(num,701,17);
}
Table[key].Insert(num);
}
boolDelete(intnum,intn)
{
intkey;
if(n==1)
{
key=H1(num,17);
}
elseif(n==2)
{
key=H2(num,0.618033,17);
}
else
{
key=H3(num,701,17);
}
returnTable[key].Delete(num);
}
intSearch(intnum,intn)
{
intkey;
if(n==1)
{
key=H1(num,17);
}
elseif(n==2)
{
key=H2(num,0.618033,17);
}
else
{
key=H3(num,701,17);
}
if(Table[key].Search(num)!=0)
{
returnkey+1;
}
else
return-1;
}
voidPrint(intnum)
{
inti;
for(i=0;i
main.h
#include"Hash.h"
intmain()
{
Hashhash(1000),ha(100),sh(100);
inta[15]={15,6,9,4,7,32,569,419,78,125,635,46,456,16,457};
inti;
for(i=0;i<15;i++)
{
hash.Insert(a[i],1);
}
for(i=0;i<15;i++)
{
ha.Insert(a[i],2);
}
cout<
以上就是C++实现哈希表的实例，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！