1、課程實驗報告課程名稱:數據結構實驗項目名稱:散列表專業班級：姓名:XXX學號：完成時間： 2015 年 06月13日背景散列表（Hash table,也叫哈希表）,是根據關鍵碼值(Key value）而直接進行訪問的數據結構.也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數,存放記錄的數組叫做散列表。在理想情況下，查找、插入、刪除操作的時間均為O(1），是一種高效的動態集合結構。例1：計算機程序設計語言的編譯程序需要維護一個符號表，其中元素的關鍵值為任意字符串,與語言中的標識符對應。該符號表常采用散列表。例2：為了節約空間，常常需要把文本文件采

2、用壓縮編碼方式存儲。LZW是對文本文件進行壓縮和解壓縮的方法之一,該方法采用了散列。問題描述我們希望在浩瀚的圖書中，去發現一本書是否存在。我們不知道書的編號，只知道它的書名。(其實這已經不錯了。.。）.通過書名，來查詢它是否存在。為了簡化問題,我們假設每本書的書名都是一組小寫字母組成，長度不超過100字符。基本要求（1） 根據輸入建立圖書名稱表,采用散列表實現該表,散列函數選用BKDE 字符串哈希.（2）數據的輸入輸出格式：輸入分為兩部分第一部分，第一行是行數n,n <= 5000.余下n行，每行一個字符串。表示已存在的圖書記錄。第二部分，第一行是行數m，m = 1000.余下m行，每行

3、一個字符串.表示要查詢的圖書記錄.輸出:輸出為m行，如果被查的記錄存在，則輸出"YES”,如果不存在則輸出”NO”.測試數據輸入：4aansandhellocpp9abanasansandandehellocbbhellocpp輸出：YESNONONOYESYESNONOYES實現提示（1)沖突處理方法為：順次循環后移到下一個位置，尋找空位插入。(2）BKDE 字符串哈希unsigned int hash_BKDE（char str） / 初始種子 seed 可取31 131 1313 13131 131313 etc。. / unsigned int seed = 131；unsi

4、gned int hash = 0；while (str)hash = hash seed + (*str+);return （hash 0x7FFFFFFF）;將字符串哈希到小于231的整數 t，再將t用隨機數哈希法映射到 215以內的數.選做內容每一種西文圖書都有一個國際標準圖書編號，它是一個10位的十進制數字，若要以它作關鍵字建立一個哈希表，當館藏書種類不到10，000時，采用折疊法構造一個四位數的哈希函數。課后題目實現文本LZW壓縮和解壓縮。源代碼include<iostream#includecstdlibincludectime using namespace std；uns

5、igned int hash_BKDE(char str） unsigned int seed = 131； unsigned int hash = 0； while (str) hash = hash seed + （str+）; return (hash 0x7FFFFFFF)； double k=(double）(rand(）999）/1000；unsigned int hash_rand（unsigned int value) double a=kvalue； double n=（a(int）a）64; unsigned int seed=（int）n； return seed; un

6、signed int Hash(charstr) return hash_rand（hash_BKDE(str）; class HashTablepublic: HashTable（）; HashTable（)； void insert（charc); bool find（charc）；private： char*Arr； int ArrSize；;HashTable：HashTable（） ArrSize=32768； Arr=new char*64； for（int i=0;i<64;i+） Arri=new char100； Arri=NULL； HashTable：:HashTa

7、ble（） 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 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”輸入待查的字符串個數m:n”； int m; cinm； cout"輸入要查找的字符串：”endl; for（int j=0；jm;j+） cinc1； aj=H。find（c1）; cout”查找結果（yes表示存在,no表示不存在)：n&