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

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

2、線性探測(cè)再散列和二次探測(cè)再散列的方法分別構(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 ） 11 3 ；3*13%11=6發(fā)生沖突，下一個(gè)存儲(chǔ)地址（ 6 1 ） 11 7 ；3*01%11=3發(fā)生沖突，下一個(gè)存儲(chǔ)地址（ 3 1 ） 11 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

3、+ 1 ）%11=7發(fā)生沖突；下一個(gè)存儲(chǔ)地址（ 7 + 1 ）%11=8未發(fā)生沖突。2.算法的基本思想 開放地址法 這個(gè)方法的基本思想是：當(dāng)發(fā)生地址沖突時(shí)，按照某種方法繼續(xù)探測(cè)哈希表中的其他存儲(chǔ)單元，直到找到空位置為止。這個(gè)過程可用下式描述： H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2, ， k ( k m 1) 其中： H ( key ) 為關(guān)鍵字 key 的直接哈希地址， m 為哈希表的長度， di 為每次再探測(cè)時(shí)的地址增量。 采用這種方法時(shí)，首先計(jì)算出元素的直接哈希地址 H ( key ) ，如果該存儲(chǔ)單元已被其他元素占用，則繼續(xù)查看

4、地址為 H ( key ) + d 2 的存儲(chǔ)單元，如此重復(fù)直至找到某個(gè)存儲(chǔ)單元為空時(shí)，將關(guān)鍵字為 key 的數(shù)據(jù)元素存放到該單元。 增量 d 可以有不同的取法，并根據(jù)其取法有不同的稱呼： （ 1 ） d i 1 ， 2 ， 3 ， 線性探測(cè)再散列； （ 2 ） d i 12 ， 12 ， 22 ， 22 ， k2， -k2 二次探測(cè)再散列；（ 3 ） d i 偽隨機(jī)序列 偽隨機(jī)再散列； 三 源程序代碼及測(cè)試結(jié)果1. 源程序代碼#include<iostream.h>#include<iomanip.h>#define M 11#define N 8struct hte

5、rmint key; /關(guān)鍵字值int si; /散列次數(shù);struct hterm hlistM;int i,adr,sum,d;int xN=22,41,53,46,30,13,1,67; /關(guān)鍵字賦值float average;void chash() /創(chuàng)建哈希表for (i=0;i<M;i+)hlisti.key=0;hlisti.si=0;for (i=0;i<N;i+) sum=0;adr=(3*xi)%M;d=adr;if (hlistadr.key=0)hlistadr.key=xi;hlistadr.si=1;elsedo /沖突處理d=(d+1)%M;sum=

6、sum+1;while (hlistd.key!=0);hlistd.key=xi;hlistd.si=sum+1;void dhash() /輸出哈希表cout <<" 哈希表地址："for(i=0;i<M;i+)cout << setw(4) <<i;cout << endl;cout<<"哈希表關(guān)鍵字："for (i=0;i<M;i+)cout<< setw(4) << hlisti.key;cout << endl;cout <<

7、; " 搜索長度："for (i=0;i<M;i+)cout << setw(4) << hlisti.si;cout << endl;average=0;for (i=0;i<M;i+)average=average+hlisti.si;average=average/N;cout << "平均搜索長度： ASL("<< N <<")="<< average << endl;void main()chash();dhash()

8、; 2. 測(cè)試結(jié)果3. 存在的問題及解決解決方法：struct htermint key; /關(guān)鍵字值int si; /散列次數(shù)“”后面少了一個(gè)“； ”。四 分析與討論（ 1 ）線性探測(cè)再散列： 22 11 = 0； 41 11=8 ； 53 11 = 9 ； 46%11=2；30%11=7；13%11=2發(fā)生沖突，下一個(gè)存儲(chǔ)地址（ 2 1 ） 11 3 ；01%11=1；67%11=1發(fā)生沖突，下一個(gè)存儲(chǔ)地址是：（ 1 1 ） 11 2 發(fā)生沖突； 下一個(gè)存儲(chǔ)地址（ 2 + 1 ）%11=3發(fā)生沖突； 下一個(gè)存儲(chǔ)地址（ 3 + 1 ）%11=4未發(fā)生沖突。五 心的體會(huì)在這次數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)中遇到了很多實(shí)際性的問題，在實(shí)際設(shè)計(jì)才發(fā)現(xiàn)，書本上理論性的東西和在實(shí)際運(yùn)用中的還是