试验十二实现顺序和二分查找算法

1、实验十二实现顺序和二分查找算法姓名：张就 班级：09计算机一班学号：2009111111一、实验目的掌握顺序和二分查找算法的基本思想及其实现方法。二、实验内容对给定的任意数组(设其长度为n),分别用顺序和二分查找方法 在此数组中查找与给定值k相等的元素。三、算法思想与算法描述1、 顺序查找，在顺序表R0.n-1中查找关键字为k的记录，成功时返回找到的记录位置，失败时返回-1 ,具体的算法如下所示：int SeqSearch(SeqList R, int n,KeyType k)(int i=0;while (i<n&&Ri.key!=k)(printf( "%d

2、”,Ri.key);i+;if (i>=n)return -1;else(printf( "%d”,Ri.key);return i;2、 二分查找，在有序表R0.n-1中进行二分查找，成功时返回记录 的位置，失败时返回-1 ,具体的算法如下：int BinSearch(SeqList R, int n,KeyType k)(int low=0,high=n-1,mid,count=0;while (low<=high)(mid=(low+high)/2;printf("第欷查找：在%d ,%d中找到元素 R%d:%dn "，+count,low,hi

3、gh,mid,Rmid.key);if (Rmid.key=k)return mid;if (Rmid.key>k)high=mid-1;elselow=mid+1;)return -1;)四、实验步骤与算法实现#include <stdio.h>#define MAXL 100typedef int KeyType;typedef char InforType10;typedef struct(KeyType key;InforType data;)NodeType;typedef NodeType SeqListMAXL;int SeqSearch(SeqList R,

4、int n,KeyType k)(int i=0;while (i<n&&Ri.key!=k)(printf( "%d”,Ri.key);i+;)if (i>=n) return -1;else(printf( "%d”,Ri.key);return i;)int BinSearch(SeqList R, int n,KeyType k)(int low=0,high=n-1,mid,count=0;while (low<=high)(mid=(low+high)/2;printf("第欷查找：在%d ,%d中找到元素 R%d:%

5、dn "，+count,low,high,mid,Rmid.key);if (Rmid.key=k)return mid;if (Rmid.key>k)high=mid-1;elselow=mid+1;)return -1;)int BinSearch1(SeqList R,KeyType k, int low, int high)(int mid;if (low>high)return -1;mid=(low+high)/2;if (k=Rmid.key)return mid;else if (k<Rmid.key)return BinSearch1(R,k,lo

6、w,mid-1);elsereturn BinSearch1(R,k,mid+1,high);)void main()(SeqList R;int n=10;KeyType k=7;int a=1,5,3,4,2,6,7,11,9,10,i;for (i=0;i<n;i+)Ri.key=ai;printf( "n" );if (i=SeqSearch(R,n,k)!=-1)printf( "n 元素由勺位置是 %dn",k,i);elseprintf( "n元素由勺位置不在表中n” ,k);printf( "n" );

7、if (i=BinSearch(R,n,k)!=-1)printf( "n 元素由勺位置是 %dn",k,i);elseprintf( "n元素由勺位置不在表中n" ,k);printf( "n");if (i=BinSearch1(R,k,0,7)!=-1)printf( "n 元素由勺位置是 %dn",k,i);elseprintf( "n元素由勺位置不在表中n" ,k);printf( "n");五、实验测试及结果153426元素&的位置是5程序完全正确的执行结

8、果，如图所示:在0 ,9】中找到元素I在5中找到I在5中找到元素Rrsnfi元素6的位置是5元素6的位置是S请按任意键继续六、总结与体会通过这次在实现顺序和二分查找算法 的过程中，让我对顺序和二分查找算法有了更多的了解。查找根据给定的某个值，在查找表中确 定一个其关键字等于给定值的数据元素或（记录）的操作，应用十分广彳之。顺序查找是一种最简单的查找方法。它的基本思路是：从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值 k相比较, 若当前扫描到的关键字与 k相等，则查找成功；若扫描结束后，仍未找 到关键字等于k的记录，则查找失败。二分查找也称为折半查找要求它首先用线性表中的结点必须己按关键字值的递增或递减顺序排列 要查找的关键字k与中间位置的结点的关键字相比较