#include<iostream.h>
#include<iomanip.h>
#define M 11
#define N 8
struct hterm
{
	int key; //關(guān)鍵字值
	int si;  //散列次數(shù)
};
struct hterm hlist[M];
int  i,adr,sum,d;
int x[N]={22,41,53,46,30,13,1,67};//關(guān)鍵字賦值
float average;
void chash()//創(chuàng)建哈希表
{
	for(i=0;i<M;i++)  //置初值
	{
		hlist[i].key=0;
		hlist[i].si=0;
	}
	for(i=0;i<M;i++)
	{
		sum=0;
		adr=(3*x[i])%M ; //哈希函數(shù)
		d=adr;
		if(hlist[adr].key==0)
		{
			hlist[adr].key=x[i];
			hlist[adr].si=1;
		}
		else
		{
			do   //采用“開放地址法”處理沖突 
			{
				d=(d+(x[i]*7)%10+1)%M;
				sum=sum+1;
			}while(hlist[d].key!=0);
			hlist[d].key=x[i];
			hlist[d].si=sum+1;
		}
	}
}
void dhash() //輸出哈希表
{
	cout<<"哈希表的地址 ";
	for(i=0;i<M;i++)
	  cout<<setw(4)<<i;
	cout<<endl;
	cout<<"哈希表關(guān)鍵字：";
	for(i=0;i<M;i++)
		cout<<setw(4)<<hlist[i].key;
	cout<<endl;
	cout<<"搜索長度：";
	for(i=0;i<M;i++)
		cout<<setw(4)<<hlist[i].si;
	cout<<endl;
	for(i=0;i<M;i++)
		average=average+hlist[i].si;
	average=average/N;
	cout<<"平均搜索長度:ASL("<< N <<")="<<average<<endl;
}
void main()
{
	chash();
	dhash();
}