散列法的課程設(shè)計(jì)說(shuō)明書

1、<p><b>　　數(shù) 據(jù) 結(jié) 構(gòu)</b></p><p>　　課 程 設(shè) 計(jì) 說(shuō) 明 書</p><p>　　2011年12月20日</p><p>　　設(shè)計(jì)任務(wù)概述（包括系統(tǒng)總體框圖及功能描述）</p><p><b>　　系統(tǒng)總體框圖</b></p><p>

2、<b>　　問(wèn)題描述</b></p><p>　　散列法中，散列函數(shù)構(gòu)造方法多種多樣，同時(shí)對(duì)于同一散列函數(shù)解決沖突的方法也可以不同。兩者是影響查詢算法性能的關(guān)鍵因素。對(duì)于幾種典型的散列函數(shù)構(gòu)造方法，做實(shí)驗(yàn)觀察，不同的解決沖突方法對(duì)查詢性能的影響。</p><p><b>　　概要設(shè)計(jì)</b></p><p>　　散列又稱哈

3、希或雜湊。散列法（Hashing）在表項(xiàng)的存儲(chǔ)位置與它的關(guān)鍵碼之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系Hash（），以使每個(gè)關(guān)鍵碼與結(jié)構(gòu)中的唯一存儲(chǔ)位置相對(duì)應(yīng)，該關(guān)系可用下式表示：</p><p>　　Address=Hash（Record.key）</p><p>　　相應(yīng)的表稱為哈希表，這種方法的基本思想是：首先在元素的關(guān)鍵字k和元素的存儲(chǔ)位置p之間建立一個(gè)對(duì)應(yīng)關(guān)系H，使得p=H(k)，H稱為哈

4、希函數(shù)。創(chuàng)建哈希表時(shí)，把關(guān)鍵字為k的元素直接存入地址為H(k)的單元；以后當(dāng)查找關(guān)鍵字為k的元素時(shí)，再利用哈希函數(shù)計(jì)算出該元素的存儲(chǔ)位置p=H(k)，從而達(dá)到按關(guān)鍵字直接存取元素的目的。 </p><p>　　哈希函數(shù)是一個(gè)映象，哈希函數(shù)的設(shè)定靈活，只要使得任何關(guān)鍵字所得的哈希函數(shù)值都落在表長(zhǎng)范圍之內(nèi)即可。 </p><p>　　當(dāng)關(guān)鍵字集合很大時(shí)，關(guān)鍵字值不同的元素可能會(huì)映

