第9章-函数的高级应用课件

哈尔滨工业大学计算机科学与技术学院苏小红

sxh@第9章函数的高级应用

C语言大学实用教程1哈尔滨工业大学计算机科学与技术学院第9章函数的高级应用C语本章内容递归与递归函数指向函数的指针返回指针值的函数本章内容递归与递归函数递归问题的提出“汉诺塔”（Hanoi）这是一个必须用递归方法才能解决的问题n=64时，18,446,744,073,709,551,615次1844亿亿次每次1微秒，需要60万年递归问题的提出“汉诺塔”（Hanoi）递归问题的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABCn=3递归问题的提出ABCn=3递归问题的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABC递归问题的提出ABC递归问题的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABC递归问题的提出ABC递归问题的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABC递归问题的提出ABC递归问题的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABCn更大些怎么办？递归问题的提出ABCn更大些递归问题的提出第一步：将问题简化。假设A杆上只有2个圆盘，即汉诺塔有2层，n＝2。ABC递归问题的提出第一步：将问题简化。ABC递归问题的提出对于一个有n（n>1）个圆盘的汉诺塔，将n个圆盘分为两部分：上面的n-1个圆盘和最下面的n号圆盘。将“上面的n-1个圆盘”看成一个整体。将n-1个盘子从一根木桩移到另一根木桩上将1个盘子从一根木桩移到另一根木桩上ACB递归问题的提出对于一个有n（n>1）个圆盘的汉诺塔，将n个递归问题的提出将n个盘子从一根木桩移到另一根木桩上问题分解为：将n-1个盘子从一根木桩上移到另一根木桩上将1个盘子从一根木桩移到另一根木桩上设计一个函数，入口参数为n：将n个盘子从一根木桩移到另一根木桩上将n-1个盘子从一根木桩上移到另一根木桩上也要调用这个函数来实现出现了函数调用自己的问题递归调用（RecursiveCall）递归问题的提出将n个盘子从一根木桩移到另一根木桩上递归（Recursion）函数递归函数函数直接或间接调用自己直接调用方式：

intf(x)

{

inty,z;

….

z=f(x);

……

}递归（Recursion）函数递归函数例9.1求整数n的阶乘n！计算n！=n*(n-1)*(n-2)*…*1迭代法用递归的方法例9.1求整数n的阶乘n！计算n！=n*(n-1)*(例9.1求整数n的阶乘n！#include<stdio.h>main(){ intn,i; longresult=1; printf("Inputn:"); scanf("%d",&n);

result=1; for(i=1;i<=n;i++) result*=i;

printf("%d!=%ld",n,result);}迭代法例9.1求整数n的阶乘n！#include<stdio.hlongfact(longn)

{ longresult; if(n<0) return–1; elseif(n==0||n==1)/*递归终止条件*/

return1; else return(n*fact(n-1));/*递归调用*/}例9.1求整数n的阶乘n！递归法longfact(longn) #include<stdio.h>longfact(longn); main(){ int n; longresult; printf("Inputn:"); scanf("%d",&n); result=fact(n); if(result==-1) printf("n<0,dataerror!\n"); else printf("%d!=%ld\n",n,result);}例9.1求整数n的阶乘n！递归法#include<stdio.h>例9.1求整数n的阶乘n递归调用过程执行过程：

fact(5)=5*fact(4)=120 fact(4)=4*fact(3)=24

fact(3)=3*fact(2)=6fact(2)=2*fact(1)=2fact(1)=1

mainfact(5)fact(4)fact(3)fact(2)fact(1)递归调用过程执行过程：mainfact(5)fact(4)f递归函数递归方法的基本原理将复杂问题逐步化简，最终转化为一个最简单的问题最简单问题的解决，就意味着整个问题的解决递归调用应该能够在有限次数内终止递归递归调用如果不加以限制，将无数次的循环调用必须在函数内部加控制语句，只有当满足一定条件时，递归终止有时将其称为条件递归递归函数递归方法的基本原理递归函数任何一个递归调用程序必须包括两部分递归循环继续的过程递归调用结束的过程

if(递归终止条件成立)

return递归公式的初值;elsereturn递归函数调用返回的结果值;

递归函数任何一个递归调用程序必须包括两部分递归函数思考：下面程序有什么问题阶乘函数的递归实现unsigned

long

Fac(unsigned

intn)

{

if(n<0) printf("dataerror!");

elseif(n==0||n==1)

return1;

else

returnn*Fac(n-1);

}编译这个程序也会给出警告，提示“非所有控制分支都有返回值”。同时，运行程序后如果我们输入了一个负数，那么程序运行结果为：Inputa:-1↙Inputdataerror!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'; returnpStr;}返回指针值的函数char*MyStrcat(char*d返回指针值的函数#include<stdio.h>#defineARR_SIZE80char*MyStrcat(char*dstStr,char*srcStr);main(){ charfirst[ARR_SIZE]="Hello"; charsecond[ARR_SIZE]="world"; char*result=NULL;

