中南大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法第9章查找課后作業(yè)答案

1、第9章查找習(xí)題練習(xí)答案1.對(duì)含有n個(gè)互不相同元素的集合，同時(shí)找最大元和最小元至少需進(jìn)行多少次比較?答：設(shè)變量max和min用于存放最大元和最小元(的位置)，第一次取兩個(gè)元素進(jìn)行比較，大的放入max，小的放入min。從第2次開(kāi)始，每次取一個(gè)元素先和max比較，如果大于max則以它替換max，并結(jié)束本次比較；若小于max則再與min相比較，在最好的情況下，一路比較下去都不用和min相比較，所以這種情況下，至少要進(jìn)行n-1次比較就能找到最大元和最小元。2.若對(duì)具有n個(gè)元素的有序的順序表和無(wú)序的順序表分別進(jìn)行順序查找，試在下述兩種情況下分別討論兩者在等概率時(shí)的平均查找長(zhǎng)度：(1)查找不成功，即表中無(wú)關(guān)

2、鍵字等于給定值K的記錄；(2)查找成功，即表中有關(guān)鍵字等于給定值K的記錄。答：查找不成功時(shí)，需進(jìn)行n+1次比較才能確定查找失敗。因此平均查找長(zhǎng)度為n+1，這時(shí)有序表和無(wú)序表是一樣的。查找成功時(shí)，平均查找長(zhǎng)度為(n+1)/2,有序表和無(wú)序表也是一樣的。因?yàn)轫樞虿檎遗c表的初始序列狀態(tài)無(wú)關(guān)。3.畫(huà)出對(duì)長(zhǎng)度為18的有序的順序表進(jìn)行二分查找的判定樹(shù)，并指出在等概率時(shí)查找成功的平均查找長(zhǎng)度，以及查找失敗時(shí)所需的最多的關(guān)鍵字比較次數(shù)。答： 等概率情況下，查找成功的平均查找長(zhǎng)度為：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556查找失敗時(shí)，最多的關(guān)鍵字比較次樹(shù)不超過(guò)判定樹(shù)的深度，此處為5.4.

3、為什么有序的單鏈表不能進(jìn)行折半查找?答：因?yàn)殒湵頍o(wú)法進(jìn)行隨機(jī)訪問(wèn)，如果要訪問(wèn)鏈表的中間結(jié)點(diǎn)，就必須先從頭結(jié)點(diǎn)開(kāi)始進(jìn)行依次訪問(wèn)，這就要浪費(fèi)很多時(shí)間，還不如進(jìn)行順序查找，而且，用鏈存儲(chǔ)結(jié)構(gòu)將無(wú)法判定二分的過(guò)程是否結(jié)束，因此無(wú)法用鏈表實(shí)現(xiàn)二分查找。5.設(shè)有序表為(a,b,c,e,f,g,i,j,k,p,q),請(qǐng)分別畫(huà)出對(duì)給定值b,g和n進(jìn)行折半查找的過(guò)程。 解：(1)查找b的過(guò)程如下(其中方括號(hào)表示當(dāng)前查找區(qū)間，圓括號(hào)表示當(dāng)前比較的關(guān)鍵字)下標(biāo)： 1 2 3 4 5 6 7 8 9 10 11 12 13第一次比較： a b c d e f (g) h i j k p q第二次比較： a b (c)

4、 d e f g h i j k p q第三次比較： a (b)c d e f g h i j k p q經(jīng)過(guò)三次比較，查找成功。 (2)g的查找過(guò)程如下： a b c d e f (g) h i j k p q 一次比較成功。 (3)n的查找過(guò)程如下： 下標(biāo)： 1 2 3 4 5 6 7 8 9 10 11 12 13 第一次比較： a b c d e f (g) h i j k p q 第二次比較： a b c d e f g h i (j) k p q 第三次比較： a b c d e f g h i j k (p) q 第四次比較： a b c d e f g h i j k p q

5、經(jīng)過(guò)四次比較，查找失敗。6.將(for, case, while, class, protected, virtual, public, private, do, template, const ,if, int)中的關(guān)鍵字依次插入初態(tài)為空的二叉排序樹(shù)中，請(qǐng)畫(huà)出所得到的樹(shù)T。然后畫(huà)出刪去for之后的二叉排序樹(shù)T,若再將for 插入T中得到的二叉排序樹(shù)T是否與T相同?最后給出T的先序、中序和后序序列。答：二叉排序樹(shù)T如下圖： 刪去for后的二叉排序樹(shù)如下圖：再插入結(jié)點(diǎn)for后的二叉排序樹(shù)T： 二叉排序樹(shù)T與T不同 T的先序序列是：do case class const while protect

