实验六-顺序和二分查找算法

数据结构实验六顺序和二分查找算法一、实验目的掌握顺序和二分查找算法的基本思想及其实现方法。二、实验要求解决实际问题；转换数据；编写程序上机调试；进行算法分析并写出实习报告。三、实验内容与分析例：对给定的任意数组（设其长度为n），分别用顺序和二分查找方法在此数组中查找与给定值k相等的元素。1、顺序查找，在顺序表R[0..n-1]中查找关键字为k的记录，成功时返回找到的记录位置，失败时返回-1，具体的算法如下所示：intSeqSearch(SeqListR,intn,KeyTypek){inti=0;while(in&&R[i].key!=k){printf(%d,R[i].key);i++;}if(i=n)return-1;else{printf(%d,R[i].key);returni;}}2、二分查找，在有序表R[0..n-1]中进行二分查找，成功时返回记录的位置，失败时返回-1，具体的算法如下：intBinSearch(SeqListR,intn,KeyTypek){intlow=0,high=n-1,mid,count=0;while(low=high){mid=(low+high)/2;printf(第%d次查找：在[%d,%d]中找到元素R[%d]:%d\n,++count,low,high,mid,R[mid].key);if(R[mid].key==k)returnmid;if(R[mid].keyk)high=mid-1;elselow=mid+1;}return-1;}四、实验测试及结果五、程序源代码#includestdio.h#defineMAXL100typedefintKeyType;typedefcharInforType[10];typedefstruct{KeyTypekey;InforTypedata;}NodeType;typedefNodeTypeSeqList[MAXL];intSeqSearch(SeqListR,intn,KeyTypek){inti=0;while(in&&R[i].key!=k){printf(%d,R[i].key);i++;}if(i=n)return-1;else{printf(%d,R[i].key);returni;}}intBinSearch(SeqListR,intn,KeyTypek){intlow=0,high=n-1,mid,count=0;while(low=high){mid=(low+high)/2;printf(第%d次查找：在[%d,%d]中找到元素R[%d]:%d\n,++count,low,high,mid,R[mid].key);if(R[mid].key==k)returnmid;if(R[mid].keyk)high=mid-1;elselow=mid+1;}return-1;}intBinSearch1(SeqListR,KeyTypek,intlow,inthigh){intmid;if(lowhigh)return-1;mid=(low+high)/2;if(k==R[mid].key)returnmid;elseif(kR[mid].key)returnBinSearch1(R,k,low,mid-1);elsereturnBinSearch1(R,k,mid+1,high);}voidmain(){SeqListR;intn=10;KeyTypek=7;inta[]={1,5,3,4,2,6,7,11,9,10},i;for(i=0;in;i++)R[i].key=a[i];printf(\n);if((i=SeqSearch(R,n,k))!=-1)printf(\n元素%d的位置是%d\n,k,i);elseprintf(\n元素%d的位置不在表中\n,k);printf(\n);if((i=BinSearch(R,n,k))!=-1)printf(\n元素%d的位置是%d\n,k,i);elseprintf(\n元素%d的位置不在表中\n,k);printf(\n);if((i=BinSearch1(R,k,0,7))!=-1)printf(\n元素%d的位置是%d\n,k,i);elseprintf(\n元素%d的位置不在表中\n,k);printf(\n);}