折半查找－流程图.docVIP

验证实验－折半查找 一、折半查找－实验目的 对给定的有序数组（假设长度为n），查找数组中与给定值k相等的元素。 二、折半查找－实验过程 1、算法思想 将数列按有序化排列(升序)，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为前半部分，否则为后半部分。通过一次比较，将查找区间缩小一半。 2、变量 I：循环变量. J：查找次数计数器 Key：需查找的值. Low：刚开始为第一个值所对应的下标. High：刚开始为最后一个值所对应的下标. Mid：第一个与最后一个值所对应下标和的一半 Arr：一维数组,用来存放15个数据. 3、步骤 读取一组15个已升序排列的数据。 取出15个数最中间下标的数与关键字进行比较，进行查找 若关键字等于这个数的话，则查找成功 若关键字小于这个数的话，则范围缩小为表的前半部分 若关键字大于这个数的话，则范围缩小为表的后半部分 重复执行3）4）5）过程，直到lowhigh为止。 输出各次查询low,high,mid值，总查询次数，验证折半算法 4、折半查找－流程图 5、折半查找－程序代码 /* 对给定的有序数组（假设长度为n），查找数组中与给定值k相等的元素。*/ #include stdio.h #include stdafx.h #define N 15 //定义常量N 为数组长度 void find(int arr[],int key,int i) //折半查找函数 { int low=0,high=N-1,mid,j=0; //j计数查找次数 while(low=high) { mid=(low+high)/2; //取中间位 ++j; printf(\n 第%2d次查找 low=%2d high=%2d mid=%2d ,j,low,high,mid); //显示每次查找低中高位，查找次数 if(arr[mid]==key) //查到数据，跳出循环 break; if(arr[mid]key) //查找的KEY大于中位值，查后半部 low=mid+1; else high=mid-1; //查找的KEY小于中位值，查前半部 } if(low=high) //查到数据 printf(\n\n经过总共%2d次查找，找到该数字，该数字位于数组第%d 位,\n\n,j,mid+1);//显示查到的数据的值，下标值，总查找次数 else printf(\n\n没有找到!); //显示没有找到 } void main() { int arr[N],key,i; printf(\n折半查找验证程序，设定被查数据有位，设定为：\n); for(i=0;iN;i++) //输入15个排好序的数据 { arr[i]=i+1; printf(%d ,arr[i]); } printf(\n请输入要查询的数字（－，输入小于等于零的数字退出验证程序）:); scanf(%d,key); //输入KEY while(key0) { find(arr,key,N); //调用折半查找函数 printf(\n请输入要查询的数字（－，输入小于等于零的数字退出验证程序）:); scanf(%d,key); //输入KEY } } 6、折半查找－运行结果 输入一个数值为1至15的有序一维数据，查询2，7，8的结果的截屏。 7、折半查找－时间性能 折半算法的时间复杂度O（N）≤log2n，即每经过一次比较,查找范围就缩小一半。经log2n 次计较可以完成查找过程。 四、折半查找－小结 折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率，而且程序实现也较为简单。但是，折半查找的先决条件是查找表中的数据元素必须有序，而对所有数据元素按大小排序是非常费时的操作，因而，还需撑握更高效的排序与查询方法。 协同作业试验四－直方图 2008年11月 一、实验要求－直方图 关键码的数据类型是整型，且用数组存储； 求出每个关键码在数组中出现的次数； 输出直方图。 二、实验流程－直方图 三、算法思想－直方图 建立一个与关键码个数相同的数组，数组元素为一个结构体，包含关键码及频率累加计数器。利用数组下标与关键码的对应关系（本例中，数组下标对应关键码减1），把输入的需统计关键码对应到相应的数组元素，并对该元素中的频率累加器进行计数，统计其出现频率。 使用冒泡排序法，对数组以频率数为序进行降序排列，输出整个数组内容，使用此算法能非