算法导论第十一章散列表的兑现（哈希表的实现）

算法导论第十一章散列表的实现（哈希表的实现）

该散列表的散列函数采用了除法散列函数、乘法散列函数、全域散列函数，每一个槽都是使用有序单向链表实现。

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;
	}
}