6.4 C语言程序设计查找

利用顺序查找方法查找数据利用二分查找方法查找数据能够分清顺序法和二分法的工作方法及优缺点能力目标：任务一用顺序查找法定位指定的数#include"stdio.h"#defineSIZE10main(){

inta[SIZE]={79,82,55,60,65,93,81,90,58,67}

inti,x;

printf("请输入x的值：");

scanf("%d",&x);

for(i=0;i<SIZE;i++)

if(a[i]==x) break;

if(i<SIZE)

printf("找到%d，位于数组第%d个元素位置\n",x,i);else

printf("没有找到%d\n",x);}任务一用顺序查找法在一组数中定位指定的数分析以下运行结果。请输入x的值：90<CR>(找到90，位于数组第8个元素位置)请输入x的值：56<CR>(没有找到56)任务一用顺序查找法在一组数中定位指定的数知识盘点：顺序查找是一种最简单的查找方法，它的思路是：从第一个元素开始，逐个把元素的关键字值和给定值比较，若某个元素的关键字值和给定值相等，则查找成功；否则，若直至第n个数据都不相等，说明不存在满足条件的数据元素，查找失败。顺序查找的优点：算法简单，且对数据的排列无任何要求。顺序查找的缺点：查找效率低，当i较大时，不宜采用顺序查找。任务二用二分查找法定位指定的数#include<stdio.h>#defineN15main(){

int

i,j,number,top,bott,min,loca,a[n],flag;charc;

printf("按从大到小的顺序输入15个数\n");scanf("%d",&a[0]);i=1;

while(i<N)接下页仔细阅读下面程序。任务二用二分查找法在一组数中定位指定的数{

scanf("%d",&a[i]);

if(a[i]>a[i-1])i++;else{printf("请重新输入一个数：");

printf("必须大于%d\n",a[i-1]);}}printf("\n");for(i=0;i<N;i++) printf("%4d",a[i]);printf("\n");flag=1;接下页任务二用二分查找法在一组数中定位指定的数while(flag){

printf("请输入查找的数据：");

scanf("%d",&number);

loca=0;top=0;

bott=N-1;

if((number<a[0])||(number>a[N-1]))

loca=-1;

while((loca==0)&&(top<=bott)){min=(bott+top)/2;

if(number==a[min]){loca=min;

printf(“%d位于表中第%d个数接下页

任务二用二分查找法在一组数中定位指定的数任务二用二分查找法在一组数中定位指定的数\n",number,loca+1);}elseif(number<a[min])

bott=min-1;elsetop=min+1;}

if(loca==0||loca==-1)

printf("%d不在表中。\n",number);

printf("是否继续查找？Y/N！\n");c=getchar();

if(c=='n'||c=='N')flag=0;}}分析以下运行结果:按从小到大的顺序输入15个数1<CR>3<CR>4<CR>5<CR>6<CR>8<CR>12<CR>23<CR>34<CR>44<CR>45<CR>56<CR>57<CR>58<CR>68<CR>①请输入查找数据：56<CR>（56位于表中第12个数）②请输入查找数据：59<CR>

（59不在表中）任务二用二分查找法在一组数中定位指定的数知识盘点：查找方法：设三个位置指针top、bott、mid。bott指向查找范围的底部，top指向查找范围的顶部，mid=（top+bott）/2指向查找范围的中间位置。假设待查找的数放在x中，数列放在a数组中，接着要进行三种判断：

①判断x是否等于a（mid），如果等于，则已找到，查找不必再进行下去，否则进行后面的判断。

②判断x是否小于a（mid），如果小于，则x必定落在top和mid-1的范围之内，下一步查找只须在这个范围内进行而不必去查找mid以后的元素。所以可以确定新的查找范围为top（原来位置不动），bott=mid-1；如果x不小于a（mid），就再进行下一个判断。

③判断x是否小于a（mid）。当然在判断了x不小于等于a（mid）之后，必然就是大于a（mid）了。这时x必定落在mid+1和bott的范围之内，下一步的查找应该在此范围内进行，所以新的查找范围为top=mid+1和bott（原来位置不动）。

④在确定了新的查找范围后，重复进行以上比较；在两种条件下不再重复进行而退出循环：一是已找到，则可退出循环；二是没有找到，以至于使bott变得小于top，这时也应该退出循环。知识盘点：“折半”是指先将给定值和所查区间中间位置的记录的关键字进行比较，若相等，则查找成功，否则，依给定值大于或小于该关键字继续在后半个区间或前半个区间中进行查找。其原理是：先确定待查元素的范围，将其分为两半，然后测试位于中间点元素的值。如果该