数据结构与算法课程设计说明书-哈希表设计

PAGEPAGE1数据结构与算法课程设计说明书

学院、系：软件学院专业软件工程设计题目：哈希表设计

需求分析（1）针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。（2）人名为汉语拼音形式，最长不超过19个字符(如：庄双双zhuangshuangshuang)。（3）假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。（4）如果随机函数自行构造，则应首先调整好随机函数，使其分布均匀。字符的取码方法可直接利用C语言中的toascii函数，并可对过长人名先进行折叠处理。（5）查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度。基本操作根据哈希函数可唯一确定一个记录的地址，在理想情况下，记录就可以按照这个存储地址进行存储。因此哈希表的存储结构可以是链表和线性表，但一般情况下选择线性表进行存储。本次课程设计用到的存储结构如下：typedefstruct{char*name;//名字的拼音intk;//名字拼音所对应的关键字}NAME;//结构体NEMA，存放名字列表typedefstruct//哈希表{char*name;//名字的拼音intk;//名字拼音所对应的关键字intsi;//名字的查找长度}HASH;//结构体HASH，哈希表首先定义两个结构体数组：NAMENameList[HASH_LENGTH];//全局变量NAME，存储原始姓名HASHHashList[HASH_LENGTH];//全局变量HASH，存储哈希表中的姓名主要函数原型及功能：voidInitNameList()功能：主要完成初始化姓名列表，并且将字符串的各个字符所对应的ASCII码相加，所得的整数作为哈希表的关键字。以便利用关键字和除留余数法得到每个姓名的哈希地址。voidCreateHashList()功能：构建一个哈希表并进行初始化；利用各个姓名的关键字得到哈希地址，将各个姓名按哈希地址进行存储，如果发生冲突，则利用伪随机探测再序列解决冲突，最终将姓名全部存放在哈希表中。voidFindList()功能：对用户输入的姓名进行查找；查找结果分两种情况：（1）查找成功，则输出姓名、关键字和查找长度；（2）查找失败，则返回相应的失败信息。查找时关键字的求法和处理冲突的方法与函数InitNameList()、CreateHashList()中的相关算法一致。voidShowHash()功能：完成度已经建立好的哈希表进行输出显示，并输出平均查找长度。voidmain()功能：完成对个函数的调用和与用户的交互。函数voidInitNameList()的实现（以班级30人的人名作为初始值）：voidInitNameList()//姓名（结构体数组）初始化{char*f;intr,s0,i;NameList[0].name="fanxu";NameList[1].name="jiangyong";NameList[2].name="guyuze";NameList[3].name="liuzhenhai";NameList[4].name="chenang";NameList[5].name="caoyandong";NameList[6].name="yangchenchen";NameList[7].name="shenjin";NameList[8].name="puping";NameList[9].name="luhaibo";NameList[10].name="renchao";NameList[11].name="wangshichuang";NameList[12].name="guoqihui";NameList[13].name="chengkang";NameList[14].name="wangyuesong";NameList[15].name="liangfangping";NameList[16].name="wangxufeng";NameList[17].name="hejie";NameList[18].name="yangyiming";NameList[19].name="wushengping";NameList[20].name="yangchaoqin";NameList[21].name="wulinfeng";NameList[22].name="xiehongwei";NameList[23].name="liushuo";NameList[24].name="yijiabin";NameList[25].name="xuhaiyang";NameList[26].name="yangwenjuan";NameList[27].name="chenjunyan"；NameList[28].name="wangjiaxin";NameList[29].name="chenwan";for(i=0;i<NAME_NO;i++) {s0=0;f=NameList[i].name;for(r=0;*(f+r)!='\0';r++)/*哈希地址方法：将字符串的各个字符所对应的ASCII码相加，所得的整数作为哈希表的关键字*/s0=*(f+r)+s0;NameList[i].k=s0; }}用除留余数法构建哈希函数用伪随机探测再散列法处理冲突构建哈希函数voidCreateHashList()的实现：voidCreateHashList(){ inti;for(i=0;i<HASH_LENGTH;i++) {HashList[i].py="";HashList[i].k=0;HashList[i].si=0; }for(i=0;i<HASH_LENGTH;i++) {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; } }}查找哈希表若查找成功，则输出姓名、关键字和查找长度；查找失败，则返回相应的失败信息。查找函数voidFindList()的实现：voidFindList()//查找{ charname[20]={0};ints0=0,r,sum=1,adr,d;printf("请输入姓名的拼音:");scanf("%s",name);for(r=0;r<20;r++)//求出姓名的拼音所对应的整数(关键字)s0+=name[r];adr=s0%M;//使用哈希函数d=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); }}显示哈希表显示哈希表的的格式：\n地址\t关键字\t\t搜索长度\tH(key)\t姓名\n显示哈希表的函数voidDisplay()的：voidDisplay()//显示{ inti;floataverage=0;printf("\n地址\t关键字\t\t搜索长度\tH(key)\t姓名\n");//显示的格式for(i=0;i<50;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"); }for(i=0;i<HASH_LENGTH;i++)average+=HashList[i].si;average/=NAME_NO;printf("\n平均查找长度：ASL(%d)=%f\n",NAME_NO,average);}主函数设计voidmain(){ charch1; InitNameList();CreateHashList(); do { printf("D.显示哈希表\nF.查找\nQ.退出\n请选择："); cin>>&ch1; switch(ch1) { case'D':Display();cout<<endl;break; case'F':FindList();cout<<endl;break; case'Q':exit(0); } cout<<"comeon!(y/n):"; cin>>&ch1; }while(ch1!='n');}3程序流程图开始开始选择操作S、F、Q显示哈希表查找哈希表SFQ退出程序、继续Y退出NYN结束4调试报告经过对哈希表的研究后，即进行程序的设计和编码；将原程序编好后，经过编译，有如下几个问题：在声明了结构体NAME后，最开始结构体内的charname[20]用来存放姓名拼音，最长为20位；经分析，name表示所存姓名拼音的首地址，无需再申明具体的数组长度来存放姓名拼音，这样增加了系统的开销，最后改成char*name，对存放姓名拼音时直接对name赋值，系统直接按照字符数组来存放姓名拼音，而存放长度没有固定。建立哈希表的函数：voidCreateHashList()中，如果遇到冲突后，在do{}while()；语句中，利用伪随机探测再散列法处理冲突，没执行一次就要将记录查找长度的sum增加一次，在这个循环执行完后，即找到一个不冲突的地址来存放姓名拼音，经过自习分析，此时的查找长度需要加1，即将原来的语句HashList[d].si=sum;改成HashList[d].si=sum+1;此时的HashList[d].si才是正确的查找长度。main函数中的do{}while()语句中，最开始while()语句是：while(a!='N'||a!='n')经过分析，在用户需要退出时，不论输入a=N还是a=n，都将继续循环；经过自习思考，最终将while()语句改成：while(a=='Y'||a=='y')，这样就实现了用户的选择。5程序代码#include<stdio.h>#include<time.h>//time用到的头文件#include<stdlib.h>//随机数用到的头文件#include<ctype.h>//toascii()用到的头文件#include<string.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;i<NAME_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;i<HASH_LEN;i++){HashTable[i].py="\0";HashTable[i].m=0;HashTable[i].si=0;}for(i=0;i<NAME_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;i<NAME_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;i<HASH_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);for(j=0;j<20;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()//主函数{chara;srand((int)time(0));for(i=0;i<30;i++)//用随机函数求得伪随机数列d[i]（在1到50之间）d[i]=1+(int)(HASH_LEN*rand()/(RAND_MAX+1.0));InitNameTable();CreateHashTable();puts("哈希表设计");//显示菜单栏start:puts("\n*菜单栏*");puts("\t\t\t1.显示姓名表");puts("\t\t\t2.显示哈希表");puts("\t\t\t3.查找");puts("\t\t\t4.退出");puts("*