哈希表實(shí)驗(yàn)報(bào)告

數(shù)據(jù)構(gòu)造實(shí)驗(yàn)報(bào)告四——哈希表查找名字（字符串）實(shí)驗(yàn)題目：哈希表查找名字（字符串）實(shí)驗(yàn)?zāi)繕?biāo)：輸入一組名字（最少50個(gè)），將其保存并利用哈希表查找。輸出哈希查找矛盾次數(shù)，哈希表負(fù)載因子、查找命中率。數(shù)據(jù)構(gòu)造：哈希表和數(shù)組（二維）。二維數(shù)組用于靜態(tài)序次儲(chǔ)藏名字（字符串），哈希表采用開放定址法，用于儲(chǔ)藏名字（字符串）對(duì)應(yīng)的要點(diǎn)字并實(shí)現(xiàn)對(duì)名字（字符串）的查找。需要的操作有：要點(diǎn)字求?。ㄖ骱瘮?shù)中兩次出現(xiàn)，未單獨(dú)編為函數(shù)）要點(diǎn)字key=abs（字符串首位ASCII碼值-第二位ASCII碼值+第（[]+1）位ASCII碼值-最后一位ASCII碼值-倒數(shù)第二位ASCII碼值）*字符串長(zhǎng)度（abs為求整數(shù)絕對(duì)值的函數(shù)）。辦理要點(diǎn)字的哈希函數(shù)（Hash）利用平方取中法求要點(diǎn)值key在哈希表中的地址。公式add=（key*key）%1000/LENGTHadd為key在哈希表中的地址）。intHash(intkey){return((key*key)/1000%LENGTH);}3.辦理哈希表中矛盾的函數(shù)（Collision）利用線性探測(cè)再散列辦理矛盾，利用全局變量count統(tǒng)計(jì)矛盾次數(shù)。intCollision(intkey,intHashtable[]){inti;or(i=1;i<=LENGTH;i++){if(Hashtable[(Hash(key)+i)%LENGTH]==-1)return((Hash(key)+i)%LENGTH);count++;}}4.哈希表初始化（InitHash）voidInitHash(intHashtable[]){inti;or(i=0;i<LENGTH;i++)Hashtable[i]=-1;}向哈希表中插入要點(diǎn)字（InsertHash）voidInsertHash(intkey,intHashtable[]){intadd;1add=Hash(key);f(Hashtable[add]==-1)Hashtable[add]=key;else{add=Collision(key,Hashtable);Hashtable[add]=key;}}查找要點(diǎn)字在哈希表中的儲(chǔ)藏地址（SearchHash）intSearchHash(intkey,intHashtable[]){intadd;add=Hash(key);f(Hashtable[add]==key)returnadd;while(Hashtable[add]!=key&&Hashtable[add]!=-1)add=Collision(key,Hashtable);returnadd;}輸出哈希表（PrintHash）（幫助調(diào)試用）voidPrintHash(intHashtable[]){inti;or(i=0;i<LENGTH;i++)if(Hashtable[i]!=-1)printf("%3d:%d\n",i+1,Hashtable[i]);}8.求字符串長(zhǎng)度（strlen）（函數(shù)庫(kù)<>包含）以及求整數(shù)的絕對(duì)值（abs）（函數(shù)庫(kù)<>包含）算法設(shè)計(jì)：1建立長(zhǎng)度為L(zhǎng)ENGTH的哈希表Hash（LENGTH詳盡值由宏定義決定）。2輸入要插入的字符串總數(shù)num（num小于等于LENGTH），再輸入num個(gè)字符串，將這num個(gè)字符串的要點(diǎn)值key計(jì)算出來后插入哈希表中。3輸出哈希表（幫助調(diào)試用，其實(shí)不是實(shí)驗(yàn)?zāi)康模?依次查找這num個(gè)字符串對(duì)應(yīng)的要點(diǎn)字在哈希表中地址，并統(tǒng)計(jì)矛盾次數(shù)，記為count。依照公式計(jì)算負(fù)載因子和命中率（負(fù)載因子=表中填入的記錄數(shù)/哈希表的長(zhǎng)度，命中率=元素個(gè)數(shù)/查找次數(shù)）。輸出元素個(gè)數(shù)、矛盾次數(shù)、查找次數(shù)、負(fù)載因子、命中率。源程序（將LENGTH定義為60，實(shí)質(zhì)調(diào)試中定義為60和100各一次）：#include<>#include<>#include<>#include<>#defineLENGTH60/*實(shí)質(zhì)調(diào)試中定義為60和100各一次*/2intHash(intkey);intCollision(intkey,intHashtable[]);voidInitHash(intHashtable[]);voidInsertHash(intkey,intHashtable[]);intSearchHash(intkey,intHashtable[]);voidPrintHash(intHashtable[]);intcount=0,num=0;voidmain(){inti,key,collapsetime,searchtime,Hash[LENGTH];floatloadelem,hitprob;charnames[LENGTH][20];InitHash(Hash);printf("inputthenumberofnames(number<=%d).\n",LENGTH);scanf("%d",&num);printf("inputnames.\n");or(i=0;i<num;i++){scanf("%s",&names[i]);key=(abs((int)names[i][0]-(int)names[i][1]+(int)names[i][strlen(names[i])/2]-(int)names[i][strlen(names[i])-2]-(int)names[i][strlen(names[i])-1]))*strlen(names[i]);/*上式為要點(diǎn)字求取，公式：要點(diǎn)字碼值+第（[n/2]+1）位ASCII碼值-最后一位長(zhǎng)度（abs為求整數(shù)絕對(duì)值的函數(shù)）。*/InsertHash(key,Hash);

