




kok电子竞技权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
kok电子竞技:文档简介
1、.数据结构实验kok电子竞技四哈希表查找名字(字符串)实验题目:哈希表查找名字(字符串) 实验目标:输入一组名字(至少50个),将其保存并利用哈希表查找。输出哈希查找冲突次数,哈希表负载因子、查找命中率。数据结构:哈希表和数组(二维)。二维数组用于静态顺序存储名字(字符串),哈希表采用开放定址法,用于存储名字(字符串)对应的关键字并实现对名字(字符串)的查找。需要的操作有:1.关键字求。ㄖ骱辛酱纬鱿,未单独编为函数)关键字key=abs(字符串首位ASCII码值-第二位ASCII码值+第(n2+1)位ASCII码值-最后一位ASCII码值-倒数第二位ASCII码值)*字符串长度(abs为求整数绝对
2、值的函数)。2.处理关键字的哈:℉ash)利用平方取中法求关键值key在哈希表中的位置。公式add=(key*key)%1000/LENGTH(add为key在哈希表中的地址)。int Hash(int key)return(key*key)/1000%LENGTH);3.处理哈希表中冲突的函数(Collision)利用线性探测再散列处理冲突,利用全局变量count统计冲突次数。int Collision(int key,int Hashtable)int i;for(i=1;i=LENGTH;i+)if(Hashtable(Hash(key)+i)%LENGTH=-1)return(H
3、ash(key)+i)%LENGTH);count+;4.哈希表初始化(InitHash)void InitHash(int Hashtable)int i;for(i=0;iLENGTH;i+)Hashtablei=-1;5.向哈希表中插入关键字(InsertHash)void InsertHash(int key,int Hashtable)int add;add=Hash(key);if(Hashtableadd=-1)Hashtableadd=key;elseadd=Collision(key,Hashtable);Hashtableadd=key;6.查找关键字在哈希表中的存储位置(
4、SearchHash)int SearchHash(int key,int Hashtable)int add;add=Hash(key);if(Hashtableadd=key)return add;while(Hashtableadd!=key&Hashtableadd!=-1)add=Collision(key,Hashtable);return add;7.输出哈希表(PrintHash)(帮助调试用)void PrintHash(int Hashtable)int i;for(i=0;iLENGTH;i+)if(Hashtablei!=-1)printf(%3d:%dn,i+1,Ha
5、shtablei);8.求字符串长度(strlen)(函数库包含)以及求整数的绝对值(abs)(函数库包含)算法设计:1建立长度为LENGTH的哈希表Hash(LENGTH具体值由宏定义决定)。2输入要插入的字符串总数num(num小于等于LENGTH),再输入num个字符串,将这num个字符串的关键值key计算出来后插入哈希表中。3输出哈希表(帮助调试用,并非实验目的)。4依次查找这num个字符串对应的关键字在哈希表中位置,并统计冲突次数,记为count。根据公式计算负载因子和命中率(负载因子=表中填入的记录数/哈希表的长度,命中率=元素个数/查找次数)。输出元素个数、冲突次数、查找次数、负
6、载因子、命中率。源程序(将LENGTH定义为60,实际调试中定义为60和100各一次):#include#include#include#include#define LENGTH 60 /*实际调试中定义为60和100各一次*/int Hash(int key);int Collision(int key,int Hashtable);void InitHash(int Hashtable);void InsertHash(int key,int Hashtable);int SearchHash(int key,int Hashtable);void PrintHash(int Hasht
7、able);int count=0,num=0;void main()int i,key,collapsetime,searchtime,HashLENGTH;float loadelem,hitprob;char namesLENGTH20;InitHash(Hash);printf(input the number of names(number=%d).n,LENGTH);scanf(%d,&num);printf(input names.n);for(i=0;inum;i+)scanf(%s,&namesi);key=(abs(int)namesi0-(int)namesi1+(int
8、)namesistrlen(namesi)/2-(int)namesistrlen(namesi)-2-(int)namesistrlen(namesi)-1)*strlen(namesi);/*上式为关键字求。:关键字key=abs(字符串首位ASCII码值-第二位ASCII码值+第(n/2+1)位ASCII码值-最后一位ASCII码值-倒数第二位ASCII码值)*字符串长度(abs为求整数绝对值的函数)。*/InsertHash(key,Hash);count=0;/*将count置零,清除插入过程中产生的冲突次数*/PrintHash(Hash);for(i=0;inum;i+)k
9、ey=(abs(int)namesi0-(int)namesi1+(int)namesistrlen(namesi)/2-(int)namesistrlen(namesi)-2-(int)namesistrlen(namesi)-1)*strlen(namesi);/*上式为关键字求。酵*/SearchHash(key,Hash);collapsetime=count;searchtime=count+num;loadelem=(float)num/LENGTH;hitprob=(float)num/searchtime;printf(元素个数:%dn,num);printf(冲突次数
10、:%dn,collapsetime);printf(查找次数:%dn,searchtime);printf(负载因子:%fn,loadelem);printf(命中率=总人数/查找数:%fn,hitprob);int Hash(int key)/*处理关键字的哈:*/return(key*key)/1000%LENGTH);int Collision(int key,int Hashtable)/*处理哈希表中冲突*/int i;for(i=1;i=LENGTH;i+)if(Hashtable(Hash(key)+i)%LENGTH=-1)return(Hash(key)+i)%LENGT
11、H);count+;/*统计冲突次数*/void InitHash(int Hashtable)/*初始化哈希表*/int i;for(i=0;iLENGTH;i+)Hashtablei=-1;void InsertHash(int key,int Hashtable)/*向哈希表中插入关键字*/int add;add=Hash(key);if(Hashtableadd=-1)Hashtableadd=key;elseadd=Collision(key,Hashtable);/*处理哈希表中冲突,注意:这里count也会计数,所以结束插入过程后应将count清零*/Hashtableadd=k
12、ey;int SearchHash(int key,int Hashtable)/*查找关键字在哈希表中的地址*/int add;add=Hash(key);if(Hashtableadd=key)return add;while(Hashtableadd!=key&Hashtableadd!=-1)add=Collision(key,Hashtable);/*处理哈希表中冲突*/return add;void PrintHash(int Hashtable)/*输出哈希表(帮助调试用)*/int i;for(i=0;iLENGTH;i+)if(Hashtablei!=-1)printf(%3
13、d:%dn,i+1,Hashtablei);截图第一组(LENGTH宏定义为60)输入:50个名字(字符串,采用英文单词)输出结果:输出:1.哈希表(帮助调试用)2.实验要求的各项参数元素个数:50,冲突次数:77,查找次数:127,负载因子:0.833333,命中率:0.393701.根据线性探测在散列成功查找时的公式ASL=12(1+11-)(其中,ASL表示平均查找长度,表示负载因子)。ASL=3.5,总平均查找次数为175,平均命中率为0.285714。显然,本程序实现的哈希查找在本次试验中优于平均状况。截图第二组(LENGTH宏定义为100)输入:50个名字(字符串,采用英文单词)输
14、出:1.哈希表(帮助调试用)2.实验要求的各项参数元素个数:50,冲突次数:27,查找次数:77,负载因子:0.500000,命中率:0.649351.根据线性探测在散列成功查找时的公式ASL=12(1+11-)(其中,ASL表示平均查找长度,表示负载因子)。ASL=1.5,总平均查找次数为75,平均命中率为0.666667。显然,本程序实现的哈希查找在本次试验中略逊于平均状况。附:输入的50个字符串abandonalacrityarchipelagoassessattenuatebigotbrakebuffooncircumspectcommittedconfrontconstringeco
15、nvictioncovendefusedetractdimensiondiscreditdoldrumsencomiumennobleepitheteuphemismexcursivefeasiblesensitiveshrewdstationarygreasyobscurepersistentprevalentprominentrelevantvulnerableinevitablypresumablyguaranteelegislationmechanismpatternessencereputationthresholdoverwhelmhinderwreckwiltfloutnovel实验总结与心得:构造合适的关键字和哈:杂谠黾用新史浅9丶,哈:钪昭∮昧似椒饺≈蟹。而关键字,对于字符串形式的存储元素作用相当重要。起初打算用(字符串首位ASCII码值*字符串长度)作为关键字,但发现命中率不到0.2;因此加上了最后一位和第二位,命中率可提高到0.26(仍不如平均状况);加上倒数第二位提高到0.3,最后加上第(n/2+1)位形成了五位相加减的状况,将命中率提高到了现在的0.39(以上所述的状况是LENGTH为60,输入字符串数目为50,这也是调试所用的宏定义状况,第二组输出结果是将LENGTH直接改为100时实现的)。这充分表明了本次实验需要一定的耐心。.;
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
kok电子竞技:最新文档
- 社交媒体时代的内容品牌传播策略
- 减肥产品效果口碑传播行业跨境出海战略研究kok电子竞技
- 天然皮革制座套企业县域市场拓展与下沉战略研究kok电子竞技
- 金及镀金废碎料企业数字化转型与智慧升级战略研究kok电子竞技
- 多功能哑铃架行业深度调研及发展战略咨询kok电子竞技
- 家用便携式洗鼻器行业跨境出海战略研究kok电子竞技
- 镀镍光亮剂791企业ESG实践与创新战略研究kok电子竞技
- 科技公司进军影视产业的策略分析与前景预测
- TS公司一线员工薪酬体系优化研究
- 20以内乘法除法口算练习册1000道可打印
- (人教PEP2024kok电子竞技)英语一kok电子竞技上册Unit 5 教学课件(新教材)
- 腰椎术后失败综合征
- 广告学概论课件
- 贵州人民kok电子竞技五kok电子竞技劳动下册全册教案
- 2024年高考英语易错题 阅读理解:推理判断题4大陷阱(教师kok电子竞技新高考专用)
- 医院环境卫生学监测和院感控制课件
- 《力与形变》教学课件(一)
- 湖北省2024年村干部定向考试真题
- 部编kok电子竞技三kok电子竞技语文下册期中试卷及参考答案
- JT-T-1199.1-2018绿色交通设施评估技术要求第1部分:绿色公路
- 桃花红杏花红混声合唱简谱
评论
0/150
提交评论