函数和结构化编程

第 7 章 函数和结构化编程,学习目标1掌握源程序结构中函数的组织方法；2理解结构化程序设计思想，并能利用它来解决问题；3. 理解函数嵌套调用的概念，并能熟练利用函数的嵌套调用来解决问题；4理解递推、递归及其算法实现；5理解编译预处理的概念，能熟练应用宏定义和文件包含；6了解用户自定义库模块。,7.1 结构化编程,结构化程序设计(Structured Programming)是一种良好的程序设计技术，它由著名计算机科学家EWDijkstra于1969年提出 7.1.1 自顶向下分析问题 自顶向下分析问题就是把一个较大的复杂问题分解成几个小问题后再解决。,7.1.2 模块化设计,模块化设计时要遵循模块独立性的原则，即模块之间的联系应该尽量简单。具体体现在：1一个模块只完成一个指定的功能2模块间只通过参数进行调用3一个模块只有一个入口和一个出口4模块内慎用全局变量 在C语言中，模块一般通过函数来实现，一个模块对应一个函数。,7.1.3 结构化编码,经模块化设计后，每个模块都可以独立编码。编程时应选用顺序、选择和循环3种控制结构，并使程序具有良好的风格。1见名知义命名对象名2使用注释3使程序结构清晰4使程序具有良好的交互性,例: 读入一组整数存入一个整型数组中，要求显示出计数、当前整数、当前数为止的所有整数之和、当前数为止的最小整数以及当前数为止的最大整数。除此之外，假设必须要显示如下所示的标题及标题下方分列显示的信息。,* 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(); read_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,biggest; 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); ,#include /*预处理命令/函数原型声明/主函数： */#include void prn_banner(void); /* 函数声明 */void prn_headings(void); /* 函数声明 */void read_and_prn_data(void); /* 函数声明 */void main(void) prn_banner(); prn_headings(); read_and_prn_data(); getch();/*显示标题函数:*/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,biggest; 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 函数的嵌套调用,11,求组合数 ,可以转化为求3次阶乘,#includefloat fac(int n) int i; float f=1; for(i=2;i=n;i+) f*=i; return f;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,例:求组合数。,#includefloat fac(int n) int i; float f=1; for(i=2;i1e-10) t1=t1*(even-1)/even; /* t1=1*(1/2)*(3/4)*(5/6) */ odd+=2 ; even+=2; /* t2=1/3 t2=1/5 t2=1/7 */ t2=1.0/odd; t3=t3/4.0; /* t3=1/8 t3=1/32 t3=1/128 */ t=t1*t2*t3; sum+=t; return sum*6;,例:A、B、C、D、E合伙夜间捕鱼，凌晨时都已疲惫不堪，各自在河边的树丛中找地方睡着了。目上三竿，A第一个醒来，他将鱼平分作5份，把多余的一条扔回湖中，拿自己的一份回家去了；B第二个醒来，也将鱼平分作5份，把多余的一条扔回湖中，只拿自己的一份；接着C、D、E依次醒来，也都按同样的办法分鱼。问5人至少合伙捕到多少条鱼？每个人醒来后看到的鱼数是多少条？,fish1=5人所捕的总鱼数fish2=(fish1-1)*4/5fish3=(fish2-1)*4/5fish4=(fish3-1)*4/5fish5=(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,fishi); 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 （边界条件）,23,main( ) int i; long int f40=1, 1; /* fib(1)=fib(2)=1 （边界条件） */ for (i=2; i40; i+) fi=fi-2+fi-1; /* fib(n)=fib(n-1)+fib(n-2) 通项公式 */ for(i=0;i40;i+) if (i%5=0) printf(n); printf(%12ld,fi); getch(); ,7.3.3 递推算法的程序实现例:王小二自夸刀工不错，有人放一张大的煎饼在砧板上，问他：“饼不许离开砧板，切100刀最多能分成多少块？” q(1)=1+1=2q(2)=1+1+2=4q(3)=1+1+2+3=7q(4)=1+1+2+3+4=11用归纳法不难得出：q(n)= q(n-1)+n（通项公式）q(0)=1 （边界条件，一刀不切只有一块）,#include#include#define N 100void main() int i,q101; q0=1; /* q(0)=1 （边界条件，一刀不切只有一块） */ for(i=1;i=N;i+) qi=qi-1+i; /* q(n)= q(n-1)+n（通项公式） */ printf(%d,qN);,7.4 递归调用,7.4.1 递归函数的执行过程 如果函数直接或间接地对自己进行调用，就说函数是递归的（分别称为直接递归和间接递归）。在C语言中，所有的函数都可以递归地使用，直接递归是最简单的形式。,27,递归是利用堆栈技术实现的，堆栈分析：压栈保护现场 （参数、数据）保护断点 保存下条指令的首地址出栈 返回下条指令的首地址堆栈技术：先进后出，后进先出。PUSH 压入指令POP 弹出指令,28,mov ax,1234mov bx,5678push axpush bxpop axpop bxint 3,例:在屏幕上以降序形式依次显示1-10之间的整数。#includevoid fun(int);void main(void) fun(10); getch();void fun(int n) if(n) printf(%3d,n); fun(n-1); else printf(nEND!); ,#includevoid fun(int);void main(void) fun(10); getch();void fun(int n) if(n) fun(n-1); printf(%3d,n); else printf(nEND!); /* 打印？*/,例: 计算前n个正整数之和。#includevoid main() printf(%d,sum(4);int sum(int n) if(n1),33,回推 PUSH,递推 POP,结束条件,34,age(int n) int c; if(n=1) c=10; else c=age(n-1)+2; return (c);main() printf(age(5)=%dn,age(5); getch();,age(int n) int c; if(n=1) c=10; else c=age(n-1)+2; printf(age(%d)=%dn,n,c); return (c);main() printf(age(5)=%dn,age(5); getch();,35,递归条件必须有完成函数任务的语句 c=age(n-1)+2; 有结束递归的条件表达式 if (n=1) c=10; 有调用语句 age(5) 先判结束递归的条件，后递归递归过程 回推 (表达式地址和数据入栈)递推 (表达式地址和数据出栈),36,18,16,10,12,14,输出18,例：求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),#includelong fib(int t) long int c; if(t=1|t=2) c=1; else c=fib(t-1)+fib(t-2); return c; void main() printf(%10ld,fib(40);,39,阶乘,jc(int n) int f; if(n=0|n=1) f=1; else f= jc(n-1) *n; return(f);main() int n; scanf(%d,40,最大公约数,gys(int m,int n) if(n=0) return(m); else return gys(n,m%n); main() int a,b,t; scanf(%d,%d,除数替换成被除数,余数替换成除数,41,数制变换 递归法,#include stdio.hint a20,i=0;main() int y,j; scanf(%d, 因递归使用堆栈,先压入低位(i=0时),#include stdio.hmain() int y; scanf(%d,42,数制变换 不用递归,#include stdio.hint a20,i=0;main() int y,j; scanf(%d,43,P10 第(3)题,long func(long x) if(x100) return x%10; else return func(x/100)*10+x%10; main() printf(The result is: %ldn,func(132645); getch(); ,x/100=1326 , 132645%10=5,第一次压入: ( )*10+5,x/100=13 , 1326%10=6,第二次压入: ( )*10+6,13%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); 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 19void display(char,int ,int);void draw(char,int);void main(void) display(SYMBOL,OFFSET,LENGTH); void 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(char 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_strncmp(+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(a0,a1); else minmax(a,n/2,7.5 编译预处理,7.5.1 预处理的概念,预处理：在C编译系统对程序进行通常的编译前，先对程序中以“”开头的命令进行的特殊处理。然后再将这些预处理的结果和源程序一起再进行通常的编译处理，从而得到目标代码。一条预处理命令以“”开头，且占用单一的书写行；预处理命令一般放在源程序的前面，且一般不以“；”结束。,54,C语言与其他高级语言的一个重要区别是可以使用预处理命令和具有预处理的功能。提供的预处理功能主要有以下三种：宏定义文件包含条件编译 这些功能分别用宏定义命令、文件包含命令、条件编译命令来实现。为了与一般语句相区别，这些命令以符号“”开头。例如： #define #include ifdef 标识符 程序段 else 程序段endif,7.5.2 宏定义,宏：代表一个字符串的标识符；宏名：被定义为“宏”的标识符；宏代换（宏展开）：在编译预处理时，对程序中所有出的“宏名”，用宏定义中的字符串去代换的过程。,一、宏替换 1无参宏的定义 格式：define 标识符 字符串 如：(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宏定义不是说明或语句，不作语法检查，不分配内存空间；如： define PI 3.14I59265宏名的作用域一般自定义起到本源程序结束；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 “%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); 对带参的宏展开后，为area=3*2; 再如：#define M(y) y*y+3*y k=M(5); 对其展开后，为k=5*5+3*5;,例：利用宏定义求两个数中的大数。,#define MAX(a, b) (ab)?a:bmain() int x,y,max; scanf(“%d %d”,本例中宏展开后的语句为：max=(xy)?x:y用于计算x、y中的大者。,例：#define PI 3.1415926#define S(r) PIrrmain() 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*a+b,3带参宏定义，形参不分配内存单元，因此不必作类型定义（与函数区别之一）；4带参宏与函数的区别之二：见以下例题,65,#define SQ(y) (y)*(y)main() int i =1; while( i=5 ) printf(%d ,SQ( i+); getch();,展开后： printf(“%dn”, ( i+)*( i+) );,结果：2 12 302*14*36*5,带参宏与函数的区别,main() int i=1; while( i=5 ) printf(“%d ”,SQ( i+);SQ(int y) return (y)*(y); ,结果：1 4 9 16 25,在多数系统中对函数参数的求值顺序是自右向左。,66,#define SQ(y) (y)*(y)main() int i=1; while (i=5) printf(i=%d , SQ(i+)=%d , i=%dn,i,SQ(i+),i); getch();,函数和带参数宏的区别,68,说明：宏定义时，宏名与带参数的括号之间不加空格。对带参数的宏展开只是将宏名后括号内的实参 字符串代替#define命令行中的形参。,例 (为便于口算,将3.14改为3)#define s(r) 3*r*rmain() float a, area,b; a = 4; area = s(a ); printf(area=%fn,area); getch();,改成 #define s(r) 3*(r)*(r),b=3;,+b,展开为3*a+b*a+b,展开为3*(a+b)*(a+b),area=48.000000,area=27.000000,69,#define s(r) 2*r*rmain() int a, x,b; a=4; b=2; x = s(a); printf(x=%dn,x); ? getch();,x=32,#define s(r) 2*r*rmain() int a, x,b; a=4; b=2; x = s(a+b); printf(x=%dn,x); ? getch();,x=18,s=(a+b)=2*4+2*4+2=18 r r,70,带参的宏定义和函数不同的另一种描述：1、函数调用时，先求实参表达式值，后代入。 带参宏只是进行简单的字符替换。2、函数调用是在程序运行时处理的，分配内存单元。 宏展开是在编译时进行的，不分配内存单元。3、函数中的实参和形参都要定义类型，类型应一致。 宏不存在类型问题，宏名和参数无类型.4、函数调用则占用运行时间。 宏替换不占运行时间，只占编译时间。,71,输出6个数及和,#define P(var) printf(#var=%dn,var)#includemain() int x,i,s=0; randomize(); for(i=0;iy?x:y); P(m);#includemain() int a,b,c=0; randomize(); a=rand()%100; P(a); b=rand()%100; P(b); MAX(a,b,c); getch();,73,求3个数的最大值、最小值,1.#define P(var) printf(#var=%dn,var)# define M(a,b,c,max,min) max=(ab?a:b)c?(ab?a:b):c; min=(amain()int c,d,e,mx,mn;randomize();#define R rand()%100;c=R; d=R; e=R;P(c); P(d); P(e);M(c,d,e,mx,mn);P(mx); P(mn);getch();,74,2.#define P(var) printf(#var=%dn,var)#define R rand()%100;# define M(a,b,c,max,min) a=R;b=R;c=R ;P(a);P(b);P(c); max=(ab?a:b)c?(ab?a:b):c; min=(amain()int c,d,e,mx,mn;randomize();M(c,d,e,mx,mn);P(mx); P(mn);getch();,#define P(var) printf(#var=%dn,var)#define R rand()%100;# define M(a,b,c,max,min) a=R;b=R;c=R ;P(a);P(b);P(c); max=(ab?a:b)c?(ab?a:b):c; min=(amain()int c,d,e,mx,mn;randomize();M(c,d,e,mx,mn);getch(); ,75,判别闰年,# include # define IS_LEAP_YEAR(y) y%4=0 ,# include # define IS_LEAP_YEAR(y) (y%4=0 ,7.5.3 文件包含,文件包含是C预处理程序的另一个重要功能。文件包含命令行的一般形式为： #include 需包含的文件名或 #include 例如：#include stdio.h#include ,说明：包含命令中的文件名可以用双引号括起来，也可以用尖括号括起来，但这两种形式是有区别的：使用尖括号()：表示预处理程序在规定的磁盘目录（通常为include子目录）查找文件。使用双引号(“”)：表示预处理程序首先在当前目录中查找文件，若没有找到，最后才去include子目录中查找。(2) 一个include命令只能指定一个被包含文件，若有多个文件要包含，则需用多个include命令。(3) 文件包含允许嵌套，即在一个被包含的文件中又可以包含另一个文件。,例：设有如下直接选择排序函数：void sel_sort(int a,int n) int i,j,k,temp; for(i=0;iaj) k=j; if(k!=i) temp=ak;ak=ai;ai=temp; 现将其以文件名sort.c存放在win-tcprojects（Win-TC环境下）当前工作目录下，要求通过文件包含的方法对一个具有10个元素值的整型数组实现排序。,#include #include sort.C“/* 第3条包含命令包含了编程者自己设计的文件，必须存在于当前工作目录下 */void main(void) int i,a10=8,3,7,9,10,-5,7,15,90,76; sel_sort(a,10); for(i=0;i10;i+) printf(%5d,ai); printf(n);,80,用引号： 带路径：按指定路径去寻找被包含文件，不再从当前目录和指定目录下找。 不带路径：先在当前目录下找，找不到再在系统指定的标准目