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

《哈希表實(shí)驗(yàn)報(bào)告》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告四——哈希表查找名字（字符串）實(shí)驗(yàn)題目：哈希表查找名字（字符串）實(shí)驗(yàn)?zāi)繕?biāo)：輸入一組名字（至少50個），將其保存并利用哈希表查找。輸出哈希查找沖突次數(shù)，哈希表負(fù)載因子、查找命中率。數(shù)據(jù)結(jié)構(gòu)：哈希表和數(shù)組（二維）。二維數(shù)組用于靜態(tài)順序存儲名字（字符串），哈希表采用開放定址法，用于存儲名字（字符串）對應(yīng)的關(guān)鍵字并實(shí)現(xiàn)對名字（字符串）的查找。需要的操作有：1.關(guān)鍵字求取（主函數(shù)中兩次出現(xiàn)，未單獨(dú)編為函數(shù)）關(guān)鍵字key=abs（字符串首位ASCII碼值-第二位ASCII碼值+第（[n2]+1）位ASCII碼值-最后一位ASCI

2、I碼值-倒數(shù)第二位ASCII碼值）*字符串長度（abs為求整數(shù)絕對值的函數(shù)）。2.處理關(guān)鍵字的哈希函數(shù)（Hash）利用平方取中法求關(guān)鍵值key在哈希表中的位置。公式add=（key*key）%1000/LENGTH（add為key在哈希表中的地址）。intHash(intkey){return((key*key)/1000%LENGTH);}3.處理哈希表中沖突的函數(shù)（Collision）利用線性探測再散列處理沖突，利用全局變量count統(tǒng)計(jì)沖突次數(shù)。intCollision(intkey,intHashtable[]){inti;

3、for(i=1;i<=LENGTH;i++){if(Hashtable[(Hash(key)+i)%LENGTH]==-1)return((Hash(key)+i)%LENGTH);count++;}}4.哈希表初始化（InitHash）voidInitHash(intHashtable[]){inti;for(i=0;i

4、key);if(Hashtable[add]==-1)Hashtable[add]=key;else{add=Collision(key,Hashtable);Hashtable[add]=key;}}6.查找關(guān)鍵字在哈希表中的存儲位置（SearchHash）intSearchHash(intkey,intHashtable[]){intadd;add=Hash(key);if(Hashtable[add]==key)returnadd;while(Hashtable[add]!=key&&Hashtable[add]!=-1)ad

5、d=Collision(key,Hashtable);returnadd;}7.輸出哈希表（PrintHash）（幫助調(diào)試用）voidPrintHash(intHashtable[]){inti;for(i=0;i包含）以及求整數(shù)的絕對值（abs）（函數(shù)庫包含）算法設(shè)計(jì)：1建立長度為LENGTH的哈希表Hash（LENGT

6、H具體值由宏定義決定）。2輸入要插入的字符串總數(shù)num（num小于等于LENGTH），再輸入num個字符串，將這num個字符串的關(guān)鍵值key計(jì)算出來后插入哈希表中。3輸出哈希表（幫助調(diào)試用，并非實(shí)驗(yàn)?zāi)康模?依次查找這num個字符串對應(yīng)的關(guān)鍵字在哈希表中位置，并統(tǒng)計(jì)沖突次數(shù)，記為count。根據(jù)公式計(jì)算負(fù)載因子和命中率（負(fù)載因子=表中填入的記錄數(shù)/哈希表的長度，命中率=元素個數(shù)/查找次數(shù)）。輸出元素個數(shù)、沖突次數(shù)、查找次數(shù)、負(fù)載因子、命中率。源程序（將LENGTH定義為60，實(shí)際調(diào)試中定義為60和100各一次）：#include

7、tdio.h>#include#include#include#defineLENGTH60/*實(shí)際調(diào)試中定義為60和100各一次*/intHash(intkey);intCollision(intkey,intHashtable[]);voidInitHash(intHashtable[]);voidInsertHash(intkey,intHashtable[]);intSearchHash(intkey,intHashtable[]);voidPrintHash(intH

8、ashtable[]);intcount=0,num=0;voidmain(){inti,key,collapsetime,searchtime,Hash[LENGTH];floatloadelem,hitprob;charnames