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

《实验六-顺序和二分查找算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验六顺序和二分查找算法一、实验目的掌握顺序和二分查找算法的基本思想及其实现方法。二、实验要求解决实际问题；转换数据；编写程序上机调试；进行算法分析并写出实习报告。三、实验内容与分析例：对给定的任意数组（设其长度为n），分别用顺序和二分查找方法在此数组中查找与给定值k相等的元素。1、顺序查找，在顺序表R[0..n-1]中查找关键字为k的记录，成功时返回找到的记录位置，失败时返回-1，具体的算法如下所示：intSeqSearch(SeqListR,intn,KeyTypek){inti=0;wh

2、ile(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+hi

3、gh)/2;printf("第%d次查找：在[%d,%d]中找到元素R[%d]:%d",++count,low,high,mid,R[mid].key);if(R[mid].key==k)returnmid;if(R[mid].key>k)high=mid-1;elselow=mid+1;}return-1;}四、实验测试及结果五、程序源代码#include#defineMAXL100typedefintKeyType;typedefcharInforType[10];typed

4、efstruct{KeyTypekey;InforTypedata;}NodeType;typedefNodeTypeSeqList[MAXL];intSeqSearch(SeqListR,intn,KeyTypek){inti=0;while(i=n)return-1;else{printf("%d",R[i].key);returni;}}intBinSearch(SeqListR,intn,KeyT

5、ypek){intlow=0,high=n-1,mid,count=0;while(low<=high){mid=(low+high)/2;printf("第%d次查找：在[%d,%d]中找到元素R[%d]:%d",++count,low,high,mid,R[mid].key);if(R[mid].key==k)returnmid;if(R[mid].key>k)high=mid-1;elselow=mid+1;}return-1;}intBinSearch1(SeqListR,KeyTypek

6、,intlow,inthigh){intmid;if(low>high)return-1;mid=(low+high)/2;if(k==R[mid].key)returnmid;elseif(k

7、r(i=0;i

8、nSearch1(R,k,0,7))!=-1)printf("元素%d的位置是%d",k,i);elseprintf("元素%d的位置不在表中",k);printf("");}