验证实验－折半查找

《验证实验－折半查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构协同上机实验第三组验证实验－折半查找一、折半查找－实验目的对给定的有序数组（假设长度为n），查找数组中与给定值k相等的元素。二、折半查找－实验过程1、算法思想将数列按有序化排列(升序)，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为前半部分，否则为后半部分。通过一次比较，将查找区间缩小一半。2、变量I：循环变量.J：查找次数计数器Key：需查找的值.Low：刚开始为第一个值所对应的下标.High：刚开始为最后一个值所对应的下标.Mid：第一个与最后一个值所对应下标和的一半Arr：一维数组,用来

2、存放15个数据.3、步骤Ø读取一组15个已升序排列的数据。Ø取出15个数最中间下标的数与关键字进行比较，进行查找Ø若关键字等于这个数的话，则查找成功Ø若关键字小于这个数的话，则范围缩小为表的前半部分Ø若关键字大于这个数的话，则范围缩小为表的后半部分Ø重复执行3）4）5）过程，直到low>high为止。Page8of8数据结构协同上机实验第三组Ø输出各次查询low,high,mid值，总查询次数，验证折半算法4、折半查找－流程图5、折半查找－程序代码/*对给定的有序数组（假设长度为n），查找数组中与给定值k相等的元素。*/#include#include

3、"stdafx.h"#defineN15//定义常量N为数组长度voidfind(intarr[],intkey,inti)//折半查找函数{intlow=0,high=N-1,mid,j=0;//j计数查找次数while(low<=high){mid=(low+high)/2;//取中间位++j;printf("第%2d次查找low=%2dhigh=%2dmid=%2d",j,low,high,mid);//显示每次查找低中高位，查找次数Page8of8数据结构协同上机实验第三组if(arr[mid]==key)//查到数据，跳出循环break;if(arr[mi

4、d]

5、的数据{arr[i]=i+1;printf("%d",arr[i]);}printf("请输入要查询的数字（－，输入小于等于零的数字退出验证程序）:");scanf("%d",&key);//输入KEYwhile(key>0){find(arr,key,N);//调用折半查找函数printf("请输入要查询的数字（－，输入小于等于零的数字退出验证程序）:");scanf("%d",&key);//输入KEY}}6、折半查找－运行结果输入一个数值为1至15的有序一维数据，查询2，7，8的结果的截屏。Page8of8数据结构协同上机实验第三组7、折半查找－时间性能折

6、半算法的时间复杂度O（N）≤log2n，即每经过一次比较,查找范围就缩小一半。经log2n次计较可以完成查找过程。四、折半查找－小结折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率，而且程序实现也较为简单。但是，折半查找的先决条件是查找表中的数据元素必须有序，而对所有数据元素按大小排序是非常费时的操作，因而，还需撑握更高效的排序与查询方法。Page8of8数据结构协同上机实验第三组协同作业试验四－直方图2008年11月一、实验要求－直方图1.关键码的数据类型是整型，且用数组存储；2.求出每个关键码在数组中出现的次数；3.输出直方图。二、实验流程－直方图

7、三、算法思想－直方图1.建立一个与关键码个数相同的数组，数组元素为一个结构体，包含关键码及频率累加计数器。利用数组下标与关键码的对应关系（本例中，数组下标对应关键码减1），把输入的需统计关键码对应到相应的数组元素，并对该元素中的频率累加器进行计数，统计其出现频率。Page8of8数据结构协同上机实验第三组1.使用冒泡排序法，对数组以频率数为序进行降序排列，输出整个数组内容，使用此算法能非常简洁的表示直方图。四、算法说明－直方图说明：使用结构体，是为了确保排序时关键码与频率之间的对应关系，可以以少量空量换取较简洁的程序设计与时间性能。五、算