5、象到哈希表的同一地址上，即 k1≠k2，但H(k1)=H(k2)，這種現(xiàn)象稱為沖突，此時(shí)稱k1和k2為同義詞。實(shí)際中，沖突是不可避免的，只能通過(guò)改進(jìn)哈希函數(shù)的性能來(lái)減少?zèng)_突。</p><p>　　綜上所述，哈希法主要包括以下兩方面的內(nèi)容。</p><p>　　(1）如何構(gòu)造哈希函數(shù)；</p><p>　　(2） 如何處理沖突。</p><p>

6、;　　2. 本設(shè)計(jì)所采用的數(shù)據(jù)結(jié)構(gòu)（如：鏈表、棧、樹(shù)、圖等）</p><p><b>　　一、散列函數(shù)</b></p><p>　　通常，構(gòu)造散列函數(shù)應(yīng)該注意的幾個(gè)問(wèn)題包括：首先，散列函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān)鍵碼，而如果散列表允許有m個(gè)地址，其值域必須在1~m-1之間;其次，散列函數(shù)計(jì)算出來(lái)的地址應(yīng)能均勻分布在整個(gè)地址空間中；再次，散列函數(shù)應(yīng)當(dāng)是盡量簡(jiǎn)單的

7、。</p><p><b>　　1．直接定址法</b></p><p>　　直接定址法藍(lán)顏元素關(guān)鍵碼的某個(gè)線性函數(shù)值作為該元素的散列地址（散列地址，即元素最終在字典中的存儲(chǔ)位置）。如下面的函數(shù)式：</p><p>　　Hash（key）=a×key+b</p><p>　　式中，a，b為常數(shù)。采用該種方法，當(dāng)向

8、字典中加入某一新元素時(shí)算法自動(dòng)調(diào)用此函數(shù)，以確定該元素最終的存儲(chǔ)位置。若某元素關(guān)鍵碼key為1，上式中，a=2，b=3則該元素最終會(huì)存儲(chǔ)在字典第5個(gè)位置中。</p><p>　　直接定址法的優(yōu)點(diǎn)是實(shí)現(xiàn)方法簡(jiǎn)單，算法時(shí)間復(fù)雜度較小，而且不會(huì)產(chǎn)生沖突。但是，直接定址法要求散列地址空間的大小與關(guān)鍵碼集合的大小一致，而這種要求是苛刻的，一般很難實(shí)現(xiàn)。例如當(dāng)關(guān)鍵碼的范圍為1~1000000時(shí)，元素散列地址的個(gè)數(shù)也要達(dá)到10

9、00000。這么大的散列地址是不合實(shí)際的。</p><p><b>　　2.除留余數(shù)法</b></p><p>　　設(shè)散列表中允許的地址數(shù)為m，取一個(gè)不大于m，但最接近或等于m的質(zhì)數(shù)k，或選取一個(gè)不含有小于20的質(zhì)因子的合數(shù)作為除數(shù)。利用下面的式子計(jì)算元素的散列地址的方法稱為除留余數(shù)法。</p><p>　　Hash（key）=key%k，k≤

10、m</p><p>　　其中，“%”是整數(shù)除余法取余的運(yùn)算，要求這時(shí)的質(zhì)數(shù)不是接近2的冪。例如，當(dāng)元素的關(guān)鍵碼key為2008，散列地址總數(shù)為50，這時(shí)取k=47，則散列地址為Hash（2008）=2008%47=34，所以運(yùn)算將存儲(chǔ)在字典第47個(gè)位置中。</p><p>　　除留余數(shù)法將有效縮減散列地址空間的大小，例如上例散列地址空間中只有50個(gè)有效的散列地址。除留余數(shù)法的缺點(diǎn)是極易發(fā)生

11、沖突，如關(guān)鍵碼為1914的元素經(jīng)過(guò)上述教例函數(shù)計(jì)算后也將獲得散列地址34。此時(shí)出現(xiàn)的兩個(gè)不同元素爭(zhēng)用同一存儲(chǔ)地址的情況就稱為沖突。</p><p><b>　　3.平方取中法</b></p><p>　　平方取中法是一種常用的實(shí)現(xiàn)散列函數(shù)的方法。</p><p>　　平方取中法是一種先放大再集合的構(gòu)造方法，這種構(gòu)造模式先通過(guò)求關(guān)鍵字的平方值擴(kuò)大

12、相近數(shù)的差別，然后根據(jù)表長(zhǎng)度取中間的幾位數(shù)作為散列函數(shù)值，這種取中間數(shù)的方法是一種類隨機(jī)方案，因此也可以認(rèn)為平方取中法是一種產(chǎn)生偽隨機(jī)數(shù)的方法。因?yàn)橐粋€(gè)乘積的中間幾位數(shù)和乘數(shù)的每一位都相關(guān)，所以有此產(chǎn)生的散列地址較為均勻。</p><p>　　利用平方取中法實(shí)現(xiàn)散列函數(shù)的過(guò)程：首先，利用一定的編碼規(guī)則把元素的關(guān)鍵碼轉(zhuǎn)換成標(biāo)識(shí)符。然后，求出標(biāo)識(shí)符的內(nèi)碼表示并計(jì)算內(nèi)碼的平方值。最后，取內(nèi)碼平方數(shù)的中間x位作為元素最終

13、的散列地址。簡(jiǎn)而言之，即先計(jì)算構(gòu)成關(guān)鍵碼表示符的內(nèi)碼平方，然后按照散列表的大小取中間的若干位作為散列地址。</p><p>　　在平方取中法中，地址空間內(nèi)散列地址的數(shù)目一般為2的k次冪，并在計(jì)算出內(nèi)碼平方的平方后，根據(jù)k的大小決定最終散列地址的位數(shù)。例如某個(gè)地址空間中散列地址的個(gè)數(shù)為128，則最終取內(nèi)碼平方中間7位作為元素最終的散列地址。</p><p><b>　　4.乘余取整

14、法</b></p><p>　　乘余取整法利用下面的式子計(jì)算元素的散列地址。</p><p>　　Hash（key）=[Z×（a×key%1）]</p><p>　　其中，a為一個(gè)常數(shù)且0<a<1，Z為一個(gè)整數(shù)。式a×key%1表示a×key取小數(shù)部分，即a×key%1= a×key

