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

1、-. z課程實(shí)驗(yàn)報(bào)告課程名稱：數(shù)據(jù)構(gòu)造實(shí)驗(yàn)工程名稱：散列表專業(yè)班級(jí)：*： * *：完成時(shí)間： 2015 年 06 月 13 日背景散列表Hash table，也叫哈希表，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)展的數(shù)據(jù)構(gòu)造。也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。在理想情況下，查找、插入、刪除操作的時(shí)間均為O(1)，是一種高效的動(dòng)態(tài)集合構(gòu)造。例1：計(jì)算機(jī)程序設(shè)計(jì)語言的編譯程序需要維護(hù)一個(gè)符號(hào)表，其中元素的關(guān)鍵值為任意字符串，與語言中的標(biāo)識(shí)符對應(yīng)。該符號(hào)表常采用散列表。例2：為了節(jié)約空間，常常需要把文本文件采用

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

3、錄。輸出：輸出為m行，如果被查的記錄存在，則輸出YES,如果不存在則輸出NO。測試數(shù)據(jù)輸入：4aansandhellocpp9abanasansandandehellocbbhellocpp輸出：YESNONONOYESYESNONOYES實(shí)現(xiàn)提示1沖突處理方法為：順次循環(huán)后移到下一個(gè)位置，尋找空位插入。2BKDE 字符串哈希unsigned int hash_BKDE(char *str) /* 初始種子 seed 可取31 131 1313 13131 131313 etc. */ unsigned int seed = 131;unsigned int hash = 0;while (*

4、str)hash = hash * seed + (*str+);return (hash & 0*7FFFFFFF);將字符串哈希到小于231的整數(shù) t，再將t用隨機(jī)數(shù)哈希法映射到 215以的數(shù)。選做容每一種西文圖書都有一個(gè)國際標(biāo)準(zhǔn)圖書編號(hào)，它是一個(gè)10位的十進(jìn)制數(shù)字，假設(shè)要以它作關(guān)鍵字建立一個(gè)哈希表，當(dāng)館藏書種類不到10,000時(shí)，采用折疊法構(gòu)造一個(gè)四位數(shù)的哈希函數(shù)。課后題目實(shí)現(xiàn)文本LZW壓縮和解壓縮。源代碼#include#include#include using namespace std;unsigned int hash_BKDE(char *str) unsigned int

5、seed = 131; unsigned int hash = 0; while (*str) hash = hash * seed + (*str+); return (hash & 0*7FFFFFFF); double k=(double)(rand()%999)/1000;unsigned int hash_rand(unsigned int value) double a=k*value; double n=(a-(int)a)*64; unsigned int seed=(int)n; return seed; unsigned int Hash(char*str) return

6、hash_rand(hash_BKDE(str); class HashTablepublic: HashTable(); HashTable(); void insert(char*c); bool find(char*c);private: char*Arr; int ArrSize;HashTable:HashTable() ArrSize=32768; Arr=new char*64; for(int i=0;i64;i+) Arri=new char100; Arri=NULL; HashTable:HashTable() for(int i=0;i64;i+) deleteArri

7、; delete Arr; void HashTable:insert(char*c) unsigned int pos=Hash(c); while(Arrpos!=NULL) pos=(pos+1); Arrpos=c; bool HashTable:find(char*c) 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; coutn; cout輸入n個(gè)字符串：n; for(int i=1;ic1; H.insert(c1); coutm; cout輸入要查找的字符串:endl; for(int j=0;jc1; aj=H.find(c1); cout查找結(jié)