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

实验报告

课程 学号

数据结构 姓名 实验名称 实验五 递归算法 实验日期： 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;itest[i]) 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;i

else if(x>test[i]) low=i+1; else high=i-1; } if(i>=high) return -1; }

int main() {

int a[10]={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(\

else printf(\

printf(\}

运行结果为：

②查找失败的例子为： #include

int Csearch(int test[],int x,int low,int high) {

int i; for( i=0;itest[i]) low=i+1; else high=i-1; } if(i>=high) return -1; }

int main() {

int a[10]={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(\

else printf(\

printf(\}

运行结果为：

（3）程序为： #include #include

int Bsearch(int a[],int x,int low,int high) { int mid; if(low>high) return -1; mid=(low+high)/2; if(x==a[mid]) return mid; else if(x

int Csearch(int test[],int x,int low,int high) {

int i; for( i=0;itest[i]) 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 a[10000],x,y,i,bn,flag; int low=0,high=10000,mid=0;

printf(\ number:\\n\ scanf(\ for( i=0;i

dif=difftime(end,start); printf(\ printf(\}

运行结果为：

总结与思考

通过实验我初步了解了递归算法到非递归算法的转换，递归算法在数据结构存储中用处很大。同时，我也熟悉了递归算法的实现过程及实现机理，较熟练并掌握递归算法的设计方法。