hash1.cpp

数据结构 基本查找算法之哈希查找 散列 使用c++语言

#include<iostream>
#include<iomanip>
using namespace std;
typedef struct{
	char *na;
	int count;
}nam;
typedef struct{
	char *na;
	int count;
	int find;
	//int xuhao;//位置序号
}has;
void inithash(nam name[],has hash[])
{   
	char *temp;
	int i,j,k;
   name[0].na="chenyong#";
   name[1].na="huting#";
   name[2].na="chenguan#";
   name[3].na="baojie#";
   name[4].na="chenglan#";
   name[5].na="gaoyang#";
   name[6].na="caohao#";
   name[7].na="lvyi#" ;
   name[8].na="lijue#";
   name[9].na="linfujun#";
   name[10].na="lidaohui#";
   name[11].na="xiaohua#";
   name[12].na="haha#";
   name[13].na="qingde#";
   name[14].na="zejun#";
   name[15].na="zhongende#";
   name[16].na="luobin#";
   name[17].na="zhixiang#";
   name[18].na="chenyao#";
   name[18].na="xushufen#";
   name[19].na="weixing#";
   name[20].na="xuxi#";
   name[21].na="liuyu#";
   name[22].na="fish#";
   name[23].na="zhangxiao#";
   name[24].na="liyuan#";
   name[25].na="zongguan#";
   name[26].na="tianye#";
   name[27].na="liutian#";
   name[28].na="xushuya#";
   name[29].na="meijia#";
   for(j=0;j<30;j++)
   {
       temp=name[j].na;
	   k=0;
	   for(i=0;*(temp+i)!='#';i++)
	   {
		   k+=*(temp+i);//字符之和
	   }
       name[j].count=k;
   }
 }
int creathash(nam name[],has hash[])
{  int po;
   for(int i=0;i<60;i++)//初始化hash表
   {
       hash[i].na="";
	   hash[i].count=0;
	   hash[i].find=0;
   }
   double m=0;
   for(i=0;i<30;i++)
   {   
       int sum=0;
	   int n=(name[i].count)%59;
	   po=n;
	   if(hash[n].find==0)
	   {
		   hash[n].na=name[i].na;
		   hash[n].count=name[i].count;
		   hash[n].find=1;
	   }
	   else
	   {   
		   do
		   {
              n=(n+7)%59;//伪随机数生成
			  sum++;
		   }while(hash[n].find!=0);
           hash[n].na=name[i].na;
		   hash[n].count=name[i].count;
		   hash[n].find=sum+1;
	   }
   }
   for(i=0;i<60;i++)
   {   
	   
	   cout<<"位置"<<i<<setw(10)<<"关键字"<<hash[i].count<<setw(20)<<"姓名  "<<hash[i].na<<endl;
   }
   for(i=0;i<60;i++)
   {
	   m+=hash[i].find;
   }
   cout<<"平均查找长度  "<<m/30.0<<endl;
}
int find(nam name[],has hash[])
{
    cout<<"请输入要找的人的姓名并以#号结束"<<endl;
	char fin[20];
	cin>>fin;
	char *p;int n=0,m=0;
	p=fin;
	for(int i=0;*(p+i)!='#';i++)
	{
        n+=*(p+i);
	}
	n=n%59;
	while(!strcmp(hash[n].na,fin)==0)
	{   
		n=(n+7)%59;
		m++;
		if(m==31)break;
	}
	if(m==31)cout<<"没有此项记录"<<endl;
	else
    cout<<"位置"<<n<<setw(10)<<"关键字"<<hash[n].count<<setw(20)<<"姓名  "<<hash[n].na<<endl;
}
int main(){
	nam name[30];
	has hash[60];
	char ad;
	inithash(name,hash);
	cout<<"输入 D--显示哈希表  F--查找  E--结束程序"<<endl;
	while(cin>>ad&&ad!='E')
	{   
		
		if(ad=='D')
			creathash(name,hash);
		if(ad=='F') find(name,hash);
	}
	cout<<"程序结束，谢谢使用"<<endl;
	return 0;
}