key=abs（字符串首位ASCII碼值-第二位ASCIIASCII碼值-倒數(shù)第二位ASCII碼值）*字符串}count=0;/*將count置零，除去插入過程中產(chǎn)生的矛盾次數(shù)*/PrintHash(Hash);or(i=0;i<num;i++){key=(abs((int)names[i][0]-(int)names[i][1]+(int)names[i][strlen(names[i])/2]-(int)names[i][strlen(names[i])-2]-(int)names[i][strlen(names[i])-1]))*strlen(names[i]);/*上式為要點(diǎn)字求取，公式同上*/SearchHash(key,Hash);}collapsetime=count;searchtime=count+num;oadelem=(float)num/LENGTH;hitprob=(float)num/searchtime;printf("元素個(gè)數(shù)：%d\n",num);3printf("矛盾次數(shù)：%d\n",collapsetime);printf("查找次數(shù)：%d\n",searchtime);printf("負(fù)載因子：%f\n",loadelem);printf("命中率=總?cè)藬?shù)/查找數(shù)：%f\n",hitprob);}intHash(intkey)/*辦理要點(diǎn)字的哈希函數(shù)*/{return((key*key)/1000%LENGTH);}intCollision(intkey,intHashtable[])/*辦理哈希表中矛盾*/{inti;for(i=1;i<=LENGTH;i++){if(Hashtable[(Hash(key)+i)%LENGTH]==-1)return((Hash(key)+i)%LENGTH);count++;/*統(tǒng)計(jì)矛盾次數(shù)*/}}voidInitHash(intHashtable[])/*初始化哈希表*/{inti;for(i=0;i<LENGTH;i++)Hashtable[i]=-1;}voidInsertHash(intkey,intHashtable[])/*向哈希表中插入要點(diǎn)字*/{intadd;add=Hash(key);f(Hashtable[add]==-1)Hashtable[add]=key;else{add=Collision(key,Hashtable);/*辦理哈希表中矛盾，注意：這里count也會(huì)計(jì)數(shù)，因此結(jié)束插入過程后應(yīng)將count清零*/Hashtable[add]=key;}}intSearchHash(intkey,intHashtable[])/*查找要點(diǎn)字在哈希表中的地址*/{intadd;add=Hash(key);f(Hashtable[add]==key)returnadd;4while(Hashtable[add]!=key&&Hashtable[add]!=-1)add=Collision(key,Hashtable);/*辦理哈希表中矛盾*/returnadd;}voidPrintHash(intHashtable[])/*輸出哈希表（幫助調(diào)試用）*/{inti;or(i=0;i<LENGTH;i++)if(Hashtable[i]!=-1)printf("%3d:%d\n",i+1,Hashtable[i]);}截圖第一組（LENGTH宏定義為60）輸入：50個(gè)名字（字符串，采用英文單詞）輸出結(jié)果：輸出：哈希表（幫助調(diào)試用）5實(shí)驗(yàn)要求的各項(xiàng)參數(shù)元素個(gè)數(shù)：50，矛盾次數(shù)：77，查找次數(shù)：127，負(fù)載因子：，命中率：.依照線性探測(cè)在散列成功查找時(shí)的公式ASL=(1+)（其中，ASL表示平均查找長(zhǎng)度，表示負(fù)載因子）。ASL=，總平均查找次數(shù)為175，平均命中率為。顯然，本程序?qū)崿F(xiàn)的哈希查找在本次試驗(yàn)中優(yōu)于平均狀況。截圖第二組（LENGTH宏定義為100）輸入：50個(gè)名字（字符串，采用英文單詞）6輸出：哈希表（幫助調(diào)試用）實(shí)驗(yàn)要求的各項(xiàng)參數(shù)元素個(gè)數(shù)：50，矛盾次數(shù)：27，查找次數(shù)：77，負(fù)載因子：，命中率：.7依照線性探測(cè)在散列成功查找時(shí)的公式ASL=(1+)（其中，ASL表示平均查找長(zhǎng)度，表示負(fù)載因子）。ASL=，總平均查找次數(shù)為75，平均命中率為。顯然，本程序?qū)崿F(xiàn)的哈希查找在本次試驗(yàn)中略遜于平均狀況。附：輸入的50個(gè)字符串a(chǎn)bandonalacrityarchipelagoassessattenuatebigotbrakebuffooncircumspectcommittedconfrontconstringeconvictioncovendefusedetractdimensiondiscreditdoldrumsencomiumennoble8epitheteuphemismexcursivefeasiblesensitiveshrewdstationarygreasyobscurepersistentprevalentprominentrelevantvulnerableinevitablypresumablyguaranteelegislationmechanismpatternessencereputationthresholdoverwhelmhinderwreckwiltfloutnovel實(shí)驗(yàn)總結(jié)與心得：構(gòu)造合適的要點(diǎn)字和哈希函數(shù)對(duì)于增加命中率特別要點(diǎn)，哈希函數(shù)最后