《验证试验-折半查找》由会员分享，可在线阅读，更多相关《验证试验-折半查找（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构协同上机实验第三组验证实验-折半查找一、折半查找一实验目的对给定的有序数组（假设长度为n）,查找数组中与给定值k相等的元素。二、折半查找-实验过程1、算法思想将数列按有序化排列（升序），查找过程中采用跳跃式方式查找，即先以有序 数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查 序列缩小为前半部分，否则为后半部分。通过一次比较，将查找区间缩小一 半。2、变量I :循环变量.J :查找次数计数器Key:需查找的值.Low刚开始为第一个值所对应的下标.High :刚开始为最后一个值所对应的下标.Mid:第一个与最后一个值所对应下标和的一半Arr :一维数组,用来存放15个数
2、据.3、步骤读取一组15个已升序排列的数据。取出15个数最中间下标的数与关键字进行比较，进行查找若关键字等于这个数的话，则查找成功若关键字小于这个数的话，则范围缩小为表的前半部分若关键字大于这个数的话，则范围缩小为表的后半部分重复执行3） 4） 5）过程，直到lowhigh为止。输出各次查询Iow,high,mid值，总查询次数，验证折半算法4、折半查找-流程图读取一组15个以 升序排列的数据5、折半查找-程序代码/*对给定的有序数组（假设长度为n）,查找数组中与给定值k相等的元素。*/#i nclude #include stdafx.h#define N 15 / 定义常量N为数组长度vo
3、id fin d(i nt arr,i nt key,i nt i) /折半查找函数int low=0,high=N-1,mid,j=0; j计数查找次数while(low=high)mid=(low+high)/2; / 取中间位+j；prin tf(n第 2次查找 low=%2d high=%2d mid=%2d,j,low,high,mid); /显示每次查找低中高位，查找次数if(arrmid=key) II查到数据，跳出循环break;if(arrmidkey) II查找的KEYt于中位值，查后半部low=mid+1;elsehigh=mid-1; /查找的KEY、于中位值，查前半部
4、 if(low=high) / 查到数据printf(nn经过总共2次查找，找到该数字，该数字位于数组第%d位,nn,j,mid+1);显示查到的数据的值，下标值，总查找次数elseprintf(nn没有找到!); /显示没有找到void mai n()int arrN,key,i;prin tf(n折半查找验证程序，设定被查数据有位，设定为：n);for(i=0;i0)fin d(arr,key,N); II 调用折半查找函数prin tf(n请输入要查询的数字(，输入小于等于零的数字退出验证程序):);sea nf(%d,&key); II 输入 KEY6折半查找-运行结果输入一个数值为1
5、至15的有序一维数据，查询2, 7, 8的结果的截屏。扶U找 次次次 12 37、折半查找一时间性能折半算法的时间复杂度0( N)wiog2n，即每经过一次比较,查找范围就缩小一 半。经log2n次计较可以完成查找过程。四、折半查找一小结折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率， 而且程序实现也较为简单。但是，折半查找的先决条件是查找表中的数据元素必须 有序，而对所有数据元素按大小排序是非常费时的操作，因而，还需撑握更高效的 排序与查询方法。协同作业试验四一直方图2008年11月、实验要求一直方图1. 关键码的数据类型是整型，且用数组存储；2. 求出每个关键码在数组中
6、出现的次数；3. 输出直方图。、实验流程-直方图三、算法思想一直方图1. 建立一个与关键码个数相同的数组，数组元素为一个结构体，包含关键码及 频率累加计数器。利用数组下标与关键码的对应关系（本例中，数组下标对 应关键码减1），把输入的需统计关键码对应到相应的数组元素， 并对该元素 中的频率累加器进行计数，统计其出现频率。2. 使用冒泡排序法，对数组以频率数为序进行降序排列，输出整个数组内容， 使用此算法能非常简洁的表示直方图。四、算法说明一直方图说明：使用结构体，是为了确保排序时关键码与频率之间的对应关系，可以以 少量空量换取较简洁的程序设计与时间性能。五、算法设计概要-直方图data自定义结
7、构，用于存放关键码及关键码出现的次数data.data nu mber 关键码data.datatimes关键码出现的次数number直方图结构数组t临时结构体，用于排序交换的临时变量i循环变量j循环变量key关键码，对应直方图结构数组下标六、步骤1）初始化直方图结构，定义每个关键码，初始化关键码频率累加计数器为02）循环接受关键码，并且根据输入的关键码找到相对应的元素，对关键码频率累加计数器累加计数3）对直方图中进行排序，排序规则根据关键码出现的频率降序4）输出直方图七、时间性能一直方图本程序中，使用了冒泡算法对数组进行了排序，这也是本程序中最大的时间复 杂度，所以本程序与冒泡排序算法的时间
8、复杂度一致为0（nT ） 0Page # of 8数据结构协同上机实验第三组八、运行结果直方图Page # of 8数据结构协同上机实验第三组Page # of 8数据结构协同上机实验第三组九、直方图一一程序代码/直方图#i nclude stdafx.h#i nclude stdio.h#defi ne N 10/输入次数10次#defi ne R 5/统计数字 1-5struct dataint data number; /存放预定数据(1-5)如果仅用数组，无法解决排序后，被统计数与频率 的对应关系int datatimes; / 存放岀现次数;void mai n()struct da
9、ta n umberR,t;int key=0,j,i;for(i=0;iR;i+) 初始化n umberi.data number=i+1; printf(“ i = 0;n umberi.datatimes=0;请输入数据，测试数据范围控制在1-5之间：n);while(ivN) sea nf(%d,&key);/如果输入有误，则继续循环，直到输入正确后，累加计数器，进行下个数据的输 入if(key5)pri ntf(“输入数据有误，请重新输入n);con ti nue;n umberkey-1.datatimes+;i+;for(i=0;ii;j-)if(n umberj-1.datat
10、imes n umberj.datatimes)t=n umberj-1; numberj-1=n umberj numberj=t;printf(nn关键码 频率 n);for(int i=0;iR;i+)pri ntf(%8d %8dn, numberi.data number, numberi.datatimes);十、小结一直方图本实验，我们小组采用了一维结构数组，比较好的解决了关键码与频率在排序后， 无法对应的问题。如果采用一维数组，关键码由数组下标承担，数组元素表示频 率，这样，排完序后，关键码与频率完全对不上号，频率咼的永远是1，所以无法采用；如果采用二维数组，空间与时间复杂度都会增加，解决方法也会更复杂 些。一维结构数组较好地解决了该问题，在牺牲极有限空间的情况下，换取了简 洁的程序设计与比较好的时间性能。附：数据结构协同作业第三组组员表（略）Page # of 8