15、-[ a×key] 。例如，當(dāng)元素關(guān)鍵碼為2008， 小數(shù)a為0.6180339，整數(shù)Z為10000，則散列地址計(jì)算為Hash（2008）=[10000×（0.6180339×2008%1）]=120。</p><p>　　乘余取整法不但會(huì)縮減散列地址空間的大小，還能極大減小沖突情況的發(fā)生幾率。Knuth對(duì)常數(shù)a的取法做了仔細(xì)的研究，發(fā)現(xiàn)雖然a取任何值都可以，但一般取黃金分割數(shù)0.6

16、180339比較好。</p><p><b>　　5.折疊法</b></p><p>　　折疊法的工作方式很有趣，此方法把關(guān)鍵嗎從左至右劃分為位數(shù)相等的幾部分，每一部分的位數(shù)與散列地址數(shù)相同。當(dāng)關(guān)鍵碼位數(shù)不能被散列地址位數(shù)整除時(shí)，最后一部分可取得短些。</p><p>　　折疊法有兩種，即位移法和分界法。 其中，位移法所采取的具體方式是把各部分

17、的最后一位對(duì)齊相加。分界法所采用的具體方式是各部分不折斷，而沿各部分的分界來(lái)回折疊，然后對(duì)齊相加，并將相加的結(jié)果當(dāng)做散列地址。折疊法適用于關(guān)鍵碼位數(shù)很多，且每一位上數(shù)字分布比較均勻的情況。下面通過(guò)實(shí)例演示這兩種方法的工作方式。</p><p>　　設(shè)關(guān)鍵碼key=987654321，散列地址為4位。位移法和分界法計(jì)算散列地址的算式如圖所示。</p><p><b>　　9876&

18、lt;/b></p><p>　　5432 2345</p><p>　　+ 1 + 1</p><p>　　15309 12222</p><p>　　移位法

19、 分界法</p><p>　　由式可見(jiàn)，位移法計(jì)算結(jié)果為15309，由于散列地址為4位，所以舍去最高位數(shù)字1，元素最終的散列地址為5309。分界法結(jié)算結(jié)果為12222，同樣舍去最高位數(shù)字1，元素最終的散列地址為2222。</p><p>　　二、散列沖突解決方法</p><p>　　在構(gòu)造散列函數(shù)的過(guò)程中，不可避免地會(huì)出現(xiàn)沖突的情況。所謂處理沖突，就是在

20、有沖突發(fā)生時(shí)，為產(chǎn)生沖突的關(guān)鍵字找到另一個(gè)地址存放該關(guān)鍵字。在解決沖突的過(guò)程中，可能會(huì)得到一系列散列地址hi（i=1,2，…，n),也就是發(fā)生第一沖突時(shí)，經(jīng)過(guò)處理后得到第一新地址記作h1，如果h1仍然會(huì)沖突，則處理后得到第二個(gè)地址h2，依此類推，直到hn不產(chǎn)生沖突，將hn作為關(guān)鍵字的儲(chǔ)存地址。</p><p>　　處理沖突的方法比較常用的主要有開(kāi)放定址法、再散列法和鏈地址法。</p><p&g

21、t;<b>　　開(kāi)放定址法</b></p><p>　　開(kāi)放定址法是解決沖突比較常用的方法。開(kāi)放定址法就是利用散列表中的空地址存儲(chǔ)產(chǎn)生沖突的關(guān)鍵字。當(dāng)沖突發(fā)生時(shí)，按照下列公式處理沖突：</p><p>　　hi=（h（key）+di）%m，其中i=1,2，…，m-1</p><p>　　其中，h（key）為散列函數(shù)，m為散列表長(zhǎng)，di為地址增量

22、。地址增量di可以以下三種方法獲得：</p><p>　　線性探測(cè)再散列：當(dāng)沖突發(fā)生時(shí)，地址增量di依次取1,2，…，m-1自然數(shù)列，即di=1,2，…，m-1。</p><p>　　二次探測(cè)再散列：在沖突發(fā)生時(shí)，地址增量di依次取自然數(shù)的平方，即di=12，—12,22，—22，…，k2，—k2。</p><p>　　偽隨機(jī)數(shù)再散列：在沖突發(fā)生時(shí)，地址增量di依次

23、取隨機(jī)數(shù)序列。</p><p>　　例如，在長(zhǎng)度為14的散列表中，在將關(guān)鍵字183,123,230,91存放在散列表中的情況如圖所示。</p><p><b>　　Hash地址</b></p><p>　　0 1 2 3 4 5 6 7 8 9 10 11 12 13<

