数据结构哈希表实验报告

HUNANUNIVERSITY课程实习报告 题 目： 哈希表 学生姓名 唐鹏学生学号 202408080216 专业班级 物联 2 班 指导老师吴帆完 成 日 期 2024 年 4 月 2 日 一、需 求 分 析：1. 本程序来自于图书馆靠书名来检索想要查找的书问题。2. 本程序要求：(1)根据输入建立图书名称表，采纳创建散列表实现.(2）建散列表后，假如想要查找的数据在散列表中输出 yes 否则输出 no.二、哈希表简介结构中存在关键字和 K 相等的记录，则必定存储在 f（K)的位置上。由此,不需比较便可直接取得所查记录。这个对应关系 f 称为散列函数(Hash function），按这个思想建立的表为散列表。＊ 对不同的关键字可能得到同一散列地址，即 key1≠key2，而 f（key1)=f（key2）,这种现象称冲突.具有相同函数值的关键字对该散列函数来说称做同义词。* 综上所述,根据散列函数 H（key）和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象”， 作为这条记录在表中的存储位置，这种表便称为散列表,这一映象过程称为散列造表或散列,所得的存储位置称散列地址。这个现象也叫散列桶,在散列桶中，只能通过顺序的方式来查找，一般只需要查找三次就可以找到。科学家计算过，当负载因子（load factor）不超过 75％，查找效率最高。＊ 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function）,这就是使关键字经过散列函数得到一个“随机的地址"，从而减少冲突。程序设计流程程序思想(一)哈希函数 unsigned int hash_BKDE(char ＊str)生成映射地址，成为散列表的编号。(二)哈希表 HashTable：：HashTable（）通过数组储存元素(三)插入函数 void HashTable：:insert（char＊c）插入字符串，先计算要插入字符串生成的映射地址，然后在相应的地址插入，假如没有空位查找空位插入。(四)查找函数 bool HashTable：：find(char＊c）进行查找，先计算要生成字符串的地址，再到散列表中进行查找比较。(五)主函数 main（）1)输入：输入散列表内容和要查找的数据个数和数据2)输出模块:散列表查找的结果。3)建散列表并查找：建立散列表并递归查找流程图三。实验源程序：＃include〈iostream〉＃include〈cstdlib〉#includeusing namespace std； unsigned int hash_BKDE（char ＊str）//哈希函数，...