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

1、數(shù)據(jù)結(jié)構(gòu)實驗報告三題目試編寫利用折半查找確定記錄所在塊的分塊查找算法。提示:1）讀入各記錄建立主表;2）按L個記錄/塊建立索引表;3）對給定關(guān)鍵字k進(jìn)行查找;測試實例：設(shè)主表關(guān)鍵字序列：12221382833384287765063 99 101 97 96，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)用不

2、同類型的數(shù)組，程序的可適用性 更大一些。折半查找函數(shù):int s,d,ss,dd;/聲明一些全局變量，方便函數(shù)與主函數(shù)之間的變量調(diào)用。temp late <class T>int Bin Search(T A,i nt low,i nt high,T key)/ 遞歸實現(xiàn)折半查找in t mid;/ 初始化中間值的位置T midvalue;/初始化中間值if (low>high)s=Ahigh;d=Alow;ss=high;dd=low;return -1;/ 如果 low的值大于high的值，輸出-1，并且將此時的low與 high的值存儲。elsemid=(low+hig

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

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

5、 0 ; i < row ; i + )p 2i = new in tcol;for( i = 0 ; i < row ; i + )for( j = 0 ; j v Bi ; j + )p 2ij=Ak;k=k+1;/將所有關(guān)鍵字，按塊的不同存入二維數(shù)組中coutvv"分塊情況為"<<endl;for( i = 0 ; i < row ; i + )for( j = 0 ;j <Bi ; j + )coutvv p2ijvv''if(p 2ij>=Mi)Mi=p2ij;coutvve ndl;/輸出二維數(shù)組，檢驗分

6、塊是否為預(yù)期將各種信息用各種數(shù)組加以存儲，在需要時不斷調(diào)用。另外，由于題目中需要多次查找，為了避免每次查找的反復(fù)輸入，引入了一個while循環(huán)，保證可以多次查找并輸出結(jié)果。在關(guān)鍵字等信息輸入完畢后，進(jìn)行查找，可以得到該關(guān)鍵字所在塊的序號,以及該關(guān)鍵字在整個關(guān)鍵字序列中的位置。主函數(shù)聲明各種變輸入關(guān)鍵字輸入分塊個量的個數(shù)數(shù)輸入每個分塊 中的關(guān)鍵字的 個數(shù)得到關(guān)鍵字所在 的塊的位置4調(diào)用折折半 查找函數(shù)*輸出二維數(shù) 組檢驗存儲情況J聲明一個二維數(shù)組 并將關(guān)鍵字按快存 儲在二維數(shù)組中* 輸入關(guān)鍵字調(diào)用順序查找函 數(shù)，對關(guān)鍵字所 在快進(jìn)行查找判斷函數(shù)返回至"YFS輸出位置是否等于輸入數(shù)組長_

7、一r程序結(jié)構(gòu)聲明折半查找函數(shù)聲明順序查* 找函數(shù)Yes輸出無該關(guān)鍵字詢問用戶是否再、， 次查找結(jié)束源代碼:#in elude <iostream>using n ames pace std;int s,d,ss,dd;/聲明一些全局變量，方便函數(shù)與主函數(shù)之間的變量調(diào)用。遞歸實現(xiàn)折半查找temp late <class T>int Bin Search(T A,i nt low,i nt high,T key)/in t mid;/ 初始化中間值的位置if (low>high)s=Ahigh;d=Alow;ss=high;dd=low;return -1;/ 如果

8、low的值大于high的值，輸出-1，并且將此時的low與high的值存儲。elsemid=(low+high)/2;/中間位置為低位與高位和的一半取整。midvalue=Amid;if (midvalue=key)return mid;else if (midvalue < key)/如果關(guān)鍵字的值大于中間值retur n Bin Search(A,mid+1,high,key);/elsereturn Bin Search(A,low,mid-1,key);/遞歸調(diào)用函數(shù)，搜索下半部否則遞歸調(diào)用哦個函數(shù)，搜索上半部分coutvv"請輸入要分塊的個數(shù)"<<

9、;endl;順序查找temp late <class T>int shuxuSearch(T A,i nt high,T key)/int i=0; Ahigh=key;/ 初始化i，使 A的最高位為key值while(Ai!=key) i+;return i;/如果A中有key值，則在i不到n+1時就會輸出，否則,返回high值，說明搜索失敗。定義一些變量int main()int i,key ,p os,le ngthfe n,k,jakuai,e;/a=0;k=0;coutvv"請輸入關(guān)鍵字的個數(shù)"<<endl;cin> >le n

