哈希查找_數(shù)據(jù)結構實驗報告

《哈希查找_數(shù)據(jù)結構實驗報告》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、南昌航空大學實驗報告課程名稱：數(shù)據(jù)結構實驗名稱：實驗九查找班級：學生姓名：學號：指導教師評定：簽名:題目：編程實現(xiàn)哈希表的造表和查找算法。要求：用除留余數(shù)法構造哈希函數(shù)，用二次探測再散列解決沖突。一、需求分析1.用戶可以根據(jù)自己的需求輸入一個順序表（哈希表）2.通過用除留余數(shù)法構造哈希函數(shù)，并用開放地址的二次探測再散列解決沖突。3.在經(jīng)過排序后顯示該哈希表。4.程序執(zhí)行的命令包括：（1）創(chuàng)建哈希表（2）輸出哈希表（3）二次探測再散列解決沖突二、概要設計⒈為實現(xiàn)上述算法，需要順序表的抽象數(shù)據(jù)類型：ADTHas

2、h{數(shù)據(jù)對象D：D是具有相同特征的數(shù)據(jù)元素的集合。各數(shù)據(jù)元素均含有類型相同，可唯一標識數(shù)據(jù)元素的關鍵字。數(shù)據(jù)關系R：數(shù)據(jù)元素同屬一個集合。基本操作P:Creathash(&h)操作結果：構造一個具有n個數(shù)據(jù)元素的哈希查找表h。destroyhash(&h)初始條件：哈希查找表h存在。操作結果：銷毀哈希查找表h。displayhash（h）初始條件：哈希查找表h存在。操作結果：顯示哈希查找表h。hash(h，&k)初始條件：哈希查找表h存在。操作結果：通過除留余數(shù)法得到地址用k返回。hash2(i，&k)初始

3、條件：哈希查找表h存在存在，i是除留余數(shù)法得到的地址。操作結果：返回二次探測再散列解決沖突得到的地址k。search(h，key)初始條件：哈希查找表h存在。10操作結果：查找表h中的key，若查找成功，返回其地址，否則返回-1insert(&h，key)初始條件：哈希查找表h存在。操作結果：若表h中沒有key，則在h中插入key。search1(h,key,&p)初始條件：哈希查找表h存在。操作結果：在表h中查找key，若沒有，則返回p的插入的地址，否則返回-1。}ADTHash2.本程序有三個模塊：⑴主

4、程序模塊main(){初始化；{接受命令；顯示結果；｝｝⑵創(chuàng)建hash表的模塊：主要建立一個哈希表；⑶解決沖突模塊：利用開放地址的二次探測再散列解決沖突；(4)輸出哈希表模塊：顯示已創(chuàng)建哈希表。三、詳細設計⒈元素類型，結點類型typedefstruct{intkey;}keytype;typedefstruct{keytypeelem[100];intlength;/*當前的長度*/intsize;/*哈希表的總長*/}hashtable;/*全局變量*/inta=0,b=0;/*哈希函數(shù)*/2.對抽象數(shù)據(jù)

5、類型中的部分基本操作的偽碼算法如下：/*哈希函數(shù)*/inthash(hashtable*h,intk){returnk%h->size;}10/*二次探測再散列解決沖突*/inthash2(inti,intt){if(i%2==0)t=t+pow(++a,2);elset=t-pow(++b,2);returnt;}/*創(chuàng)建哈希表*/voidcreat(hashtable*h){inti,j,key,t,p;printf("inputhashsizeandlength:");scanf("%d%d",&h-

6、>size,&h->length);for(i=0;isize;i++)h->elem[i].key=-1;printf("inputdata:");for(j=0;jlength;j++){scanf("%d",&key);p=hash(h,key);if(h->elem[p].key==-1)h->elem[p].key=key;else{i=0;t=p;while(h->elem[p].key!=-1&&h->elem[p].key!=key&&isize/2){p=has

7、h2(i,t);i++;}a=b=0;h->elem[p].key=key;}}}/*查找哈希表中的元素，返回元素的地址，否則返回-1*/intsearch(hashtable*h,intkey){intp,t,i=0;p=hash(h,key);t=p;10while(h->elem[p].key!=-1&&h->elem[p].key!=key&&isize/2){p=hash2(i,t);i++;}if(h->elem[p].key==key)returnp;elsereturn(-1);}/

8、*查找哈希表的元素，返回p的插入的位置*/voidsearch1(hashtable*h,intkey,int*p){intt,s,c=0;t=hash(h,key);s=t;while(h->elem[t].key!=-1&&h->elem[t].key!=key&&csize/2){t=hash2(c,s);c++;}if(h->elem[t].key==key)*p=t;else{t=-1;*p=t