數據結構哈希表實驗報告

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

2、鍵字可能得到同一散列地址，即key1key2，而f(key1）=f(key2)，這種現象稱沖突.具有相同函數值的關鍵字對該散列函數來說稱做同義詞. 綜上所述，根據散列函數H(key)和處理沖突的方法將一組關鍵字映象到一個有限的連續(xù)的地址集（區(qū)間）上，并以關鍵字在地址集中的“象”， 作為這條記錄在表中的存儲位置，這種表便稱為散列表,這一映象過程稱為散列造表或散列，所得的存儲位置稱散列地址.這個現象也叫散列桶，在散列桶中，只能通過順序的方式來查找，一般只需要查找三次就可以找到?？茖W家計算過,當負載因子(load factor)不超過75,查找效率最高。 若對于關鍵字集合中的任一個關鍵字，經散列函數

3、映象到地址集合中任何一個地址的概率是相等的,則稱此類散列函數為均勻散列函數（Uniform Hash function)，這就是使關鍵字經過散列函數得到一個“隨機的地址",從而減少沖突。程序設計流程程序思想(一) 哈希函數unsigned int hash_BKDE（char str）生成映射地址，成為散列表的編號.(二) 哈希表HashTable：HashTable（)通過數組儲存元素(三) 插入函數void HashTable:insert（char*c）插入字符串,先計算要插入字符串生成的映射地址，然后在相應的地址插入,如果沒有空位查找空位插入。(四) 查找函數bool Has

4、hTable:：find(charc）進行查找，先計算要生成字符串的地址，再到散列表中進行查找比較。(五) 主函數main（)1) 輸入：輸入散列表內容和要查找的數據個數和數據2) 輸出模塊：散列表查找的結果.3) 建散列表并查找：建立散列表并遞歸查找流程圖三。實驗源程序：includeiostream#includecstdlibincludectime>using namespace std； unsigned int hash_BKDE(char str)/哈希函數，題目給出 /初始種子 seed 可取31 131 1313 13131 131313 etc。 unsigned i

5、nt seed = 131；unsigned int hash = 0;while (str）hash = hash seed + (*str+）；return (hash & 0x7FFFFFFF）；double k=(double）（rand（）999）/1000； /隨機生成小數隨機數 0k1unsigned int hash_rand（unsigned int value) /value232 ，將轉化地址轉化為seeddouble a=kvalue; double n=(a(int)a)64; /取小數部分與25相乘unsigned int seed=（int)n；retur

6、n seed；unsigned int Hash（charstr） /生成最終的地址映射即計算散列地址位置 return hash_rand（hash_BKDE（str)）； class HashTable/哈希表類 public: HashTable()； HashTable（）； void insert(charc）; bool find(charc）； private： char*Arr； /二維數組用于保存字符串 書名 int ArrSize； /散列表單元個數 在此為215=32768 ；HashTable：:HashTable()ArrSize=32768;Arr=new char

7、*64;for(int i=0;i<64；i+）Arri=new char100；Arri=NULL;HashTable:：HashTable(）for（int i=0;i64;i+）deleteArri；delete Arr； void HashTable:insert(char*c)/插入到哈希表unsigned int pos=Hash（c）;/計算散列地址位置while(Arrpos!=NULL)pos=（pos+1）; /解決沖突的辦法，尋找空位，向后面挪動一個 Arrpos=c； /插入存儲 bool HashTable：find（charc）/查找unsigned int

8、pos=Hash（c）; /計算散列地址while（Arrpos!=NULL） /非空時進行查找 比較 if（Arrpos=c）return true; pos=（pos+1）; /尋找下一地址，如果運行這一步，這說明之前產生了沖突 return false； int main（）bool a20；char *c1=new char100;HashTable H；cout”輸入字符串個數n：n”;int n；cinn;cout"輸入n個字符串:n”；for（int i=1；i<=n;i+）cin>c1；H.insert(c1)；/直接插入到散列表的數組中cout"

9、;輸入待查的字符串個數m:n”;int m；cinm;cout<”輸入要查找的字符串："endl；for(int j=0；jm；j+)cin>c1; aj=H.find（c1）;/bool量cout<”查找結果(yes表示存在,no表示不存在）：n”；for（int k=0;k<m；k+） if(ak）cout<"yesn”;elsecout<”Non”；return 0; 四、實驗截圖五、實驗感想本次的實驗首先要弄清楚哈希表，然后弄清楚最關鍵的兩個模塊,插入和查找.插入模塊中，首先要有哈希函數生成映射地址,要有哈希表保存元素，然后就是自己設定的解決沖突的辦法,這個程序是采用向下挪動一個辦法，直到找到為