6.2 哈希表设计

哈希表设计一实验目的【问题描述】针对某个集体（比如说班级）中“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。【基本要求】假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2，哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。【测试数据】取读者周围较熟悉的30个人的姓名。二实验内容typedef struct char *py; /名字的拼音 int k; /拼音所对应的整数NAME; typedef struct /哈希表 char *py; /名字的拼音 int k; /拼音所对应的整数 int si; /查找长度HASH;1、自定义数据类型2、基本操作函数#includeusing namespace std;#define HASH_LENGTH 50#define NAME_NO 30#define M 50 /哈希表表长NAME NameListNAME_NO;HASH HashListHASH_LENGTH;void InitNameList() char *f; int r,s0,i; NameList0.py=abcde; NameList1.py=bdee; NameList2.py=csd; NameList3.py=defg; if(HashListadr.si=0) /如果不冲突 HashListadr.k=NameListi.k; HashListadr.py=NameListi.py; HashListadr.si=1; else /冲突 dod=(d+NameListi.k%10+1)%M; /伪随机探测再散列法处理冲突 sum=sum+1; /查找次数加1 while (HashListd.k!=0); HashListd.k=NameListi.k; HashListd.py=NameListi.py; HashListd.si=sum+1;void FindList() /查找char name20=0; int s0=0,r,sum=1,adr,d; coutname; for(r=0;r20;r+) /求出姓名的拼音所对应的整数(关键字)s0+=namer; adr=s0%M; /使用哈希函数 d=adr; if(HashListadr.k=s0) /分3种情况进行判断 cout姓名: HashListd.py关键字: s0查找长度为: 1endl; else if (HashListadr.k=0) cout无此记录!endl; else int g=0; do d=(d+s0%10+1)%M; /伪随机探测再散列法处理冲突 sum=sum+1; if(HashListd.k=0) cout无此记录! endl;g=1; if(HashListd.k=s0) cout姓名: HashListd.py关键字: s0查找长度为: sumendl; g=1;while(g=0); NameList4.py=eerf; NameList5.py=fegg; NameList6.py=ggthh; NameList7.py=hqwd; NameList8.py=iwefd; NameList9.py=jffr; NameList10.py=kweds; NameList11.py=lwwe; NameList12.py=mwesd; NameList13.py=nwerg; NameList14.py=oweee; NameList15.py=pqwed; NameList16.py=qqwff; NameList17.py=rqwed; NameList18.py=swedf; NameList19.py=terw; NameList20.py=uwessd; NameList21.py=vwesd; NameList22.py=wwqes; NameList23.py=xqwes; NameList24.py=yqws; NameList25.py=zqws; NameList26.py=abqws; NameList27.py=bcqw; NameList28.py=cdqw; NameList29.py=deqw; for(i=0;iNAME_NO;i+) s0=0; f=NameListi.py; for(r=0;*(f+r)!=0;r+) /*将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字*/ s0=*(f+r)+s0;NameListi.k=s0;void CreateHashList() int i; for(i=0; iHASH_LENGTH;i+) HashListi.py=; HashListi.k=0; HashListi.si=0; for(i=0;iHASH_LENGTH;i+) int sum=0; int adr=(NameListi.k)%M; /哈希函数 int d=adr;void Display() int i; float average=0; cout地址t关键字tt搜索长度tH(key)t 姓名endl; /显示的格式 for(i=0;iHASH_LENGTH;i+)printf(%d ,i); printf(t%d ,HashListi.k); printf(tt%d ,HashListi.si); printf(tt%d ,HashListi.k%M); printf(t %s ,HashListi.py); printf(n); for(i=0;iHASH_LENGTH;i+) average+=HashListi.si; average/=NAME_NO; cout平均查找长度：average; /ASL(%d)=%f n,NAME_NO,3、主函数void main()/主函数设计char ch1;InitNameList(); CreateHashList (); docoutch1;switch(ch1)case D:Display(); coutendl;break;case F:FindList();coutendl;break;case Q:exit(0);coutch1;while(ch1!=n); system(pause);三实验的结果及分析。四实验中出现的问题、解决方法和心得体会本系统设计需要运用的是索引表的知识。索引表结构的建立定义和应用是