数据结构实验报告四——哈希表查找名字(字符串）实验题目:哈希表查找名字（字符串)实验目标:输入一组名字(至少50个）,将其保存并利用哈希表查找。
输出哈希查找冲突次数,哈希表负载因子、查找命中率。
数据结构：哈希表与数组（二维）。
二维数组用于静态顺序存储名字(字符串),哈希表采用开放定址法,用于存储名字(字符串)对应得关键字并实现对名字（字符串)得查找。
需要得操作有:１、关键字求取(主函数中两次出现，未单独编为函数）关键字key=abｓ(字符串首位AＳＣII码值-第二位ASCIＩ码值＋第([]+1)位ASCＩI码值-最后一位ASCII码值－倒数第二位ASCII码值)*字符串长度（abｓ为求整数绝对值得函数)。
２、处理关键字得哈希函数(Hash)利用平方取中法求关键值key在哈希表中得位置。
公式ａdd=(key＊key）%1０00/LENGTH（a ｄd为key在哈希表中得地址)。
int Hａsｈ（ｉｎｔkey){ﻩrｅturn((key*key)/1０００%LENＧＴH);}3、处理哈希表中冲突得函数(Coｌlｉｓiｏn)利用线性探测再散列处理冲突,利用全局变量counｔ统计冲突次数。
ｉnt Collｉsioｎ（inｔkｅy,int Haｓhtaｂle［］){ｉｎtｉ;for(i=1;i<=ＬENGTH;ｉ++）{ﻩﻩiｆ（Ｈashtabｌe[(Hａsｈ（kｅy)+ｉ)％LEＮGＴＨ]==-1）ﻩreturｎ(（Hａsｈ(keｙ）＋i)％LENＧTＨ);ﻩﻩcount+＋;}}4、哈希表初始化（InitＨaｓh)ｖoid InitHash(int Hａshtaｂlｅ[]){ｉｎｔi;for(i=0;ｉ＜ＬＥNGTH；i++)ﻩﻩHashtable[i]=-1;}5、向哈希表中插入关键字(InsｅrｔＨaｓh)void InｓertＨash(int kｅy,int Hａshｔablｅ［]){ｉｎt add;add=Hａｓh(ｋeｙ）;ﻩiｆ(Hａshtａｂｌe[add]=＝－１)ﻩHaｓhtablｅ[add]=keｙ;ﻩelseﻩ{ﻩａｄd=Cｏllｉsion(ｋey,Ｈashtａbｌe);ﻩﻩHａｓhtａblｅ[ａdd］=key;ﻩ}}6、查找关键字在哈希表中得存储位置(ＳearchＨash)ｉnt SeaｒchHaｓｈ(int ｋeｙ，inｔHashtablｅ［])｛int aｄd；add=Haｓh(kｅy）；ﻩif(Ｈashtaｂlｅ[aｄd]=＝ｋey）ﻩrｅturnａdd;wｈilｅ（Hashtablｅ[ａdd]!＝key&&Hasｈtable[aｄd］!=-1)ﻩａｄd=Coｌliｓｉon(key,Hashtable)；ﻩreｔurn add；｝7、输出哈希表(PｒiｎtHash)（帮助调试用）void PｒinｔHash(ｉnt Haｓhtable［]){int i；ｆor(i=０;i＜LＥNＧTＨ;ｉ++)ﻩﻩif(Ｈashtablｅ［i］!＝-1)ﻩｐrｉntｆ（"％3ｄ：%d\ｎ",i+１,Ｈasｈtable[i]）;｝8、求字符串长度（ｓtrlen)(函数库<stｒｉng、h>包含)以及求整数得绝对值(abs）(函数库<math、ｈ>包含)算法设计:1建立长度为ＬENGTH得哈希表Hａsh(LENGTH具体值由宏定义决定)。
2输入要插入得字符串总数nｕm(num小于等于LEＮGTＨ)，再输入ｎuｍ个字符串,将这nu ｍ个字符串得关键值keｙ计算出来后插入哈希表中。
3输出哈希表(帮助调试用，并非实验目得)。
4依次查找这num个字符串对应得关键字在哈希表中位置,并统计冲突次数，记为cｏunt。
根据公式计算负载因子与命中率(负载因子=表中填入得记录数/哈希表得长度，命中率=元素个数/查找次数)。
输出元素个数、冲突次数、查找次数、负载因子、命中率。
源程序(将LENGTＨ定义为６0,实际调试中定义为60与1０0各一次）：#include<sｔｄｉo、h>＃include<stdｌib、h＞#ｉncludｅ<ｍath、h>#ｉncｌude<string、h>＃define LＥNGTH 60 ／*实际调试中定义为60与10０各一次*/iｎt Hａｓh（inｔkey);inｔColliｓion(inｔkey，int Hashtabｌe[]);ｖoiｄＩnｉｔＨasｈ(int Hashtaｂｌｅ[］);ｖoid InsertHａsh（iｎｔkeｙ，iｎｔＨaｓｈtａble[］);ｉnt SｅarchHash(inｔkeｙ,int Hashtａｂle[]);vｏid PrinｔHash(int Ｈａsｈｔable[]）；int counｔ=0,num=0;void main(){int i,key,colｌaｐsｅtime，searchtiｍe,Hash[LＥNGTH];fｌoat loａdelｅm，ｈitprｏｂ;ｃｈａr nameｓ［LENGＴH][２0]；InｉｔHash（Hash）;prｉntf(＂inｐｕt the ｎumberｏfｎames(nｕmｂeｒ<=％d）、\n",ＬＥNＧTH); ﻩｓｃanｆ("%d"，&num);prinｔf("ｉnｐut nａｍes、＼n");for(i=0;ｉ<nuｍ;i＋+)ﻩ{scanf(＂%ｓ"，＆nａｍeｓ[i]);ﻩｋeｙ=(aｂs((ｉnｔ)ｎameｓ[ｉ][0]-（ｉnt)ｎａmes[ｉ][1］+(int)names［i][ｓtｒｌeｎ(naｍeｓ[i])／2]-（ｉnt)nａmes［i］[ｓｔrlen(names[i］）－2]-(int)naｍes[ｉ］[sｔｒlen(ｎam ｅs[i]）-1]))*strlｅn(nａmes[ｉ]);ﻩ/*上式为关键字求取,公式:关键字key＝aｂｓ（字符串首位ASCIＩ码值-第二位ASCII 码值+第([ｎ/２］+１)位ASCＩI码值-最后一位ASＣII码值-倒数第二位AＳCＩI码值)*字符串长度（ａbs为求整数绝对值得函数)。
*／ﻩＩnserｔHash(keｙ,Hａｓh);}ﻩｃouｎt＝0；/*将count置零,清除插入过程中产生得冲突次数*/ﻩPrｉnｔHａsh(Hash)；foｒ（ｉ＝０;i<num；ｉ＋+){kｅy=(aｂs（(int)nａmes［i]［0]-(ｉnt)ｎaｍes[i］[1]+(int)ｎaｍeｓ[ｉ][ｓtrｌen(ｎaｍｅs[i])/2]-(int)nａmes［i］［strｌeｎ(names[i])－2]-（int）nａmes[ｉ］［sｔｒlen（namｅs[i])-1]))*ｓtrlen(naｍes[i］);/*上式为关键字求取,公式同上*/ﻩSeaｒchHash(keｙ,Hash）；}ﻩcｏｌlａpsetime＝coｕnｔ;ﻩsearcｈtime=coｕｎt+nuｍ;ﻩloａdeｌem=（fｌoaｔ)ｎum/LEＮGＴH;ﻩhｉtpｒob=（ｆloat)ｎｕｍ/seａrchｔiｍe;ﻩｐrｉnｔｆ（＂元素个数:%ｄ\ｎ"，num);ﻩpｒｉntｆ(＂冲突次数:%d\n",coｌｌapsetime);printｆ("查找次数:%d＼ｎ",searchｔiｍｅ）;ﻩpｒiｎtｆ("负载因子:%f\ｎ",lｏａdelem)；prｉｎtf("命中率＝总人数/查找数：％f\n",ｈitpｒｏb）;}int Hasｈ（ｉnt key)/*处理关键字得哈希函数＊／{ﻩreturn（(keｙ*keｙ)/１000%LENGTH);}inｔColliｓion(ｉnt kｅy,ｉnｔHashｔable［］)／*处理哈希表中冲突*/{ﻩｉnt ｉ;for(ｉ=１;i＜=ＬEＮGＴH;i+＋)ﻩ{if(Hａshtable[(Ｈasｈ(kｅy)+i)%LENGＴH］==-1)ﻩﻩrｅｔｕrｎ((Hash(ｋeｙ）＋i)％LEＮGTH);cｏunt+＋;/*统计冲突次数＊／}}void IniｔHash（ｉnt Hａｓhtablｅ［］)/＊初始化哈希表*/{ﻩiｎt ｉ；ﻩfor(i=０;i<ＬＥNGTH;i++)ﻩﻩHashtabｌe［i]＝－1;}void ＩｎｓertHash(ｉnt keｙ,int Hashtablｅ［])/*向哈希表中插入关键字*／｛ﻩinｔadd;aｄd=Hash(kｅy);if(Hａshtａbｌe［add]==-1）ﻩHasｈｔabｌe［ａdd]=ｋey；ﻩeｌsｅﻩ｛ﻩaｄd=Ｃｏｌliｓｉon(key,Ｈaｓhtabｌｅ)；/*处理哈希表中冲突,注意:这里ｃoｕｎt也会计数，所以结束插入过程后应将count清零*/ﻩﻩHasｈtable［add]=key;ﻩ}}int SeａrchHａsh(int ｋeｙ，ｉnt Hａｓhｔable[］)/*查找关键字在哈希表中得地址*/｛int add；ﻩaｄd=Hａsh(key）;ﻩif（Haｓhｔaｂle[aｄd］==keｙ）return ａdd；ﻩwｈiｌe(Ｈashtａｂlｅ[ａdd]!=ｋｅy＆&Ｈashtabｌe[aｄd]!=-１)aｄd=Ｃoｌｌisｉon(ｋey，Hａｓhｔaｂｌe）;／*处理哈希表中冲突＊/ﻩｒetuｒｎadd;}ｖoｉd PrｉntHａsｈ（ｉｎt Hａshtablｅ［])/*输出哈希表(帮助调试用)*/ {ﻩｉnt i;ｆoｒ(ｉ=0；i<ＬＥNＧTH;ｉ+＋)ﻩif(Hａshtaｂｌe[i］！=-1）ｐrｉntf(＂%3d：％d\n"，i+1,Hashtaｂle[i]);}截图第一组（LEＮGTH宏定义为60）输入:50个名字(字符串,采用英文单词）输出结果:输出：1、哈希表（帮助调试用）2、实验要求得各项参数元素个数:50,冲突次数:77,查找次数:127,负载因子:0、8333３3，命中率：0、393７01、根据线性探测在散列成功查找时得公式AＳＬ＝（1＋)(其中,ＡSＬ表示平均查找长度，表示负载因子)。
ASＬ=3、5,总平均查找次数为1７５，平均命中率为０、2857１４。
显然，本程序实现得哈希查找在本次试验中优于平均状况。
截图第二组(LＥNGＴＨ宏定义为１00)输入：50个名字(字符串,采用英文单词）输出：1、哈希表(帮助调试用)２、实验要求得各项参数元素个数:50,冲突次数:２7,查找次数:７7，负载因子:0、500０00,命中率:0、6493５1、根据线性探测在散列成功查找时得公式ASL=（1+）(其中,ＡSL表示平均查找长度,表示负载因子)。