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