哈希表设计大大数据结构课程设计.docx
- 文档编号:14533346
- 上传时间:2023-06-24
- 格式:DOCX
- 页数:12
- 大小:195.95KB
哈希表设计大大数据结构课程设计.docx
《哈希表设计大大数据结构课程设计.docx》由会员分享,可在线阅读,更多相关《哈希表设计大大数据结构课程设计.docx(12页珍藏版)》请在冰点文库上搜索。
哈希表设计大大数据结构课程设计
实习6、哈希表设计
一、需求分析
1.问题描述
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度均不超过R,完成相应的建表和查表顺序。
2.基本要求
假设人名为中国人姓名的汉语拼音形式。
待填入哈希表的人名共有30个,取平均查找长度的上限为2。
哈希函数用除留余数法构造,用伪随机探测再散列法处理冲突。
3.测试数据
取读者周围较熟悉的30个人的姓名。
4.实现提示
如果随机数自行构造,则应首先调整好随机函数,使其分布均匀。
人名的长度均不超过19个字符(最长的人名如:
庄双双(ZhuangShuangshuang))。
字符的取码方法可直接利用C语言中的toascii函数,并可先对过长的人名先作折叠处理。
二、概要设计
ADTHash{
数据对象D:
D是具有相同特征的数据元素的集合。
各数据元素均含有类型相同,可唯一标识数据元素的关键字。
数据关系R:
数据元素同属一个集合。
InitNameTable()
操作结果:
初始化姓名表。
CreateHashTable()
操作结果:
建立哈希表。
DisplayNameTable()
操作结果:
显示姓名表。
DisplayHashTable()
操作结果:
显示哈希表。
FindName()
操作结果:
查找姓名。
}ADTHash
三、详细设计(源代码)
(使用C语言)
#include
#include
#include
#include
#include
#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、j
voidInitNameTable()
{//姓名表的初始化
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;i { 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 { HashTable[i].py="\0"; HashTable[i].m=0; HashTable[i].si=0; } for(i=0;i { intsum=1,j=0; intadr=(NameTable[i].m)%P;//除留余数法H(key)=keyMODp,p<=m if(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 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 { 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;//求得ASL printf("\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;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;//查找次数加1 if(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;i<30;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。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈希表 设计 大大 数据结构 课程设计
![提示](https://static.bingdoc.com/images/bang_tan.gif)