C语言程序设计第7章函数进阶和结构化编程.ppt

1、第 7 章 函数进阶和结构化编程,学习目标 1掌握源程序结构中函数的组织方法； 2理解结构化程序设计思想，并能利用它来解决问题； 3. 理解函数嵌套调用的概念，并能熟练利用函数的嵌套调用来解决问题； 4理解递推、递归及其算法实现； 5理解编译预处理的概念，能熟练应用宏定义和文件包含； 6了解用户自定义库模块。,7.1 结构化编程,结构化程序设计(Structured Programming)是一种良好的程序设计技术，它由著名计算机科学家EWDijkstra于1969年提出 7.1.1 自顶向下分析问题 自顶向下分析问题就是把一个较大的复杂问题分解成几个小问题后再解决。,7.1.2 模块化设计,

2、模块化设计时要遵循模块独立性的原则，即模块之间的联系应该尽量简单。具体体现在： 1一个模块只完成一个指定的功能 2模块间只通过参数进行调用 3一个模块只有一个入口和一个出口 4模块内慎用全局变量 在C语言中，模块一般通过函数来实现，一个模块对应一个函数。,7.1.3 结构化编码,经模块化设计后，每个模块都可以独立编码。编程时应选用顺序、选择和循环3种控制结构，并使程序具有良好的风格。 1见名知义命名对象名 2使用注释 3使程序结构清晰 4使程序具有良好的交互性,例: 读入一组整数存入一个整型数组中，要求显示出计数、当前整数、当前数为止的所有整数之和、当前数为止的最小整数以及当前数为止的最大整数

3、。除此之外，假设必须要显示如下所示的标题及标题下方分列显示的信息。,* running sums, minimums, and maximums * Count Item Sum Minimum Maximum,预处理命令/函数原型声明/主函数： #include #include void prn_banner(void); /* 函数声明 */ void prn_headings(void); /* 函数声明 */ void read_and_prn_data(void); /* 函数声明 */ void main(void) prn_banner(); prn_headings(); r

4、ead_and_prn_data(); ,显示标题函数： void prn_banner(void) printf(n*); printf(n running sums, minimums, and maximums ); printf(n*n); 显示各列上部的标题函数： void prn_headings(void) printf(%5s%12s%12s ,Count,Item,Sum); printf(%12s%12snn,Minimum,Maximum); 初始化数据并按要求显示函数： void read_and_prn_data(void) int i,sum,smallest,bi

5、ggest; int a10=1,2,6,7,0,-6,19,52,10,-10; sum=0;smallest=biggest=a0; for(i=0;i10;i+) sum+=ai; smallest=min(ai,smallest); biggest=max(ai,biggest); printf(%5d%12d%12d%12d%12dn,i+1,ai,sum,smallest,biggest); ,7.2 函数的嵌套调用,例:求组合数。,#include float fac(int n) int i; float f=1; for(i=2;i=n;i+) f*=i; return f;

