哈希表设计-数据结构课程设计

山东科技大学学生课程设计实习6、哈希表设计一、需求分析1.问题描述针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。2.基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。3.测试数据取读者周围较熟悉的30个人的姓名。4.实现提示如果随机数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19个字符（最长的人名如：庄双双（ZhuangShuangshuang））。字符的取码方法可直接利用C语言中的toascii函数，并可先对过长的人名先作折叠处理。二、概要设计ADTHash{数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。InitNameTable()操作结果：初始化姓名表。CreateHashTable()操作结果：建立哈希表。DisplayNameTable()操作结果：显示姓名表。DisplayHashTable()操作结果：显示哈希表。FindName()操作结果：查找姓名。}ADTHash三、详细设计（源代码）（使用C语言）#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=caowukui;NameTable[1].py=langzhijie;NameTable[2].py=dongshuliang;NameTable[3].py=qiuhouyang;NameTable[4].py=zhangxu;NameTable[5].py=duhuan;NameTable[6].py=fanqing;NameTable[7].py=songxiaofei;NameTable[8].py=dutongtong;NameTable[9].py=sunhaohao;NameTable[10].py=shanjianfeng;NameTable[11].py=wangbaoshan;NameTable[12].py=houfeng;NameTable[13].py=hujiaming;NameTable[14].py=jiangkaiqiang;NameTable[15].py=xuyang;NameTable[16].py=lvdelu;NameTable[17].py=shenjinfeng;NameTable[18].py=xuhui;NameTable[19].py=hanle;NameTable[20].py=xunwenwen;NameTable[21].py=chenhongcong;NameTable[22].py=zhangyanyan;NameTable[23].py=nieyanshun;NameTable[24].py=haopengcheng;NameTable[25].py=yuhaiyuan;NameTable[26].py=shuxiang;NameTable[27].py=sunyingjie;NameTable[28].py=wangbo;NameTable[29].py=zhaoqing;NameTable[30].py=zhangshengqian;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(){//显示哈希表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);}voidFindName()山东科技大学学生课程设计{//查找charname[20]={0};ints=0,sum=1,adr;printf(\n请输入想要查找的姓名的拼音:);scanf(%s,name);getchar();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;}}}}intmain(){//主函数charc;inta=1;srand((int)time(0));for(i=0;i30;i++)//用随机函数求得伪随机数列d[i]（在1到50之间）d[i]=1+(int)(HASH_LEN*rand()/(RAND_MAX+1.0));InitNameTable();CreateHashTable();printf(*******************************************************\n);printf(**\n);printf(*哈希表设计*\n);printf(**\n);printf(*A:显示姓名表B:显示哈希表*\n);printf(**\n);printf(*C:查找D:退出*\n);printf(**\n);山东科技大学学生课程设计printf(*******************************************************\n);while(a){printf(\n请选择:);scanf(%c,&c);getchar();switch(c)//根据选择进行判断，直到选择退出时才可以退出{case'A':case'a':DisplayNameTable();break;case'B':case'b':DisplayHashTable();break;case'C':case'c':FindName();break;case'D':case'd':a=0;break;default:printf(\n请输入正确的选择!\n);break;}}return0;}四、调试分析编译环境为CodeBlocks。山东科技大学学生课程设计山东科技大学学生课程设计山东科技大学学生课程设计