哈希表实验报告

《哈希表实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、-.数据构造实验报告四——哈希表查找名字〔字符串〕实验题目：哈希表查找名字〔字符串〕实验目标：输入一组名字〔至少50个〕，将其保存并利用哈希表查找。输出哈希查找冲突次数，哈希表负载因子、查找命中率。数据构造：哈希表和数组〔二维〕。二维数组用于静态顺序存储名字〔字符串〕，哈希表采用开放定址法，用于存储名字〔字符串〕对应的关键字并实现对名字〔字符串〕的查找。需要的操作有：1.关键字求取〔主函数中两次出现，未单独编为函数〕关键字key=abs〔字符串首位ASCII码值-第二位ASCII码值+第〔[]+1〕位ASCII码

2、值-最后一位ASCII码值-倒数第二位ASCII码值〕*字符串长度〔abs为求整数绝对值的函数〕。2.处理关键字的哈希函数〔Hash〕利用平方取中法求关键值key在哈希表中的位置。公式add=〔key*key〕%1000/LENGTH〔add为key在哈希表中的地址〕。intHash(intkey){return((key*key)/1000%LENGTH);}3.处理哈希表中冲突的函数〔Collision〕利用线性探测再散列处理冲突，利用全局变量count统计冲突次数。intCollision(intkey,i

3、ntHashtable[]){inti;for(i=1;i<=LENGTH;i++){if(Hashtable[(Hash(key)+i)%LENGTH]==-1)return((Hash(key)+i)%LENGTH);count++;}}4.哈希表初始化〔InitHash〕voidInitHash(intHashtable[]){inti;for(i=0;i

4、tHashtable[]){intadd;-.可修编.-.add=Hash(key);if(Hashtable[add]==-1)Hashtable[add]=key;else{add=Collision(key,Hashtable);Hashtable[add]=key;}}6.查找关键字在哈希表中的存储位置〔SearchHash〕intSearchHash(intkey,intHashtable[]){intadd;add=Hash(key);if(Hashtable[add]==key)returnadd;

5、while(Hashtable[add]!=key&&Hashtable[add]!=-1)add=Collision(key,Hashtable);returnadd;}7.输出哈希表〔PrintHash〕〔帮助调试用〕voidPrintHash(intHashtable[]){inti;for(i=0;i包含〕以及

6、求整数的绝对值〔abs〕〔函数库包含〕算法设计：1建立长度为LENGTH的哈希表Hash〔LENGTH具体值由宏定义决定〕。2输入要插入的字符串总数num〔num小于等于LENGTH〕，再输入num个字符串，将这num个字符串的关键值key计算出来后插入哈希表中。3输出哈希表〔帮助调试用，并非实验目的〕。4依次查找这num个字符串对应的关键字在哈希表中位置，并统计冲突次数，记为count。根据公式计算负载因子和命中率〔负载因子=表中填入的记录数/哈希表的长度，命中率=元素个数/查找次数〕。输出元素

7、个数、冲突次数、查找次数、负载因子、命中率。源程序〔将LENGTH定义为60，实际调试中定义为60和100各一次〕：#include#include#include#include#defineLENGTH60/*实际调试中定义为60和100各一次*/-.可修编.-.intHash(intkey);intCollision(intkey,intHashtable[]);voidInitHash(intHashtable[]);voidIns

8、ertHash(intkey,intHashtable[]);intSearchHash(intkey,intHashtable[]);voidPrintHash(intHashtable[]);intcount=0,num=0;voidmain(){inti,key,collapsetime,searchtime,Hash[LENGTH];floatloadelem,h