6、ed private if for int virtual public templateT的中序序列是：case class const do for if int private protected public template virtual whileT的后序序列是：const class case for int if private template public virtual protected while do7.對(duì)給定的關(guān)鍵字集合，以不同的次序插入初始為空的樹(shù)中，是否有可能得到同一棵二叉排序樹(shù)?答： 有可能。如有兩個(gè)序列：3，1，2，4 和 3，4，1，2，它們插入空樹(shù)所

7、得的二叉排序樹(shù)是相同的。8.將二叉排序樹(shù)T的先序序列中的關(guān)鍵字依次插入一空樹(shù)中，所得和二叉排序樹(shù)T與T否相同?為什么?答： 這兩棵二叉樹(shù)完全相同。9.設(shè)二叉排序樹(shù)中關(guān)鍵字由1至1000的整數(shù)構(gòu)成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點(diǎn)，下述關(guān)鍵字序列哪一個(gè)不可能是在二叉排序樹(shù)上查找到的序列?(a) 2，252，401，398，330, 344，397，363；(b) 924, 220, 911, 244, 898, 258, 362, 363;(c) 925, 202, 911, 240, 912, 245, 363;(d) 2, 399, 387, 219, 266, 382, 381, 278, 3

8、63.答：(c)是不可能查找到的序列。把這四個(gè)序列各插入到一個(gè)初始為空的二叉排序樹(shù)中，結(jié)果可以發(fā)現(xiàn)，(c)序列所形成的不是一條路徑，而是有分支的，可見(jiàn)它是不可能在查找過(guò)程中訪問(wèn)到的序列。10.設(shè)二叉排序樹(shù)中關(guān)鍵字互不相同，則其中最小元必?zé)o左孩子，最大元必?zé)o右孩子。此命題是否正確?最小元和最大元一定是葉子嗎?一個(gè)新結(jié)點(diǎn)總是插在二叉排序樹(shù)的某葉子上嗎?答：此命題正確。假設(shè)最小元有左孩子，則根據(jù)二叉排序樹(shù)性質(zhì)，此左孩子應(yīng)比最小元更小，如此一來(lái)就產(chǎn)生矛盾了，因此最小元不可能有左孩子，對(duì)于最大元也是這個(gè)道理。 但最大元和最小元不一定是葉子，它也可以是根、內(nèi)部結(jié)點(diǎn)(分支結(jié)點(diǎn))等，這得根據(jù)插入結(jié)點(diǎn)時(shí)的次序而

9、定。新結(jié)點(diǎn)總是作為葉子插入在二叉排序樹(shù)中的。11.在一棵m階的B-樹(shù)中，當(dāng)將一關(guān)鍵字插入某結(jié)點(diǎn)而引起該結(jié)點(diǎn)的分裂時(shí)，此結(jié)點(diǎn)原有多少個(gè)關(guān)鍵字?若刪去某結(jié)點(diǎn)中的一個(gè)關(guān)鍵字，而導(dǎo)致結(jié)點(diǎn)合并時(shí)，該結(jié)點(diǎn)中原有幾個(gè)關(guān)鍵字?答：在一棵m階的B-樹(shù)中，若由于一關(guān)鍵字的插入某結(jié)點(diǎn)而引起該結(jié)點(diǎn)的分裂時(shí)，則該結(jié)點(diǎn)原有m-1個(gè)關(guān)鍵字。若刪去某結(jié)點(diǎn)中一個(gè)關(guān)鍵字而導(dǎo)致結(jié)點(diǎn)合并時(shí)，該結(jié)點(diǎn)中原有m/2-1個(gè)關(guān)鍵字。12.在一棵B-樹(shù)中，空指針數(shù)總是比關(guān)鍵字?jǐn)?shù)多一個(gè)，此說(shuō)法是否正確?請(qǐng)問(wèn)包含8個(gè)關(guān)鍵字的3階B-樹(shù)(即2-3樹(shù))最多有幾個(gè)結(jié)點(diǎn)?最少有幾個(gè)結(jié)點(diǎn)?畫(huà)出這兩種情況的B-樹(shù)。答：這個(gè)說(shuō)法是正確的。包含8個(gè)關(guān)鍵字的3階B-

