哈希表-算法-hash表-C++实现

哈希表算法hash表问题描述：针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。#includestdio.h#includemalloc.h#includestring.h//#include#defineHASH_LEN50//哈希表的长度#defineM47#defineNAME_NO30//人名的个数typedefstructNAME{char*py;//名字的拼音intk;//拼音所对应的整数}NAME;NAMENameList[HASH_LEN];typedefstructhterm//哈希表{char*py;//名字的拼音intk;//拼音所对应的整数intsi;//查找长度}HASH;HASHHashList[HASH_LEN];/*-----------------------姓名（结构体数组）初始化---------------------------------*/voidInitNameList(){NameList[0].py=zhanghongshuai;NameList[1].py=xurensong;NameList[2].py=huangxiangyu;NameList[3].py=luoqi;NameList[4].py=zhangsan;NameList[5].py=lisi;NameList[6].py=wangwu;NameList[7].py=renwei;NameList[8].py=zhangchu;NameList[9].py=wangmengyuan;NameList[10].py=libaohua;NameList[11].py=zhaoyanlong;NameList[12].py=jwangyuxin;NameList[13].py=duyanmo;NameList[14].py=wangmingyang;NameList[15].py=lijiawei;NameList[16].py=hesiyu;NameList[17].py=zhanghailong;NameList[18].py=lixinyu;NameList[19].py=songdiyao;NameList[20].py=zhaomingzhi;NameList[21].py=zhangchenglong;NameList[22].py=sunjie;NameList[23].py=zhangdongmei;NameList[24].py=antianyu;NameList[25].py=zhulaiao;NameList[26].py=wangyuting;NameList[27].py=wangxiliang;NameList[28].py=zhangdeshuai;NameList[29].py=xumingming;char*f;intr,s0;for(inti=0;iNAME_NO;i++)//求出各个姓名的拼音所对应的整数{s0=0;f=NameList[i].py;for(r=0;*(f+r)!='\0';r++)//方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字s0=*(f+r)+s0;NameList[i].k=s0;}}/*-----------------------建立哈希表---------------------------------*/voidCreateHashList(){for(inti=0;iHASH_LEN;i++)//哈希表的初始化{HashList[i].py=;HashList[i].k=0;HashList[i].si=0;}for(inti=0;i=NAME_NO;){intsum=0;intadr=(NameList[i].k)%M;//哈希函数intd=adr;if(HashList[adr].si==0)//如果不冲突{HashList[adr].k=NameList[i].k;HashList[adr].py=NameList[i].py;HashList[adr].si=1;}else//冲突{do{d=(d+((NameList[i].k))%10+1)%M;//伪散列sum=sum+1;//查找次数加1}while(HashList[d].k!=0);HashList[d].k=NameList[i].k;HashList[d].py=NameList[i].py;HashList[d].si=sum+1;}i++;}}/*-------------------------------------查找------------------------------------*/voidFindList(){printf(\n\n请输入姓名的拼音:);//输入姓名charname[20]={0};scanf(%s,name);ints0=0;for(intr=0;r20;r++)//求出姓名的拼音所对应的整数(关键字)s0+=name[r];intsum=1;intadr=s0%M;//使用哈希函数intd=adr;if(HashList[adr].k==s0)//分3种情况进行判断printf(\n姓名:%s关键字:%d查找长度为:1,HashList[d].py,s0);elseif(HashList[adr].k==0)printf(无该记录!);else{intg=0;do{d=(d+s0%10+1)%M;//伪散列sum=sum+1;if(HashList[d].k==0){printf(无记录!);g=1;}if(HashList[d].k==s0){printf(\n姓名:%s关键字:%d查找长度为:%d,HashList[d].py,s0,sum);g=1;}}while(g==0);}}/*--------------------------------显示哈希表----------------------------*/voidDisplay(){printf(\n\n地址\t关键字\t\t搜索长度\tH(key)\t\t拼音\n);//显示的格式for(inti=0;i15;i++){printf(%d,i);printf(\t%d,HashList[i].k);printf(\t\t%d,HashList[i].si);printf(\t\t%d,(HashList[i].k)%M);printf(\t%s,HashList[i].py);printf(\n);}//printf(按任意键继续显示...\n);//由于数据比较多，所以分屏显示（以便在Win9x／DOS下能看到所有的数据）//getch();for(inti=15;i30;i++){printf(%d,i);printf(\t%d,HashList[i].k);printf(\t\t%d,HashList[i].si);printf(\t\t%d,(HashList[i].k)%M);printf(\t%s,HashList[i].py);printf(\n);}//printf(按任意键继续显示...\n);//getch();for(inti=30;i40;i++){printf(%d,i);printf(\t%d,HashList[i].k);printf(\t\t%d,HashList[i].si);printf(\t\t%d,(HashList[i].k)%M);printf(\t%s,HashList[i].py);printf(\n);}//printf(按任意键继续显示...\n);//getch();for(inti=40;i50;i++){printf(%d,i);printf(\t%d,HashList[i].k);printf(\t\t%d,HashList[i].si);printf(\t\t%d,(HashList[i].k)%M);printf(\t%s,HashList[i].py);printf(\n);}floataverage=0;for(inti=0;iHASH_LEN;i++)average+=HashList[i].si;average/=NAME_NO;printf(\n\n平均查找长度：ASL(%d)=%f\n\n,NAME_NO,average);}/*--------------------------------主函数----------------------------*/main(){/*::SetConsoleTitle(哈希表操作);//WindowsAPI函数,设置控制台窗口的标题HANDLEhCon=::GetStdHandle(STD_OUTPUT_HANDLE);//获得标准输出设备的句柄::SetConsoleTextAttribute(hCon,10|0);//设置文本颜色*/printf(\n------------------------哈希表的建立和查找----------------------);InitNameList();CreateHashList();while(1){printf(\n\n);printf(1.显示哈希表\n);printf(2.查找\n);printf(3.退出\n);err:charch1;scanf(%c,&ch1);if(ch1=='1')Display();elseif(ch1=='2')FindList();elseif(ch1=='3')return0;else{printf(\n请输入正确的选择!);gotoerr;}}显示哈希表：查找退出