《数据结构- 递归算法实验报告》由会员分享，可在线阅读，更多相关《数据结构- 递归算法实验报告（4页珍藏版）》请在金锄头文库上搜索。
1、实验报告实验报告课程数据结构实验名称实验五 递归算法学号姓名实验日期：2012/11/23实验五 递归算法 实验目的：实验目的： 1.熟悉递归算法的实现过程及实现机理； 2.熟练并掌握递归算法的设计方法； 3.了解递归算法到非递归算法的转换。 实验原理： 高级程序语言函数调用原理； 递归算法的设计方法。 实验内容： 6-14 折半查找问题。折半查找问题的描述见 6.1 节，折半查找问题的递归算法见例 6-2。 要求： （1）设计折半查找问题的循环结构算法； （2）设计一个查找成功的例子和一个查找不成功的例子，并设计测试主程序； （3）设计一个包含 10000 个数据元素的查找成功的例子，然后分
2、别调用循环结构的查找算 法和递归结构的查找算法，并测试出两种算法在计算机上的实际运行时间。实验结果： （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）查找成功的例子： #includeint Csearch(int test,int x,int low,int high) int i; for( i=0;itesti) low=i+1; else high=i-1;
3、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“); 运行结果为：查找失败的例子为： #includeint Csearch(int test,int x,in
4、t 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 10
5、273206n“); 运行结果为：（3）程序为： #include #include int 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(xtesti) 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)
6、; 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“, for( i=0;ihigh;i+) ai=i+1;time( 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( dif
7、=difftime(end,start); printf(“di gui method use time is:%f secondsn“,dif);time( 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(dif=difftime(end,start); printf(“xun huan method use time is :%f secondsn“,dif); printf(“This program is made by 10273206n“); 运行结果为：总结与思考通过实验我初步了解了递归算法到非递归算法的转换，递归算法在数据结构存储中用 处很大。同时，我也熟悉了递归算法的实现过程及实现机理，较熟练并掌握递归算法的设 计方法。
