數(shù)據(jù)結(jié)構(gòu)哈希表實驗報告

《數(shù)據(jù)結(jié)構(gòu)哈希表實驗報告》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、HUNANUNIVERSITY課程實習(xí)報告題目：哈希表學(xué)生姓名唐鵬學(xué)生學(xué)號201208080216專業(yè)班級物聯(lián)2班指導(dǎo)老師吳帆完成日期2014年4月2日7一、需求分析：1.本程序來自于圖書館靠書名來檢索想要查找的書問題。2.本程序要求：（1）根據(jù)輸入建立圖書名稱表，采用創(chuàng)建散列表實現(xiàn)。（2）建散列表后，如果想要查找的數(shù)據(jù)在散列表中輸出yes否則輸出no。二、哈希表簡介結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定存儲在f(K）的位置上。由此，不需比較便可直接取得所查記錄。這個對應(yīng)關(guān)系f稱為散列函數(shù)(Hashfunct

2、ion），按這個思想建立的表為散列表。*對不同的關(guān)鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2），這種現(xiàn)象稱沖突。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞。*綜上所述，根據(jù)散列函數(shù)H(key）和處理沖突的方法將一組關(guān)鍵字映象到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”，作為這條記錄在表中的存儲位置，這種表便稱為散列表，這一映象過程稱為散列造表或散列，所得的存儲位置稱散列地址。這個現(xiàn)象也叫散列桶，在散列桶中，只能通過順序的方式來查找，一般只需要查找三

3、次就可以找到?？茖W(xué)家計算過，當(dāng)負載因子(loadfactor)不超過75%，查找效率最高。*若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)（UniformHashfunction），這就是使關(guān)鍵字經(jīng)過散列函數(shù)得到一個“隨機的地址”，從而減少沖突。程序設(shè)計流程程序思想(一)哈希函數(shù)unsignedinthash_BKDE(char*str)生成映射地址，成為散列表的編號。(二)哈希表HashTable::HashTable()通過數(shù)組儲存元

4、素(三)插入函數(shù)voidHashTable::insert(char*c)插入字符串，先計算要插入字符串生成的映射地址，然后在相應(yīng)的地址插入，如果沒有空位查找空位插入。(四)查找函數(shù)boolHashTable::find(char*c)進行查找，先計算要生成字符串的地址，再到散列表中進行查找比較。(五)主函數(shù)main（）1)輸入：輸入散列表內(nèi)容和要查找的數(shù)據(jù)個數(shù)和數(shù)據(jù)2)輸出模塊：散列表查找的結(jié)果。71)建散列表并查找：建立散列表并遞歸查找流程圖7三.實驗源程序：#include#incl

5、ude#includeusingnamespacestd;unsignedinthash_BKDE(char*str)//哈希函數(shù)，題目給出{//初始種子seed可取31131131313131131313etc..unsignedintseed=131;unsignedinthash=0;while(*str)7{hash=hash*seed+(*str++);}return(hash&0x7FFFFFFF);}doublek=(double)(rand()%999)/100

6、0;//隨機生成小數(shù)隨機數(shù)0

7、able//哈希表類{public:HashTable();~HashTable();voidinsert(char*c);boolfind(char*c);private:char**Arr;//二維數(shù)組用于保存字符串書名intArrSize;//散列表單元個數(shù)在此為2^15=32768};HashTable::HashTable(){ArrSize=32768;Arr=newchar*[64];for(inti=0;i<64;i++){Arr[i]=newchar[100];Arr[i]=NULL;}}H

8、ashTable::~HashTable(){for(inti=0;i<64;i++)delete[]Arr[i];delete[]Arr;7}voidHashTable::insert(char*c)//插入到哈希表{unsignedintpos=Hash(c);//計算散列地址位置while(Arr[pos]!=NULL)pos=(pos+1);//解決沖突的辦法，尋找空位，向后面挪動一個Arr