哈希表设计

哈希表设计一．问题描述问题描述：针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。二.需求分析（1）针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。（2）人名为汉语拼音形式，最长不超过19个字符(如：庄双双zhuangshuangshuang)。（3）假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。（4）在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息要求重新输入。（5）查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度三．概要设计1.为实现上述算法，需要顺序的抽象数据类型。ADTHash｛数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识的数据元素的关键字。数据关系：数据元素同属于一个集合。基本操作P：Creat（&ST，n）；操作结果：构造一个含n个数据元素的静态查找表ST。Destroy（&ST）初始条件：静态查找表ST存在。操作结果：销毁表ST.Search：（ST,key）初始条件：静态查找表ST存在，key为和关键字类型相同的定值。操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该数据元素的值或在表中的位置，否则为“空”。Insert（&h,key）初始条件：哈希表h存在。操作结果：若表中没有key，则在h中插入key。Hash（h,&k）初始条件：哈希表h存在。操作结果：通过除留余数法得到地址用k返回。2.本程序有三个模块：（1）主程序模块Main()｛初始化；｛接受命令；显示结果；｝｝（2）创建hash表的模块（3）查找hash表的模块（4）显示哈希表的模块四．详细设计#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=baojianbo;NameList[1].py=chenjiabin;NameList[2].py=chenxi;NameList[3].py=dinglin;NameList[4].py=fangzewei;NameList[5].py=fengpan;NameList[6].py=guidong;NameList[7].py=hanlijuan;NameList[8].py=haoxiaoju;NameList[9].py=heqing;NameList[10].py=jishaomei;NameList[11].py=jiyunfeng;NameList[12].py=jiangshanshan;NameList[13].py=lixuefei;NameList[14].py=lixueqin;NameList[15].py=liyuanxin;NameList[16].py=liangguannan;NameList[17].py=liuna;NameList[18].py=liupeiyu;NameList[19].py=nixiaodong;NameList[20].py=peixue;NameList[21].py=sunke;NameList[22].py=sunying;NameList[23].py=wanqishuai;NameList[24].py=wangna;NameList[25].py=linglei;NameList[26].py=xinnaping;NameList[27].py=xuyuanfei;NameList[28].py=yanlipeng;NameList[29].py=yangmengjiao;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(i=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(i=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(i=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(i=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(i=0;iHASH_LEN;i++)average+=HashList[i].si;average/=NAME_NO;printf(\n\n平均查找长度：ASL(%d)=%f\n\n,NAME_NO,average);}/*--------------------------------主函数----------------------------*/voidmain(){/*::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')return;else{printf(\n请输入正确的选择!);gotoerr;}}}五．调试分析1.因为人数太多，所以最初总得不到想要的结果，有很多人名的关键字重复2.该程序不占用额外空间，因此时间复杂度是O（n）的3.注意人名的长度，正确的输入信息六．用户手册七．测试数据