10、樹(shù)最多有7個(gè)結(jié)點(diǎn)，最少有4個(gè)結(jié)點(diǎn)。13.從空樹(shù)開(kāi)始，依次輸入20，30，50，52，60，68，70，畫(huà)出建立2-3樹(shù)的過(guò)程。并畫(huà)出刪除50和68后的B-樹(shù)狀態(tài)。答：過(guò)程如下：(1) 插入20，30： (2) 插入50：(3) 插入52：(4) 插入60：(5) 插入68：(6) 插入70：(7)刪去50：(8) 刪去6814.畫(huà)出依次插入z,v,o,p,w,y到圖9.12(h)所示的5階B-樹(shù)的過(guò)程。 解： (1)插入z后：(2)插入v,o后 (3)插入p,w,y后 16.為什么在內(nèi)存中使用的B-樹(shù)通常是3階的，而不使用更高階的B-樹(shù)? 答： 因?yàn)椴檎业炔僮鞯腸pu時(shí)間在B-樹(shù)上是O(lgn

11、(m/lgt),而m/lgt1,所以m較大時(shí)它所費(fèi)時(shí)間比平衡的二叉排序樹(shù)上相應(yīng)操作時(shí)間大得多，因此，僅在內(nèi)存中使用的B-樹(shù)通常取最小值317.為什么二叉排序樹(shù)長(zhǎng)高時(shí)，新結(jié)點(diǎn)總是一個(gè)葉子，而B(niǎo)-樹(shù)長(zhǎng)高時(shí)，新結(jié)點(diǎn)總是根?哪一種長(zhǎng)高能保證樹(shù)平衡?答： 因?yàn)樵诙媾判驑?shù)中，關(guān)鍵字總是作為一個(gè)葉子結(jié)點(diǎn)插入以原來(lái)的樹(shù)中，所以當(dāng)樹(shù)增高時(shí)，新結(jié)點(diǎn)總是一個(gè)葉子；而B(niǎo)-樹(shù)中關(guān)鍵字插入總是插入到葉子結(jié)點(diǎn)內(nèi)部，在葉結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目尚未超過(guò)它能夠容納的數(shù)目之前是不會(huì)增加結(jié)點(diǎn)的，當(dāng)關(guān)鍵字?jǐn)?shù)超過(guò)結(jié)點(diǎn)可容納的數(shù)目時(shí)，葉結(jié)點(diǎn)就會(huì)發(fā)生分裂，產(chǎn)生一個(gè)新結(jié)點(diǎn)(但不一定引起樹(shù)增高)，并且將其中的中間結(jié)點(diǎn)傳至上一層，只有當(dāng)這種分裂操作

12、傳遞至根結(jié)點(diǎn)并引起根結(jié)點(diǎn)的分裂時(shí)，才能引起樹(shù)高增加，此時(shí)產(chǎn)生一個(gè)新的根結(jié)點(diǎn)。所以說(shuō)B樹(shù)長(zhǎng)高時(shí)，新結(jié)點(diǎn)總是根。 顯然，后一種長(zhǎng)高總能保證樹(shù)的平衡。19.對(duì)于一組給定的、固定不變的關(guān)鍵字序列，有可能設(shè)計(jì)出無(wú)沖突的散列函數(shù)H，此時(shí)稱(chēng)H為完備的散列函數(shù)(perfect hashing function)，若H能無(wú)沖突地將關(guān)鍵字完全填滿(mǎn)散列表，則稱(chēng)H是最小完備(minimal perfect)的散列函數(shù)。通常找完備的散列函數(shù)非常困難，找最小完備的散列函數(shù)就更困難。請(qǐng)問(wèn)： (1)若h是已知關(guān)鍵字集合K的完備的散列函數(shù)，若要增加一個(gè)新的關(guān)鍵字到集合K，一般情況下H還是完備的嗎?(2)已知關(guān)鍵字集合為(81，

13、129，301，38，434，216，412，487，234)，散列函數(shù)為H(x)=(x+18)/63,請(qǐng)問(wèn)H是完備的嗎?它是最小完備的嗎?(3)考慮由字符串構(gòu)成的關(guān)鍵字集合(Bret,Jane,Shirley,Bryce,Michelle,Heather)，試為散列表0.6設(shè)計(jì)一個(gè)完備的散列函數(shù)。(提示：考慮每個(gè)字符串的第3個(gè)字符，即s2)答：(1) 一般情況下H不是完備的，如果說(shuō)插入一個(gè)新的關(guān)鍵字它還是完備的，那么再插入一個(gè)呢?它豈不是永遠(yuǎn)是完備的散列函數(shù)了? 所以一般情況下它不能總是完備的，只有一些很少的情況下它還可能是完備的。(2)這個(gè)H是完備的，其函數(shù)值依次為：1，2，5，0，7，3

