《折半查找数据结构实验报告》由会员分享，可在线阅读，更多相关《折半查找数据结构实验报告（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 循环使程序可以多次查找，语句并不复杂，但是实现的功能却比较理想。