result=MyStrcat(first,second); printf("\nTheresultis:%s\n",result);}这个字符数组应该保证足够大返回指针值的函数#include<stdio.h>这个字符数函数指针（FunctionPointers）编译器将不带()的函数名解释为该程序的入口地址换句话说，函数名是指向程序入口的指针数据类型(*指针名)();例如：int(*p)();几个容易犯的错误：忘记了前一个()，写成int*p();声明一个返回值是整型指针的函数，函数名为p忘掉了后一个()，写成int(*p);定义了一个整型指针定义时后一个括号内参数类型与指向的函数不匹配函数指针（FunctionPointers）编译器将不函数指针求下列函数的定积分函数指针求下列函数的定积分函数指针不用函数指针的编程方法floatIntegralFun1(floata,floatb){ floats,h,y; intn,i;

s=((1.0+a*a)+(1.0+b*b))/2.0; n=100; h=(b-a)/n;

for(i=0;i<n;i++) { y=a+i*h;

s+=1.0+y*y;

} returns*h;}函数指针不用函数指针的编程方法函数指针不用函数指针的编程方法floatIntegralFun2(floata,floatb){ floats,h,y; intn,i;

s=(a/(1.0+a*a)+b/(1.0+b*b))/2.0; n=100; h=(b-a)/n;

for(i=0;i<n;i++) { y=a+i*h;

s+=y/(1.0+y*y);

} returns*h;}函数指针不用函数指针的编程方法函数指针使用函数指针的编程方法floatIntegral(float(*f)(float),floata,floatb){ floats,h,y; intn,i;

s=((*f)(a)+(*f)(b))/2.0; n=100; h=(b-a)/n; for(i=0;i<n;i++) { y=a+i*h;

s+=(*f)(y); } returns*h;}y1=Integral(Fun2,0.0,3.0);y2=Integral(Fun1,0.0,1.0);

floatFun1(floatx){return1+x*x;}

floatFun2(floatx){returnx/(1+x*x)

;}