14、，6，8，4。如果散列表長(zhǎng)m=9時(shí)，它就是最小完備的。(3) 這個(gè)函數(shù)如下：int Hash (char key) return key2%7;20.設(shè)散列函數(shù)為h(key)=key%101,解決沖突的方法為線性探查，表中用-1表示空單元。若刪去散列表HT中的304(即令HT1=-1)之后，在表HT中查找707將會(huì)發(fā)生什么?若將刪去的表項(xiàng)標(biāo)記為-2,查找時(shí)探查到-2繼續(xù)向前搜索，探查到-1時(shí)終止搜索。請(qǐng)問(wèn)用這種方法刪304后能否正確地查找到707?0 1 2 3 100HT202 304 507 707 . 答： 查找707時(shí)，首先根據(jù)散列函數(shù)計(jì)算得出該元素應(yīng)在散列表中的0單元，但是在0單元沒(méi)

15、有找到，因此將向下一單元探查，結(jié)果發(fā)現(xiàn)該單元是-1(為空單元)，所以結(jié)束查找，這將導(dǎo)致707無(wú)法找到。 如果改用-2作為刪除標(biāo)記，則可以正確找到707所在的結(jié)點(diǎn)。21.設(shè)散列表長(zhǎng)度為11，散列函數(shù)h(x)=x%11,給定的關(guān)鍵字序列為：1，13，13，34，38，33，27，22.試畫(huà)出分別用拉鏈法和線性探查法解決沖突時(shí)所構(gòu)造的散列表，并求出在等概率情況下，這兩種方法查找成功和失敗時(shí)的平均查找長(zhǎng)度。請(qǐng)問(wèn)裝填因子的值是什么?答：(1)拉鏈法如下圖： T0.10 0 33 22 1 1 12 34 2 13 3 4 5 38 27 6 7 8 9 10 (2)線性探查法如下圖： 下標(biāo) 0 1 2

16、3 4 5 6 7 8 9 10 T0.10331 131234382722 探查次數(shù) 1 1 1 3 4 1 7 8 用拉鏈法的查找成功平均查找長(zhǎng)度為： ASLsucc=(1*4+2*3+3*1)/8=1.625 查找失敗時(shí)平均查找長(zhǎng)度為： ASLunsucc=(2+3+1+0+0+0+2+0+0+0+0)/11=0.73 用線性探查法查找成功時(shí)平均查找長(zhǎng)度為： ASLsucc=(1+1+1+3+4+1+7+8)/8=3.25 查找失敗時(shí)平均查找長(zhǎng)度為： ASLunsucc=(9+8+7+6+5+4+3+2+1+1+1)/11=4.3 裝填因子拉鏈=4/11=0.36 線性探查=8/11=0

17、.7322.假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探查法把這些同義詞存入散列表中，至少要進(jìn)行多少次探查?答： 至少要進(jìn)行1+2+3.+k-1+k次探查。 也就是說(shuō)，在散列表的一連串連續(xù)空間內(nèi)，第一個(gè)關(guān)鍵字只需探查一次，第二個(gè)就要探查2次，如此這般，第k個(gè)關(guān)鍵字就要探查k次才能找到位置存放。所以至少要把它們?nèi)悠饋?lái)才夠。23.為什么說(shuō)當(dāng)裝填因子非常接近1時(shí)，線性探查類(lèi)似于順序查找?為什么說(shuō)當(dāng)裝填因子比較小(比如=0.7左右)時(shí)，散列查找的平均查找時(shí)間為O(1)?答： 當(dāng)非常接近1時(shí)，整個(gè)散列表幾乎被裝滿(mǎn)。由于線性探查法在關(guān)鍵字同義時(shí)解決沖突的辦法是線性地向后查找，當(dāng)整個(gè)表幾乎裝滿(mǎn)時(shí)，它就很類(lèi)似于順

