數(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、散列表的設(shè)計(jì)實(shí)驗(yàn)報(bào)告1、題目：散列表的設(shè)計(jì):針對(duì)某個(gè)集體中人名設(shè)計(jì)一個(gè)散列表，使得平均查找長(zhǎng)度不超過(guò)R,并完成相應(yīng)的建表和查表程序。2、基本要求：假設(shè)人名為中國(guó)人姓名的漢語(yǔ)拼音形式。待填入哈希表的人名共30個(gè)，取平均查找長(zhǎng)度上限為2，哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測(cè)再散列法處理沖突。人名長(zhǎng)度不超過(guò)20個(gè)字符?？上葘?duì)過(guò)長(zhǎng)的人名作折疊處理。3、設(shè)計(jì)思想：a.構(gòu)造哈希函數(shù)的方法很多，常用的有(1)直接定址法(2)數(shù)字分析法;(3)平方取中法;(4)折疊法;(5)除留余數(shù)法;(6)隨機(jī)數(shù)法；本實(shí)驗(yàn)采用的是除留

2、余數(shù)法:取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)為哈希地址H(key)=keyMODp,p<=m.b.哈希函數(shù)可以減少?zèng)_突，但不能避免。通常用的處理沖突的方法有：（1）開(kāi)放定址法，這種方法還包含三種形式，一種叫線性探測(cè)再散列，一種叫二次探測(cè)再散列，另一種叫偽隨機(jī)探測(cè)再散列。本實(shí)驗(yàn)采用的是第三種偽隨機(jī)探測(cè)再散列。求下一個(gè)開(kāi)放地址的公式為：Hi=(H(k)+di)MODm(Di=偽隨機(jī)數(shù)序列)c.對(duì)哈希表的操作InitNameList()操作結(jié)果：姓名（結(jié)構(gòu)體數(shù)組）初始化CreateHashList(

3、)操作結(jié)果：建立哈希表FindList()操作結(jié)果：在哈希表中查找Display()操作結(jié)果：顯示哈希表4、程序結(jié)構(gòu)圖主程序查找顯示哈希表建立哈希表初始化姓名5、流程圖6、數(shù)據(jù)測(cè)試7、程序清單#include#includeusingnamespacestd;#defineHASH_LENGTH50#defineM47#defineNAME_NO30typedefstruct{char*py;intk;}NAME;NAMENameList[HASH_LENGTH];typ

4、edefstruct{char*py;intk;intsi;//查找長(zhǎng)度}HASH;HASHHashList[HASH_LENGTH];voidInitNameList(){char*f;intr,s0,i;for(i=0;i

5、rcpy(NameList[2].py,"jianghaiyan");strcpy(NameList[3].py,"wangtingting");strcpy(NameList[4].py,"zhouhuihui");strcpy(NameList[5].py,"zhuzhenguo");strcpy(NameList[6].py,"wuqingwen");strcpy(NameList[7].py,"chenzuopeng");strcpy(NameList[8].py,"jinlining");strc

6、py(NameList[9].py,"zhandakan");strcpy(NameList[10].py,"linjiajia");strcpy(NameList[11].py,"huangwenjun");strcpy(NameList[12].py,"lizhongjing");strcpy(NameList[13].py,"sushiding");strcpy(NameList[14].py,"ouyangyaoyao");strcpy(NameList[15].py,"chenwei");strc

7、py(NameList[16].py,"linxiaxiao");strcpy(NameList[17].py,"zhanjie");strcpy(NameList[18].py,"baishujun");strcpy(NameList[19].py,"gongqiaoqiao");strcpy(NameList[20].py,"lvhaitao");strcpy(NameList[21].py,"jiangqingsong");strcpy(NameList[22].py,"gubaolong");str

8、cpy(NameList[23].py,"yehuaisong");strcpy(NameList[24].py,"wangyuqin");strcpy(NameList[25].py,"xuefeifei");strcpy(NameList[26].py,"wujianshu");strcpy(NameList[27].py,"zhanghuajiang");strcpy(NameList[28].py,"zh