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

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告三題目：試編寫(xiě)利用折半查找確定記錄所在塊的分塊查找算法。提示：1) 讀入各記錄建立主表；2) 按L個(gè)記錄/塊建立索引表；3) 對(duì)給定關(guān)鍵字k進(jìn)行查找；測(cè)試實(shí)例：設(shè)主表關(guān)鍵字序列：12 22 13 8 28 33 38 42 87 76 50 63 99 101 97 96，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ù)組

2、進(jìn)行存儲(chǔ)的，這樣可以調(diào)用不同類型的數(shù)組，程序的可適用性更大一些。折半查找函數(shù)：int s,d,ss,dd;/聲明一些全局變量，方便函數(shù)與主函數(shù)之間的變量調(diào)用。 template <class T>int BinSearch(T A,int low,int high,T key)/遞歸實(shí)現(xiàn)折半查找 int mid;/ 初始化中間值的位置 T midvalue;/ 初始化中間值 if (low>high) s=Ahigh; d=Alow; ss=high; dd=low; return -1;/ 如果low的值大于high的值，輸出-1，并且將此時(shí)的low與high的值存儲(chǔ)。 e

3、lse mid=(low+high)/2;/ 中間位置為低位與高位和的一半取整。 midvalue=Amid; if (midvalue=key) return mid; else if (midvalue < key) /如果關(guān)鍵字的值大于中間值 return BinSearch(A,mid+1,high,key);/ 遞歸調(diào)用函數(shù)，搜索下半部分 else return BinSearch(A,low,mid-1,key);/ 否則遞歸調(diào)用哦個(gè)函數(shù)，搜索上半部分 以上為通用的折半查找的函數(shù)代碼，這里引入了幾個(gè)全局變量，主要是方便在搜索關(guān)鍵字在哪一個(gè)分塊中時(shí)，作為判斷條件。順尋查找函數(shù)：

4、template <class T>int shuxuSearch(T A,int high,T key)/ 順序查找 int i=0; Ahigh=key;/ 初始化i，使 A的最高位為key值 while(Ai!=key) i+; return i;/ 如果A中有key值，則在i不到n+1時(shí)就會(huì)輸出，否則，返回high值，說(shuō)明搜索失敗。 主函數(shù)中，首先對(duì)所需要的參數(shù)變量進(jìn)行初始化，由鍵盤(pán)輸入關(guān)鍵字，分塊的多少，每一塊有多少個(gè)關(guān)鍵字。為了用戶的人性化考慮，這里由用戶自己決定分塊的多少和數(shù)目。為了實(shí)現(xiàn)這一功能，引入了一個(gè)動(dòng)態(tài)存儲(chǔ)的二維數(shù)組：int *p2 ;p2 = new int

5、*row ;/聲明一個(gè)二維數(shù)組 for( i = 0 ; i < row ; i + ) p2i = new intcol ;for( i = 0 ; i < row ; i + ) for( j = 0 ; j < Bi ; j + ) p2ij=Ak; k=k+1; /將所有關(guān)鍵字，按塊的不同存入二維數(shù)組中 cout<<"分塊情況為"<<endl;for( i = 0 ; i < row ; i + ) for( j = 0 ;j <Bi ; j + ) cout<<p2ij<<' &

6、#39; ; if(p2ij>=Mi) Mi=p2ij; 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>using namespace std;int s,d,ss,dd;/聲明一些全局變量，方便函數(shù)與主函數(shù)之間的變量調(diào)用。 template

7、 <class T>int BinSearch(T A,int low,int high,T key)/遞歸實(shí)現(xiàn)折半查找 int mid;/ 初始化中間值的位置 T midvalue;/ 初始化中間值 if (low>high) s=Ahigh; d=Alow; ss=high; dd=low; return -1;/ 如果low的值大于high的值，輸出-1，并且將此時(shí)的low與high的值存儲(chǔ)。 else mid=(low+high)/2;/ 中間位置為低位與高位和的一半取整。 midvalue=Amid; if (midvalue=key) return mid; el

8、se if (midvalue < key) /如果關(guān)鍵字的值大于中間值 return BinSearch(A,mid+1,high,key);/ 遞歸調(diào)用函數(shù)，搜索下半部分 else return BinSearch(A,low,mid-1,key);/ 否則遞歸調(diào)用哦個(gè)函數(shù)，搜索上半部分 template <class T>int shuxuSearch(T A,int high,T key)/ 順序查找 int i=0; Ahigh=key;/ 初始化i，使 A的最高位為key值 while(Ai!=key) i+; return i;/ 如果A中有key值，則在i不到

