數(shù)據(jù)結(jié)構(gòu)作業(yè)-分塊查找算法

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告三題目：試編寫利用折半查找確定記錄所在塊的分塊查找算法。提示：讀入各記錄建立主表；按L個(gè)記錄/塊建立索引表；對(duì)給定關(guān)鍵字k進(jìn)行查找；測(cè)試實(shí)例：設(shè)主表關(guān)鍵字序列：12221382833384287765063991019796，L=4，依次查找K=13，K=86，K=88算法思路題意要求對(duì)輸入的關(guān)鍵字序列先進(jìn)行分塊，得到分塊序列。由于序列不一定有序，故對(duì)分塊序列進(jìn)行折半查找，找到關(guān)鍵字所在的塊，然后對(duì)關(guān)鍵字所在的塊進(jìn)行順序查找，從而找到關(guān)鍵字的位置。故需要折半查找和順序查找兩個(gè)函數(shù)，考慮用C+中的類函數(shù)實(shí)現(xiàn)。因?yàn)樾蛄幸话闶怯脭?shù)組進(jìn)行存儲(chǔ)的，這樣可以調(diào)用不同類型的數(shù)組，程序的可適用

2、性更大一些。折半查找函數(shù)：ints,d,ss,dd;聲明一些全局變量，方便函數(shù)與主函數(shù)之間的變量調(diào)用。templateintBinSearch(TA,intlow,inthigh,Tkey)/遞歸實(shí)現(xiàn)折半查找intmid;/初始化中間值的位置Tmidvalue;/初始化中間值if(lowhigh)s=Ahigh;d=Alow;ss=high;dd=low;return-1;/如果low的值大于high的值，輸出-1，并且將此時(shí)的low與high的值存儲(chǔ)。elsemid=(low+high)/2;/中間位置為低位與高位和的一半取整。midvalue=Amid;if(midvalue=key)re

3、turnmid;elseif(midvaluekey)/如果關(guān)鍵字的值大于中間值returnBinSearch(A,mid+1,high,key);/遞歸調(diào)用函數(shù)，搜索下半部分elsereturnBinSearch(A,low,mid-1,key);/否則遞歸調(diào)用哦個(gè)函數(shù)，搜索上半部分以上為通用的折半查找的函數(shù)代碼，這里引入了幾個(gè)全局變量，主要是方便在搜索關(guān)鍵字在哪一個(gè)分塊中時(shí)，作為判斷條件。順尋查找函數(shù)：templateintshuxuSearch(TA,inthigh,Tkey)/順序查找inti=0;Ahigh=key;初始化i,使A的最高位為key值while(Ai!=key)i+;r

4、eturni;如果A中有key值，則在i不到n+1時(shí)就會(huì)輸出，否則，返回high值,說明搜索失敗。主函數(shù)中，首先對(duì)所需要的參數(shù)變量進(jìn)行初始化，由鍵盤輸入關(guān)鍵字，分塊的多少，每一塊有多少個(gè)關(guān)鍵字。為了用戶的人性化考慮，這里由用戶自己決定分塊的多少和數(shù)目。為了實(shí)現(xiàn)這一功能，引入了一個(gè)動(dòng)態(tài)存儲(chǔ)的二維數(shù)組：int*p2;p2=newint*row;/聲明一個(gè)二維數(shù)組for(i=0;irow;i+)p2i=newintcol;for(i=0;irow;i+)for(j=0;jBi;j+)p2ij=Ak;k=k+1;/將所有關(guān)鍵字，按塊的不同存入二維數(shù)組中coutvv分塊情況為endl;for(i=0;i

5、row;i+)for(j=0;jBi;j+)coutp2ij=Mi)Mi=p2ij;coutendl;/輸出二維數(shù)組，檢驗(yàn)分塊是否為預(yù)期將各種信息用各種數(shù)組加以存儲(chǔ)，在需要時(shí)不斷調(diào)用。另外，由于題目中需要多次查找，為了避免每次查找的反復(fù)輸入，引入了一個(gè)while循環(huán)，保證可以多次查找并輸出結(jié)果。在關(guān)鍵字等信息輸入完畢后，進(jìn)行查找，可以得到該關(guān)鍵字所在塊的序號(hào)，以及該關(guān)鍵字在整個(gè)關(guān)鍵字序列中的位置。程序結(jié)構(gòu)輸入每個(gè)分塊中的關(guān)鍵字的個(gè)數(shù)調(diào)用順序查找函數(shù)，對(duì)關(guān)鍵字所判斷函數(shù)返回至是否等于輸入數(shù)組長YES輸出位置輸出無該關(guān)鍵字YES.詢問用戶是否再次查找”1源代碼：#includeusingnames

6、pacestd;ints,d,ss,dd;聲明一些全局變量，方便函數(shù)與主函數(shù)之間的變量調(diào)用。templateintBinSearch(TA,intlow,inthigh,Tkey)/遞歸實(shí)現(xiàn)折半查找intmid;/初始化中間值的位置Tmidvalue;/初始化中間值if(lowhigh)s=Ahigh;d=Alow;ss=high;dd=low;return-1;/如果low的值大于high的值，輸出-1，并且將此時(shí)的low與high的值存儲(chǔ)。elsemid=(low+high)/2;/中間位置為低位與高位和的一半取整。midvalue=Amid;if(midvalue=key)returnm

7、id;elseif(midvaluekey)/如果關(guān)鍵字的值大于中間值returnBinSearch(A,mid+1,high,key);/遞歸調(diào)用函數(shù)，搜索下半部分elsereturnBinSearch(A,low,mid-1,key);/否則遞歸調(diào)用哦個(gè)函數(shù)，搜索上半部分templateintshuxuSearch(TA,inthigh,Tkey)/順序查找inti=0;Ahigh=key;初始化i,使A的最高位為key值while(Ai!=key)i+;returni;如果A中有key值，則在i不到n+1時(shí)就會(huì)輸出，否則，返回high值,說明搜索失敗。intmain()inti,key,

