哈希表實驗報告

數(shù)據(jù)構(gòu)造實驗報告四——哈希表查找名字（字符串）實驗題目：哈希表查找名字（字符串）實驗?zāi)繕耍狠斎胍唤M名字（最少50個），將其保存并利用哈希表查找。輸出哈希查找矛盾次數(shù)，哈希表負載因子、查找命中率。數(shù)據(jù)構(gòu)造：哈希表和數(shù)組（二維）。二維數(shù)組用于靜態(tài)序次儲藏名字（字符串），哈希表采用開放定址法，用于儲藏名字（字符串）對應(yīng)的要點字并實現(xiàn)對名字（字符串）的查找。需要的操作有：要點字求?。ㄖ骱瘮?shù)中兩次出現(xiàn)，未單獨編為函數(shù)）要點字key=abs（字符串首位ASCII碼值-第二位ASCII碼值+第（[]+1）位ASCII碼值-最后一位ASCII碼值-倒數(shù)第二位ASCII碼值）*字符串長度（abs為求整數(shù)絕對值的函數(shù)）。辦理要點字的哈希函數(shù)（Hash）利用平方取中法求要點值key在哈希表中的地址。公式add=（key*key）%1000/LENGTHadd為key在哈希表中的地址）。intHash(intkey){return((key*key)/1000%LENGTH);}3.辦理哈希表中矛盾的函數(shù)（Collision）利用線性探測再散列辦理矛盾，利用全局變量count統(tǒng)計矛盾次數(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;}向哈希表中插入要點字（InsertHash）voidInsertHash(intkey,intHashtable[]){intadd;1add=Hash(key);f(Hashtable[add]==-1)Hashtable[add]=key;else{add=Collision(key,Hashtable);Hashtable[add]=key;}}查找要點字在哈希表中的儲藏地址（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.求字符串長度（strlen）（函數(shù)庫<>包含）以及求整數(shù)的絕對值（abs）（函數(shù)庫<>包含）算法設(shè)計：1建立長度為LENGTH的哈希表Hash（LENGTH詳盡值由宏定義決定）。2輸入要插入的字符串總數(shù)num（num小于等于LENGTH），再輸入num個字符串，將這num個字符串的要點值key計算出來后插入哈希表中。3輸出哈希表（幫助調(diào)試用，其實不是實驗?zāi)康模?依次查找這num個字符串對應(yīng)的要點字在哈希表中地址，并統(tǒng)計矛盾次數(shù)，記為count。依照公式計算負載因子和命中率（負載因子=表中填入的記錄數(shù)/哈希表的長度，命中率=元素個數(shù)/查找次數(shù)）。輸出元素個數(shù)、矛盾次數(shù)、查找次數(shù)、負載因子、命中率。源程序（將LENGTH定義為60，實質(zhì)調(diào)試中定義為60和100各一次）：#include<>#include<>#include<>#include<>#defineLENGTH60/*實質(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]);/*上式為要點字求取，公式：要點字碼值+第（[n/2]+1）位ASCII碼值-最后一位長度（abs為求整數(shù)絕對值的函數(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]);/*上式為要點字求取，公式同上*/SearchHash(key,Hash);}collapsetime=count;searchtime=count+num;oadelem=(float)num/LENGTH;hitprob=(float)num/searchtime;printf("元素個數(shù)：%d\n",num);3printf("矛盾次數(shù)：%d\n",collapsetime);printf("查找次數(shù)：%d\n",searchtime);printf("負載因子：%f\n",loadelem);printf("命中率=總?cè)藬?shù)/查找數(shù)：%f\n",hitprob);}intHash(intkey)/*辦理要點字的哈希函數(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)計矛盾次數(shù)*/}}voidInitHash(intHashtable[])/*初始化哈希表*/{inti;for(i=0;i<LENGTH;i++)Hashtable[i]=-1;}voidInsertHash(intkey,intHashtable[])/*向哈希表中插入要點字*/{intadd;add=Hash(key);f(Hashtable[add]==-1)Hashtable[add]=key;else{add=Collision(key,Hashtable);/*辦理哈希表中矛盾，注意：這里count也會計數(shù)，因此結(jié)束插入過程后應(yīng)將count清零*/Hashtable[add]=key;}}intSearchHash(intkey,intHashtable[])/*查找要點字在哈希表中的地址*/{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個名字（字符串，采用英文單詞）輸出結(jié)果：輸出：哈希表（幫助調(diào)試用）5實驗要求的各項參數(shù)元素個數(shù)：50，矛盾次數(shù)：77，查找次數(shù)：127，負載因子：，命中率：.依照線性探測在散列成功查找時的公式ASL=(1+)（其中，ASL表示平均查找長度，表示負載因子）。ASL=，總平均查找次數(shù)為175，平均命中率為。顯然，本程序?qū)崿F(xiàn)的哈希查找在本次試驗中優(yōu)于平均狀況。截圖第二組（LENGTH宏定義為100）輸入：50個名字（字符串，采用英文單詞）6輸出：哈希表（幫助調(diào)試用）實驗要求的各項參數(shù)元素個數(shù)：50，矛盾次數(shù)：27，查找次數(shù)：77，負載因子：，命中率：.7依照線性探測在散列成功查找時的公式ASL=(1+)（其中，ASL表示平均查找長度，表示負載因子）。ASL=，總平均查找次數(shù)為75，平均命中率為。顯然，本程序?qū)崿F(xiàn)的哈希查找在本次試驗中略遜于平均狀況。附：輸入的50個字符串a(chǎn)bandonalacrityarchipelagoassessattenuatebigotbrakebuffooncircumspectcommittedconfrontconstringeconvictioncovendefusedetractdimensiondiscreditdoldrumsencomiumennoble8epitheteuphemismexcursivefeasiblesensitiveshrewdstationarygreasyobscurepersistentprevalentprominentrelevantvulnerableinevitablypresumablyguaranteelegislationmechanismpatternessencereputationthresholdoverwhelmhinderwreckwiltfloutnovel實驗總結(jié)與心得：構(gòu)造合適的要點字和哈希函數(shù)對于增加命中率特別要點，哈希函數(shù)最后