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

./数据结构实验报告三题目：试编写利用折半查找确定记录所在块的分块查找算法。提示：读入各记录建立主表；按L个记录/块建立索引表；对给定关键字k进行查找；测试实例：设主表关键字序列：{12221382833384287765063991019796},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循环,保证可以多次查找并输出结果。在关键字等信息输入完毕后,进行查找,可以得到该关键字所在块的序号,以及该关键字在整个关键字序列中的位置。程序结构源代码：#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元素都不在关键字序列中。另外,由于程序中引入了可以由用户自己选择分