第9章 函数的高级应用.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,C,语言大学实用教程课件 制作人 苏小红,*,哈尔滨工业大学计算机科学与技术学院,苏小红,sxh,第,9,章,函数的高级应用,C语言大学实用教程,本章内容,递归与递归函数,指向函数的指针,返回指针值的函数,递归问题的提出,“汉诺塔”（,Hanoi,）,这是一个必须用递归方法才能解决的问题,n=64,时，,18,446,744,073,709,551,615,次,1844,亿亿次,每次,1,微秒，需要,60,万年,递归问题的提出,AC,，,AB,，,CB,，,AC,，,BA,，,BC,，,AC,A,B,C,n=,3,递归问题的提出,AC,，,AB,，,CB,，,AC,，,BA,，,BC,，,AC,A,B,C,递归问题的提出,AC,，,AB,，,CB,，,AC,，,BA,，,BC,，,AC,A,B,C,递归问题的提出,AC,，,AB,，,CB,，,AC,，,BA,，,BC,，,AC,A,B,C,递归问题的提出,AC,，,AB,，,CB,，,AC,，,BA,，,BC,，,AC,A,B,C,n,更大些,怎么办？,递归问题的提出,第一步：将问题简化。,假设,A,杆上只有,2,个圆盘，即汉诺塔有,2,层，,n,2,。,A,B,C,递归问题的提出,对于一个有,n,（,n1,）个圆盘的汉诺塔，将,n,个圆盘分为两部分：上面的,n-1,个圆盘和最下面的,n,号圆盘。将,“,上面的,n-1,个圆盘,”,看成一个整体。,将,n-1,个盘子从一根木桩移到另一根木桩上,将,1,个盘子从一根木桩移到另一根木桩上,A,C,B,递归问题的提出,将,n,个盘子从一根木桩移到另一根木桩上,问题分解为：,将,n-1,个盘子从一根木桩上移到另一根木桩上,将,1,个盘子从一根木桩移到另一根木桩上,设计一个函数，入口参数为,n,：,将,n,个盘子从一根木桩移到另一根木桩上,将,n-1,个盘子从一根木桩上移到另一根木桩上,也要调用这个函数来实现,出现了函数调用自己的问题,递归调用（,Recursive Call,）,递归（,Recursion,）函数,递归函数,函数直接或间接调用自己,直接调用方式：,int,f(x,),int,y,z,;.z=,f(x,);,例,9.1,求整数,n,的阶乘,n,！,计算,n,！,=,n,*(,n,-1)*(,n,-2)*1,迭代法,用递归的方法,例,9.1,求整数,n,的阶乘,n,！,#include,main(),int,n,i;,long result=1;,printf(Input,n:);,scanf(%d,result=1;,for(i=1;i=n;i+),result*=i;,printf(%d,!=%ld,n,result);,迭代法,long,fact(long,n),long result;,if(n 0),return 1;,else if(n=0|n=1),/*,递归终止条件*,/,return 1;,else,return(n*fact(n-1);,/*,递归调用*,/,例,9.1,求整数,n,的阶乘,n,！,递归法,#include,long,fact(long,n);,main(),int,n;,long result;,printf(Input,n:);,scanf(%d,result=,fact(n,);,if(result,=-1),printf(n,0,data error!n);,else,printf(%d,!=%ldn,n,result);,例,9.1,求整数,n,的阶乘,n,！,递归法,递归调用过程,执行过程：,fact(5)=5*fact(4)=120,fact(4)=4*fact(3)=24,fact(3)=3*fact(2)=6,fact(2)=2*fact(1)=2,fact(1)=1,main,fact(5),fact(4),fact(3),fact(2),fact(1),递归函数,递归方法的基本原理,将复杂问题逐步化简，最终转化为一个最简单的问题,最简单问题的解决，就意味着整个问题的解决,递归调用应该能够在有限次数内终止递归,递归调用如果不加以限制，将无数次的循环调用,必须在函数内部加控制语句，只有当满足一定条件时，递归终止,有时将其称为条件递归,递归函数,任何一个递归调用程序必须包括两部分,递归循环继续的过程,递归调用结束的过程,if(,递归终止条件成立,),return,递归公式的初值,;,else,return,递归函数调用返回的结果值,;,递归函数,思考：下面程序有什么问题,阶乘函数的递归实现,unsigned,long,Fac,(,unsigned,int,n),if,(n 0),printf(data,error!);,else if,(n=0|n=1),return,1;,else,return,n*,Fac,(n-1);,编译这个程序也会给出警告，提示,“非所有控制分支都有返回值”,。,同时，运行程序后如果我们输入了一个负数，那么程序运行结果为：,Input a:-1,Input data error!,a!=11,如果某个函数需要返回值的话，那么一定要确保该函数中的所有控制分支都有返回值。,返回指针值的函数,数据类型*函数名,(,参数表,),例,9.3:,编一个函数连接两个字符串，然后返回连接后字符串的首地址,返回指针值的函数,char*,MyStrcat(char,*,dstStr,char*,srcStr,),char*,pStr,=,dstStr,;,while(*,dstStr,!=0),dstStr,+;,for(;*,srcStr,!=0;,dstStr,+,srcStr,+),*,dstStr,=*,srcStr,;,*,dstStr,=0;,return,pStr,;,返回指针值的函数,#include,#define ARR_SIZE 80,char*,MyStrcat(char,*,dstStr,char*,srcStr,);,main(),char,firstARR_SIZE,=Hello;,char,secondARR_SIZE,=world;,char*result=NULL;,result=,MyStrcat(first,second);,printf(nThe,result is:%,sn,result);,这个字符数组应该保证足够大,函数指针（,Function Pointers,）,编译器将不带,(),的函数名解释为该程序的入口地址,换句话说，函数名是指向程序入口的指针,数据类型,(*,指针名,)();,例如：,int,(*p)();,几个容易犯的错误：,忘记了前一个,(),，写成,int,*p();,声明一个返回值是整型指针的函数，函数名为,p,忘掉了后一个,(),，写成,int,(*p);,定义了一个整型指针,定义时后一个括号内参数类型与指向的函数不匹配,函数指针,求下列函数的定积分,函数指针,不用函数指针的编程方法,float IntegralFun,1,(float a,float b),float,s,h,y,;,int,n,i,;,s=(1.0+a*a)+(1.0+b*b)/2.0;,n=100;,h=(b-a)/n;,for(i=0;in;i+),y=a+i*h;,s+=1.0+y*y;,return s*h;,函数指针,不用函数指针的编程方法,float IntegralFun,2,(float a,float b),float,s,h,y,;,int,n,i,;,s=(a/(1.0+a*a)+b/(1.0+b*b)/2.0;,n=100;,h=(b-a)/n;,for(i=0;in;i+),y=a+i*h;,s+=y/(1.0+y*y);,return s*h;,函数指针,使用函数指针的编程方法,float,Integral(,float,(*,f)(float,),float a,float b),float s,h,y;,int,n,i;,s=(*,f)(a,)+(*,f)(b,)/2.0;,n=100;,h=(b-a)/n;,for(i=0;in;i+),y=a+i*h;,s+=(*,f)(y,);,return s*h;,y1=Integral(Fun2,0.0,3.0);,y2=Integral(Fun1,0.0,1.0);,float Fun1(float x),return 1+x*x;,float Fun,2,(float x),return x/(1+x*x),;,函数指针,应用,编写通用性更强的函数,典型实例,计算函数的定积分,另一个典型实例,既能按照升序排序，又能按降序排序,见,C,语言大学实用教程学习指导,P385-395,函数指针,void,Sort(int,a,int,n,int,(*,compare)(int,a,int,b),if(*,compare)(ai,max,),.,/*,决定数据是否按升序排序,ab,为真,则按升序排序*,/,int,Ascending(int,a,int,b),return a b,为真,则按降序排序*,/,int,Descending(int,a,int,b),return a b;,函数指针,其他应用,函数指针通常用在菜单驱动的系统中,系统提示用户从菜单中选择一种操作（可能是,1,6,）,对应于用户选择的不同操作是由不同的函数来完成的,先将指向每个函数的指针存储在一个指针数组中,调用函数完成相应操作时,将用户输入的选择，作为该指针数组的下标,利用存储于相应数组元素中的函数指针，调用相应的函数,见,C,语言大学实用教程学习指导,作业,P374376,9.19.3,