《哈希表及其查找》由会员分享，可在线阅读，更多相关《哈希表及其查找（3页珍藏版）》请在金锄头文库上搜索。
1、云南高校数学与统计学试验教学中心试验报告云南高校数学与统计学试验教学中心实 验 报 告课程名称：数据构造与算法学期：2021-2021 学年其次学期成果：指导教师： 汪苹同学姓名：同学学号：试验名称：哈希表及其查找试验要求：必做试验学时：4+2学时试验编号：4及 5试验日期： 第 6-8 周完成日期：学院： 数学与统计学院专业 ：信息与计算科学班级：2021 级一、试验目的通过试验把握散列存储的根本概念，进展哈希问题的处理，同时附带进展字符串的处理的练习。二、试验内容为某单位的人名n=30 人设计一个哈希表，使得平均查找长度2，要求完成相应的哈希建表和查表。三、试验环境Windows XP程序
2、设计语言 C四、试验过程1. 试验要求：1、 设人名长度10 个字符，用二维字符数组存储哈希表：char hash 10;2、 要求哈希函数用除留余数法，并用人名的 10 个字符代码和作为分子； 用补偿性线性探测再散列处理冲突。3、 依题意有： 平均查找长度=1+1/(1-)/2 2，取=0.6，由此哈希表长 m=n/=30/0.6=50;所以有char hashlist 5010； 令：除留余数法中的 P 取 47；补偿性线性探测再散列的地址：j=(j+Q)% m 中的 Q 取 17。4、 对程序构造的要求： 要求为哈希建表和哈希查表分别编写和设计相应的函数：createhash( . .
3、);hashsearch(.)； 再设计一个哈希函数表的输出函数 printhash( )，对构造的哈希表进展输出，留意输出格式要在屏幕好看，先输出序号130，再输出该序号的人名或 null，每行输出 10 项，共输出 5 行。 还应有一个初始化 char hashlist 5010的函数 Inithashlist( )， 初始时将 50 个人名全赋值为 null.5、 在主函数中：调用 Inithashlist( )初始化哈希表；第 3 页 共 3 页调用 createhash( hashlist，30 )构造哈希表； 调用 printhash( )输出所建立的哈希表；承受待查找人名到字符数
4、组 name ；调用 hashsearch(hashlist，name )进展查找，假设查到显示“found！“并显示人名在数组中的序号；假设未查到显示“no found！“测试数据：健表时输入以下数据：JanuaryFebruarymarchaprilmayjunejulyaugustseptember OctoberNovemberDecemberSundayMondayTuesdaywednesdaythurdayf ridaySaturday Onetwothreefourfivesixserveeightninetendata实现提示：参照杨秀清主编数据构造西安电子科技高校出版社 P
5、171。附加要求：1. 在哈希查表时考虑插入。当查找失败，且查找时的冲突次数规定数字(如表长之半)时插入待查找的字符串，并给出“已插入”的显示；2. 在哈希查表时考虑删除。承受待删除人名到字符数组 name ；在 hash 表中找到， 并删除之。须留意，删除后不能影响以后的查找。2. 试验设计的各流程图：以下内容请同学认真填写3. 程序设计的关键代码及解释：留意对程序代码给出必要的注解，保证可读性4. 试验程序运行结果的粘贴：必需是你的程序运行结果五、试验总结1. 遇到的问题及分析：请结合你的试验过程认真总结2. 解决方案列出遇到的问题和解决方法，列出没有解决的问题：3. 体会和收获。六、参考文献数据构造C 语言版 严蔚敏、吴伟民编著清华高校出版社出版国家级规划教材数据构造题集C 语言版 严蔚敏、吴伟民编著清华高校出版社出版数据构造扬秀金 西安电子科技大出版社 高等学校电子信息类教材数据构造有用教程C/C+描述 徐孝凯编著清华高校出版社出版数据构造 许卓群、张乃孝等编著高等训练出版社出版算法与数据构造 付清祥、王小东编著电子工业出版社出版数据构造极其应用教程严蔚敏、陈文博编著清华高校出版社出版七、教师评语：