8、pos,length,fen,k,j,a,kuai,e;/定義一些變量a=0;k=0;coutvv請(qǐng)輸入關(guān)鍵字的個(gè)數(shù)length;intAlength-1;/根據(jù)輸入關(guān)鍵字的個(gè)數(shù)初始化一個(gè)數(shù)組進(jìn)行存儲(chǔ)coutvv請(qǐng)輸入要分塊的個(gè)數(shù)vvendl;cinfen;intBfen-1;intMfen-1;for(i=0;ivfen;i+)Mi=0;/初始化兩個(gè)數(shù)組，一個(gè)用來存儲(chǔ)每一塊元素的大小，另一個(gè)用來存儲(chǔ)每一塊的中元素的最大值coutvv請(qǐng)輸入每個(gè)分塊關(guān)鍵字的個(gè)數(shù)vvendl;for(i=0;ivfen;i+)cinBi;使數(shù)組B中表示每塊中關(guān)鍵字的個(gè)數(shù)coutvv請(qǐng)輸入關(guān)鍵字endl;for(i

9、=0;iAi;輸入所有的關(guān)鍵字，存在數(shù)組A中introw,col;row=fen;col=length;int*p2;p2=newint*row;/聲明一個(gè)二維數(shù)組for(i=0;irow;i+)p2i=newintcol;for(i=0;irow;i+)for(j=0;jBi;j+)p2ij=Ak;k=k+1;/將所有關(guān)鍵字，按塊的不同存入二維數(shù)組中coutvv分塊情況為endl;for(i=0;i=Mi)Mi=p2ij;coutvvendl;/輸出二維數(shù)組，檢驗(yàn)分塊是否為預(yù)期coutvv每個(gè)塊最大元素為vvendl;for(i=0;ivfen;i+)coutvvMivvendl;將每一組的

10、最大元素存入數(shù)組M中coutvvendlvv請(qǐng)輸入要查找的元素；cinkey;將要查找的關(guān)鍵字賦值給keypos=BinSearch(M,O,length-1,key);調(diào)用折半查找函數(shù)，查找關(guān)鍵字處于哪個(gè)塊中coutvv該元素所處的塊是vvendl;if(pos!=-1)kuai=pos;coutvvkuaivvendl;elsekuai=dd;coutvvkuaivvendl;將關(guān)鍵字所在的塊輸出。int*S;S=newintkuai;for(i=0;iBkuai;i+)Si=p2kuaii;/初始化一個(gè)一維數(shù)組，將關(guān)鍵字所在快的元素重新定義為一個(gè)數(shù)組Spos=shuxuSearch(S,

11、Bkuai,key);在S中順序查找關(guān)鍵字intq=0;for(i=0;ikuai;i+)q=q+Bi;if(pos!=Bkuai)coutvv該元素的位置為vvpos+qvvendl;如果關(guān)鍵字存在，輸出其位置elsecoutvv不存在該元素endl;若不存在，輸出“不存在該元素”coutvv還要繼續(xù)查找嗎？是的話，輸入1,不是的話輸入0e;/引入判斷條件，以便多次查找while(e!=1)&(e!=0)coutvv輸入不合法，請(qǐng)重新輸入ee;保證輸入合法while(e=1)coutvvendlvv請(qǐng)輸入要查找的元素；cinkey;pos=BinSearch(M,0,length-1,key

12、);coutvv該元素所處的塊是vvendl;if(pos!=-1)kuai=pos;coutvvkuaivvendl;elsekuai=dd;coutvvkuaivvendl;for(i=0;ivBkuai;i+)Si=p2kuaii;pos=shuxuSearch(S,Bkuai,key);intq=0;for(i=0;ivkuai;i+)q=q+Bi;if(pos!=Bkuai)coutvv該元素的位置為vvpos+qvvendl;elsecoutvv不存在該元素vvendl;coutvv還要繼續(xù)查找嗎？是的話，輸入1，不是的話輸入0vvendl;cine;/與上面程序一致，通過循環(huán)條件

13、保證可以多次進(jìn)行查system(pause);return0;輸出結(jié)果：胃輛人天鍵土?xí)A八機(jī)善輸入要分塊的個(gè)數(shù)當(dāng)軸入毎個(gè)分塊關(guān)鏈自的八數(shù)4444請(qǐng)輸入關(guān)鍵土122213828333842877&5063991019796分庚情饑為122213828333B4287765363亦101779G莓八塊最大元素為224287101嗎1是的話,嗎？是的話,輸人1輸人1不是的話輸入不是的話輸入0C:U5ersAdministratorDeskto|嘗三次數(shù)揭結(jié)啕作ik，exeKffl=義查處元查人素墓輸元存要請(qǐng)?jiān)?不還耗的-B杳處元查W所1叢素1輸一兀存要請(qǐng)?jiān)?不還1IlIlS是的話，輸入不是的話輸入回1請(qǐng)技任邕犍繼縝-說明：可見，按照16=4*4分塊的選擇方式，13元素在第0塊，處于關(guān)鍵字序列中的第2位。86和88元素都不在關(guān)鍵字序列中。另外，由于程序中引入了可以由用戶自己選擇分塊數(shù)目和大小的功能，因此，選擇16=5+5+6的分塊方法可以得到一樣的結(jié)果：發(fā)現(xiàn)結(jié)果完全一致。心得體會(huì)：本次實(shí)驗(yàn)程序結(jié)構(gòu)