哈希表实验报告

数据结构实验报告四哈希表查找名字（字符串）实验题目：哈希表查找名字（字符串） 实验目标：输入一组名字（至少50个），将其保存并利用哈希表查找。输出哈希查找冲突次数，哈希表负载因子、查找命中率。数据结构：哈希表和数组（二维）。二维数组用于静态顺序存储名字（字符串），哈希表采用开放定址法，用于存储名字（字符串）对应的关键字并实现对名字（字符串）的查找。需要的操作有：1.关键字求取（主函数中两次出现，未单独编为函数）关键字key=abs（字符串首位ASCII码值-第二位ASCII码值+第（n2+1）位ASCII码值-最后一位ASCII码值-倒数第二位ASCII码值）*字符串长度（abs为求整数绝对值的函数）。2.处理关键字的哈希函数（Hash）利用平方取中法求关键值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(Hash(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.查找关键字在哈希表中的存储位置（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,Hashtablei);8.求字符串长度（strlen）（函数库包含）以及求整数的绝对值（abs）（函数库包含）算法设计：1建立长度为LENGTH的哈希表Hash（LENGTH具体值由宏定义决定）。2输入要插入的字符串总数num（num小于等于LENGTH），再输入num个字符串，将这num个字符串的关键值key计算出来后插入哈希表中。3输出哈希表（帮助调试用，并非实验目的）。4依次查找这num个字符串对应的关键字在哈希表中位置，并统计冲突次数，记为count。根据公式计算负载因子和命中率（负载因子=表中填入的记录数/哈希表的长度，命中率=元素个数/查找次数）。输出元素个数、冲突次数、查找次数、负载因子、命中率。源程序（将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 Hashtable);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)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+)key=(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(冲突次数：%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)%LENGTH);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=key;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(%3d:%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个名字（字符串，采用英文单词）输出：1.哈希表（帮助调试用）2.实验要求的各项参数元素个数：50，冲突次数：27，查找次数：77，负载因子：0.500000，命中率：0.649351.根据线性探测在散列成功查找时的公式ASL=12(1+11-)（其中，ASL表示平均查找长度，表示负载因子）。ASL=1.5，总平均查找次数为75，平均命中率为0.666667。显然，本程序实现的哈希查找在本次试验中略逊于平均状况。附：输入的50个字符串abandonalacrityarchipelagoassessattenuatebigotbrakebuffooncircumspectcommittedconfrontconstringeconvictioncovendefusedetractdimensiondiscreditdoldrumsencomiumennobleepitheteuphemismexcursivefeasiblesensitiveshrewdstationarygreasyobscurepersistentprevalentprominentrelevantvulnerableinevitablypresumablyguaranteelegislationmechanismpatternessencereputationthresholdoverwhelmhinderwreckwiltfloutnovel实验总结与心得：构造合适的关键字和哈希函数对于增加命中率非常关键，哈希函数最终选用了平方取中法。而关键字，对于