折半查找数据结构实验报告..docx

数据结构实验报告三题目：试编写利用折半查找确定记录所在块的分块查找算法。提示：读入各记录建立主表；按L个记录/块建立索引表；对给定关键字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 class Tint BinSearch(T A[],int low,int high,T key)//递归实现折半查找{ int mid;// 初始化中间值的位置 T midvalue;// 初始化中间值 if (lowhigh) { 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 class Tint 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分块情况为endl;for( i = 0 ; i row ; i ++ ) { for( j = 0 ;j B[i] ; j ++ ) {coutp2[i][j] ; if(p2[i][j]=M[i]) M[i]=p2[i][j]; } coutendl;}//输出二维数组，检验分块是否为预期将各种信息用各种数组加以存储，在需要时不断调用。另外，由于题目中需要多次查找，为了避免每次查找的反复输入，引入了一个while循环，保证可以多次查找并输出结果。在关键字等信息输入完毕后，进行查找，可以得到该关键字所在块的序号，以及该关键字在整个关键字序列中的位置。程序结构源代码：#include iostreamusing namespace std;int s,d,ss,dd;//声明一些全局变量，方便函数与主函数之间的变量调用。 template class Tint BinSearch(T A[],int low,int high,T key)//递归实现折半查找{ int mid;// 初始化中间值的位置 T midvalue;// 初始化中间值 if (lowhigh) { s=A[high]; d=A[low]; ss=high; dd=low; return -1;}// 如果low的值大于high的值，输出-1，并且将此时的low与high