基于Hash表的班级成员管理数据结构课程设计.docx
《基于Hash表的班级成员管理数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《基于Hash表的班级成员管理数据结构课程设计.docx（29页珍藏版）》请在冰点文库上搜索。
基于Hash表的班级成员管理数据结构课程设计
沈阳航空航天大学
课程设计报告
课程设计名称：
数据结构课程设计
课程设计题目：
基于Hash表的班级成员管理
目录
1题目介绍和功能要求1
1.1题目介绍1
1.2功能要求1
1.3基本功能1
2系统功能模块结构图2
2.1系统功能结构框图2
2.2系统主要模块的功能说明2
3使用的数据结构的描述4
3.1数据结构设计4
3.2数据结构用法说明4
4函数的描述5
4.1主要函数设计5
4.2主要函数流程图5
5程序测试和运行的结果8
5.1程序测试8
5.2运行结果9
6参考文献11
附录（关键部分程序清单）12
1题目介绍和功能要求
1.1题目介绍
针对本班成员以姓名为关键字设计一个Hash表，使得平均查找长度不超过R。
要求：
1.自行设计至少3中Hash函数；
2.每种Hash函数采用线性探测再散列和伪随机数探测再散列进行冲突处理；
针对本班成员给出每种Hash函数的平均查找长度。
建立一个确定的对应关系f，使每个关键字和结构中的一个唯一的存储位置相对应。
在查找时，只要根据这个对应关系f找到给定值K的像f（K）所建立的表即为哈希表。
1.2功能要求
1.用三种方法创建哈希函数，分别为除留取余法，随机数法和分割法。
2.当哈希地址产生冲突时，利用线性探测再散列和伪随机数探测再散列进行冲突处理得到新的哈希地址，并存入哈希表中。
3.给出每个用户名的查找长度和该函数的平均查找长度，并比较哪种方法最好。
1.3基本功能
1.CreateHashList（）建立Hash函数，并采用两种冲突处理方法进行操作。
2.SearchHash（）查找Hash表，将用户所输入的信息从Hash表中调出，并给出查找长度
2系统功能模块结构图
2.1系统功能结构框图
图2.1系统功能结构框图
2.2系统主要模块的功能说明
1.哈希模块
CreateHashList（）；（adr为哈希地址）
初始化Hash表，并创建Hash函数，并将用户姓名添加至Hash表中。
1）除留取余法：
adr=（DATALIST[i].k）%M;（将DATALIST[i].k所存的ASCII码除以M取余所得的哈希地址赋给adr）
2）随机函数法:
srand（DATALIST[i].k）;
intadr=rand（）%L;（将DATALIST[i].k所存的ASCII码作为种子传入至srand函数中，并用rand函数产生L以内的随机值为哈希地址赋给adr）
3）分割法:
change（DATALIST,A,i）;
intadr=A[1]*10+A[2];（DATALIST[i].k所存的ASCII码利用change（）函数分割开，并去第二个数字和第三个数字作为哈希地址赋给adr）
2.冲突处理模块
1）srand（姓名ASCII码）;
d=（d+rand（）%L）%M;
伪随机探测再散列
2）d=d+1;
线性探测再散列
3.查找模块
SearchHash（）;
查找用户输入姓名是否在Hash表中；
给出该姓名的查找长度和该Hash函数的平均查找长度。
3使用的数据结构的描述
3.1数据结构设计
建立一个确定的对应关系f，使每个关键字和结构中的一个唯一的存储位置相对应。
在查找时，只要根据这个对应关系f找到给定值K的像f（K）为存储地址的结构体数组即为哈希表。
哈希表举例（平方取中法）：
ABC……Z012……9
0102033260616271
记录
关键字
（关键字）2
哈希地址（217-29）
A
I
J
I0
P1
P2
Q1
Q2
Q3
0100
1100
1200
1160
2061
2062
2161
2162
2163
0010000
1210000
1440000
1370400
4310541
4314704
4734741
4741304
4745651
010
210
440
370
310
314
734
741
745
表3.1哈希表
3.2数据结构用法说明
取关键字平方后的中间几位为哈希地址。
这是一种比较常用的构造哈希函数的方法。
通常在选定哈希函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随即分布的关键字得到的哈希地址也是随即的。
取的位数由表长决定。
如表3.1列出了一些标识符及它们的哈希地址。
4函数的描述
4.1主要函数设计
1.Input（）；
作用：
将用户姓名换算成ASCII码。
2.CreateHashList（）；
作用：
将用户名输入至哈希表中，并用两种冲突处理方法进行冲突处理。
3.SearchHash（）;
作用：
将用户输入的用户名在哈希表中进行查找，并给出查找结果和查找长度，和该函数的平均查找长度。
4.Print（）；
作用：
打印出程序的主菜单和界面。
5.Change（）;
作用:
将用户姓名的ASCII码分割为多个数字并存入数组中。
4.2主要函数流程图
1.CreateHashList（）；
图4.2.1创建函数流程图
2.SearchHash（）;
图4.2.2查找函数流程图
5程序测试和运行的结果
5.1程序测试
程序开始菜单：
图5.1.1一号菜单图
输入1或者2；
图5.1.2二号菜单图
输入1；
图5.1.3查找图
输入2；
图5.1.4平均查找图
5.2运行结果
给出3组数据，每组数据29个用户名，分别用三种哈希函数和两种冲突处理方法进行操作，结果如图：
1.数据1：
1）除留取余法：
（一）线性探测再散列：
（二）伪随机数探测再散列：
2）随机数法：
（一）线性探测再散列：
（二）伪随机数探测再散列：
3）分割法：
（一）线性探测再散列：
（二）伪随机数探测再散列：
2.数据2：
1）除留取余法：
（一）线性探测再散列：
（二）伪随机数探测再散列：
2）随机数法：
（一）线性探测再散列：
（二）伪随机数探测再散列：
3）分割法：
（一）线性探测再散列：
（二）伪随机数探测再散列：
3.数据3：
1）除留取余法：
（一）线性探测再散列：
（二）伪随机数探测再散列：
2）随机数法：
（一）线性探测再散列：
（二）伪随机数探测再散列：
3）分割法：
（一）线性探测再散列：
（二）伪随机数探测再散列：
结论：
经比较可知，分割法所建立的哈希函数平均查找长度最短。
6参考文献
[1]高富平，张楚.电子商务法［M］.北京：
北京大学出版社，2002
[2]HuangSC，HuangYM，ShiehSM．Vibrationandstabilityofarotatingshaftcontainingatransersecrack［J］,JSoundandVibration，1993，162（3）：
387－401．
[3]谭浩强著.C程序设计（第三版）.北京:
清华大学出版社,2005
[4]数据结构:
C语言版/严蔚敏,吴伟明编著.—北京:
清华大学出版社,2007
附录（关键部分程序清单）
#include
#include
#include
#defineL50//哈希表的长度
#defineRAND_MAX10//随机数范围
#defineM47//除留取余数值
#defineNAME_NO29//人名的个数
#defineSUCCESS1
#defineUNSUCESS0
#defineElemTypechar
typedefstructHash//哈希表
{
ElemType*data;
ints;//查找长度
intk;//当前姓名的ASCII码
}Hash;Hashhlist[L];
typedefstructDATE//班级成员
{char*data;//姓名
intk;//姓名ASCII码
}DATA;DATEDATALIST[NAME_NO];
voidinput（）//姓名（结构体数组）初始化
{char*m;
intr,s0,i;
DATALIST[0].data="hudi";
DATALIST[1].data="lijing";
DATALIST[2].data="peiting";
DATALIST[3].data="yinhang";
DATALIST[4].data="liulu";
DATALIST[5].data="lishengnan";
DATALIST[6].data="cuililong";
DATALIST[7].data="songchongyuan";
DATALIST[8].data="xiejinhua";
DATALIST[9].data="mashuangmin";
DATALIST[10].data="wangjing";
DATALIST[11].data="qiyueyu";
DATALIST[12].data="gaozhiwei";
DATALIST[13].data="fuzedong";
DATALIST[14].data="shidailong";
DATALIST[15].data="sujun";
DATALIST[16].data="zhangxinglei";
DATALIST[17].data="liuyang";
DATALIST[18].data="liushuxin";
DATALIST[19].data="fengkunkun";
DATALIST[20].data="suzheng";
DATALIST[21].data="sunjianwei";
DATALIST[22].data="mengbaiyu";
DATALIST[23].data="yushaolong";
DATALIST[24].data="lishaolun";
DATALIST[25].data="zhangkuo";
DATALIST[26].data="wangdanran";
DATALIST[27].data="lizhanying";
DATALIST[28].data="yangjun";
for（i=0;i{
s0=0;
m=DATALIST[i].data;
for（r=0;*（m+r）!
='\0';r++）
s0=*（m+r）+s0;
DATALIST[i].k=s0;
}
}
intCreateHashList（）//建立哈希表
{
inti,num,sum;
printf（"请选择冲突处理方法\n"）;
printf（"1.线性探测再散列\n"）;
printf（"2.伪随机数探测再散列\n"）;
scanf（"%d",&num）;
switch（num）
{
case1:
{
for（i=0;i{
hlist[i].data="";
hlist[i].k=0;
hlist[i].s=0;
}
for（i=0;i{
sum=0;
intadr=（DATALIST[i].k）%M;//哈希函数（除留取余）
if（i==NAME_NO）
break;
intd=adr;
if（hlist[adr].s==0）
{
hlist[adr].k=DATALIST[i].k;
hlist[adr].data=DATALIST[i].data;
hlist[adr].s=1;//此处已有数据
}
else
{
do
{
d=d+1;//线性探测再散列法处理冲突
sum=sum+1;//查找次数加1
}while（hlist[d].s!
=0）;
hlist[d].k=DATALIST[i].k;
hlist[d].data=DATALIST[i].data;
hlist[d].s=sum+1;
}
}
return1;
}break;
case2:
{
for（i=0;i{
hlist[i].data="";
hlist[i].k=0;
hlist[i].s=0;
}
for（i=0;i{
sum=0;
intadr=（DATALIST[i].k）%M;//哈希函数
if（i==NAME_NO）
break;
intd=adr;
if（hlist[adr].s==0）
{
hlist[adr].k=DATALIST[i].k;
hlist[adr].data=DATALIST[i].data;
hlist[adr].s=1;//此处已有数据
}
else
{
do
{
srand（DATALIST[i].k）;
d=（d+rand（）%L）%M;//伪随机数探测再散列法处理冲突
sum=sum+1;//查找次数加1
}while（hlist[d].s!
=0）;
hlist[d].k=DATALIST[i].k;
hlist[d].data=DATALIST[i].data;
hlist[d].s=sum+1;
}
}
return2;
}break;
}
}
intSearchHash1（char*name,Hashhlist[],int*k）//k为查找次数,线性探测查找
{
ints0=0,r,n=1;
for（r=0;*（name+r）!
='\0';r++）
s0=*（name+r）+s0;
intadr=s0%M;
if（stricmp（hlist[adr].data,name）==0）
{
*k=hlist[adr].s;
returnSUCCESS;
}
else
{
while
（1）
{
if（n>L||strlen（hlist[adr].data）==0）
returnUNSUCESS;
adr=adr+1;
n++;
if（stricmp（hlist[adr].data,name）==0）
{
*k=hlist[adr].s;
returnSUCCESS;
}
}
}
}
intSearchHash2（char*name,Hashhlist[],int*k）//k为查找次数,伪随机数探测查找
{
ints0=0,r,n=1;//n为初始查找长度
for（r=0;*（name+r）!
='\0';r++）
s0=*（name+r）+s0;
intadr=s0%M;
if（stricmp（hlist[adr].data,name）==0）
{
*k=hlist[adr].s;
returnSUCCESS;
}
else
{
while
（1）
{
if（n>L||strlen（hlist[adr].data）==0）
returnUNSUCESS;
srand（s0）;
adr=（adr+rand（）%L）%M;
n++;
if（stricmp（hlist[adr].data,name）==0）
{
*k=hlist[adr].s;
returnSUCCESS;
}
}
}
}
voidprint（）
{
printf（"%*******************************************\n"）;
printf（"****\n"）;
printf（"****\n"）;
printf（"**哈希表**\n"）;
printf（"****\n"）;
printf（"****\n"）;
printf（"****\n"）;
printf（"******************************************\n"）;
}
voidmain（）
{
charname[20];intresult=0,m,n;intk;inti=1;//m判断选择探测方法
floatc=0,d;
while
（1）
{
lp:
print（）;
printf（"请选择：
\n"）;
input（）;
m=CreateHashList（）;
printf（"请选择：
\n"）;
printf（"1.查找姓名\n"）;
printf（"2.显示该哈希函数的平均查找长度\n"）;
printf（"3.退到上级\n"）;
scanf（"%d",&n）;
switch（n）
{
case1:
{
if（m==1）
{
printf（"请输入姓名\n"）;
scanf（"%s",name）;
result=SearchHash1（name,hlist,&k）;
if（result==1）
{
printf（"查找成功\n"）;
printf（"查找长度为%d\n",k）;
}
else
printf（"查找失败\n"）;
}
if（m==2）
{
printf（"请输入姓名\n"）;
scanf（"%s",name）;
result=SearchHash2（name,hlist,&k）;
if（result==1）
{
printf（"查找成功\n"）;
printf（"查找长度为%d\n",k）;
}
else
printf（"查找失败\n"）;
}
}break;
case2:
{
d=0;
for（i=0;id+=hlist[i].s;
c=d/NAME_NO;
printf（"平均查找长度为%f\n",c）;
}break;
case3:
{
system（"cls"）;
gotolp;
}break;
}
}
}
课程设计总结：
指导教师评语：
指导教师（签字）：
年月日
课程设计成绩
毕业设计（论文）原创性声明和使用授权说明
原创性声明
本人郑重承诺：
所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。
尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。
对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。
作者签名：
日 期：
指导教师签名：
日 期：
使用授权说明
本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：
按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。
作者签名：
日 期：
学位论文原创性声明
本人郑重声明：
所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。
除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。
对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。
本人完全意识到本声明的法律后果由本人承担。
作者签名：
日期：
年月日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。
本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
涉密论文按学校规定处理。
作者签名：
日期：
年月日
导师签名：
日期：
年月日
指导教师评阅书
指导教师评价：
一、撰写（设计）过程
1、学生在论文（设计）过程中的治学态度、工作精神
□优□良□中□及格□不及格
2、学生掌握专业知识、技能的扎实程度
□优□良□中□及格□不及格
3、学生综合运用所学知识和专业技能分析和解决问题的能力
□优□良□中□及格□不及格
4、研究方法的科学性；技术线路的可行性；设计方案的合理性
□优□良□中□及格□不及格
5、完成毕业论文（设计）期间的出勤情况
□
升级会员 