設(shè)計(jì)構(gòu)造哈希表的完整算法,求出平均查找長(zhǎng)度

《設(shè)計(jì)構(gòu)造哈希表的完整算法,求出平均查找長(zhǎng)度》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、《程序設(shè)計(jì)與算法分析》實(shí)驗(yàn)報(bào)告一設(shè)計(jì)的目的與內(nèi)容1?設(shè)計(jì)目的通過(guò)本實(shí)驗(yàn)需要掌握構(gòu)造哈希函數(shù)表，需要完成設(shè)計(jì)構(gòu)造哈希表的完整算法,并求出平均查找長(zhǎng)度。2實(shí)驗(yàn)內(nèi)容使用哈希函數(shù)：H（K）=3*KMOD11并采用開放地址法解決沖突，試在0到10的散列地址空間對(duì)關(guān)鍵字序列（22,41,53,46,30,13,01，67）構(gòu)造哈希函數(shù)表，并設(shè)計(jì)構(gòu)造哈希表的完整算法,并求出平均查找長(zhǎng)度。二算法的基本思想1?數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)10,對(duì)關(guān)鍵字哈希函數(shù)H（key）=3*keymod11,哈希表的地址空間為0?序列（22,41,53,46,30,13,01,67）按線性探測(cè)再散列和二次探測(cè)再散列的

2、方法分別構(gòu)造哈希表。（1）線性探測(cè)再散列:3*22%11=0；3*41%11=2；3*53%11=5；3*46%11=6；3*30%11=2發(fā)生沖突，下一個(gè)存儲(chǔ)地址（2+1）%們=3；3*13%11=6發(fā)生沖突，下一個(gè)存儲(chǔ)地址（6+1）%11=7；3*01%11=3發(fā)生沖突，下一個(gè)存儲(chǔ)地址（3+1）%笛=4；3*67%11=3發(fā)生沖突，下一個(gè)存儲(chǔ)地址是：（3+1）%11=4發(fā)生沖突;下一個(gè)存儲(chǔ)地址（4+1）%11=5發(fā)生沖突；下一個(gè)存儲(chǔ)地址（5+1）%11=6發(fā)生沖突；下一個(gè)存儲(chǔ)地址（6+1）%11=7發(fā)生沖突；下一個(gè)存儲(chǔ)地址（7+1)%11=8未發(fā)生沖突。2?算法的基本

3、思想???開放地址法這個(gè)方法的基本思想是：當(dāng)發(fā)生地址沖突時(shí)，按照某種方法繼續(xù)探測(cè)哈希表中的其他存儲(chǔ)單元，直到找到空位置為止。這個(gè)過(guò)程可用下式描述:Hi(key)=(H(key)+di)modm(i=1,2,,k(k

4、稱呼：(1)di=1,2,3,……線性探測(cè)再散列；(2)di=1A2,-1A2,2A2,-2A2,kA2,-kA2二次探測(cè)再散列;(3)di=偽隨機(jī)序列偽隨機(jī)再散列;三源程序代碼及測(cè)試結(jié)果源程序代碼#include#include#defineM11#defineN8structhtermintkey;〃關(guān)鍵字值};structhtermhlist

5、MJ;inttadr^sum^d;〃關(guān)鍵字賦值intx[N]={22,41,53,46,30,13,1,67};floataverage;voidchashO〃創(chuàng)建哈希表for(i

6、=0;i

7、i])%M;d=adr;if(hlist[adr]>key=0){hlist[adr].key=x[i];hlist[adr].si=l;}else{do〃沖突處理{d=(d+l)%M;sum=sum+l;while(hlist[d]>key!=0);hlist[d]

8、ut?setw(4)?i;cout?endl;cout?n哈希表關(guān)鍵字：”；for(i=0;ivM;i++)cout?setw(4)?hlist[i

9、.key;cout?endl;cout?n搜索長(zhǎng)度：”；for(i=0;isi;average=average/N;cout?"平均搜索長(zhǎng)度：ASL(n?N?n)=H?average?endl;}voidmain(){chash();dha

10、sh();CD回2.測(cè)試結(jié)果■G:VC++'MicrosoftVisualStudioMyProjects123456Debug123456.exe":哈希表地址：tels^=乎均毅索長(zhǎng)度:Pressanykeyto0123226741301312ASL<8>=2.125continue45605346011813210163?存在的問(wèn)題及解決Configuration:123456-Win32DebugCompiling...123.cpp執(zhí)彳亍cl.exeMS?-

11、G:UC^?MicrosoFtUisuolS