数据结构作业任务分块查找算法.docx
《数据结构作业任务分块查找算法.docx》由会员分享，可在线阅读，更多相关《数据结构作业任务分块查找算法.docx（13页珍藏版）》请在冰点文库上搜索。
数据结构作业任务分块查找算法
数据结构实验报告三
题目：
试编写利用折半查找确定记录所在块的分块查找算法。
提示：
1）读入各记录建立主表；
2）按L个记录/块建立索引表；
3）对给定关键字k进行查找；
测试实例：
设主表关键字序列：
{12221382833384287765063991019796}，L=4，依次查找K=13，K=86，K=88
算法思路
题意要求对输入的关键字序列先进行分块，得到分块序列。
由于序列不一定有序，故对分块序列进行折半查找，找到关键字所在的块，然后对关键字所在的块进行顺序查找，从而找到关键字的位置。
故需要折半查找和顺序查找两个函数，考虑用C++中的类函数实现。
因为序列一般是用数组进行存储的，这样可以调用不同类型的数组，程序的可适用性更大一些。
折半查找函数：
ints,d,ss,dd;//声明一些全局变量，方便函数与主函数之间的变量调用。
template
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（midvaluereturnBinSearch（A,mid+1,high,key）;//递归调用函数，搜索下半部分
else
returnBinSearch（A,low,mid-1,key）;//否则递归调用哦个函数，搜索上半部分
}
}
以上为通用的折半查找的函数代码，这里引入了几个全局变量，主要是方便在搜索关键字在哪一个分块中时，作为判断条件。
顺寻查找函数：
template
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;ip2[i]=newint[col];
for（i=0;i{for（j=0;j{p2[i][j]=A[k];
k=k+1;}
}//将所有关键字，按块的不同存入二维数组中
cout<<"分块情况为"<for（i=0;i{
for（j=0;j{cout<if（p2[i][j]>=M[i]）
M[i]=p2[i][j];
}
cout<}//输出二维数组，检验分块是否为预期
将各种信息用各种数组加以存储，在需要时不断调用。
另外，由于题目中需要多次查找，为了避免每次查找的反复输入，引入了一个while循环，保证可以多次查找并输出结果。
在关键字等信息输入完毕后，进行查找，可以得到该关键字所在块的序号，以及该关键字在整个关键字序列中的位置。
程序结构
源代码：
#include
usingnamespacestd;
ints,d,ss,dd;//声明一些全局变量，方便函数与主函数之间的变量调用。
template
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（midvaluereturnBinSearch（A,mid+1,high,key）;//递归调用函数，搜索下半部分
else
returnBinSearch（A,low,mid-1,key）;//否则递归调用哦个函数，搜索上半部分
}
}
template
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<<"请输入关键字的个数"<cin>>length;
intA[length-1];//根据输入关键字的个数初始化一个数组进行存储
cout<<"请输入要分块的个数"<cin>>fen;
intB[fen-1];
intM[fen-1];
for（i=0;i{M[i]=0;}//初始化两个数组，一个用来存储每一块元素的大小，另一个用来存储每一块的中元素的最大值
cout<<"请输入每个分块关键字的个数"<for（i=0;i{cin>>B[i];}//使数组B中表示每块中关键字的个数
cout<<"请输入关键字"<for（i=0;i{cin>>A[i];}//输入所有的关键字，存在数组A中
introw,col;
row=fen;
col=length;
int**p2;
p2=newint*[row];//声明一个二维数组
for（i=0;ip2[i]=newint[col];
for（i=0;i{for（j=0;j{p2[i][j]=A[k];
k=k+1;}
}//将所有关键字，按块的不同存入二维数组中
cout<<"分块情况为"<for（i=0;i{
for（j=0;j{cout<if（p2[i][j]>=M[i]）
M[i]=p2[i][j];
}
cout<}//输出二维数组，检验分块是否为预期
cout<<"每个块最大元素为"<for（i=0;i{cout<cout<cin>>key;//将要查找的关键字赋值给key
pos=BinSearch（M,0,length-1,key）;//调用折半查找函数，查找关键字处于哪个块中
cout<<"该元素所处的块是"<if（pos!
=-1）
{kuai=pos;
cout<}
else
{kuai=dd;
cout<int*S;
S=newint[kuai];
for（i=0;i{S[i]=p2[kuai][i];
}//初始化一个一维数组，将关键字所在快的元素重新定义为一个数组S
pos=shuxuSearch（S,B[kuai],key）;//在S中顺序查找关键字
intq=0;
for（i=0;i{q=q+B[i];}
if（pos!
=B[kuai]）
cout<<"该元素的位置为"<else
cout<<"不存在该元素"<cout<<"还要继续查找吗？
是的话，输入1，不是的话输入0"<cin>>e;//引入判断条件，以便多次查找
while（（e!
=1）&&（e!
=0））
{cout<<"输入不合法,请重新输入e"<cin>>e;}//保证输入合法
while（e==1）
{
cout<cin>>key;
pos=BinSearch（M,0,length-1,key）;
cout<<"该元素所处的块是"<if（pos!
=-1）
{kuai=pos;
cout<}
else
{kuai=dd;
cout<for（i=0;i{S[i]=p2[kuai][i];}
pos=shuxuSearch（S,B[kuai],key）;
intq=0;
for（i=0;i{q=q+B[i];}
if（pos!
=B[kuai]）
cout<<"该元素的位置为"<else
cout<<"不存在该元素"<cout<<"还要继续查找吗？
是的话，输入1，不是的话输入0"<cin>>e;//与上面程序一致，通过循环条件保证可以多次进行查找
}
system（"pause"）;
return0;
}
输出结果：
说明：
可见，按照16=4*4分块的选择方式，13元素在第0块，处于关键字序列中的第2位。
86和88元素都不在关键字序列中。
另外，由于程序中引入了可以由用户自己选择分块数目和大小的功能，因此，选择16=5+5+6的分块方法可以得到一样的结果：
发现结果完全一致。
心得体会：
1）本次实验程序结构比较简单，无需复杂的函数调用。
但是由于本人编程基础不够扎实，在面对需要很多数组声明和调用的时候，经常弄错，在编译的过程中出现了很多次内存调用出错的情况。
后来发现是二维数组的定义上没有做好，引入了动态定义的方法解决了这一问题。
2）用户的需求是编程的主要目的，这道题如果输入以及分块由编程者自己定义，虽然可以大大简化编程的繁琐度，但是并没有太大的实际意义。
3）引入while循环使程序可以多次查找，语句并不复杂，但是实现的功能却比较理想。
升级会员 