9、n+1時(shí)就會(huì)輸出，否則，返回high值，說(shuō)明搜索失敗。 int main() int i,key,pos,length,fen,k,j,a,kuai,e;/ 定義一些變量 a=0;k=0;cout<<"請(qǐng)輸入關(guān)鍵字的個(gè)數(shù)"<<endl;cin>>length;int Alength-1; / 根據(jù)輸入關(guān)鍵字的個(gè)數(shù)初始化一個(gè)數(shù)組進(jìn)行存儲(chǔ) cout<<"請(qǐng)輸入要分塊的個(gè)數(shù)"<<endl;cin>>fen;int Bfen-1; int Mfen-1;for(i=0;i<fen;i+

10、)Mi=0;/ 初始化兩個(gè)數(shù)組，一個(gè)用來(lái)存儲(chǔ)每一塊元素的大小，另一個(gè)用來(lái)存儲(chǔ)每一塊的中元素的最大值 cout<<"請(qǐng)輸入每個(gè)分塊關(guān)鍵字的個(gè)數(shù)"<<endl;for(i=0;i<fen;i+)cin>>Bi;/使數(shù)組B中表示每塊中關(guān)鍵字的個(gè)數(shù) cout<<"請(qǐng)輸入關(guān)鍵字"<<endl; for(i=0;i<length;i+)cin>>Ai;/輸入所有的關(guān)鍵字，存在數(shù)組A中 int row,col;row=fen;col=length;int *p2 ;p2 = new i

11、nt*row ;/聲明一個(gè)二維數(shù)組 for( i = 0 ; i < row ; i + ) p2i = new intcol ;for( i = 0 ; i < row ; i + ) for( j = 0 ; j < Bi ; j + ) p2ij=Ak; k=k+1; /將所有關(guān)鍵字，按塊的不同存入二維數(shù)組中 cout<<"分塊情況為"<<endl;for( i = 0 ; i < row ; i + ) for( j = 0 ;j <Bi ; j + ) cout<<p2ij<<'

12、 ' ; if(p2ij>=Mi) Mi=p2ij; cout<<endl;/輸出二維數(shù)組，檢驗(yàn)分塊是否為預(yù)期 cout<<"每個(gè)塊最大元素為"<<endl;for(i=0;i<fen;i+) cout<<Mi<<endl;/將每一組的最大元素存入數(shù)組M中 cout<<endl<<"請(qǐng)輸入要查找的元素"cin>>key;/將要查找的關(guān)鍵字賦值給key pos=BinSearch(M,0,length-1,key);/調(diào)用折半查找函數(shù)，查找關(guān)

13、鍵字處于哪個(gè)塊中 cout<<"該元素所處的塊是"<<endl; if (pos!=-1) kuai=pos; cout<<kuai<<endl; else kuai=dd; cout<<kuai<<endl;/將關(guān)鍵字所在的塊輸出。 int *S;S = new intkuai ;for(i=0;i<Bkuai;i+) Si=p2kuaii; /初始化一個(gè)一維數(shù)組，將 關(guān)鍵字所在快的元素重新定義為一個(gè)數(shù)組S pos=shuxuSearch(S,Bkuai,key);/在S中順序查找關(guān)鍵字 int

14、 q=0;for(i=0;i<kuai;i+) q=q+Bi;if (pos!=Bkuai) cout<<"該元素的位置為"<<pos+q<<endl;/如果關(guān)鍵字存在，輸出其位置 else cout<<"不存在該元素"<<endl;/若不存在，輸出“不存在該元素” cout<<"還要繼續(xù)查找嗎？是的話，輸入1，不是的話輸入0"<<endl; cin>>e; /引入判斷條件，以便多次查找 while (e!=1)&&(

15、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; cou

16、t<<kuai<<endl; for(i=0;i<Bkuai;i+) Si=p2kuaii; pos=shuxuSearch(S,Bkuai,key); int q=0; for(i=0;i<kuai;i+) q=q+Bi; if (pos!=Bkuai) cout<<"該元素的位置為"<<pos+q<<endl; else cout<<"不存在該元素"<<endl; cout<<"還要繼續(xù)查找嗎？是的話，輸入1，不是的話輸入0"<<endl; cin>>e; /與上面程序一致，通過(guò)循環(huán)條件保證可以多次進(jìn)行查找 system("pause");return 0;輸出結(jié)果：說(shuō)明：可見(jiàn)，按照16=4*4分塊的選擇方式，13元素在第0塊，處于關(guān)鍵字序列中的第2位。86和88元素都不在關(guān)鍵字序列中。另外，由于程序中引入了可以由用戶自己選擇分塊數(shù)目和大小的功能，因此，選擇16=5+