数据结构- 递归算法实验报告.doc

实验报告课程数据结构实验名称实验五 递归算法学号姓名实验日期：2012/11/23实验五 递归算法实验目的：1.熟悉递归算法的实现过程及实现机理；2.熟练并掌握递归算法的设计方法；3.了解递归算法到非递归算法的转换。实验原理：高级程序语言函数调用原理；递归算法的设计方法。实验内容：6-14 折半查找问题。折半查找问题的描述见6.1节，折半查找问题的递归算法见例6-2。要求：（1）设计折半查找问题的循环结构算法；（2）设计一个查找成功的例子和一个查找不成功的例子，并设计测试主程序；（3）设计一个包含10000个数据元素的查找成功的例子，然后分别调用循环结构的查找算法和递归结构的查找算法，并测试出两种算法在计算机上的实际运行时间。实验结果：（1）折半查找问题的循环结构算法程序为：int Csearch(int test,int x,int low,int high) int i;for( i=0;itesti) low=i+1;else high=i-1;if(i=high) return -1;（2）查找成功的例子：#include int Csearch(int test,int x,int low,int high) int i;for( i=0;itesti) low=i+1;else high=i-1;if(i=high) return -1;int main() int a10=1,2,3,4,5,6,7,8,9,10; int x=6,flag ; int low=0,high=10; flag=Csearch(a,x,0,10); if(flag=-1) printf(searching is failed!n);else printf(searching is success!n) ;printf(This program is made by 10273206n);运行结果为：查找失败的例子为：#include int Csearch(int test,int x,int low,int high) int i;for( i=0;itesti) low=i+1;else high=i-1;if(i=high) return -1;int main() int a10=1,2,3,4,5,6,7,8,9,10; int x=11,flag ; int low=0,high=10; flag=Csearch(a,x,0,10); if(flag=-1) printf(searching is failed!n);else printf(searching is success!n) ;printf(This program is made by 10273206n);运行结果为：（3）程序为：#include#includeint Bsearch(int a,int x,int low,int high)int mid;if(lowhigh) return -1;mid=(low+high)/2;if(x=amid) return mid;else if(xamid) Bsearch(a,x,low,mid-1);else Bsearch(a,x,mid+1,high);int Csearch(int test,int x,int low,int high) int i;for( i=0;itesti) low=i+1;else high=i-1;if(i=high) return -1;int main()time_t start,end;double dif;int Bsearch(int a,int x,int low,int high);int Csearch(int test,int x,int low,int high);int a10000,x,y,i,bn,flag;int low=0,high=10000,mid=0;printf(please enter number:n);scanf(%ld,&x);for( i=0;ihigh;i+)ai=i+1; time(&start);bn=Bsearch(a,x,0,10000);if(bn=-1) printf(%d is not in a !n,x);else printf(%d is in a,suffix is %dn,x,bn);time(&end);dif=difftime(end,start);printf(di gui method use time is:%f secondsn,dif); time(&start);flag=Csearch(a,x,0,10000);if(flag=-1) printf(%ld is not in a !n,x);else printf(%d is in a,suffix is %dn,x,flag);time(&end); dif=difftime(end,start);printf(xun huan method use time is :%f secondsn,dif);printf(This program i