數(shù)據(jù)結(jié)構(gòu)作業(yè)

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)作業(yè)

數(shù)據(jù)結(jié)構(gòu)試驗報告三

題目：

試編寫利用折半查找確定記錄所在塊的分塊查找算法。提醒：

1)讀入各記錄建立主表；

2)按L個記錄/塊建立索引表；3)對給定關(guān)鍵字k進(jìn)行查找；

測試實例：設(shè)主表關(guān)鍵字序列：{12221382833384287765063991019796}，L=4，依次查找K=13，K=86，K=88

算法思路

題意要求對輸入的關(guān)鍵字序列先進(jìn)行分塊，得到分塊序列。由于序列不一定有序，故對分塊序列進(jìn)行折半查找，找到關(guān)鍵字所在的塊，然后對關(guān)鍵字所在的塊進(jìn)行順序查找，從而找到關(guān)鍵字的位置。

故需要折半查找和順序查找兩個函數(shù)，考慮用C++中的類函數(shù)實現(xiàn)。由于序列一般是用數(shù)組進(jìn)行存儲的，這樣可以調(diào)用不同類型的數(shù)組，程序的可適用性更大一些。

折半查找函數(shù)：

ints,d,ss,dd;//聲明一些全局變量，便利函數(shù)與主函數(shù)之間的變量調(diào)用。template

intBinSearch(TA[],intlow,inthigh,Tkey)//遞歸實現(xiàn)折半查找{

intmid;//初始化中間值的位置Tmidvalue;//初始化中間值if(low>high){

s=A[high];d=A[low];ss=high;dd=low;

return-1;}//假使low的值大于high的值，輸出-1，并且將此時的low與high的值存儲。

else{

mid=(low+high)/2;//中間位置為低位與高位和的一半取整。midvalue=A[mid];if(midvalue==key)returnmid;

elseif(midvalue

intshuxuSearch(TA[],inthigh,Tkey)//順序查找{

inti=0;A[high]=key;//初始化i，使A的最高位為key值while(A[i]!=key)i++;

returni;//假使A中有key值，則在i不到n+1時就會輸出，否則，返回high值，說明探尋失敗。

}

主函數(shù)中，首先對所需要的參數(shù)變量進(jìn)行初始化，由鍵盤輸入關(guān)鍵字，分塊的多少，每一塊有多少個關(guān)鍵字。為了用戶的人性化考慮，這里由用戶自己決定分塊的多少和數(shù)目。為了實現(xiàn)這一功能，引入了一個動態(tài)存儲的二維數(shù)組：

int**p2;

p2=newint*[row];//聲明一個二維數(shù)組for(i=0;iusingnamespacestd;

ints,d,ss,dd;//聲明一些全局變量，便利函數(shù)與主函數(shù)之間的變量調(diào)用。template

intBinSearch(TA[],intlow,inthigh,Tkey)//遞歸實現(xiàn)折半查找{

intmid;//初始化中間值的位置Tmidvalue;//初始化中間值if(low>high){

s=A[high];d=A[low];ss=high;

dd=low;

return-1;}//假使low的值大于high的值，輸出-1，并且將此時的low與high的值存儲。

else{

mid=(low+high)/2;//中間位置為低位與高位和的一半取整。midvalue=A[mid];if(midvalue==key)returnmid;

elseif(midvalue

intshuxuSearch(TA[],inthigh,Tkey)//順序查找{

inti=0;A[high]=key;//初始化i，使A的最高位為key值while(A[i]!=key)i++;

returni;//假使A中有key值，則在i不到n+1時就會輸出，否則，返回high值，說明探尋失敗。

}

intmain(){

inti,key,pos,length,fen,k,j,a,kuai,e;//定義一些變量a=0;k=0;

cout>length;

intA[length-1];//根據(jù)輸入關(guān)鍵字的個數(shù)初始化一個數(shù)組進(jìn)行存儲cout>fen;intB[fen-1];intM[fen-1];for(i=0;i>B[i];}//使數(shù)組B中表示每塊中關(guān)鍵字的個數(shù)cout>A[i];}//輸入所有的關(guān)鍵字，存在數(shù)組A中introw,col;row=fen;col=length;int**p2;

p2=newint*[row];//聲明一個二維數(shù)組for(i=0;i>key;//將要查找的關(guān)鍵字賦值給key

pos=BinSearch(M,0,length-1,key);//調(diào)用折半查找函數(shù)，查找關(guān)鍵字處于哪個塊中

cout<<\該元素所處的塊是\if(pos!=-1){kuai=pos;

cout<<kuai