函数指针使用函数指针的编程方法y1=Integral(F函数指针应用编写通用性更强的函数典型实例计算函数的定积分另一个典型实例既能按照升序排序，又能按降序排序见《C语言大学实用教程学习指导》P385-395函数指针应用函数指针voidSort(inta[],intn,int(*compare)(inta,intb)){…… if((*compare)(a[i],max)…….}/*决定数据是否按升序排序,a<b为真,则按升序排序*/intAscending(inta,intb){ returna<b;}/*决定数据是否按降序排序,a>b为真,则按降序排序*/intDescending(inta,intb){ returna>b;}函数指针voidSort(inta[],intn,函数指针其他应用函数指针通常用在菜单驱动的系统中系统提示用户从菜单中选择一种操作（可能是1～6）对应于用户选择的不同操作是由不同的函数来完成的先将指向每个函数的指针存储在一个指针数组中调用函数完成相应操作时将用户输入的选择，作为该指针数组的下标利用存储于相应数组元素中的函数指针，调用相应的函数见《C语言大学实用教程学习指导》函数指针其他应用见《C语言大学实用教程学习指导》作业P374~3769.1~9.3作业P374~376哈尔滨工业大学计算机科学与技术学院苏小红

sxh@第9章函数的高级应用

C语言大学实用教程33哈尔滨工业大学计算机科学与技术学院第9章函数的高级应用C语本章内容递归与递归函数指向函数的指针返回指针值的函数本章内容递归与递归函数递归问题的提出“汉诺塔”（Hanoi）这是一个必须用递归方法才能解决的问题n=64时，18,446,744,073,709,551,615次1844亿亿次每次1微秒，需要60万年递归问题的提出“汉诺塔”（Hanoi）递归问题的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABCn=3递归问题的提出ABCn=3递归问题的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABC递归问题的提出ABC递归问题的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABC递归问题的提出ABC递归问题的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABC递归问题的提出ABC递归问题的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABCn更大些怎么办？递归问题的提出ABCn更大些递归问题的提出第一步：将问题简化。假设A杆上只有2个圆盘，即汉诺塔有2层，n＝2。ABC递归问题的提出第一步：将问题简化。ABC递归问题的提出对于一个有n（n>1）个圆盘的汉诺塔，将n个圆盘分为两部分：上面的n-1个圆盘和最下面的n号圆盘。将“上面的n-1个圆盘”看成一个整体。将n-1个盘子从一根木桩移到另一根木桩上将1个盘子从一根木桩移到另一根木桩上ACB递归问题的提出对于一个有n（n>1）个圆盘的汉诺塔，将n个递归问题的提出将n个盘子从一根木桩移到另一根木桩上问题分解为：将n-1个盘子从一根木桩上移到另一根木桩上将1个盘子从一根木桩移到另一根木桩上设计一个函数，入口参数为n：将n个盘子从一根木桩移到另一根木桩上将n-1个盘子从一根木桩上移到另一根木桩上也要调用这个函数来实现出现了函数调用自己的问题递归调用（RecursiveCall）递归问题的提出将n个盘子从一根木桩移到另一根木桩上递归（Recursion）函数递归函数函数直接或间接调用自己直接调用方式：

intf(x)

{

inty,z;

….

z=f(x);

……

}递归（Recursion）函数递归函数例9.1求整数n的阶乘n！计算n！=n*(n-1)*(n-2)*…*1迭代法用递归的方法例9.1求整数n的阶乘n！计算n！=n*(n-1)*(例9.1求整数n的阶乘n！#include<stdio.h>main(){ intn,i; longresult=1; printf("Inputn:"); scanf("%d",&n);

result=1; for(i=1;i<=n;i++) result*=i;

printf("%d!=%ld",n,result);}迭代法例9.1求整数n的阶乘n！#include<stdio.hlongfact(longn)

{ longresult; if(n<0) return–1; elseif(n==0||n==1)/*递归终止条件*/

return1; else return(n*fact(n-1));/*递归调用*/}例9.1求整数n的阶乘n！递归法longfact(longn) #include<stdio.h>longfact(longn); main(){ int n; longresult; printf("Inputn:"); scanf("%d",&n); result=fact(n); if(result==-1) printf("n<0,dataerror!\n"); else printf("%d!=%ld\n",n,result);}例9.1求整数n的阶乘n！递归法#include<stdio.h>例9.1求整数n的阶乘n递归调用过程执行过程：

fact(5)=5*fact(4)=120 fact(4)=4*fact(3)=24

fact(3)=3*fact(2)=6fact(2)=2*fact(1)=2fact(1)=1

mainfact(5)fact(4)fact(3)fact(2)fact(1)递归调用过程执行过程：mainfact(5)fact(4)f递归函数递归方法的基本原理将复杂问题逐步化简，最终转化为一个最简单的问题最简单问题的解决，就意味着整个问题的解决递归调用应该能够在有限次数内终止递归递归调用如果不加以限制，将无数次的循环调用必须在函数内部加控制语句，只有当满足一定条件时，递归终止有时将其称为条件递归递归函数递归方法的基本原理递归函数任何一个递归调用程序必须包括两部分递归循环继续的过程递归调用结束的过程

if(递归终止条件成立)

return递归公式的初值;elsereturn递归函数调用返回的结果值;

递归函数任何一个递归调用程序必须包括两部分递归函数思考：下面程序有什么问题阶乘函数的递归实现unsigned

long

Fac(unsigned

intn)

{

if(n<0) printf("dataerror!");

elseif(n==0||n==1)

return1;

else

returnn*Fac(n-1);

}编译这个程序也会给出警告，提示“非所有控制分支都有返回值”。同时，运行程序后如果我们输入了一个负数，那么程序运行结果为：Inputa:-1↙Inputdataerror!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'; returnpStr;}返回指针值的函数char*MyStrcat(char*d返回指针值的函数#include<stdio.h>#defineARR_SIZE80char*MyStrcat(char*dstStr,char*srcStr);main(){ charfirst[ARR_SIZE]="Hello"; charsecond[ARR_SIZE]="world"; char*result=NULL;

result=MyStrcat(first,second); printf("\nTheresultis:%s\n",result);}这个字符数组应该保证足够大返回指针值的函数#include<stdio.h>这个字符数函数指针（FunctionPointers）编译器将不带()的函数名解释为该程序的入口地址换句话说，函数名是指向程序入口的指针数据类型(*指针名)();例如：int(*p)();几个容易犯的错误：忘记了前一个()，写成int*p();声明一个返回值是整型指针的函数，函数名为p忘掉了后一个()，写成int(*p);定义了一个整型指针定义时后一个括号内参数类型与指向的函数不匹配函数指针（FunctionPointers）编译器将不函数指针求下列函数的定积分函数指针求下列函数的定积分函数指针不用函数指针的编程方法floatIntegralFun1(floata,floatb){ floats,h,y; intn,i;

s=((1.0+a*a)+(1.0+b*b))/2.0; n=100; h=(b-a)/n;

for(i=0;i<n;i++) { y=a+i*h;

s+=1.0+y*y;

} returns*h;}函数指针不用函数指针的编程方法函数指针不用函数指针的编程方法floatIntegralFun2(floata,floatb){ floats,h,y; intn,i;

s=(a/(1.0+a*a)+b/(1.0+b*b))/2.0; n=100; h=(b-a)/n;

for(i=0;i<n;i++) { y=a+i*h;