Chap 10 函数与程序结构 10.1 函数的组织 10.2 递归函数.

Presentation on theme: "Chap 10 函数与程序结构 10.1 函数的组织 10.2 递归函数."— Presentation transcript:

1 Chap 10 函数与程序结构 10.1 函数的组织 10.2 递归函数

2 本章要点 怎样把多个函数组织起来？ 怎样用结构化程序设计的思想解决问题？ 怎样用函数嵌套求解复杂的问题？ 怎样用函数递归解决问题？
如何使用宏？

3 10.1 函数的组织 使用结构化程序设计方法解决复杂的问题 把大问题分解成若干小问题，小问题再进一步分解成若干更小的问题
写程序时，用main()解决整个问题，它调用解决小问题的函数 这些函数又进一步调用解决更小问题的函数，从而形成函数的嵌套调用

4 程序结构 main( ) 函数1 函数2 …… 函数m 函数1_1 函数1_2 函数m_1 函数m_n

5 程序解析-计算常用圆形体体积 例10-1 设计一个常用圆形体体积计算器，采用命令方式输入1、2、3，分别选择计算球体、圆柱体、圆锥体的体积，并输入计算所需相应参数。 分析： 输入1、2、3选择计算3种体积，其他输入结束计算 设计一个控制函数cal()，经它辨别圆形体的类型再调用计算球体、圆柱体、圆锥体体积的函数 设计单独的函数计算不同圆形体的体积

6 程序结构 3层结构，5个函数 降低程序的构思、编写、调试的复杂度 可读性好 main( ) cal ( ) vol_ball ( )
vol_cylind ( ) vol_cone ( ) 3层结构，5个函数 降低程序的构思、编写、调试的复杂度 可读性好

7 例10-1源程序 #define PI 3.141592654 void cal ( int sel ); int main(void)
while( 1 ) { printf(" 1-计算球体体积\n"); printf(" 2-计算圆柱体积\n"); printf(" 3-计算圆锥体积\n"); printf(" 其他-退出程序运行\n"); printf(“请输入计算命令：”); scanf("%d",&sel); if (sel < 1 || sel > 3) break; /* 输入非1~3，循环结束 */ else cal (sel ); /* 输入1~3，调用cal() */ } return 0; 例10-1源程序

