數據結構作業(yè)任務分塊查找算法

**數據結構實驗報告三題目：試編寫利用折半查找確定記錄所在塊的分塊查找算法。提示：讀入各記錄建立主表；按L個記錄/塊建立索引表；對給定關鍵字k進行查找；測試實例：設主表關鍵字序列：{1222138283338428776 50 63991019796}，L=4，依次查找K=13，K=86，K=88謝謝閱讀算法思路題意要求對輸入的關鍵字序列先進行分塊，得到分塊序列。由于序列不一定有序，故對分塊序列進行折半查找，找到關鍵字所在的塊，然后對關鍵字所在的塊進行順序查找，從而找到關鍵字的位置。謝謝閱讀故需要折半查找和順序查找兩個函數，考慮用C++中的類函數實現。因為序列一般是用數組進行存儲的，這樣可以調用不同類型的數組，程序的可適用性更大一些。精品文檔放心下載折半查找函數：ints,d,ss,dd;//聲明一些全局變量，方便函數與主函數之間的變量調用。感謝閱讀template<classT>intBinSearch(TA[],intlow,inthigh,Tkey)//遞歸實現折半查找精品文檔放心下載**{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<key) //如果關鍵字的值大于中間值謝謝閱讀returnBinSearch(A,mid+1,high,key);//遞歸調用函數，搜索下半部謝謝閱讀分elsereturnBinSearch(A,low,mid-1,key);//否則遞歸調用哦個函數，搜謝謝閱讀**索上半部分}}以上為通用的折半查找的函數代碼，這里引入了幾個全局變量，主要是方便在搜索關鍵字在哪一個分塊中時，作為判斷條件。精品文檔放心下載順尋查找函數：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時就會輸出，否則，返回high值，說明搜索失敗。精品文檔放心下載}主函數中，首先對所需要的參數變量進行初始化，由鍵盤輸入關鍵字，分塊的多少，每一塊有多少個關鍵字。為了用戶的人性化考慮，這里由用戶自己決定分塊的多少和數目。為了實現這一功能，引入了一個動態(tài)存儲的二維數組：精品文檔放心下載int**p2;p2=newint*[row];//聲明一個二維數組謝謝閱讀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;}}//將所有關鍵字，按塊的不同存入二維數組中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;}//輸出二維數組，檢驗分塊是否為預期將各種信息用各種數組加以存儲，在需要時不斷調用。另外，由于題目中需要多次查找，為了避免每次查找的反復輸入，引入了一個while循環(huán)，保證可以多次查找并輸出結果。精品文檔放心下載在關鍵字等信息輸入完畢后，進行查找，可以得到該關鍵字所在塊的序號，以及該關鍵字在整個關鍵字序列中的位置。感謝閱讀**程序結構聲明折半查找函數主函數得到關鍵字所在的塊的位置

聲明順序查找函數聲明各種變輸入關鍵字量的個數調用折折半輸出二維數組檢驗存儲查找函數情況

輸入分塊個數聲明一個二維數組并將關鍵字按快存儲在二維數組中

輸入每個分塊中的關鍵字的個數輸入關鍵字調用順序查找函數，對關鍵字所在快進行查找

判斷函數返回至是否等于輸入數組長No輸出無該關鍵字

YES 輸出位置YES詢問用戶是否再次查找NO結束源代碼：#include<iostream>usingnamespacestd;ints,d,ss,dd;//聲明一些全局變量，方便函數與主函數之間的變量調用。精品文檔放心下載template<classT>intBinSearch(TA[],intlow,inthigh,Tkey)//遞歸實現折半查找謝謝閱讀{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<key) //如果關鍵字的值大于中間值精品文檔放心下載returnBinSearch(A,mid+1,high,key);//遞歸調用函數，搜索下半部精品文檔放心下載分elsereturnBinSearch(A,low,mid-1,key);//否則遞歸調用哦個函數，搜索上半部分謝謝閱讀}}**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時就會輸出，否則，返回high值，說明搜索失敗。謝謝閱讀}intmain(){inti,key,pos,length,fen,k,j,a,kuai,e;//定義一些變量精品文檔放心下載a=0;k=0;cout<<"請輸入關鍵字的個數"<<endl;cin>>length;intA[length-1];//根據輸入關鍵字的個數初始化一個數組進行存儲cout<<"請輸入要分塊的個數"<<endl;cin>>fen;精品文檔放心下載intB[fen-1];**intM[fen-1];for(i=0;i<fen;i++){M[i]=0;}//初始化兩個數組，一個用來存儲每一塊元素的大小，另一個用來存儲每一塊的中元素的最大值精品文檔放心下載cout<<"請輸入每個分塊關鍵字的個數"<<endl;for(i=0;i<fen;i++)謝謝閱讀{cin>>B[i];}//使數組B中表示每塊中關鍵字的個數精品文檔放心下載cout<<"請輸入關鍵字"<<endl;for(i=0;i<length;i++){cin>>A[i];}//輸入所有的關鍵字，存在數組A中精品文檔放心下載introw,col;row=fen;col=length;int**p2;p2=newint*[row];//聲明一個二維數組精品文檔放心下載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;}}//將所有關鍵字，按塊的不同存入二維數組中**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;}//輸出二維數組，檢驗分塊是否為預期cout<<"每個塊最大元素為"<<endl;for(i=0;i<fen;i++){cout<<M[i]<<endl;}//將每一組的最大元素存入數組M中cout<<endl<<"請輸入要查找的元素";cin>>key;//將要查找的關鍵字賦值給keypos=BinSearch(M,0,length-1,key);//調用折半查找函數，查找關鍵字處于精品文檔放心下載哪個塊中cout<<"該元素所處的塊是"<<endl;if(pos!=-1){kuai=pos;cout<<kuai<<endl;**}else{kuai=dd;cout<<kuai<<endl;}//將關鍵字所在的塊輸出。感謝閱讀int*S;S=newint[kuai];for(i=0;i<B[kuai];i++){S[i]=p2[kuai][i];}//初始化一個一維數組，將關鍵字所在快的元素重新定義為一個數組感謝閱讀Spos=shuxuSearch(S,B[kuai],key);//在S中順序查找關鍵字謝謝閱讀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;//引入判斷條件，以便多次查找感謝閱讀**while((e!=1)&&(e!=0)){cout<<"輸入不合法,請重新輸入e"<<endl;感謝閱讀cin>>e;}//保證輸入合法while(e==1){cout<<endl<<"請輸入要查找的元素";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)條件保證可以多次進行感謝閱讀查找}system("pause");return0;}**輸出結果：說明：可見，按照16=4*4分塊的選擇方式，13元素在第0塊，處于關鍵字序感謝閱讀列中的第2位。86和88元素都不在關鍵字序列中。精品文檔放心下載另外，由于程序中引入了可以由用戶自己選擇分塊數目和大小的功能，因此，選謝謝閱讀擇16=5+5+6的分塊方法可以得到一樣的結果