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

./數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告三題目：試編寫利用折半查找確定記錄所在塊的分塊查找算法。提示：讀入各記錄建立主表；按L個(gè)記錄/塊建立索引表；對(duì)給定關(guān)鍵字k進(jìn)行查找；測試實(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ù)組,程序的可適用性更大一些。折半查找函數(shù)：ints,d,ss,dd;//聲明一些全局變量,方便函數(shù)與主函數(shù)之間的變量調(diào)用。template<classT>intBinSearch<TA[],intlow,inthigh,Tkey>//遞歸實(shí)現(xiàn)折半查找{intmid;//初始化中間值的位置Tmidvalue;//初始化中間值if<low>high>{s=A[high];d=A[low];ss=high;dd=low;return-1;}//如果low的值大于high的值,輸出-1,并且將此時(shí)的low與high的值存儲(chǔ)。else{mid=<low+high>/2;//中間位置為低位與高位和的一半取整。midvalue=A[mid];if<midvalue==key>returnmid;elseif<midvalue<key>//如果關(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ù)：template<classT>intshuxuSearch<TA[],inthigh,Tkey>//順序查找{inti=0;A[high]=key;//初始化i,使A的最高位為key值while<A[i]!=key>i++;returni;//如果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;i<row;i++>p2[i]=newint[col];for<i=0;i<row;i++>{for<j=0;j<B[i];j++>{p2[i][j]=A[k];k=k+1;}}//將所有關(guān)鍵字,按塊的不同存入二維數(shù)組中cout<<"分塊情況為"<<endl;for<i=0;i<row;i++>{for<j=0;j<B[i];j++>{cout<<p2[i][j]<<'';if<p2[i][j]>=M[i]>M[i]=p2[i][j];}cout<<endl;}//輸出二維數(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)源代碼：#include<iostream>usingnamespacestd;ints,d,ss,dd;//聲明一些全局變量,方便函數(shù)與主函數(shù)之間的變量調(diào)用。template<classT>intBinSearch<TA[],intlow,inthigh,Tkey>//遞歸實(shí)現(xiàn)折半查找{intmid;//初始化中間值的位置Tmidvalue;//初始化中間值if<low>high>{s=A[high];d=A[low];ss=high;dd=low;return-1;}//如果low的值大于high的值,輸出-1,并且將此時(shí)的low與high的值存儲(chǔ)。else{mid=<low+high>/2;//中間位置為低位與高位和的一半取整。midvalue=A[mid];if<midvalue==key>returnmid;elseif<midvalue<key>//如果關(guān)鍵字的值大于中間值returnBinSearch<A,mid+1,high,key>;//遞歸調(diào)用函數(shù),搜索下半部分elsereturnBinSearch<A,low,mid-1,key>;//否則遞歸調(diào)用哦個(gè)函數(shù),搜索上半部分}}template<classT>intshuxuSearch<TA[],inthigh,Tkey>//順序查找{inti=0;A[high]=key;//初始化i,使A的最高位為key值while<A[i]!=key>i++;returni;//如果A中有key值,則在i不到n+1時(shí)就會(huì)輸出,否則,返回high值,說明搜索失敗。}intmain<>{inti,key,pos,length,fen,k,j,a,kuai,e;//定義一些變量a=0;k=0;cout<<"請(qǐng)輸入關(guān)鍵字的個(gè)數(shù)"<<endl;cin>>length;intA[length-1];//根據(jù)輸入關(guān)鍵字的個(gè)數(shù)初始化一個(gè)數(shù)組進(jìn)行存儲(chǔ)cout<<"請(qǐng)輸入要分塊的個(gè)數(shù)"<<endl;cin>>fen;intB[fen-1];intM[fen-1];for<i=0;i<fen;i++>{M[i]=0;}//初始化兩個(gè)數(shù)組,一個(gè)用來存儲(chǔ)每一塊元素的大小,另一個(gè)用來存儲(chǔ)每一塊的中元素的最大值cout<<"請(qǐng)輸入每個(gè)分塊關(guān)鍵字的個(gè)數(shù)"<<endl;for<i=0;i<fen;i++>{cin>>B[i];}//使數(shù)組B中表示每塊中關(guān)鍵字的個(gè)數(shù)cout<<"請(qǐng)輸入關(guān)鍵字"<<endl;for<i=0;i<length;i++>{cin>>A[i];}//輸入所有的關(guān)鍵字,存在數(shù)組A中introw,col;row=fen;col=length;int**p2;p2=newint*[row];//聲明一個(gè)二維數(shù)組for<i=0;i<row;i++>p2[i]=newint[col];for<i=0;i<row;i++>{for<j=0;j<B[i];j++>{p2[i][j]=A[k];k=k+1;}}//將所有關(guān)鍵字,按塊的不同存入二維數(shù)組中cout<<"分塊情況為"<<endl;for<i=0;i<row;i++>{for<j=0;j<B[i];j++>{cout<<p2[i][j]<<'';if<p2[i][j]>=M[i]>M[i]=p2[i][j];}cout<<endl;}//輸出二維數(shù)組,檢驗(yàn)分塊是否為預(yù)期cout<<"每個(gè)塊最大元素為"<<endl;for<i=0;i<fen;i++>{cout<<M[i]<<endl;}//將每一組的最大元素存入數(shù)組M中cout<<endl<<"請(qǐng)輸入要查找的元素";cin>>key;//將要查找的關(guān)鍵字賦值給keypos=BinSearch<M,0,length-1,key>;//調(diào)用折半查找函數(shù),查找關(guān)鍵字處于哪個(gè)塊中cout<<"該元素所處的塊是"<<endl;if<pos!=-1>{kuai=pos;cout<<kuai<<endl;}else{kuai=dd;cout<<kuai<<endl;}//將關(guān)鍵字所在的塊輸出。int*S;S=newint[kuai];for<i=0;i<B[kuai];i++>{S[i]=p2[kuai][i];}//初始化一個(gè)一維數(shù)組,將關(guān)鍵字所在快的元素重新定義為一個(gè)數(shù)組Spos=shuxuSearch<S,B[kuai],key>;//在S中順序查找關(guān)鍵字intq=0;for<i=0;i<kuai;i++>{q=q+B[i];}if<pos!=B[kuai]>cout<<"該元素的位置為"<<pos+q<<endl;//如果關(guān)鍵字存在,輸出其位置elsecout<<"不存在該元素"<<endl;//若不存在,輸出"不存在該元素"cout<<"還要繼續(xù)查找嗎？是的話,輸入1,不是的話輸入0"<<endl;cin>>e;//引入判斷條件,以便多次查找while<<e!=1>&&<e!=0>>{cout<<"輸入不合法,請(qǐng)重新輸入e"<<endl;cin>>e;}//保證輸入合法while<e==1>{cout<<endl<<"請(qǐng)輸入要查找的元素";cin>>key;pos=BinSearch<M,0,length-1,key>;cout<<"該元素所處的塊是"<<endl;if<pos!=-1>{kuai=pos;cout<<kuai<<endl;}else{kuai=dd;cout<<kuai<<endl;}for<i=0;i<B[kuai];i++>{S[i]=p2[kuai][i];}pos=shuxuSearch<S,B[kuai],key>;intq=0;for<i=0;i<kuai;i++>{q=q+B[i];}if<pos!=B[kuai]>cout<<"該元素的位置為"<<pos+q<<endl;elsecout<<"不存在該元素"<<endl;cout<<"還要繼續(xù)查找嗎？是的話,輸入1,不是的話輸入0"<<endl;cin>>e;//與上面程序一致,通過循環(huán)條件保證可以多次進(jìn)行查找}system<"pause">;return0;}輸出結(jié)果：說明：可見,按照16=4*4分塊的選擇方式,13元素在第0塊,處于關(guān)鍵字序列中的第2位。86和88元素都不在關(guān)鍵字序列中。另外,由于程序中引入了可以由用戶自己選擇分