8 { double vol_ball(void ); double vol_cylind(void );
/* 常用圆形体体积计算器的主控函数 */ void cal ( int sel ) { double vol_ball(void ); double vol_cylind(void ); double vol_cone(void ); switch (sel) { case 1: printf("球体积为：%.2f\n", vol_ball( )); break; case 2: printf("圆柱体积为：%.2f\n", vol_cylind( ) ); case 3: printf("圆锥体积为：%.2f\n", vol_cone( ) ); } /* 计算圆锥体积 V=h/3*PI*r*r */ double vol_cone( ) { double r , h ; printf("请输入圆锥的底圆半径和高："); scanf("%lf%lf",&r,&h); return(PI*r*r*h/3.0); } /* 计算球体体积 V=4/3*PI*r*r*r */ double vol_ball( ) { double r ; printf("请输入球的半径："); scanf("%lf",&r); return(4.0/3.0*PI*r*r*r); } /* 计算圆柱体积 V=PI*r*r*h */ double vol_cylind( ) { double r , h ; printf("请输入圆柱的底圆半径和高："); scanf("%lf%lf",&r,&h); return(PI*r*r*h); }

9 10.1.2 函数的嵌套调用 顺序调用 int main(void) { …… y = fact(3); ……
{ …… y = fact(3); …… z = mypow(3.5, 2); …… } double fact(int n) { double mypow(double x, in n) main fact mypow main fact mypow

10 函数的嵌套调用 嵌套调用 int main(void) { …… cal (sel); …… } void cal (int sel)
{ …… cal (sel); …… } void cal (int sel) { …… vol_ball() double vol_ball( ) { main cal vol_ball main cal vol_ball

11 例9-1 分析 int main(void) { …… cal (sel); } void cal (int sel) { ……
{ …… cal (sel); } void cal (int sel) { …… vol_ball(); vol_cylind(); vol_cone(); double vol_ball( ) { …… double vol_cylind( ) double vol_cone( ) 例9-1 分析 main( ) cal ( ) vol_ball ( ) vol_cylind ( ) vol_cone ( )

12 函数的嵌套调用 在一个函数中再调用其它函数的情况称为函数的嵌套调用。
如果函数A调用函数B，函数B再调用函数C，一个调用一个地嵌套下去，构成了函数的嵌套调用。 具有嵌套调用函数的程序，需要分别定义多个不同的函数体，每个函数体完成不同的功能，它们合起来解决复杂的问题。

13 10.1.3 文件包含 程序文件模块 为了避免一个文件过长，可以把程序分别保存为几个文件。
一个大程序会由几个文件组成，每一个文件又可能包含若干个函数。 保存有一部分程序的文件称为程序文件模块。 程序－文件－函数 大程序－若干程序文件模块 各程序文件模块分别编译，再连接 整个程序只允许有一个main()函数

14 文件包含 问题：如何把若干程序文件模块连接成一个完整的可执行程序？
当一个Ｃ语言程序由多个文件模块组成时，整个程序只允许有一个main()函数。 为了能调用写在其它文件模块中的函数，文件包含是一个有效的解决方法。

15 文件包含 格式 作用 注意 # include <需包含的文件名> # include “需包含的文件名”
编译预处理命令，以#开头。 在程序编译时起作用，不是真正的C语句，行尾没有分号。

16 例10-2 将例10-1的5个函数分别存储在2个.C文件上，要求通过文件包含把它们联结起来。

17 常用标准头文件 ctype.h 字符处理 math.h 与数学处理函数有关的说明与定义 stdio.h 输入输出函数中使用的有关说明和定义
string.h 字符串函数的有关说明和定义 stddef.h 定义某些常用内容 stdlib.h 杂项说明 time.h 支持系统时间函数

18 10.1.4 全局变量与程序文件模块 局部变量 全局变量 生命周期：从程序执行开始－程序运行结束 静态局部变量
作用范围：函数（复合语句）内部 生命周期：从函数调用开始－函数调用结束 全局变量 作用范围：从定义处到源文件结束 生命周期：从程序执行开始－程序运行结束 静态局部变量 作用范围：局部变量 生命周期：全局变量

19 外部变量（extern） 在某个程序文件模块中定义了全局变量 该全局变量可以在整个程序的所有文件模块中起作用
在其他模块中如果要使用该全局变量，必须将它声明为外部变量 说明这是一个在其他模块中定义的全局变量

20 文件名 file1.c 文件名 file2.c int x； extern x; void main() f1( ) {……… { }
扩大全局变量的作用域 文件名 file2.c int x； void main() {……… } extern x; /*使用file1.c中的全局变量 x */ f1( ) { ……… }

21 静态全局变量 使全局变量只限于本文件引用，而不能被其他文件引用 文件名 file1.c 文件名 file2.c static int x；
无法引用 static int x； void main() {……… } extern x; /*使用file1.c中的全局变量 x */ int f1( ) { ……… }

22 10.1.6 函数与程序文件模块 外部函数 函数能够被程序中的其他程序文件模块调用 在其他文件模块中调用该函数前，声明为外部函数
函数与程序文件模块 外部函数 函数能够被程序中的其他程序文件模块调用 在其他文件模块中调用该函数前，声明为外部函数 extern 函数类型 函数名(参数表说明)； 文件名 file1.c 文件名 file2.c extern int f1(); int main(void) { ……… f1( ); ……… } int f1( ) { ……… } 调用另一模块中的函数

23 static 函数类型 函数名(参数表说明)；
内部函数 使函数只能在本程序文件模块中被调用 static 函数类型 函数名(参数表说明)； 文件名 file1.c 文件名 file2.c extern int f1(); int main(void) { ……… f1( ); ……… } static int f1( ) { ……… } 无法调用

24 10.2 递归函数 程序解析 递归函数基本概念 递归程序设计

25 10.2.1 程序解析 例10-3 用递归函数求n!。 #include <stdio.h>
double fact(int n)； int main(void) { int n; scanf ("%d", &n); printf ("%f", fact (n) ); return 0; } double fact(int n) /* 函数定义 */ { double result; if (n==1 || n == 0) /* 递归出口 */ result = 1; else result = n * fact(n-1); return result;

26 递归函数基本概念

27 递推法与递归法求阶乘 递推法 递归法 n!=1*2*3*....*n
for (result = 1, i = 1; i <= n; i++) result = result * i; 递归法 递归定义 n! = n * (n-1)! (n > 1) n! = (n = 0,1) 递归函数 fact(n)

28 例9-3分析 递归出口 递归式 #include <stdio.h> double fact(int n)；
int main(void) { int n; scanf ("%d", &n); printf ("%f", fact (n) ); return 0; } double fact(int n) { double result; if (n==1 || n == 0) result = 1; else result = n * fact(n-1); return result; 求n! 递归定义 n! = n * (n-1)! (n > 1) n! = (n = 0,1) 递归出口 fact(n)=n*fact(n-1); 递归式

29 递归函数 fact( n )的实现过程 fact(3)= 3*fact(2)＝ 3*2=6 2*fact(1)＝ fact(1)＝1
同时有4个函数在运行，且都未完成 fact(3)= 3*fact(2)＝ 2*fact(1)＝ fact(1)＝1 3*2=6 2*1=2 main() fact(3) fact(2) fact(1) { { { { .... printf(fact(3)) f=3*fact(2) f=2*fact(1) f=1 } return(f) return(f) return(f) } } }

30 例10-4 写输出结果 递归出口 递归式 # include <stdio.h> long fib(int g)
{ switch(g) { case 0: return(0); case 1: case 2: return(2); } printf("g=%d,", g); return ( fib(g-1) + fib(g-2) ); void main() { long k; k = fib(4); printf("k=%ld\n", k); fib(g) = g=0 fib(g) = g=1, 2 fib(g) = fib(g-1)+fib(g-2) g>=3 递归出口 g=4, g=3, k=6 递归式 如何求Fibonacci数列?

31 10.2.3 递归程序设计 两个条件缺一不可 解决递归问题的两个着眼点 用递归实现的问题，满足两个条件：
递归程序设计 用递归实现的问题，满足两个条件： 问题可以逐步简化成自身较简单的形式（递归式） n! = n * (n-1)! n n-1 Σi = n +Σ i i= i=1 递归最终能结束(递归出口) 两个条件缺一不可 解决递归问题的两个着眼点

32 例10-5 汉诺(Hanoi)塔 将64 个盘从座A搬到座B A B C (1) 一次只能搬一个盘子 (2) 盘子只能插在A、B、C三个杆中
(3) 大盘不能压在小盘上

33 分析 A B C

34 分析 n A B C n-1 A B C

35 分析 n A B C n-1 A B C

36 算法 hanio(n个盘，A→B) // C为过渡 { if (n == 1) 直接把盘子A→B else{
hanio(n-1个盘，A→C) // B为过渡 把n号盘 A→B hanio(n-1个盘，C→B) // A为过渡 } 算法

37 函数 /* 搬动n个盘，从a到b，c为中间过渡 */ void hanio(int n, char a, char b, char c)
{ if (n == 1) printf("%c-->%c\n", a, b); else{ hanio(n-1, a, c, b); printf("%c-->%c\n", a, b); hanio(n-1, c, b, a); } 函数 hanio(n个盘，A→B) // C为过渡 { if (n == 1) 直接把盘子A→B else{ hanio(n-1个盘, A→C) 把n号盘 A→B hanio(n-1个盘, C→B) }

38 源程序 /* 搬动n个盘，从a到b，c为中间过渡 */ void hanio(int n, char a, char b, char c)
{ if (n == 1) printf("%c-->%c\n", a, b); else{ hanio(n-1, a, c, b); hanio(n-1, c, b, a); } int main(void) { int n; printf("input the number of disk: " ); scanf("%d", &n); printf("the steps for %d disk are:\n",n); hanio(n, 'a', ‘b', ‘c') ; return 0;