24、;/p><p>　　散列表沖突發(fā)生前示意圖</p><p>　　當(dāng)要插入關(guān)鍵字149時(shí)，有散列函數(shù)h（149）=149%13=6，而單元6已經(jīng)存在關(guān)鍵字，產(chǎn)生沖突，利用線性探測(cè)再散列法解決沖突，即h1=（6+1）%14=7，將149儲(chǔ)存在單元7中，如圖所示。</p><p><b>　　Hash地址</b></p><p>

25、　　0 1 2 3 4 5 6 7 8 9 10 11 12 13</p><p>　　插入關(guān)鍵字149后的示意圖</p><p>　　當(dāng)要插入關(guān)鍵字227時(shí)，由散列函數(shù)h（227）=227%13=6，而單元6已經(jīng)存在關(guān)鍵字，產(chǎn)生沖突，利用線性探測(cè)再散列法解決沖突，即h1=（6+1）%14=7，仍然沖突，繼續(xù)利用線性

26、探測(cè)法，即h2=（6+2）%14=8，單元8空閑，因此將227存儲(chǔ)在單元8中，如圖所示。</p><p><b>　　Hash地址</b></p><p>　　0 1 2 3 4 5 6 7 8 9 10 11 12 13</p><p>　　插入關(guān)鍵字227后的示意圖&

27、lt;/p><p>　　當(dāng)然，在沖突發(fā)生時(shí)，也可以利用二次探測(cè)再散列解決沖突。在圖11.33中，如果要插入關(guān)鍵字227，因?yàn)楫a(chǎn)生沖突，利用二次探測(cè)再散列法解決沖突，即h1=（6+1）%14=7，再次產(chǎn)生沖突時(shí)，有h2=（6—1）%14=5，將227儲(chǔ)存在單元5中，如圖所示。</p><p><b>　　Hash地址</b></p><p>　　0

28、 1 2 3 4 5 6 7 8 9 10 11 12 13</p><p>　　利用二次探測(cè)再散列解決沖突示意圖</p><p><b>　　再散列法</b></p><p>　　再散列法就是在沖突發(fā)生時(shí)，利用另外一個(gè)散列函數(shù)再次求散列函數(shù)的地址，直到?jīng)_突不再發(fā)生為止，即

29、</p><p>　　hi=rehash（key），i=1,2…，n</p><p>　　其中，rehash表示不同的散列函數(shù)。這種再散列法一般不容易再次發(fā)生沖突，但是需要事先構(gòu)造多個(gè)散列函數(shù)，這是一件不太容易的也不現(xiàn)實(shí)的事情。</p><p><b>　　鏈地址法</b></p><p>　　數(shù)組的特點(diǎn)是：尋址容易，插

30、入和刪除困難；而鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實(shí)現(xiàn)方法，我接下來(lái)解釋的是最常用的一種方法——鏈地址法，我們可以理解為“鏈表的數(shù)組”，如圖：</p><p>　　左邊很明顯是個(gè)數(shù)組，數(shù)組的每個(gè)成員包括一個(gè)指針，指向一個(gè)鏈表的頭，當(dāng)然這個(gè)鏈表可能為空，也可能元素很多。我們根據(jù)元

31、素的一些特征把元素分配到不同的鏈表中去，也是根據(jù)這些特征，找到正確的鏈表，再?gòu)逆湵碇姓页鲞@個(gè)元素。三、 哈希法性能分析</p><p>　　由于沖突的存在，哈希法仍需進(jìn)行關(guān)鍵字比較，因此仍需用平均查找長(zhǎng)度來(lái)評(píng)價(jià)哈希法的查找性能。哈希法中影響關(guān)鍵字比較次數(shù)的因素有三個(gè)：哈希函數(shù)、處理沖突的方法以及哈希表的裝填因子。哈希表的裝填因子α的定義如下： </p><p><b>　　■線

32、性探測(cè)再散列</b></p><p><b>　　查找成功時(shí) </b></p><p><b>　　查找失敗時(shí) </b></p><p>　　■偽隨機(jī)探測(cè)再散列、 二次探測(cè) </p><p><b>　　查找成功時(shí) </b></p><p>

33、<b>　　查找失敗時(shí) </b></p><p><b>　　■鏈址法</b></p><p><b>　　查找成功時(shí)</b></p><p><b>　　查找失敗時(shí)</b></p><p>　　從以上討論可知：哈希表的平均查找長(zhǎng)度是裝填因子α的函數(shù)，而與

