《折半查找数据结构实验报告》由会员分享,可在线阅读,更多相关《折半查找数据结构实验报告(8页珍藏版)》请在金锄头文库上搜索。
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算法思路算法思路题意要求对输入的关键字序列先进行分块,得到分块序列。由于序列不一 定有序,故对分块序列进行折半查找,找到关键字所在的块,然后对关键字所 在的块进行顺序查找,从而找到关键字的位置。 故需要折半查找和顺序查
2、找两个函数,考虑用 C+中的类函数实现。因为 序列一般是用数组进行存储的,这样可以调用不同类型的数组,程序的可适用 性更大一些。 折半查找函数: int s,d,ss,dd;/声明一些全局变量,方便函数与主函数之间的变量调用。 template int BinSearch(T A,int low,int high,T key)/递归实现折半查找 int mid;/ 初始化中间值的位置 T midvalue;/ 初始化中间值 if (lowhigh)s=Ahigh;d=Alow;ss=high;dd=low;return -1;/ 如果 low 的值大于 high 的值,输出-1,并且将此时的
3、low 与 high 的值存储。 elsemid=(low+high)/2;/ 中间位置为低位与高位和的一半取整。 midvalue=Amid;if (midvalue=key)return mid;else if (midvalue 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 值,说明搜索失败。 主函数中,首先对所需要的参数
4、变量进行初始化,由键盘输入关键字,分 块的多少,每一块有多少个关键字。为了用户的人性化考虑,这里由用户自己 决定分块的多少和数目。为了实现这一功能,引入了一个动态存储的二维数组:int *p2 ; p2 = new int*row ;/声明一个二维数组 for( i = 0 ; i =Mi)Mi=p2ij;cout using namespace std;int s,d,ss,dd;/声明一些全局变量,方便函数与主函数之间的变量调用。 template int BinSearch(T A,int low,int high,T key)/递归实现折半查找 int mid;/ 初始化中间值的位置
5、T midvalue;/ 初始化中间值 if (lowhigh)s=Ahigh;d=Alow;ss=high;dd=low;return -1;/ 如果 low 的值大于 high 的值,输出-1,并且将此时的 low 与 high 的值存储。 elsemid=(low+high)/2;/ 中间位置为低位与高位和的一半取整。 midvalue=Amid;if (midvalue=key)return mid;else if (midvalue int shuxuSearch(T A,int high,T key)/ 顺序查找 int i=0; Ahigh=key;/ 初始化 i,使 A 的最高
6、位为 key 值 while(Ai!=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; coutlength; int Alength-1; / 根据输入关键字的个数初始化一个数组进行存储 coutfen; int Bfen-1; int Mfen-1; for(i=0;iBi;/使数组 B 中表示每块中关键字的个数 coutAi;/输入所有的关键字,存在数组 A
7、中 int row,col; row=fen; col=length; int *p2 ; p2 = new int*row ;/声明一个二维数组 for( i = 0 ; i =Mi)Mi=p2ij;coutkey;/将要查找的关键字赋值给 key pos=BinSearch(M,0,length-1,key);/调用折半查找函数,查找关键字处于哪个 块中 coute; /引入判断条件,以便多次查找 while (e!=1)/保证输入合法 while (e=1)coutkey;pos=BinSearch(M,0,length-1,key);coute; /与上面程序一致,通过循环条件保证可以
8、多次进行 查找 system(“pause“); return 0; 输出结果:输出结果:说明:可见,按照 16=4*4 分块的选择方式,13 元素在第 0 块,处于关键字序 列中的第 2 位。86 和 88 元素都不在关键字序列中。 另外,由于程序中引入了可以由用户自己选择分块数目和大小的功能,因此,选择 16=7+5+4(同样保证了分块有序)的分块方法可以得到一样的结果:发现结果完全一致。心得体会:心得体会:1)本次实验程序结构比较简单,无需复杂的函数调用。但是由于本人编 程基础不够扎实,在面对需要很多数组声明和调用的时候,经常弄错, 在编译的过程中出现了很多次内存调用出错的情况。后来发现是二维 数组的定义上没有做好,引入了动态定义的方法解决了这一问题。 2)用户的需求是编程的主要目的,这道题如果输入以及分块由编程者自 己定义,虽然可以大大简化编程的繁琐度,但是并没有太大的实际意 义。 3)引入 while 循环使程序可以多次查找,语句并不复杂,但是实现的功能却比较理想。