《数据结构实验答案数据结构课程设计哈希表设计》由会员分享，可在线阅读，更多相关《数据结构实验答案数据结构课程设计哈希表设计（11页珍藏版）》请在金锄头文库上搜索。
1、课 程 设 计 课程名称 数据结构 题目名称 哈希表设计 学生学院 计算机学院 专业班级 07级网络工程2班 学 号 3207007022 学生姓名 刘晓慧 指导教师 杨劲涛 2021 年 6 月 28 日一问题描述1问题描述针对某个集体比方你所在的班级中的“人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。二. 需求分析1 针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。2人名为汉语拼
2、音形式，最长不超过19个字符(如：庄双双 zhuangshuangshuang)。3 假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。4 在输入人名过程中能自动识别非法输入，并给与非法输入的反应信息要求重新输入。5查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度三程序设计1 .存储结构设计typedef struct char *py; /名字的拼音 int k; /拼音所对应的整数NAME; typedef struct /哈希表 char *py; /名字的拼音 int k; /拼音所对应的整数 int si;
3、/查找长度HASH;2 .主要算法设计 1 姓名结构体数组初始化 名字以拼音的形式够成字符串，将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字。void InitNameList() char *f; int r,s0,i; NameList0.py=chenliang;/陈亮 NameList1.py=chenyuanhao;/陈元浩 NameList2.py=chengwenliang;/程文亮 NameList3.py=dinglei;/丁磊 NameList4.py=fenghanzao;/冯汉枣 NameList5.py=fuzongkai;/付宗楷 Name
4、List6.py=hujingbin;/胡劲斌 NameList7.py=huangjianwu;/黄建武 NameList8.py=lailaifa;/赖来发 NameList9.py=lijiahao;/李嘉豪 NameList10.py=liangxiaocong;/梁晓聪 NameList11.py=linchunhua;/林春华 NameList12.py=liujianhui;/刘建辉 NameList13.py=luzhijian;/卢志健 NameList14.py=luonan;/罗楠 NameList15.py=quegaoxiang;/阙高翔 NameList16.py=
5、sugan;/苏淦 NameList17.py=suzhiqiang;/苏志强 NameList18.py=taojiayang;/陶嘉阳 NameList19.py=wujiawen;/吴嘉文 NameList20.py=xiaozhuoming;/肖卓明 NameList21.py=xujinfeng; /许金峰 NameList22.py=yanghaichun;/杨海春 NameList23.py=yeweixiong;/叶维雄 NameList24.py=zengwei;/曾玮 NameList25.py=zhengyongbin;/郑雍斌 NameList26.py=zhongmi
6、nghua;/钟明华 NameList27.py=chenliyan;/陈利燕 NameList28.py=liuxiaohui;/刘晓慧 NameList29.py=panjinmei;/潘金梅 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; (2) 建立哈希表 1 用除留余数法构建哈希函数 2 用伪随机探测再散列法处理冲突void CreateHashList() in
7、t 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; if(HashListadr.si=0) /如果不冲突 HashListadr.k=NameListi.k; HashListadr.py=NameListi.py; HashListadr.si=1; else /冲突 do d=(d+NameListi.k%10+1)%M; /伪随机探
8、测再散列法处理冲突 sum=sum+1; /查找次数加1 while (HashListd.k!=0); HashListd.k=NameListi.k; HashListd.py=NameListi.py; HashListd.si=sum+1; (3) 查找哈希表 在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度void FindList() /查找 char name20=0; int s0=0,r,sum=1,adr,d; printf(请输入姓名的拼音:); scanf(%s,name); for(r=0;r20;r+) /求出姓名的拼音所对应的整数(关
9、键字) s0+=namer; adr=s0%M; /使用哈希函数 d=adr; if(HashListadr.k=s0) /分3种情况进行判断 printf(n姓名:%s 关键字:%d 查找长度为: 1,HashListd.py,s0); else if (HashListadr.k=0) printf(无此记录!); else int g=0; do d=(d+s0%10+1)%M; /伪随机探测再散列法处理冲突 sum=sum+1; if(HashListd.k=0) printf(无此记录! ); g=1; if(HashListd.k=s0) printf(n姓名:%s 关键字:%d
10、查找长度为:%d,HashListd.py,s0,sum); g=1; while(g=0); (4) 显示哈希表 显示哈希表的的格式： n地址t关键字tt搜索长度tH(key)t 姓名nvoid Display() int i; float average=0; printf(n地址t关键字tt搜索长度tH(key)t 姓名n); /显示的格式 for(i=0; i50; 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;i&ch1;switch(ch1)case D:Display(); coutendl;break;case F:FindList();coutendl;break;case Q:exit(0);cout&ch1;while(ch1!=n
