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

**数据结构实验报告三题目：试编写利用折半查找确定记录所在块的分块查找算法。提示：读入各记录建立主表；按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值，说明搜索失败。精品文档放心下载}主函数中，首先对所需要的参数变量进行初始化，由键盘输入关键字，分块的多少，每一块有多少个关键字。为了用户的人性化考虑，这里由用户自己决定分块的多少和数目。为了实现这一功能，引入了一个动态存储的二维数组：精品文档放心下载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循环，保证可以多次查找并输出结果。精品文档放心下载在关键字等信息输入完毕后，进行查找，可以得到该关键字所在块的序号，以及该关键字在整个关键字序列中的位置。感谢阅读**程序结构声明折半查找函数主函数得到关键字所在的块的位置

声明顺序查找函数声明各种变输入关键字量的个数调用折折半输出二维数组检验存储查找函数情况

输入分块个数声明一个二维数组并将关键字按快存储在二维数组中

输入每个分块中的关键字的个数输入关键字调用顺序查找函数，对关键字所在快进行查找

判断函数返回至是否等于输入数组长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<<"还要继续查找吗？是的话，输入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<<"还要继续查找吗？是的话，输入 1，不是的话输入精品文档放心下载0"<<endl;cin>>e;//与上面程序一致，通过循环条件保证可以多次进行感谢阅读查找}system("pause");return0;}**输出结果：说明：可见，按照16=4*4分块的选择方式，13元素在第0块，处于关键字序感谢阅读列中的第2位。86和88元素都不在关键字序列中。精品文档放心下载另外，由于程序中引入了可以由用户自己选择分块数目和大小的功能，因此，选谢谢阅读择16=5+5+6的分块方法可以得到一样的结果