溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
C++ 實現(xiàn)哈希表的實例
該散列表的散列函數(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ū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內(nèi)容。
