数据结构实验-二分查找

课程题目：数据结构实验学院：班级：姓名：学号：●实验题目：查找的应用●实验内容：二分查找●实验目的：掌握查找法的工作原理及应用过程，利用其工作原理完成上述实验题目中的内容。●实验要求：为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序伪码(写在纸上及盘中均可)以便在实验课中完成老师所布置的实验内容。●实验学时：4学时●设计原理：二分查找（BinarySearch)又称折半查找，它是一种效率比较高的查找方法。但是，这种查找方法的前提是：“已经排序好的线性表”。我们的一维数组就是线性表。一位数组中的成员数据必须已经排序好了，才能用二分法来进行查找操作。排序可以是升序，也可是降序。二分查找法也是一种通过关键字比较的查找方法。他的原理就是用关键字与被查找数据集（如一维数组）的中间位置（以下均是指下标）的数据比较。我们假设有一个20个数据的一位数组，升序。[a1,a2,a3,........,a20]我们要查找的数据值为Key。中间位置的计算方法为：mid＝（首+尾）/2的底。“首”是指第一个数组成员的下标数组成员的下标值，“尾”在易语言自然是命令“取数组成员数(数组)”的值。“底”相当于易语言中的“取整”命令如本例mid＝（1+20）/2＝10.5取底mid＝10则首先Key与数组的第10个成员进行比较。如果Keya10,那么我们要找的数据就可能在数组的第11到20成员之间，反之，Keya10，我们要找的数据就可能在数组的1到9之间。这样就确定了定了新的寻找范围。重复以上步骤，直到寻找结束。最后的结果是：找到||未找到。●详细程序清单及注释说明：#includestdio.h#includeconio.h#includemalloc.h#includestdlib.h#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{int*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储空间(以sizeof(ElemType)为单位)}Sqlist;voidinitlist_sq(Sqlist&l){l.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));l.length=0;//空表长度为0l.listsize=LIST_INIT_SIZE;//初始存储容量}voidamount(Sqlist&l){//输入数组长度以及每个数组元素的值inta,b,c;loop:printf(请输入数字的个数：);scanf(%d,&b);if(b=0){printf(输入错误!请重新输入!\n);gotoloop;}printf(\n);l.length=l.length+b;//确定表长printf(请输入数组元素!\n);for(a=1;a=l.length;a++){printf(输入第%d个数:,a);printf(\n);scanf(%d,&c);l.elem[a]=c;}}voidorder(Sqlist&l){//按照冒泡排序法为数组中的元素排序(升序)inti,j,k;for(i=1;i=l.length;i++)for(j=1;j=l.length-i;j++)if(l.elem[j]l.elem[j+1]){k=l.elem[j];l.elem[j]=l.elem[j+1];l.elem[j+1]=k;}}voidoutput(Sqlist&l){//将排序后的数组元素输出printf(经排序后的数组元素:);for(inti=1;i=l.length;i++){printf(%d,l.elem[i]);printf();}printf(\n);}intSearch_Bin(Sqlistl,intkey){intlow=1;//置区间初值inthigh=l.length;//置区间初值intmid;while(low=high){mid=(low+high)/2;if(key==l.elem[mid])returnmid;//找到待查元素elseif(keyl.elem[mid])high=mid-1;//Keyl.elem[mid],继续在前半区间进行查找elselow=mid+1;//Keyl.elem[mid],继续在后半区间进行查找}return0;//顺序表中不存在待查元素}main(){intm,n,v;Sqlistl;initlist_sq(l);amount(l);order(l);output(l);loop1:printf(请输入要查找的元素:);scanf(%d,&m);printf(\n);n=Search_Bin(l,m);if(n==0){printf(数组中没有此元素!);printf(\n);printf(是否继续??(输入1继续/输入0结束));scanf(%d,&v);if(v==0)return0;elseif(v==1)gotoloop1;}else{printf(数组中找到此元素!);printf(\n);printf(是否继续??(输入1继续/输入0结束));scanf(%d,&v);if(v==0)return0;elseif(v==1)gotoloop1;}}●运行测试结果：●实验中所遇的问题及解决方法：①、实验过程中会遇到在查找数组的头元素或者尾元素时，程序显示数组中没有此元素。原因：在放置数组元素时，使用了0号单元，但经过验算，发现使用0号单元时会出现边界值的bug，导致程序出现异常。在放弃使用0号单元后，程序能正常使用