数据结构作业任务分块查找算法

1、数据结构实验报告三题目试编写利用折半查找确定记录所在块的分块查找算法。提示:1）读入各记录建立主表;2）按L个记录/块建立索引表;3）对给定关键字k进行查找;测试实例：设主表关键字序列：12221382833384287765063 99 101 97 96，L=4，依次查找K=13 ，K=86 ， K=88算法思路题意要求对输入的关键字序列先进行分块,得到分块序列。由于序列不一定有序，故对分块序列进行折半查找，找到关键字所在的块，然后对关键字所在的 块进行顺序查找，从而找到关键字的位置。故需要折半查找和顺序查找两个函数，考虑用C+中的类函数实现。因为序列一般是用数组进行存储的，这样可以调用不

2、同类型的数组，程序的可适用性 更大一些。折半查找函数:int s,d,ss,dd;/声明一些全局变量，方便函数与主函数之间的变量调用。temp late <class T>int Bin Search(T A,i nt low,i nt high,T key)/ 递归实现折半查找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)/如果关键字的值大于中间值递归调用函数，搜索下半部否则递归调用哦个函数，搜retur n Bin Search(A,mid+1,high,key);/elsereturn Bin Search(A,low,mid-1,key);/索上半部分以上为通用的折半查找的函数代码， 这里引入了几个全局变量，主要是方便 在搜索关键字在哪一个分块中时，作为判断条件。顺寻查找函数:顺序查找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值，说明搜索失败。主函数中，首先对所需要的参数变量进行初始化， 由键盘输入关键字，分块 的多少，每一块有多少个关键字。为了用户的人性化考虑，这里由用户自己决定 分块的多少和数目。为了实现这一功能，引入了一个动态存储的二维数组:int *p2 ;p2 = new in t*row ;/ 声明一个二维数组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;/将所有关键字，按块的不同存入二维数组中coutvv"分块情况为"<<endl;for( i = 0 ; i < row ; i + )for( j = 0 ;j <Bi ; j + )coutvv p2ijvv''if(p 2ij>=Mi)Mi=p2ij;coutvve ndl;/输出二维数组，检验分

6、块是否为预期将各种信息用各种数组加以存储，在需要时不断调用。另外，由于题目中需要多次查找，为了避免每次查找的反复输入，引入了一个while循环，保证可以多次查找并输出结果。在关键字等信息输入完毕后，进行查找，可以得到该关键字所在块的序号,以及该关键字在整个关键字序列中的位置。主函数声明各种变输入关键字输入分块个量的个数数输入每个分块 中的关键字的 个数得到关键字所在 的块的位置4调用折折半 查找函数*输出二维数 组检验存储情况J声明一个二维数组 并将关键字按快存 储在二维数组中* 输入关键字调用顺序查找函 数，对关键字所 在快进行查找判断函数返回至"YFS输出位置是否等于输入数组长_

7、一r程序结构声明折半查找函数声明顺序查* 找函数Yes输出无该关键字询问用户是否再、， 次查找结束源代码:#in elude <iostream>using n ames pace std;int s,d,ss,dd;/声明一些全局变量，方便函数与主函数之间的变量调用。递归实现折半查找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)/如果关键字的值大于中间值retur n Bin Search(A,mid+1,high,key);/elsereturn Bin Search(A,low,mid-1,key);/递归调用函数，搜索下半部否则递归调用哦个函数，搜索上半部分coutvv"请输入要分块的个数"<<

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"请输入关键字的个数"<<endl;cin> >le n

10、gth;int Ale ngth-1; /根据输入关键字的个数初始化一个数组进行存储cin>>fen;int Bfen-1;int Mfen-1;for(i=0;ivfe n;i+)Mi=O;/初始化两个数组，一个用来存储每一块元素的大小，另一个用来存储每一块的中元素的最大值coutvv"请输入每个分块关键字的个数"<<endl;for(i=0;i<fe n;i+)cin>>Bi;/使数组B中表示每块中关键字的个数coutvv"请输入关键字"<<endl;for(i=0;i<le ngth;i+

11、)cin>>Ai;/输入所有的关键字，存在数组A中int row,col;row=fe n;col=le ngth;int *p2 ;p2 = new in t*row ;/ 声明一个二维数组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;/将所有关键字，按块的不同存入二维数组中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;/输出二维数组，检验分块是否为预期coutvv"每个块最大元素为"vvendl;foMirOjvfe n;i+)coutvvMivvendl;/将每一组的最大元素存入数组 M中coutvvendlvv"请输入要查找的元素"cin >>key;/将要查找的关键字赋值给keypos=BinSearch(M,O,length-1,key);/调用折半查找函数，查找关键字处

13、于哪个块中if (p os!=-1)kuai=pos;coutvvkuaivve ndl;coutvv"该元素所处的块是"vvendl;else kuai=dd;coutvvkuaivve ndl;/将关键字所在的块输出。int *S;S = new in tkuai;for(i=0;ivBkuai;i+)Si=p2kuaii;/初始化一个一维数组，将关键字所在快的元素重新定义为一个数组pos=shuxuSearch(S,Bkuai,key);/ 在 S 中顺序查找关键字int q=0;for(i=0;i<kuai;i+)q=q+Bi;if (po s!=Bkuai)

14、coutvv"该元素的位置为"<<pos+qvvendl;/如果关键字存在，输出其位置elsecoutvv"不存在该元素"<<endl;/若不存在，输出“不存在该元素”cin >>e; /引入判断条件，以便多次查找coutvv"还要继续查找吗？是的话，输入 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;还要继续查找吗？是的话，输入 1，不是的话输入cin>>e; /与上面程序一致，通过循环条件保证可以多次进行system(" pause");return 0;输出结果:律输入要分块的，卜数W输入母个分块关犍字的人数4 4 4 4请输入关琏宇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块，处于关键字序列中的第2位。86和88元素都不在关键字序列中。择16=5+5+6 的分块方法可以得到一样的结果:另外，由于程序中引入了可以由用户自己选择分块数目和大小的功能，因此，选匕弓 'ITU yJ II J I A善输入要分块的个数3请输入转卜分块关键字的亍数5 5 6情输人关键宇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