34、待散列元素?cái)?shù)目n無(wú)關(guān)。因此，無(wú)論元素?cái)?shù)目n有多大，都能通過(guò)調(diào)整α，使哈希表的平均查找長(zhǎng)度較小。 </p><p>　　3. 功能模塊詳細(xì)設(shè)計(jì)</p><p>　　3.1 詳細(xì)設(shè)計(jì)思想</p><p>　　(1)程序中結(jié)構(gòu)體的定義</p><p>　　typedef struct</p><p><b>　　{

35、</b></p><p><b>　　int key;</b></p><p><b>　　int si;</b></p><p>　　}HashTable1;</p><p>　　typedef struct node</p><p><b>　　{&

36、lt;/b></p><p><b>　　int key;</b></p><p><b>　　int si;</b></p><p>　　struct node *next;</p><p><b>　　}Node;</b></p><p>　　

37、typedef struct</p><p><b>　　{</b></p><p>　　Node *link;</p><p>　　}HashTable2;</p><p>　　typedef struct </p><p><b>　　{</b></p>&

38、lt;p>　　int * elem[HashSize];</p><p>　　int count;</p><p><b>　　int size;</b></p><p>　　}HashTable3;</p><p><b>　　(2) 主函數(shù)模塊</b></p><p&g

39、t;　　void main()</p><p><b>　　{</b></p><p><b>　　int data;</b></p><p>　　HashTable1 hash1[HashSize];</p><p>　　HashTable2 * hash2[HashSize];</p>

40、;<p>　　HashTable3 * ha;</p><p>　　ha=(HashTable3 *)malloc(sizeof(HashTable3));</p><p>　　for(int i=0;i<HashSize;i++)</p><p>　　ha->elem[i]=NULL;</p><p>　　ha-&

41、gt;count=0;</p><p>　　ha->size=HashSize;</p><p>　　int a[MaxSize];</p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p>　　printf(&quo

42、t;\n ┏━━━━━━━━━━━━━━━┓ "); </p><p>　　printf("\n ┃ 歡迎使用本系統(tǒng) ┃ "); </p><p>　　printf("\n ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓"); </p><p>

43、;　　printf("\n ┃★ ★ ★ ★ ★ ★散列法的實(shí)驗(yàn)研究★ ★ ★ ★ ★ ★");</p><p>　　printf("\n ┃ 【1】. 添加數(shù)據(jù)信息 【2】 數(shù)據(jù)的輸出 ┃");</p><p>　　printf("\n ┃ 【3】. 建立哈希表(線性再散列)

44、 ");</p><p>　　printf("\n ┃ 【4】. 建立哈希表(二次探測(cè)再散列) ");</p><p>　　printf("\n ┃ 【5】. 建立哈希表(鏈地址法) ");</p><p>　　printf("\n

45、 ┃ 【6】. 線性再散列法查找 ┃");</p><p>　　printf("\n ┃ 【7】. 二次探測(cè)再散列法查找 ┃");</p><p>　　printf("\n ┃ 【8】. 鏈地址法查找

46、┃");</p><p>　　printf("\n ┃ 【0】. 退出程序 ┃");</p><p>　　printf("\n ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓");</p><p>　　printf("\n")

47、;</p><p>　　printf("\n");</p><p>　　printf("請(qǐng)輸入一個(gè)任務(wù)選項(xiàng)>>>");</p><p><b>　　int x;</b></p><p>　　scanf("%d",&x);</p&g

48、t;<p><b>　　switch(x)</b></p><p><b>　　{</b></p><p><b>　　case 1:</b></p><p>　　GetIn (a);break;</p><p><b>　　case 2:</b&

49、gt;</p><p>　　GetOut(a);break;</p><p><b>　　case 3:</b></p><p>　　CreateHashTable1(hash1,a,num);break;</p><p><b>　　case 4:</b></p><p>

50、　　CreateHash3(ha,a,num);break;</p><p><b>　　case 5:</b></p><p>　　CreateHashTable2(hash2,a,num);break;</p><p><b>　　case 6:</b></p><p>　　printf(&qu

51、ot;請(qǐng)輸入你查找的數(shù)據(jù)：");</p><p>　　scanf("%d",&data);</p><p>　　SearchHash1(hash1,data);break;</p><p><b>　　case 7:</b></p><p>　　printf("請(qǐng)輸入你查找

52、的數(shù)據(jù)：");</p><p>　　scanf("%d",&data);</p><p>　　SearchHash3(ha,data);break;</p><p><b>　　case 8:</b></p><p>　　printf("請(qǐng)輸入你查找的數(shù)據(jù)：");

53、</p><p>　　scanf("%d",&data);</p><p>　　SearchHash2(hash2,data,num);break;</p><p>　　case 0:exit(-1);</p><p><b>　　}</b></p><p><b

54、>　　} </b></p><p><b>　　}</b></p><p><b>　　3.2 核心代碼</b></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><

55、p>　　#define HashSize 53</p><p>　　#define MaxSize 20</p><p>　　typedef struct</p><p><b>　　{</b></p><p><b>　　int key;</b></p><p>&l

56、t;b>　　int si;</b></p><p>　　}HashTable1;</p><p>　　void CreateHashTable1(HashTable1 *H,int *a,int num)//哈希表線性探測(cè)在散列；</p><p><b>　　{</b></p><p>　　int i,

57、d,cnt;</p><p>　　for(i=0;i<HashSize;i++)</p><p><b>　　{</b></p><p>　　H[i].key=0;</p><p>　　H[i].si=0;</p><p><b>　　}</b></p>

58、<p>　　for(i=0;i<num;i++)</p><p><b>　　{</b></p><p><b>　　cnt=1;</b></p><p>　　d=a[i]%HashSize;</p><p>　　if(H[d].key==0)</p><p>

59、;<b>　　{</b></p><p>　　H[d].key=a[i];</p><p>　　H[d].si=cnt;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{<

60、;/b></p><p><b>　　do</b></p><p><b>　　{</b></p><p>　　d=(d+1)%HashSize;</p><p><b>　　cnt++;</b></p><p>　　}while(H[d].key

61、!=0);</p><p>　　H[d].key=a[i];</p><p>　　H[d].si=cnt;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("\n線性再探索哈希表已建成!")

62、;</p><p><b>　　}</b></p><p>　　void SearchHash1(HashTable1 *h,int data)</p><p><b>　　{</b></p><p><b>　　int d;</b></p><p>　

63、　d=data%HashSize;</p><p>　　if(h[d].key==data)</p><p>　　printf("數(shù)字%d的探查次數(shù)為：%d\n",h[d].key,h[d].si);</p><p><b>　　else</b></p><p><b>　　{</b&

64、gt;</p><p><b>　　do</b></p><p>　　d=(d+1)%HashSize;</p><p>　　while(h[d].key!=data && d<HashSize);</p><p>　　if(d<HashSize)</p><p>　　

65、printf("數(shù)字%d的探查次數(shù)為：%d\n",h[d].key,h[d].si);</p><p><b>　　else</b></p><p>　　printf("沒(méi)有查找到你所輸入的數(shù)\n");</p><p><b>　　}</b></p><p>

66、<b>　　}</b></p><p>　　typedef struct node</p><p><b>　　{</b></p><p><b>　　int key;</b></p><p><b>　　int si;</b></p>&l

67、t;p>　　struct node *next;</p><p><b>　　}Node;</b></p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　Node *link;</p><p>　　}HashTab

68、le2;</p><p>　　void CreateHashTable2(HashTable2 *ht[],int *a,int num)//哈希表鏈地址；</p><p><b>　　{</b></p><p>　　int i,d,cnt;</p><p>　　Node *s,*q;</p><p&

69、gt;　　for(i=0;i<num; i++)</p><p><b>　　{</b></p><p>　　ht[i]=(HashTable2 *)malloc(sizeof(HashTable2));</p><p>　　ht[i]->link=NULL;</p><p><b>　　}<

70、/b></p><p>　　for(i=0;i<num;i++)</p><p><b>　　{</b></p><p><b>　　cnt=1;</b></p><p>　　s=(Node *)malloc(sizeof(Node));</p><p>　　s-

71、>key=a[i];s->next=NULL;</p><p>　　d=a[i]%num;</p><p>　　if(ht[d]->link==NULL)</p><p><b>　　{</b></p><p>　　ht[d]->link=s;</p><p>　　s-&g

72、t;si=cnt;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　q=ht[d]->link;</p><p>　　while(q->next

73、!=NULL)</p><p><b>　　{</b></p><p>　　q=q->next;cnt++;</p><p><b>　　}</b></p><p><b>　　cnt++;</b></p><p>　　s->si=cnt;&

74、lt;/p><p>　　q->next=s;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void SearchHash2(HashTable2 * h[]

75、,int data,int num)</p><p><b>　　{</b></p><p><b>　　int d;</b></p><p><b>　　Node *q;</b></p><p>　　d=data%num;</p><p>　　q=h[

76、d]->link;</p><p>　　while(q->key!=data && q->next!=NULL)</p><p>　　q=q->next;</p><p>　　if(q->next!=NULL)</p><p>　　printf("數(shù)字%d的查找次數(shù)為：%d\n"

77、;,q->key,q->next);</p><p><b>　　else</b></p><p>　　printf("沒(méi)有找到你要查找的那個(gè)數(shù)\n");</p><p><b>　　}</b></p><p>　　typedef struct </p>

78、<p><b>　　{</b></p><p>　　int * elem[HashSize];</p><p>　　int count;</p><p><b>　　int size;</b></p><p>　　}HashTable3;</p><p>　　in

79、t Collision(int p,int &c)//二次探測(cè)再散列法解決沖突</p><p><b>　　{</b></p><p><b>　　int i,q;</b></p><p><b>　　i=c/2+1;</b></p><p>　　while(i<

80、HashSize)</p><p><b>　　{</b></p><p>　　if(c%2==0)</p><p><b>　　{</b></p><p><b>　　c++;</b></p><p>　　q=(p+i*i)%HashSize;<

81、/p><p><b>　　if(q>=0)</b></p><p><b>　　return q;</b></p><p><b>　　else</b></p><p><b>　　i=c/2+1;</b></p><p><

82、;b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　q=(p-i*i)%HashSize;</p><p><b>　　c++;</b></p><p>　　i

83、f(q>=0)return q;</p><p>　　else i=c/2+1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return (-1);</p><p><b>　　}</b>&

84、lt;/p><p>　　void CreateHash3(HashTable3 *h,int *a,int num)//二次探索表</p><p><b>　　{</b></p><p>　　int i,p=-1,c,pp;</p><p>　　for(i=0;i<num;i++)</p><p&g

85、t;<b>　　{</b></p><p><b>　　c=0;</b></p><p>　　p=a[i]%HashSize;</p><p><b>　　pp=p;</b></p><p>　　while(h->elem[pp]!=NULL)</p>&l

86、t;p><b>　　{</b></p><p>　　pp=Collision(p,c);</p><p><b>　　if(pp<0)</b></p><p><b>　　{</b></p><p>　　printf("第%d個(gè)記錄無(wú)法解決沖突\n&quo

87、t;,i+1);</p><p><b>　　continue;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　h->elem[pp]=&(a[a[i]]);</p><p>　

88、　h->count++;</p><p>　　printf("第%d個(gè)記錄沖突次數(shù)為%d\n",i+1,c);</p><p><b>　　}</b></p><p>　　printf("\n建表完成！\n此哈希表容量為%d,當(dāng)前表內(nèi)存儲(chǔ)的記錄個(gè)數(shù)%d.\n",HashSize,h->coun

89、t);</p><p><b>　　}</b></p><p>　　void SearchHash3(HashTable3 *h,int data)//哈希表二次探索再散列查找</p><p><b>　　{</b></p><p>　　int c=0,p,pp;</p><p&

90、gt;　　p=data%HashSize;</p><p><b>　　pp=p;</b></p><p>　　while((h->elem[pp]!=NULL)&&(*(h->elem[pp])!=data))</p><p>　　pp=Collision(p,c);</p><p>　　i

91、f((h->elem[pp]!=NULL)&&(*(h->elem[pp])==data))</p><p>　　printf("\n查找成功!\n查找沖突次數(shù)為%d:",c);</p><p><b>　　else</b></p><p>　　printf("\n沒(méi)有查到此數(shù)!\n&q

92、uot;);</p><p><b>　　}</b></p><p><b>　　int num;</b></p><p>　　void GetIn(int *a)</p><p><b>　　{</b></p><p>　　printf("輸

93、入添加的個(gè)數(shù)：");</p><p>　　scanf("%d",&num);</p><p>　　for(int i=0;i<num;i++)</p><p>　　scanf("%d",&a[i]);</p><p>　　printf("數(shù)據(jù)已經(jīng)輸入完畢!\n&

94、quot;);</p><p><b>　　}</b></p><p>　　void GetOut(int *a)</p><p><b>　　{</b></p><p>　　printf("你所輸入的數(shù)據(jù)：");</p><p>　　for(int i=

95、0;i<num;i++)</p><p>　　printf("%d,",a[i]);</p><p>　　printf("\n輸出已完畢!");</p><p><b>　　}</b></p><p>　　void main()</p><p><

96、;b>　　{</b></p><p><b>　　int data;</b></p><p>　　HashTable1 hash1[HashSize];</p><p>　　HashTable2 * hash2[HashSize];</p><p>　　HashTable3 * ha;</p>

97、;<p>　　ha=(HashTable3 *)malloc(sizeof(HashTable3));</p><p>　　for(int i=0;i<HashSize;i++)</p><p>　　ha->elem[i]=NULL;</p><p>　　ha->count=0;</p><p>　　ha-&g

98、t;size=HashSize;</p><p>　　int a[MaxSize];</p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p>　　printf("\n ┏━━━━━━━━━━━━━━━┓ "

99、); </p><p>　　printf("\n ┃ 歡迎使用本系統(tǒng) ┃ "); </p><p>　　printf("\n ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓"); </p><p>　　printf("\n ┃★ ★ ★ ★ ★ ★散列法的實(shí)驗(yàn)研

100、究★ ★ ★ ★ ★ ★┃");</p><p>　　printf("\n ┃ 【1】. 添加數(shù)據(jù)信息 【2】 數(shù)據(jù)的輸出 ┃");</p><p>　　printf("\n ┃ 【3】. 建立哈希表(線性再散列) ┃");</p><p>　　print

101、f("\n ┃ 【4】. 建立哈希表(二次探測(cè)再散列) ┃");</p><p>　　printf("\n ┃ 【5】. 建立哈希表(鏈地址法) ┃");</p><p>　　printf("\n ┃ 【6】. 線性再散列法查找

102、 ┃");</p><p>　　printf("\n ┃ 【7】. 二次探測(cè)再散列法查找 ┃");</p><p>　　printf("\n ┃ 【8】. 鏈地址法查找 ┃");</p><p>　　print

103、f("\n ┃ 【0】. 退出程序 ┃");</p><p>　　printf("\n ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛");</p><p>　　printf("\n");</p><p>　　printf("

104、;\n");</p><p>　　printf("請(qǐng)輸入一個(gè)任務(wù)選項(xiàng)>>>");</p><p><b>　　int x;</b></p><p>　　scanf("%d",&x);</p><p><b>　　switch(x)<

105、;/b></p><p><b>　　{</b></p><p><b>　　case 1:</b></p><p>　　GetIn (a);break;</p><p><b>　　case 2:</b></p><p>　　GetOut(a);

106、break;</p><p><b>　　case 3:</b></p><p>　　CreateHashTable1(hash1,a,num);break;</p><p><b>　　case 4:</b></p><p>　　CreateHash3(ha,a,num);break;</p

107、><p><b>　　case 5:</b></p><p>　　CreateHashTable2(hash2,a,num);break;</p><p><b>　　case 6:</b></p><p>　　printf("請(qǐng)輸入你查找的數(shù)據(jù)：");</p><

108、;p>　　scanf("%d",&data);</p><p>　　SearchHash1(hash1,data);break;</p><p><b>　　case 7:</b></p><p>　　printf("請(qǐng)輸入你查找的數(shù)據(jù)：");</p><p>　　s

109、canf("%d",&data);</p><p>　　SearchHash3(ha,data);break;</p><p><b>　　case 8:</b></p><p>　　printf("請(qǐng)輸入你查找的數(shù)據(jù)：");</p><p>　　scanf("%

110、d",&data);</p><p>　　SearchHash2(hash2,data,num);break;</p><p>　　case 0:exit(-1);</p><p><b>　　}</b></p><p><b>　　} </b></p><p&

111、gt;<b>　　}</b></p><p>　　3.3 程序運(yùn)行結(jié)果（拷屏）</p><p>　　利用線性再散列法，二次探查再散列，鏈地址法解決沖突</p><p>　　4. 課程設(shè)計(jì)心得、存在問(wèn)題及解決方法</p><p><b>　　(1) 收獲</b></p><p&g

112、t;　　通過(guò)本次課程設(shè)計(jì)，使我對(duì)計(jì)算機(jī)語(yǔ)言有了更深一層的了解，也使我對(duì)算法的運(yùn)用有了更多的體會(huì)，對(duì)算法和生活的聯(lián)系也有了更多的體會(huì)。更進(jìn)一步了解和熟悉了關(guān)于哈希表的創(chuàng)建和運(yùn)用。現(xiàn)在，計(jì)算機(jī)領(lǐng)域，他只向我展現(xiàn)了冰山一角，以后我會(huì)繼續(xù)探索。好的算法源于我們不斷的思考，思考源于我們對(duì)夢(mèng)想的追尋。</p><p><b>　　(2) 心得體會(huì)</b></p><p>　　在