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->key next; } } return0; } intSearch(intnum) { LinkNode*p=head; while(p) { if(p->key==num) { returnnum; } elseif(p->key next; } 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;imain.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++实现哈希表的实例,如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!