18、序查找了。 當(dāng)比較小時(shí)，關(guān)鍵字碰撞的幾率比較小，一般情況下只要按照散列函數(shù)計(jì)算出的結(jié)果能夠1次性就找到相應(yīng)結(jié)點(diǎn)，因此它的平均查找時(shí)間接近于1.24.設(shè)順序表中關(guān)鍵字是遞增有序的，試寫(xiě)一順序查找算法，將哨兵設(shè)在表的高下標(biāo)端。然后求出等概率情況下查找成功與失敗時(shí)的ASL.答: typedef structKeyType key；InfoType otherinfo； /此類(lèi)型依賴(lài)于應(yīng)用NodeType；typedef NodeType SeqListn+1； /n號(hào)單元用作哨兵int SeqSearch(Seqlist R，KeyType K) /在關(guān)鍵字遞增有序的順序表R0.n-1中順序查找關(guān)鍵

19、字為K的結(jié)點(diǎn)，/成功時(shí)返回找到的結(jié)點(diǎn)位置，失敗時(shí)返回-1int i；Rn.key=K； /設(shè)置哨兵for(i=0；Ri.key=K;i-)； /從表前往后找if (in&Ri.key=K) return i; /Ri是要找的結(jié)點(diǎn)else return -1 /SeqSearch等概率情況下查找成功ASL=(1+2+3+n)/n等概率情況下查找失敗時(shí)的ASL=(1+2+3+n+n+1)/(n+1)25試寫(xiě)出二分查找的遞歸算法。解： int BinSearch(SeqList R，KeyType K，int low，int high) /在有序表Rlow.high中進(jìn)行二分查找，成功時(shí)返回結(jié)點(diǎn)的位

20、置，失敗時(shí)返回零int mid； /置當(dāng)前查找區(qū)間上、下界的初值if (lowK)return BinSearch( R，K,low，mid-1)/在Rlow.mid-1中查找elsereturn BinSearch( R，K,mid+1，high)； /在Rmid+1.high中查找return 0； /當(dāng)lowhigh時(shí)表示查找區(qū)間為空，查找失敗 /BinSeareh26試寫(xiě)一算法判別給定的二叉樹(shù)是否為二叉排序樹(shù)，設(shè)此二叉樹(shù)以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，且樹(shù)中結(jié)點(diǎn)的關(guān)鍵字均不相同。解：由二叉排序樹(shù)的定義可得：二叉排序樹(shù)中左子樹(shù)的所有結(jié)點(diǎn)的值都小于根結(jié)點(diǎn)的值，所有右子樹(shù)中結(jié)點(diǎn)的值都大于根結(jié)點(diǎn)的值。那