6、 float cmn(int m,int n) float res; res=fac(m)/(fac(n)*fac(m-n); return res; ,void main() int m,n; float t; printf(Input m ,例: 设计一个用于计算常用圆形体体积的计算器，该计算器可支持多次反复计算。采用菜单方式输入1或2或3，分别表示需要计算球体、圆柱体和圆锥体的体积，计算时需输入函数所需的相应参数。,#include #include #define PI 3.141592654 void calculate(int); void main(void) int sel;

7、/* 循环选择计算圆形体的体积，直到输入非13数字为止 */ while(1) printf(tt%s,1-balln); printf(tt%s,2-cylindn); printf(tt%s,3-conen); printf(tt%s,other-exitn); printf(ttPlease input your selete: ); scanf(%d, ,void calculate(int sel) double vol_ball(void); double vol_cylind(void); double vol_cone(void); switch(sel) case 1: pr

8、intf(ball:%.2lfn,vol_ball(); break; case 2: printf(cylind:%.2lfn,vol_cylind(); break; case 3: printf(cone:%.2lfn,vol_cone(); break; ,/* ball:v=4/3*PI*r*r*r */ double vol_ball() double r; printf(Please input r:); scanf(%lf, ,/* cylind : v=PI*r*r*h */ double vol_cylind() double r,h; printf(Please inpu

9、t r ,7.3 递推,7.3.1 递推的一般概念 递推也称为迭代，思路是通过数学推导，将一个复杂的运算化解为若干简单运算的重复执行。 例:通过公式： 计算的近似值，计算过程在所加项的值小于10-10时终止。,#include double fun(double); void main( ) double eps=1e-10,sum; sum=fun(eps); printf(nPI=%.8lf,sum); double fun(double eps) double sum=0.5,t,t1,t2,t3; int odd=1,even=2; t=t1=t2=1.0; t3=0.5; while

10、(t1e-10) t1=t1*(even-1)/even; odd+=2 ; even+=2; t2=1.0/odd; t3=t3/4.0; t=t1*t2*t3; sum+=t; return sum*6; ,例:A、B、C、D、E合伙夜间捕鱼，凌晨时都已疲惫不堪，各自在河边的树丛中找地方睡着了。目上三竿，A第一个醒来，他将鱼平分作5份，把多余的一条扔回湖中，拿自己的一份回家去了；B第二个醒来，也将鱼平分作5份，把多余的一条扔回湖中，只拿自己的一份；接着C、D、E依次醒来，也都按同样的办法分鱼。问5人至少合伙捕到多少条鱼？每个人醒来后看到的鱼数是多少条？,fish1=5人所捕的总鱼数 fis

11、h2=(fish1-1)*4/5 fish3=(fish2-1)*4/5 fish4=(fish3-1)*4/5 fish5=(fish4-1)*4/5 写成一般式为： fishi=(fishi-1-1)*4/5 i=2,3,5,#include void main() int fish6=1,1,1,1,1,1, i; do fish5=fish5+5; for(i=4;i0;i-) if(fishi+1%5=1) fishi=fishi+1*5/4+1; else break; while(fish1=1|fish1%5!=1); for(i=1;i=5;i+) printf(%10d,f

12、ishi); printf(n); ,7.3.2 递推数列 如果一个数列从某一项起，它的任何一项都可以用它前面的若干项来确定，这样的数列被称为递推数列，表示某项与其前面的若干项的关系就称为递推公式。例如Fibonacci数列如下： 1，1，2，3，5，8，13， 令fib(n)表示Fibonacci数列的第n项，依据数列中项与项之间的关系可写出如下Fibonacci数列的递推公式： fib(n)=fib(n-1)+fib(n-2) n=3,4, （通项公式） fib(1)=fib(2)=1 （边界条件）,7.3.3 递推算法的程序实现 例:王小二自夸刀工不错，有人放一张大的煎饼在砧板上，问他：

13、“饼不许离开砧板，切100刀最多能分成多少块？” q(1)=1+1=2 q(2)=1+1+2=4 q(3)=1+1+2+3=7 q(4)=1+1+2+3+4=11 用归纳法不难得出： q(n)= q(n-1)+n（通项公式） q(0)=1 （边界条件，一刀不切只有一块）,#include #include #define N 100 void main() int i,q101; q0=1; for(i=1;i=N;i+) qi=qi-1+i; printf(%d,qN); ,7.4 递归调用,7.4.1 递归函数的执行过程 如果函数直接或间接地对自己进行调用，就说函数是递归的（分别称为直接递

14、归和间接递归）。在C语言中，所有的函数都可以递归地使用，直接递归是最简单的形式。,例:在屏幕上以降序形式依次显示1-10之间的整数。 #include void fun(int); void main(void) fun(10); void fun(int n) if(n) printf(%3d,n); fun(n-1); else printf(nEND!); ,例: 计算前n个正整数之和。 #include void main() printf(%d,sum(4); int sum(int n) if(n=1) return n; else return (n+sum(n-1); ,7.4

15、.2 递归问题求解,例:有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁；问第4个人多少岁？他说比第3个人大2岁；问第3个人多少岁？他说比第2个人大2岁；问第2个人多少岁？他说比第1个人大2岁；问第1个人，他说是10岁。请问第5个人多大？ 分析： age(5) =age(4)+2 age(4) =age(3)+2 age(3) =age(2)+2 age(2) =age(1)+2 age(1)=10 可以用数学公式表述如下： 10 (n=1) age(n)= age(n-1)+2 (n1),#include stdio.h int age(int n) int c ; if (n=1)

16、 c=10; else c=age(n-1)+2; return(c); main() printf(%d,age(5); ,例：求Fibonacci数列的第40个数。Fibonacci数列有如下特点：第1、第2个数均为1，从第3个数开始的每一个数均是其前两个数之和。即： F1=1 (n=1) F2=1 (n=2) Fn=Fn-1+Fn-2 (n3) 分析：根据任务要求，求Fibonacci数列可以用下列递归公式表示 1 (n=1,2) Fn= Fn-1+Fn-2 (n3),#include long fib(int t) long int c; if(t=1|t=2) c=1; else c

17、=fib(t-1)+fib(t-2); return c; void main() printf(%10ld,fib(40); ,例：Hanoi塔问题。相传在古代印度的Bramah庙中，有位僧人整天把3根柱子上的金盘倒来倒去，原来他是想把64只一个比一个大的金盘从一根柱子上移到另一根柱子上去，移动过程要遵循下列规则：(1) 每次只允许移动一只盘；(2) 任何时刻任何柱子上都不允许大盘摞在小盘的上面。如图7.7所示。,分析如下： 1如果n=1，并假定盘号为1，则将盘1从A直接移动到C。 2如果n=2，则： (1) 将A上的n-1（等于1）个盘移到B上； (2) 再将A上的一个盘移到C上； (3)

18、 最后将B上的n-1（等于1）个盘移到C上。 3. 如果n=3，则： (1) 将A上的n-1(等于2，令其为n)个盘移到B（借助于C） 将A上的n-1（等于1）个盘移到C上； 将A上的一个盘移到B上； 将C上的n-1（等于1）个盘移到B上。 (2) 将A上的一个盘移到C (3) 将B上的n-1(等于2，令其为n)个盘移到C（借助A） 将B上的n-1(等于1)个盘移到A； 将B上的一个盘移到C； 将A上的n-1(等于1)个盘移到C。,从上面分析可以看出，当n大于等于2时，移动的过程可分解为三个步骤： 第一步：把A上的n-1个盘借助C移到B上； 第二步：把A上的一个盘移到C上； 第三步：把B上的n

19、-1个盘借助A移到C上。 其中第一步和第三步是类同的，可以用递归解决。递归函数中使用了四个参数： (1) 准备移动的盘数； (2) 最初放置这些盘的柱子； (3) 最后放置这些盘的柱子； (4) 临时存放的柱子。,#include stdio.h void move(char x,char y) printf(%c-%cn,x,y); void hanoi(int n,char one,char two,char three) /* 将n个盘从one柱借助two柱，移到three柱 */ if(n=1)move(one,three); else hanoi(n-1,one,three,two)

20、; move(one,three); hanoi(n-1,two,one,three); void main() int m; printf(input the number of diskes:) ; scanf(%d, ,7.4.3 递归算法举例,例：在屏幕上绘制图案 #include #define SYMBOL * #define OFFSET 0 #define LENGTH 19 void display(char,int ,int); void draw(char,int); void main(void) display(SYMBOL,OFFSET,LENGTH); void

21、display(char c,int m,int n) if(n0) draw( ,m); draw(c,n); putchar(n); display(c,m+1,n-2); ,void draw(char c,int k) if(k0) putchar(c); draw(c,k-1); ,运行结果： * * * * * *,例：用递归处理串：(1) 求串长(2) 模拟字符串比较函数。 用递归求串长 #include void main(void) char str=One World! One Dream!; printf(%dn,r_strlen(str); int r_strlen(c

22、har s) if(*s=0) return 0; else return 1+r_strlen(s+1); ,(2) 用递归模拟字符串比较函数 #include void main(void) char str1=One World!,str2=One Dream!; printf(%dn,r_strncmp(str1,str2,10); /* Recursive string n compare.*/ int r_strncmp(char *s1,char *s2,int n) if(*s1!=*s2|*s1=0|n=1) return *s1-*s2; else return r_str

23、ncmp(+s1,+s2,-n); ,例：整型数组a有n个元素值，求其中的最大数和最小数。 #include #include /* stdlib.h是杂项说明，内含求两数中的大数、求两数中的小数等函数原型说明 */ void minmax(int a,int n,int *min_ptr,int *max_ptr) int min1,max1,min2,max2; if(n=1) *min_ptr=*max_ptr=a0; /* 子问题只有一个元素的情况 */ else if(n=2) /* 子问题有两个元素的情况 */ *min_ptr=min(a0,a1); *max_ptr=max(a

24、0,a1); else minmax(a,n/2, ,7.5 编译预处理,7.5.1 预处理的概念,预处理：在C编译系统对程序进行通常的编译前，先对程序中以“”开头的命令进行的特殊处理。然后再将这些预处理的结果和源程序一起再进行通常的编译处理，从而得到目标代码。 一条预处理命令以“”开头，且占用单一的书写行； 预处理命令一般放在源程序的前面，且一般不以“；”结束。,7.5.2 宏定义,宏：代表一个字符串的标识符； 宏名：被定义为“宏”的标识符； 宏代换（宏展开）：在编译预处理时，对程序中所有出的“宏名”，用宏定义中的字符串去代换的过程。,一、宏替换 1无参宏的定义 格式：define 标识符

25、字符串 如：(1) define PI 3.1415926 (2) define M (y*y+3*y),例：由键盘输入y值，求表达式： 3(y2+3y)+4(y2+3y)+5(y2+3y),#define M (y*y+3*y) main() int s, y; printf(“Input a number:”); scanf(“%d”, ,先宏展开：s=3*(y*y+3*y)+4*(y*y+3*y)+5*(y*y+3*y) 再与源程序一起编译。,说明： 1宏定义中表达式两边的括号不能省； 2宏名习惯上用大写字母； 3使用宏名使程序易读、易修改； 4宏定义不是说明或语句，不作语法检查；如：

26、define PI 3.14I5926 5宏名的作用域一般自定义起到本源程序结束； 6可用undef宏定义的作用域；如： #define G 9.8 main() #undef G f1() ,7宏定义允许嵌套；如： #define PI 3.1415926 #define S PI*y*y printf(“%f”,S); 8宏名在源程序中若用引号括起来，则TC中预处理不对其作宏代换；如： #define OK 100 main() printf(“OK”); prinf(“n”); ,9对“输出格式”进行宏定义，可以减少书写麻烦； 如:,#define P printf #define D

27、“%d, %d, %dn” #define F “%6.2f, %6.2f, %6.2fn” main() int a=5, c=8, e=11; float b=3.8, d=9.7, f=21.08; P(D,a,c,e); P(F, b,d,f); P(F, a+b, c+d, e+f); ,二、有参宏,格式： #define 宏名(参数1，参数2，参数n) 字符串 如： define S(a, b) a*b area=S(3, 2); 再如：#define M(y) y*y+3*y k=M(5); ,例：利用宏定义求两个数中的大数。,#define MAX(a, b) (ab)?a:b

28、 main() int x,y,max; scanf(“%d %d”, ,本例中宏展开后的语句为： max=(xy)?x:y 用于计算x、y中的大者。,例： #define PI 3.1415926 #define S(r) PIrr main() float a, area; a=3.6; area=S(a); printf(“r=%fnarea=%fn”,a, area); ,说明： 1带参宏定义中，宏名与参数间不能有空格； 2如上例程序改为： #define PI 3.1415926 #define S(r) PIrr main() float a, b, area; a=3.6; b=4.1; area=S(a+b); printf(“r=%fnarea=%fn”,a+b, area); 则宏展开为： area=3.1415926*a+b*