哈希表實驗報告

1、.數(shù)據(jù)結構實驗報告四哈希表查找名字（字符串）實驗題目：哈希表查找名字（字符串） 實驗目標：輸入一組名字（至少50個），將其保存并利用哈希表查找。輸出哈希查找沖突次數(shù)，哈希表負載因子、查找命中率。數(shù)據(jù)結構：哈希表和數(shù)組（二維）。二維數(shù)組用于靜態(tài)順序存儲名字（字符串），哈希表采用開放定址法，用于存儲名字（字符串）對應的關鍵字并實現(xiàn)對名字（字符串）的查找。需要的操作有：1.關鍵字求?。ㄖ骱瘮?shù)中兩次出現(xiàn)，未單獨編為函數(shù)）關鍵字key=abs（字符串首位ASCII碼值-第二位ASCII碼值+第（n2+1）位ASCII碼值-最后一位ASCII碼值-倒數(shù)第二位ASCII碼值）*字符串長度（abs為求整數(shù)絕對

2、值的函數(shù)）。2.處理關鍵字的哈希函數(shù)（Hash）利用平方取中法求關鍵值key在哈希表中的位置。公式add=（key*key）%1000/LENGTH（add為key在哈希表中的地址）。int Hash(int key)return(key*key)/1000%LENGTH);3.處理哈希表中沖突的函數(shù)（Collision）利用線性探測再散列處理沖突，利用全局變量count統(tǒng)計沖突次數(shù)。int Collision(int key,int Hashtable)int i;for(i=1;i=LENGTH;i+)if(Hashtable(Hash(key)+i)%LENGTH=-1)return(H

3、ash(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.查找關鍵字在哈希表中的存儲位置（

4、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,Ha

5、shtablei);8.求字符串長度（strlen）（函數(shù)庫包含）以及求整數(shù)的絕對值（abs）（函數(shù)庫包含）算法設計：1建立長度為LENGTH的哈希表Hash（LENGTH具體值由宏定義決定）。2輸入要插入的字符串總數(shù)num（num小于等于LENGTH），再輸入num個字符串，將這num個字符串的關鍵值key計算出來后插入哈希表中。3輸出哈希表（幫助調試用，并非實驗目的）。4依次查找這num個字符串對應的關鍵字在哈希表中位置，并統(tǒng)計沖突次數(shù)，記為count。根據(jù)公式計算負載因子和命中率（負載因子=表中填入的記錄數(shù)/哈希表的長度，命中率=元素個數(shù)/查找次數(shù)）。輸出元素個數(shù)、沖突次數(shù)、查找次數(shù)、負

6、載因子、命中率。源程序（將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 Hasht

7、able);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

8、)namesistrlen(namesi)/2-(int)namesistrlen(namesi)-2-(int)namesistrlen(namesi)-1)*strlen(namesi);/*上式為關鍵字求取，公式：關鍵字key=abs（字符串首位ASCII碼值-第二位ASCII碼值+第（n/2+1）位ASCII碼值-最后一位ASCII碼值-倒數(shù)第二位ASCII碼值）*字符串長度（abs為求整數(shù)絕對值的函數(shù)）。*/InsertHash(key,Hash);count=0;/*將count置零，清除插入過程中產生的沖突次數(shù)*/PrintHash(Hash);for(i=0;inum;i+)k

9、ey=(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(元素個數(shù)：%dn,num);printf(沖突次數(shù)

10、：%dn,collapsetime);printf(查找次數(shù)：%dn,searchtime);printf(負載因子：%fn,loadelem);printf(命中率=總人數(shù)/查找數(shù)：%fn,hitprob);int Hash(int key)/*處理關鍵字的哈希函數(shù)*/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)%LENGT

11、H);count+;/*統(tǒng)計沖突次數(shù)*/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也會計數(shù)，所以結束插入過程后應將count清零*/Hashtableadd=k

12、ey;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(%3

13、d:%dn,i+1,Hashtablei);截圖第一組（LENGTH宏定義為60）輸入：50個名字（字符串，采用英文單詞）輸出結果：輸出：1.哈希表（幫助調試用）2.實驗要求的各項參數(shù)元素個數(shù)：50，沖突次數(shù)：77，查找次數(shù)：127，負載因子：0.833333，命中率：0.393701.根據(jù)線性探測在散列成功查找時的公式ASL=12(1+11-)（其中，ASL表示平均查找長度，表示負載因子）。ASL=3.5，總平均查找次數(shù)為175，平均命中率為0.285714。顯然，本程序實現(xiàn)的哈希查找在本次試驗中優(yōu)于平均狀況。截圖第二組（LENGTH宏定義為100）輸入：50個名字（字符串，采用英文單詞）輸

14、出：1.哈希表（幫助調試用）2.實驗要求的各項參數(shù)元素個數(shù)：50，沖突次數(shù)：27，查找次數(shù)：77，負載因子：0.500000，命中率：0.649351.根據(jù)線性探測在散列成功查找時的公式ASL=12(1+11-)（其中，ASL表示平均查找長度，表示負載因子）。ASL=1.5，總平均查找次數(shù)為75，平均命中率為0.666667。顯然，本程序實現(xiàn)的哈希查找在本次試驗中略遜于平均狀況。附：輸入的50個字符串abandonalacrityarchipelagoassessattenuatebigotbrakebuffooncircumspectcommittedconfrontconstringeco

15、nvictioncovendefusedetractdimensiondiscreditdoldrumsencomiumennobleepitheteuphemismexcursivefeasiblesensitiveshrewdstationarygreasyobscurepersistentprevalentprominentrelevantvulnerableinevitablypresumablyguaranteelegislationmechanismpatternessencereputationthresholdoverwhelmhinderwreckwiltfloutnovel實驗總結與心得：構造合適的關鍵字和哈希函數(shù)對于增加命中率非常關鍵，哈希函數(shù)最終選用了平方取中法。而關鍵字，對于字符