数据结构哈希表设计

实验六：存储管理、查找和排序题目：哈希表设计班级：姓名：学号：一、问题描述针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。二、基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。三、概要设计1.构造结构体：typedefstruct{}；2.姓名表的初始化：voidInitNameTable()；3.建立哈希表：voidCreateHashTable()；4.显示姓名表：voidDisplayNameTable()；5.姓名查找：voidFindName()；6.主函数：voidmain()；四、详细设计1.姓名表的初始化voidInitNameTable(){NameTable[0].py=louyuhong;NameTable[1].py=shenyinghong;NameTable[2].py=wangqi;NameTable[3].py=zhuxiaotong;NameTable[4].py=zhataotao;NameTable[5].py=chenbinjie;NameTable[6].py=chenchaoqun;NameTable[7].py=chencheng;NameTable[8].py=chenjie;NameTable[9].py=chenweida;NameTable[10].py=shanjianfeng;NameTable[11].py=fangyixin;NameTable[12].py=houfeng;NameTable[13].py=hujiaming;NameTable[14].py=huangjiaju;NameTable[15].py=huanqingsong;NameTable[16].py=jianghe;NameTable[17].py=jinleicheng;NameTable[18].py=libiao;NameTable[19].py=liqi;NameTable[20].py=lirenhua;NameTable[21].py=liukai;NameTable[22].py=louhanglin;NameTable[23].py=luchaoming;NameTable[24].py=luqiuwei;NameTable[25].py=panhaijian;NameTable[26].py=shuxiang;NameTable[27].py=suxiaolei;NameTable[28].py=sunyubo;NameTable[29].py=wangwei;for(i=0;iNAME_LEN;i++)//将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字{ints=0;char*p=NameTable[i].py;for(j=0;*(p+j)!='\0';j++)s+=toascii(*(p+j));NameTable[i].m=s;}}2.建立哈希表voidCreateHashTable(){for(i=0;iHASH_LEN;i++){HashTable[i].py=\0;HashTable[i].m=0;HashTable[i].si=0;}for(i=0;iNAME_LEN;i++){intsum=1,j=0;intadr=(NameTable[i].m)%P;//除留余数法H(key)=keyMODp,p=mif(HashTable[adr].si==0)//如果不冲突，将姓名表赋值给哈希表{HashTable[adr].m=NameTable[i].m;HashTable[adr].py=NameTable[i].py;HashTable[adr].si=1;}else//如果冲突{while(HashTable[adr].si!=0){adr=(adr+d[j++])%HASH_LEN;//伪随机探测再散列法处理冲突sum=sum+1;//查找次数加1}HashTable[adr].m=NameTable[i].m;//将姓名表复制给哈希表对应的位置上HashTable[adr].py=NameTable[i].py;HashTable[adr].si=sum;}}}3.显示姓名表与哈希表voidDisplayNameTable(){printf(\n地址\t\t姓名\t\t关键字\n);for(i=0;iNAME_LEN;i++)printf(%2d%18s\t\t%d\n,i,NameTable[i].py,NameTable[i].m);}voidDisplayHashTable(){floatasl=0.0;printf(\n\n地址\t\t姓名\t\t关键字\t搜索长度\n);//显示的格式for(i=0;iHASH_LEN;i++){printf(%2d%18s\t\t%d\t\t%d\n,i,HashTable[i].py,HashTable[i].m,HashTable[i].si);asl+=HashTable[i].si;}asl/=NAME_LEN;//求得ASLprintf(\n\n平均查找长度：ASL(%d)=%f\n,NAME_LEN,asl);}4.姓名查找voidFindName(){charname[20]={0};ints=0,sum=1,adr;printf(\n请输入想要查找的姓名的拼音:);scanf(%s,name);for(j=0;j20;j++)//求出姓名的拼音所对应的ASCII作为关键字s+=toascii(name[j]);adr=s%P;//除留余数法j=0;if(HashTable[adr].m==s&&!strcmp(HashTable[adr].py,name))//分3种情况进行判断，并输出超找结果printf(\n姓名:%s关键字:%d查找长度为:1\n,HashTable[adr].py,s);elseif(HashTable[adr].m==0)printf(没有想要查找的人!\n);else{while(1){adr=(adr+d[j++])%HASH_LEN;//伪随机探测再散列法处理冲突sum=sum+1;//查找次数加1if(HashTable[adr].m==0){printf(没有想要查找的人!\n);break;}if(HashTable[adr].m==s&&!strcmp(HashTable[adr].py,name)){printf(\n姓名:%s关键字:%d查找长度为:%d\n,HashTable[adr].py,s,sum);break;}}}}五、测试结果六、实验环境C-Free七、源程序代码#includestdio.h#includetime.h//time用到的头文件#includestdlib.h//随机数用到的头文件#includectype.h//toascii()用到的头文件#includestring.h//查找姓名时比较用的头文件#defineHASH_LEN50//哈希表的长度#defineP47//小于哈希表长度的P#defineNAME_LEN30//姓名表的长度typedefstruct//姓名表{char*py;//名字的拼音intm;//拼音所对应的}NAME;NAMENameTable[HASH_LEN];//全局定义姓名表typedefstruct//哈希表{char*py;//名字的拼音intm;//拼音所对应的ASCII总和intsi;//查找长度}HASH;HASHHashTable[HASH_LEN];//全局定义哈希表intd[30],i,j;//全局定义随机数,循环用的i、jvoidInitNameTable()//姓名表的初始化{NameTable[0].py=louyuhong;NameTable[1].py=shenyinghong;NameTable[2].py=wangqi;NameTable[3].py=zhuxiaotong;NameTable[4].py=zhataotao;NameTable[5].py=chenbinjie;NameTable[6].py=chenchaoqun;NameTable[7].py=chencheng;NameTable[8].py=chenjie;NameTable[9].py=chenweida;NameTable[10].py=shanjianfeng;NameTable[11].py=fangyixin;NameTable[12].py=houfeng;NameTable[13].py=hujiaming;NameTable[14].py=huangjiaju;NameTable[15].py=huanqingsong;NameTable[16].py=jianghe;NameTable[17].py=jinleicheng;NameTable[18].py=libiao;NameTable[19].py=liqi;NameTable[20].py=lirenhua;NameTable[21].py=liukai;NameTable[22].py=louhanglin;NameTable[23].py=luchaoming;NameTable[24].py=luqiuwei;NameTable[25].py=panhaijian;NameTable[26].py=shuxiang;NameTable[27].py=suxiaolei;NameTable[28].py=sunyubo;NameTable[29].py=wangwei;for(i=0;iNAME_LEN;i++)//将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字{ints=0;char*p=NameTable[i].py;for(j=0;*(p+j)!='\0';j++)s+=toascii(*(p+j));NameTable[i].m=s;}}voidCreateHashTable()//建立哈希表{for(i=0;iHASH_LEN;i++){HashTable[i].py=\0;HashTable[i].m=0;HashTable[i].si=0;}for(i=0;iNAME_LEN;i++){intsum=1,j=0;intadr=(NameTable[i].m)%P;//除留余数法H(key)=keyMODp,p=mif(HashTable[adr].si==0)//如果不冲突，将姓名表赋值给哈希表{HashTable[adr].m=NameTable[i].m;HashTable[adr].py=NameTable[i].py;HashTable[adr].si=1;}else//如果冲突{while(HashTable[adr].si!=0){adr=(adr+d[j++])%HASH_LEN;//伪随机探测再散列法处理冲突sum=sum+1;//查找次数加1}HashTable[adr].m=NameTable[i].m;//将姓名表复制给哈希表对应的位置上HashTable[adr].py=NameTable[i].py;HashTable[adr].si=sum;}}}voidDisplayNameTable()//显示姓名表{printf(\n地址\t\t姓名\t\t关键字\n);for(i=0;iNAME_LEN;i++)printf(%2d%18s\t\t%d\n,i,NameTable[i].py,NameTable[i].m);}voidDisplayHashTable()//显示哈希表{fl