數(shù)據(jù)結(jié)構(gòu)哈希表實(shí)驗(yàn)報(bào)告

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

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

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

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

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

7、able//哈希表類{public:HashTable();~HashTable();voidinsert(char*c);boolfind(char*c);private:char**Arr;//二維數(shù)組用于保存字符串書(shū)名intArrSize;//散列表單元個(gè)數(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);//計(jì)算散列地址位置while(Arr[pos]!=NULL)pos=(pos+1);//解決沖突的辦法，尋找空位，向后面挪動(dòng)一個(gè)Arr