21、么只要對(duì)待判定的二叉樹(shù)中的結(jié)點(diǎn)按層遍歷并判斷即可。在該算法中要用到隊(duì)列保存已遍歷的結(jié)點(diǎn)指針。typedef BinTNode *DataType;/循環(huán)隊(duì)列中元素為二叉樹(shù)結(jié)點(diǎn)指針int BinSortStree(BinTree T)CirQueue Q;BinTNode *p;if (!T) return 1;/空樹(shù)為二叉排序樹(shù)InitQueue(&Q);EnQueue(&Q,T);while(!QueueEmpty(&Q)p=DeQueue(&Q);if (p-lchild)if (p-datalchild-data) return -1;/不是二叉排序樹(shù)else EnQueue(&Q,p-

22、lchild);if (p-rchild)if (p-datap-rchild-data) return -1;/不是二叉排序樹(shù)else EnQueue(&Q,p-rchild);return 1;/是二叉排序樹(shù)27.試寫(xiě)一遞歸算法，從大到小輸出二叉排序樹(shù)中所有其值不小于x的關(guān)鍵字。要求算法的時(shí)間為O(lgn+m)，n為樹(shù)中結(jié)點(diǎn)數(shù)，m為輸出關(guān)鍵字個(gè)數(shù)(提示：先遍歷右子樹(shù)，后遍歷左子樹(shù))。答：typedef int KeyType； /假定關(guān)鍵字類(lèi)型為整數(shù)typedef struct node /結(jié)點(diǎn)類(lèi)型KeyType key； /關(guān)鍵字項(xiàng)InfoType otherinfo； /其它數(shù)據(jù)域，I

23、nfoType視應(yīng)用情況而定，下面不處理它struct node *lchild，*rchild； /左右孩子指針 BSTNode；typedef BSTNode *BSTree；void OUTPUTNODE(BSTree T,KeyType x)/從大到小輸出二叉排序樹(shù)中所有其值不小于x的關(guān)鍵字if (T)OUTPUTNODE( T-rchild,x);if (T-key=x) printf(%d,T-key);OUTPUTNODE( T-Lchild,x);28.寫(xiě)一個(gè)遍歷B-樹(shù)的算法，使輸出的關(guān)鍵字序列遞增有序。算法中的讀盤(pán)操作可假定為DiskRead。答：#define Max l0

24、00 /結(jié)點(diǎn)中關(guān)鍵字的最大數(shù)目：Max=m-1，m是B-樹(shù)的階#define Min 500 /非根結(jié)點(diǎn)中關(guān)鍵字的最小數(shù)目：Min=m/2(-1typedef int KeyType； /KeyType應(yīng)由用戶(hù)定義typedef struct node /結(jié)點(diǎn)定義中省略了指向關(guān)鍵字代表的記錄的指針int keynum； /結(jié)點(diǎn)中當(dāng)前擁有的關(guān)鍵字的個(gè)數(shù)，keynum=MaxKeyType keyMax+1； /關(guān)鍵字向量為key1.keynum，key0不用。struct node *parent； /指向雙親結(jié)點(diǎn)struct node *sonMax+1；/孩子指針向量為son0.keynum

25、BTreeNode；typedef BTreeNode *BTree；void travelBtree(BTree T)/按關(guān)鍵字遞增序輸出B-樹(shù)序列int i;if (T)for(i=0;ikeynum;i+)/T-keynum個(gè)關(guān)鍵字的結(jié)點(diǎn)有T-keynum+1棵子樹(shù)if (T-soni)DiskRead(T-soni);/讀入根結(jié)點(diǎn)的第i棵子樹(shù)travelBtree(T-soni);/遍歷第i棵子樹(shù)if (ikeynmu)/若剛遍歷的子樹(shù)不是最后一棵子樹(shù)printf(%d,T-keyi+1; 29若采用除余法作為散列函數(shù)，線性探查解決沖突，則9.4.4節(jié)中通用的散列表查找算法可改寫(xiě)為對(duì)線

26、性探查專(zhuān)用的查找算法：int HashSearch(HashTable T,KeyType K,int *pos)int i=0;/記錄探查次數(shù)*pos=K%m; /散列函數(shù)值作為第一個(gè)散列地址while(i+m) /最多探查m次if(T*pos.key=K) return 1;/查找成功返回if(T*pos.key=NIL) return 0;/查找失敗返回*pos=(*pos+1)%m;/用線性探查法求下一個(gè)探查地址return -1;/查找失敗，且表滿(mǎn)/HashSearch假設(shè)散列表上的刪除操作已將結(jié)點(diǎn)的關(guān)鍵字標(biāo)記為DELETED(例如，不妨設(shè)DELETED為-2)。請(qǐng)修改上述散列表上的

27、查找算法及插入算法HashInsert，使之能正確地查找和插入。解：(1)查找算法#define DELETED -2#define NIL -1 /空結(jié)點(diǎn)標(biāo)記依賴(lài)于關(guān)鍵字類(lèi)型，本節(jié)假定關(guān)鍵字均為非負(fù)整數(shù)#define M 997 /表長(zhǎng)度依賴(lài)于應(yīng)用，但一般應(yīng)根據(jù)。確定m為一素?cái)?shù)typedef struct /散列表結(jié)點(diǎn)類(lèi)型KeyType key；InfoType otherinfo； /此類(lèi)依賴(lài)于應(yīng)用NodeType；typedef NodeType HashTablem； /散列表類(lèi)型int HashSearch(HashTable T,KeyType K,int *pos)int i=0;/記錄探查次數(shù)*pos=K%m; /散列函數(shù)值作為第一個(gè)散列地址while(i+m) /最多探查m次if(T*pos.key=K) return 1;/查找成功返回if(T*pos.key=NIL) return 0;/查找失敗返回*pos=(*pos+1)%m;/用線