顺序查找、折半查找.doc

《顺序查找、折半查找.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、顺序查找与折半查找的比较顺序查找简单的从头到尾的查找，对数据没有要求，而折半查找要求查找的数据是按顺序排列的，然后找中间数，若中间数大，则把中间数当成最后一个数找他们的中间数。反之，则把中间数当成第一个数。找他们的中间数。这样，一直找下去，直到找到或者中间数和第一个数或者最后一个数相等。它较顺序查找，效率较高。依据顺序查找算法和折半查找算法的特点，对下面的两个查找表选择一个合适的算法，设计出完整的C源程序。并完成问题：查找表1：{8，15，19，26，33，41，47，52，64，90}，查找key=41查找表2：{12，76，29，15，62，35，33，

2、89，48，20}，查找key=35查找key=41的算法：比较次数：查找key=35的算法：比较次数：查找key=41的算法：折半查找法比较次数：3次查找key=35的算法：顺序查找法比较次数：6次顺序查找算法实现代码：intSequenceSearch(inta[],intn,intkey){inti=0,cnt=0;for(i=0;i

3、ntBinarySearch(inta[],intn,intkey){intlow=0,high=n-1,mid=0;intcnt=0;while(low<=high){cnt++;mid=(low+high)/2;printf("compare%dwith%d",a[mid],key);if(a[mid]==key){printf("SequencialSearchcomparetimes:%d",cnt);returnkey;}if(a[mid]>key){high=mid-1;}else{low=mid+1;}}return-1;}/*折半查找

4、法例题1*/#includevoidmain(){inta[10]={8,18,27,42,47,50,56,68,95,120};intb=8;//要查找的数intmin=0;intmax=9;intmid=(min+max)/2;while(b!=a[mid]){if(b>a[mid]){min=mid;mid=(min+max)/2;}elseif(b

5、mid]);}elseif(b==a[max]){printf("a[%d]=%d",max,a[max]);}elseprintf("没有此数");}/*折半查找法例题2*/#includeintmain(){intkey=0;printf("请输入要查找的数：");scanf("%d",&key);intdata[10]={1,3,5,7,8,9,13,18,22,28};intret=BinarySearch(key,data);if(ret>=0)printf("%d是数组中的第%d个数",key,ret+1);el

6、seprintf("%d在数组中未找到！",key);system("pause");return0;}intBinarySearch(intkey,intdata[]){intlow=0,high=9,middle;while(low>=middle){/*查找结束条件*/intmiddle=（low+high）/2;/*获取数组中间位置*/if(key==data[middle])/*如查当前数据元素的值等于key*/returnmiddle;/*返回所在位置*/if(key

7、=(low+middle)/2;/*在数组的前半部继续查找*/elselow=(middle+high)/2/*在数组的后半部继续查找*/}return-1;/*返回查找不成功标记*/}/*简单排序法*/#include#defineN6voidswap(int*a,int*b){intt;t=*a;*a=*b;*b=t;}voidmain(){inta[6]={15,14,22,30,37,11};intmin;for(inti=0;i

8、in=j;}swap(a+i,a+min);}for