10、gth;int Ale ngth-1; /根據(jù)輸入關(guān)鍵字的個數(shù)初始化一個數(shù)組進(jìn)行存儲cin>>fen;int Bfen-1;int Mfen-1;for(i=0;ivfe n;i+)Mi=O;/初始化兩個數(shù)組，一個用來存儲每一塊元素的大小，另一個用來存儲每一塊的中元素的最大值coutvv"請輸入每個分塊關(guān)鍵字的個數(shù)"<<endl;for(i=0;i<fe n;i+)cin>>Bi;/使數(shù)組B中表示每塊中關(guān)鍵字的個數(shù)coutvv"請輸入關(guān)鍵字"<<endl;for(i=0;i<le ngth;i+

11、)cin>>Ai;/輸入所有的關(guān)鍵字，存在數(shù)組A中int row,col;row=fe n;col=le ngth;int *p2 ;p2 = new in t*row ;/ 聲明一個二維數(shù)組for( i = 0 ; i v row ; i + )p 2i = new in tcol;for( i = 0 ; i v row ; i + )for( j = 0 ; j v Bi ; j + )p 2ij=Ak;k=k+1;/將所有關(guān)鍵字，按塊的不同存入二維數(shù)組中coutvv"分塊情況為"<<endl;for( i = 0 ; i < row ;

12、 i + )for( j = 0 ;j vBi ; j + )coutvv p2ijvv''if(p 2ij>=Mi)Mi=p2ij;coutvve ndl;/輸出二維數(shù)組，檢驗分塊是否為預(yù)期coutvv"每個塊最大元素為"vvendl;foMirOjvfe n;i+)coutvvMivvendl;/將每一組的最大元素存入數(shù)組 M中coutvvendlvv"請輸入要查找的元素"cin >>key;/將要查找的關(guān)鍵字賦值給keypos=BinSearch(M,O,length-1,key);/調(diào)用折半查找函數(shù)，查找關(guān)鍵字處

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

14、coutvv"該元素的位置為"<<pos+qvvendl;/如果關(guān)鍵字存在，輸出其位置elsecoutvv"不存在該元素"<<endl;/若不存在，輸出“不存在該元素”cin >>e; /引入判斷條件，以便多次查找coutvv"還要繼續(xù)查找嗎？是的話，輸入 1，不是的話輸入0"<<endl;while (e!=1)&&(e!=0)coutvv"輸入不合法，請重新輸入e"<<endl;cin>>e;/保證輸入合法while (e=

15、1)coutvvendlvv"請輸入要查找的元素"cin> >key;pos=Bi nSearch(M,0,le ngth-1,key);coutvv"該元素所處的塊是"<<endl;if (p os!=-1) kuai=pos;coutvvkuaivve ndl;else kuai=dd;coutvvkuaivve ndl; for(i=0;ivBkuai;i+) Si=P2kuaii; po s=shuxuSearch(S,Bkuai,key);int q=0;for(i=0;ivkuai;i+) q=q+Bi;0"

16、<<e ndl;查找if (p os!=Bkuai)cout<<"elsecout<<"cout<<"該元素的位置為"vvpos+qvvendl;不存在該元素"<<endl;還要繼續(xù)查找嗎？是的話，輸入 1，不是的話輸入cin>>e; /與上面程序一致，通過循環(huán)條件保證可以多次進(jìn)行system(" pause");return 0;輸出結(jié)果:律輸入要分塊的，卜數(shù)W輸入母個分塊關(guān)犍字的人數(shù)4 4 4 4請輸入關(guān)璉宇12 22 13 8 38 33 3B 4

17、3 S7 76 50 &3 ?9 131 97 96 分按情況為12 22 13 828 33 38 4237 7& 50 G399 101 97 96毎裟最大元素為224287161SIWF0 _是的話，輸人1,1不是的話輸入B2 亠_廡辜貓嬴/是的話，輸入1,1不是的話輸入0L 蠶蠶嗎的話,輸人 0請按任邕犍繼牘-不呆的話輸入0說明：可見，按照16=4*4分塊的選擇方式，13元素在第0塊，處于關(guān)鍵字序列中的第2位。86和88元素都不在關(guān)鍵字序列中。擇16=5+5+6 的分塊方法可以得到一樣的結(jié)果:另外，由于程序中引入了可以由用戶自己選擇分塊數(shù)目和大小的功能，因此，選匕弓 'ITU yJ II J I A善輸入要分塊的個數(shù)3請輸入轉(zhuǎn)卜分塊關(guān)鍵字的亍數(shù)5 5 6情輸人關(guān)鍵宇12 22 13 8 28 33 38 42 87 76 5 63 99 101 97 96 分塊情祝為h 22 13 8 2833 38 42 07 7&50 63 99 lei 97 96何個塊最大元素為se071010該元素卸位S為2 還要繼豊查抑貂是的話,1不是的話輸入0聲飜斷是的話,1輸人：不是的話輸入02