算法导论第十一章习题11.2-4
该算法是在上一篇文章的基础上进行改进而得到的，跟上一篇比较，本代码添加了head头文件,Head即为散列表中的每一个槽，该槽包含执行上一个空槽的pre节点，指向下一个空槽的next节点，指向链表Link的table节点和指示该槽是否为空的标志位flag，flag为1时表示槽位有元素，否则为空。
Hash头文件较上一篇文章，较大的改进是Insert函数和Delete函数，主要是添加了如何将刚刚空出来的空槽位添加到空槽位链表，以及如何将刚刚填充入元素 的空槽位从链表中删除。其具体代码如下：
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 Head;class Link{private:friend Head;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;}elsereturn 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;}};
head.h
#include<iostream>using namespace std;class Hash;class Head{private:friend Hash;Link* table;Head* pre;Head* next;int flag;public:Head():table(new Link()),pre(NULL),next(next),flag(0){}Head(Link* node1,Head* node2,Head* node3):table(node1),pre(node2),next(node3),flag(1){}~Head(){delete table;pre=NULL;next=NULL;}Head* GetNext(){return this->next;}Head* GetPre(){return this->pre;}Link* GetTable(){return this->table;}bool IsEmpty(){return this->table->IsEmpty();}void Insert(int num){this->table->Insert(num);flag=1;}bool Delete(int num){flag=0;return this->table->Delete(num);}};
Hash.h
#include"Link.h"#include"head.h"class Hash{private:Head*head;int length;//Link*Table;public:Hash(int num):head(new Head [num]),length(num){int i;head[0].pre=head[num-1].next=NULL;for(i=1;i<num;i++){head[i-1].next=&head[i];head[i].pre=&head[i-1];}}~Hash(){delete [] head;}//除法散列法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);}//如果该节点为空if(head[key].flag==0){//将该节点从空链表上删除if(head[key].pre==NULL){if(head[key].next!=NULL){head[key].next->pre=NULL;head[key].next=NULL;}}else{if(head[key].next==NULL){head[key].pre->next=NULL;head[key].pre=NULL;}else{head[key].pre->next=head[key].next;head[key].next->pre=head[key].pre;}}}head[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);}bool f=head[key].Delete(num);//如果该节点的table为空，则将该节点连接到空链上if(head[key].table->IsEmpty()){int i=key-1,j=key+1;bool flagi=1,flagj=1,flag1=0,flag2=0;while(1){if(i<0){head[key].pre=NULL;flagi=0;flag1=1;}if(j>=length){head[key].next=NULL;flagj=0;flag2=1;}if(flagi&&!head[i].IsEmpty()){i--;}else{if(flagi&&head[i].IsEmpty()){head[key].pre=&head[i];head[i].next=&head[key];flag1=1;}}if(flagj&&!head[i].IsEmpty()){j++;}else{if(flagi&&head[i].IsEmpty()){head[key].next=&head[i];head[i].pre=&head[key];flag2=1;}}if(flag1&&flag2){break;}}}return f;}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(head[key].table->Search(num)!=0){return key+1;}elsereturn -1;}void Print(int num){int i;for(i=0;i<num;i++){if(head[i].IsEmpty())continue;head[i].table->Print(i);}}};
test.cpp
#include"Hash.h"int main(){Hash hash(100),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(100);cout<<endl;ha.Print(100);cout<<endl;sh.Print(100);cout<<endl;cout<<hash.Search(46,1)<<endl;if(hash.Delete(4,1)){cout<<hash.Search(4,1)<<endl;}}