数据结构实验 二分查找

1、课程题目：数据结构实验 学院： 班级： 姓名： 学号：实验题目：查找的应用实验内容：二分查找实验目的：掌握查找法的工作原理及应用过程，利用其工作原理完成上述实验题目中的内容。实验要求：为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序伪码(写在纸上及盘中均可) 以便在实验课中完成老师所布置的实验内容。实验学时：4学时设计原理：二分查找（Binary Search) 又称折半查找，它是一种效率比较高的查找方法。但是，这种查找方法的前提是： “已经排序好的线性表”。我们的一维数组就是线性表。一位数组中的成员数据必须已经排序好了，才能用二分法来进

2、行查找操作。排序可以是升序，也可是降序。二分查找法也是一种通过关键字比较的查找方法。他的原理就是用关键字与被查找数据集（如一维数组）的中间位置（以下均是指下标）的数据比较。我们假设有一个20个数据的一位数组，升序。a1,a2,a3,.,a20 我们要查找的数据值为Key 。中间位置的计算方法为：mid（首+尾）/2的底。“首”是指第一个数组成员的下标数组成员的下标值，“尾”在易语言自然是 命令“取数组成员数 (数组)”的值。“底”相当于易语言中的“取整”命令 如本例 mid（1+20）/210.5 取底 mid10 则首先 Key与数组的第10个成员进行比较。如果Key>a10,那么我们

3、要找的数据就可能在数组的第11到20成员之间，反之，Key<a10，我们要找的数据就可能在数组的1到9之间。这样就确定了定了新的寻找范围。重复以上步骤，直到寻找结束。最后的结果是：找到 | 未找到。详细程序清单及注释说明：#include <stdio.h>#include <conio.h>#include <malloc.h>#include <stdlib.h>#define LIST_INIT_SIZE100 /线性表存储空间的初始分配量#define LISTINCREMENT10 /线性表存储空间的分配增量typedefstru

4、ctint *elem; /存储空间基址intlength; /当前长度intlistsize; /当前分配的存储空间(以sizeof(ElemType)为单位)Sqlist;void initlist_sq(Sqlist &l)l.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int); l.length=0; /空表长度为0l.listsize=LIST_INIT_SIZE; /初始存储容量void amount(Sqlist &l)/输入数组长度以及每个数组元素的值int a,b,c;loop:printf("请输入数字的个数

5、：");scanf("%d",&b);if(b<=0)printf("输入错误!请重新输入!n");goto loop;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.elema=c;void order(S

6、qlist &l) /按照冒泡排序法为数组中的元素排序(升序)int i,j,k; for(i=1;i<=l.length;i+) for(j=1;j<=l.length-i;j+)if(l.elemj>l.elemj+1)k=l.elemj;l.elemj=l.elemj+1;l.elemj+1=k;void output(Sqlist &l)/将排序后的数组元素输出printf("经排序后的数组元素:");for(int i=1;i<=l.length;i+)printf("%d",l.elemi);print

7、f(" ");printf("n");int Search_Bin(Sqlist l,intkey)int low=1; /置区间初值int high=l.length; /置区间初值int mid;while(low<=high)mid=(low+high)/2;if(key=l.elemmid) return mid; /找到待查元素else if(key<l.elemmid) high=mid-1; / Key<l.elemmid,继续在前半区间进行查找else low=mid+1; /Key>l.elemmid,继续在后半

8、区间进行查找return 0; /顺序表中不存在待查元素main()int m,n,v;Sqlist l; 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) return 0;else if(v=1) goto loop1;elseprintf("数组中找到此元素!");printf("n");printf("是否继续?(输入1继续/输入0结束)");scanf("%d",&v);if(v=0) return 0;else if(v=1) goto l