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

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

2、进行存储的，这样可以调用不同类型的数组，程序的可适用性更大一些。折半查找函数：int s,d,ss,dd;/声明一些全局变量，方便函数与主函数之间的变量调用。 template <class T>int BinSearch(T A,int low,int high,T key)/递归实现折半查找 int mid;/ 初始化中间值的位置 T midvalue;/ 初始化中间值 if (low>high) s=Ahigh; d=Alow; ss=high; dd=low; return -1;/ 如果low的值大于high的值，输出-1，并且将此时的low与high的值存储。 e

3、lse mid=(low+high)/2;/ 中间位置为低位与高位和的一半取整。 midvalue=Amid; if (midvalue=key) return mid; else if (midvalue < key) /如果关键字的值大于中间值 return BinSearch(A,mid+1,high,key);/ 递归调用函数，搜索下半部分 else return BinSearch(A,low,mid-1,key);/ 否则递归调用哦个函数，搜索上半部分 以上为通用的折半查找的函数代码，这里引入了几个全局变量，主要是方便在搜索关键字在哪一个分块中时，作为判断条件。顺寻查找函数：

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时就会输出，否则，返回high值，说明搜索失败。 主函数中，首先对所需要的参数变量进行初始化，由键盘输入关键字，分块的多少，每一块有多少个关键字。为了用户的人性化考虑，这里由用户自己决定分块的多少和数目。为了实现这一功能，引入了一个动态存储的二维数组：int *p2 ;p2 = new int

5、*row ;/声明一个二维数组 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; /将所有关键字，按块的不同存入二维数组中 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;/输出二维数组，检验分块是否为预期将各种信息用各种数组加以存储，在需要时不断调用。另外，由于题目中需要多次查找，为了避免每次查找的反复输入，引入了一个while循环，保证可以多次查找并输出结果。在关键字等信息输入完毕后，进行查找，可以得到该关键字所在块的序号，以及该关键字在整个关键字序列中的位置。程序结构源代码：#include <iostream>using namespace std;int s,d,ss,dd;/声明一些全局变量，方便函数与主函数之间的变量调用。 template

7、 <class T>int BinSearch(T A,int low,int high,T key)/递归实现折半查找 int mid;/ 初始化中间值的位置 T midvalue;/ 初始化中间值 if (low>high) s=Ahigh; d=Alow; ss=high; dd=low; return -1;/ 如果low的值大于high的值，输出-1，并且将此时的low与high的值存储。 else mid=(low+high)/2;/ 中间位置为低位与高位和的一半取整。 midvalue=Amid; if (midvalue=key) return mid; el

8、se if (midvalue < key) /如果关键字的值大于中间值 return BinSearch(A,mid+1,high,key);/ 递归调用函数，搜索下半部分 else return BinSearch(A,low,mid-1,key);/ 否则递归调用哦个函数，搜索上半部分 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时就会输出，否则，返回high值，说明搜索失败。 int main() int i,key,pos,length,fen,k,j,a,kuai,e;/ 定义一些变量 a=0;k=0;cout<<"请输入关键字的个数"<<endl;cin>>length;int Alength-1; / 根据输入关键字的个数初始化一个数组进行存储 cout<<"请输入要分块的个数"<<endl;cin>>fen;int Bfen-1; int Mfen-1;for(i=0;i<fen;i+

10、)Mi=0;/ 初始化两个数组，一个用来存储每一块元素的大小，另一个用来存储每一块的中元素的最大值 cout<<"请输入每个分块关键字的个数"<<endl;for(i=0;i<fen;i+)cin>>Bi;/使数组B中表示每块中关键字的个数 cout<<"请输入关键字"<<endl; for(i=0;i<length;i+)cin>>Ai;/输入所有的关键字，存在数组A中 int row,col;row=fen;col=length;int *p2 ;p2 = new i

11、nt*row ;/声明一个二维数组 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; /将所有关键字，按块的不同存入二维数组中 cout<<"分块情况为"<<endl;for( i = 0 ; i < row ; i + ) for( j = 0 ;j <Bi ; j + ) cout<<p2ij<<'

12、 ' ; if(p2ij>=Mi) Mi=p2ij; cout<<endl;/输出二维数组，检验分块是否为预期 cout<<"每个块最大元素为"<<endl;for(i=0;i<fen;i+) cout<<Mi<<endl;/将每一组的最大元素存入数组M中 cout<<endl<<"请输入要查找的元素"cin>>key;/将要查找的关键字赋值给key pos=BinSearch(M,0,length-1,key);/调用折半查找函数，查找关

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

14、 q=0;for(i=0;i<kuai;i+) q=q+Bi;if (pos!=Bkuai) cout<<"该元素的位置为"<<pos+q<<endl;/如果关键字存在，输出其位置 else cout<<"不存在该元素"<<endl;/若不存在，输出“不存在该元素” cout<<"还要继续查找吗？是的话，输入1，不是的话输入0"<<endl; cin>>e; /引入判断条件，以便多次查找 while (e!=1)&&(

15、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; 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<<"还要继续查找吗？是的话，输入1，不是的话输入0"<<endl; cin>>e; /与上面程序一致，通过循环条件保证可以多次进行查找 system("pause");return 0;输出结果：说明：可见，按照16=4*4分块的选择方式，13元素在第0块，处于关键字序列中的第2位。86和88元素都不在关键字序列中。另外，由于程序中引入了可以由用户自己选择分块数目和大小的功能，因此，选择16=5+