数据结构作业——分块查找算法.doc

《数据结构作业——分块查找算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告三题目：试编写利用折半查找确定记录所在块的分块查找算法。提示：1)读入各记录建立主表；2)按L个记录/块建立索引表；3)对给定关键字k进行查找；测试实例：设主表关键字序列：{12221382833384287765063991019796}，L=4，依次查找K=13，K=86，K=88算法思路题意要求对输入的关键字序列先进行分块，得到分块序列。由于序列不一定有序，故对分块序列进行折半查找，找到关键字所在的块，然后对关键字所在的块进行顺序查找，从而找到关键字的位置。故需要折半查找和顺序查找两个函数，考虑用C++中的类函数实现。因为序列一般是用数组进行存储的，这样可以调用

2、不同类型的数组，程序的可适用性更大一些。折半查找函数：ints,d,ss,dd;//声明一些全局变量，方便函数与主函数之间的变量调用。templateintBinSearch(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;//中间位置

3、为低位与高位和的一半取整。midvalue=A[mid];if(midvalue==key)returnmid;elseif(midvalueintshuxuSearch(TA[],

4、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

5、[col];for(i=0;i=M[i])M[i]=p2[i][j];}cout<

6、保证可以多次查找并输出结果。在关键字等信息输入完毕后，进行查找，可以得到该关键字所在块的序号，以及该关键字在整个关键字序列中的位置。程序结构源代码：#includeusingnamespacestd;ints,d,ss,dd;//声明一些全局变量，方便函数与主函数之间的变量调用。templateintBinSearch(TA[],intlow,inthigh,Tkey)//递归实现折半查找{intmid;//初始化中间值的位置Tmidvalue;//初始化中间值if(low>high){s=A[high];d=A[low];ss=high;dd=l

7、ow;return-1;}//如果low的值大于high的值，输出-1，并且将此时的low与high的值存储。else{mid=(low+high)/2;//中间位置为低位与高位和的一半取整。midvalue=A[mid];if(midvalue==key)returnmid;elseif(midvalue