数据结构作业——分块查找算法
- 格式：doc
- 大小：316.50 KB
- 文档页数：9
. . .
.. .. 数据结构实验报告三
题目：
试编写利用折半查找确定记录所在块的分块查找算法。
提示：
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++中的类函数实现。因为序列一般是用数组进行存储的，这样可以调用不同类型的数组，程序的可适用性更大一些。
折半查找函数：
int s,d,ss,dd;//声明一些全局变量，方便函数与主函数之间的变量调用。
template
int BinSearch(T A[],int low,int high,T key)//递归实现折半查找
{
int mid;// 初始化中间值的位置
T midvalue;// 初始化中间值
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)
return mid; . . .
.. .. else if (midvalue < key) //如果关键字的值大于中间值
return BinSearch(A,mid+1,high,key);// 递归调用函数，搜索下半部分
else
return BinSearch(A,low,mid-1,key);// 否则递归调用哦个函数，搜索上半部分
}
}
以上为通用的折半查找的函数代码，这里引入了几个全局变量，主要是方便在搜索关键字在哪一个分块中时，作为判断条件。
顺寻查找函数：
template
int shuxuSearch(T A[],int high,T key)// 顺序查找
{
int i=0; A[high]=key;// 初始化i，使 A的最高位为key值
while(A[i]!=key)
i++;
return i;// 如果A中有key值，则在i不到n+1时就会输出，否则，返回high值，说明搜索失败。
}
主函数中，首先对所需要的参数变量进行初始化，由键盘输入关键字，分块的多少，每一块有多少个关键字。为了用户的人性化考虑，这里由用户自己决定分块的多少和数目。为了实现这一功能，引入了一个动态存储的二维数组：
int **p2 ;
p2 = new int*[row] ;//声明一个二维数组
for( i = 0 ; i < row ; i ++ )
p2[i] = new int[col] ;
for( i = 0 ; i < row ; i ++ )
{for( j = 0 ; j < B[i] ; j ++ )
{p2[i][j]=A[k];
k=k+1;}
}//将所有关键字，按块的不同存入二维数组中
cout<<"分块情况为"<
for( i = 0 ; i < row ; i ++ )
{
for( j = 0 ;j
{cout<
if(p2[i][j]>=M[i])
M[i]=p2[i][j];
}
cout<
}//输出二维数组，检验分块是否为预期
. . .
.. .. 将各种信息用各种数组加以存储，在需要时不断调用。
另外，由于题目中需要多次查找，为了避免每次查找的反复输入，引入了一个while循环，保证可以多次查找并输出结果。
在关键字等信息输入完毕后，进行查找，可以得到该关键字所在块的序号，以及该关键字在整个关键字序列中的位置。
程序结构
主函数声明各种变量输入关键字的个数输入分块个数输入每个分块中的关键字的个数输入关键字声明一个二维数组并将关键字按快存储在二维数组中输出二维数组检验存储情况调用折折半查找函数声明折半查找函数声明顺序查找函数得到关键字所在的块的位置调用顺序查找函数，对关键字所在快进行查找判断函数返回至是否等于输入数组长YES输出位置输出无该关键字No询问用户是否再次查找YES结束NO
源代码：
#include
using namespace std;
int s,d,ss,dd;//声明一些全局变量，方便函数与主函数之间的变量调用。
template
int BinSearch(T A[],int low,int high,T key)//递归实现折半查找
{
int mid;// 初始化中间值的位置
T midvalue;// 初始化中间值
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)
return mid;
else if (midvalue < key) //如果关键字的值大于中间值
return BinSearch(A,mid+1,high,key);// 递归调用函数，搜索下半部分
else
return BinSearch(A,low,mid-1,key);// 否则递归调用哦个函数，搜索上半部分
}
}
template
int shuxuSearch(T A[],int high,T key)// 顺序查找
{
int i=0; A[high]=key;// 初始化i，使 A的最高位为key值
while(A[i]!=key)
i++;
return i;// 如果A中有key值，则在i不到n+1时就会输出，否则，返回high值，说明搜索失败。
}
int main()
{
int i,key,pos,length,fen,k,j,a,kuai,e;// 定义一些变量
a=0;
k=0;
cout<<"请输入关键字的个数"<
cin>>length;
int A[length-1]; // 根据输入关键字的个数初始化一个数组进行存储
cout<<"请输入要分块的个数"<
cin>>fen;
int B[fen-1];
int M[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中
int row,col;
row=fen;
col=length;
int **p2 ;
p2 = new int*[row] ;//声明一个二维数组
for( i = 0 ; i < row ; i ++ )
p2[i] = new int[col] ;
for( i = 0 ; i < row ; i ++ )
{for( j = 0 ; j < B[i] ; j ++ )
{p2[i][j]=A[k];
k=k+1;}
}//将所有关键字，按块的不同存入二维数组中
cout<<"分块情况为"<
for( i = 0 ; i < row ; 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<<"该元素所处的块是"<
