C语言程序设计ppt-第5章.ppt

1、2020/10/13,华中科技大学计算机学院,1,C语言程序设计,The C Programming Language,华中科技大学计算机学院曹计昌,2020/10/13,华中科技大学计算机学院,2,第5章 函数与程序结构,本章内容: 构化编程和C程序的一般结构。 函数的机制: 包括函数定义、函数声明、函数调用、变量的存储类型、参数数目可变的函数等。 递归与回溯: 包括解释递归与回溯的概念、递归函数设计,以及递归调用。 多文件程序设计。,2020/10/13,华中科技大学计算机学院,3,5.1 C程序的一般结构,5.1.1 结构化程序设计 结构化编程是一种解决问题的策略，它包括如下2条编程标准

2、： (1) 程序中的控制流应该尽可能简单。 (2) 应该自顶向下地设计程序结构。 自顶向下设计也称为逐步细化，即把一个问题按功能分解为若干子问题，如果子问题还较复杂，可将其继续分解，直到分解成为容易求解的子问题为止。分解而来的每个子问题被称为模块，C中提供的函数机制完成每个模块的编程任务，即用函数编写由分解而来的子问题的代码。,2020/10/13,华中科技大学计算机学院,4,例 显示从1到10的整数幂。,* * A TABLE OF POWERS * * Int Square Cube Quartic Quintic 1 1 1 1 1 2 4 8 16 32 3 9 27 81 243 4

3、 16 64 256 1024 5 25 125 625 3125 6 36 216 1296 7776 7 49 343 2401 16807 8 64 512 4096 32768 9 81 729 6561 59049 10 100 1000 10000 100000,2020/10/13,华中科技大学计算机学院,5,自顶向下的分解问题：,(1) 显示标题 (2) 显示表头 (3) 分列整齐地显示整数1到10的2至5次幂 每个子问题都能作为函数直接被编写成代码， 在main中调用这些函数，解决总的问题。,2020/10/13,华中科技大学计算机学院,6,#include void prn

4、_banner(void); /* prn_banner的函数原型 */ void prn_headings(void); /* prn_headings的函数原型 */ double power(int x,int n); /* power的函数原型 */ void main(void) int i,j; prn_banner() ; /* 显示标题 */ prn_headings(); /* 显示表头 */ for(i=1;i=10;i+) printf(%5d,i); for(j=2;j=5;j+) printf(%10.0f, power(i,j); /* i j */ printf(

5、n); ,main函数：,2020/10/13,华中科技大学计算机学院,7,结构化程序设计的益处,使程序编制方便，易于管理、修改和调试。 增强了程序的可读性、可维护性和可扩充性，方便于多人分工合作完成程序的编制。 函数可以公用，避免在程序中使用重复的代码。 提高软件的可重用性，软件的可重用性是转向面向对象程序设计的重要因素。,2020/10/13,华中科技大学计算机学院,8,5.1.2 C程序的一般结构,C程序由一或多个函数组成，这些函数可以编辑成多个C源文件，每一个C源文件含有一个或多个函数定义。 各C源文件中要用到的一些外部变量说明、枚举类型声明、结构类型声明、函数原型和编译预处理指令等可

6、编辑成一个.h头文件，然后在每个C文件中包含该头文件。 每个源文件可单独编译生成目标文件，组成一个C程序的所有源文件都被编译之后，由连接程序将各目标文件中的目标函数和系统标准函数库的函数装配成一个可执行C程序。 除main以外的其它函数分两类，一类是由系统提供的标准函数。另一类是需要由程序员自己编写的函数（“自定义函数”）。,2020/10/13,华中科技大学计算机学院,9,5.2 函数的定义与函数的声明,程序中若要使用自定义函数实现所需的功能，需要做三件事： 按语法规则编写完成指定任务的函数，即定义函数； 有些情况下在调用函数之前要进行函数声明； 在需要使用函数时调用函数,2020/10/1

7、3,华中科技大学计算机学院,10,5.2.1 函数的定义,函数定义的一般形式为： 类型名 函数名（参数列表） 声明部分 语句部分 无返回值，类型名用void。 无参数，参数列表void（可缺省不写）,2020/10/13,华中科技大学计算机学院,11,函数定义的例子,/* 函数prn_banner：显示标题 */ void prn_banner(void) /* 同于void prn_banner() */ printf(n %s%s%sn, * n, * A TABLE OF POWERS * n, * n ); ,2020/10/13,华中科技大学计算机学院,12,未指明函数返回值的类型，

8、默认为 int,/* 函数prn_headings：显示表头 */ void prn_headings( ) /* 不同于 prn_headings( ) */ printf(n %5s%10s%10s%10s%10sn, Int,Square,Cube,Quartic,Quintic); ,2020/10/13,华中科技大学计算机学院,13,必须明确地列出每一个参数的类型。函数定义中的参数称为形式参数（形参）,/* 函数power：计算x n ，n 0 */ double power(int x，int n) /*不能为 double power(int x,n) */ int i； dou

9、ble p； for (i=1，p=1;i=n;i+) p*=x; return p; ,2020/10/13,华中科技大学计算机学院,14,5.2.2 return语句,return语句可以是如下两种形式之一： （1）return ； /* void函数 */ （2）return 表达式 ； /* 非void函数 */ void函数也可以不包含return语句。如果没有return语句，当执行到函数结束的右花括号时，控制返回到调用处，把这种情况称为离开结束。 表达式值的类型应该与函数定义的返回值类型一致，如果不相同，就把表达式值的类型自动转换为函数返回值的类型 。,2020/10/13,华中

10、科技大学计算机学院,15,函数返回的值，程序可以使用它，也可以不使用它,while() getchar(); /* 返回值不被使用 */ c=getchar(); /* 返回值被使用 */ ,2020/10/13,华中科技大学计算机学院,16,一旦return被执行，控制立即返回到调用处，其后的代码不可能被执行,/* is_prime：如果n是素数，则返回1；否则，返回0 */ int is_prime(int n) /* 等价于 is_prime(int n) */ int k, limit; if (n=2) return 1; if (!(n % 2) return 0; limit=n

11、/2 ; for (k=3; k=limit; k+=2) if ( !(n % k) ) return 0; return 1; ,2020/10/13,华中科技大学计算机学院,17,5.2.3 函数的声明,1函数定义起函数声明的作用 函数定义在前，调用函数在后。例： #include void prn_banner(void) void prn_headings(void) double power(int x,int n) void main(void) ,2020/10/13,华中科技大学计算机学院,18,2函数原型,函数定义出现在函数调用后 被调用函数在其它文件中定义 必须在函数调用

12、之前给出函数原型。,2020/10/13,华中科技大学计算机学院,19,函数原型的一般形式,类型名 函数名（参数类型表）； 参数类型表通常是用逗号隔开的形参类型列表，而形参名可以省略。例如， double power(int, int); 等价于 double power(int x, int n); 无参函数的函数原型参数表必须指定为void,2020/10/13,华中科技大学计算机学院,20,函数原型的作用,函数原型告诉编译器函数返回值的数据类型，传递给函数的参数个数、参数类型和参数顺序。编译器用函数原型校验函数调用, 强制转换传递的参数类型,从而避免错误的函数调用导致的致命运行错误或微妙

13、而难以检测的非致命逻辑错误。例如， printf (%.1f n, sqrt(4) ) ; (1)包含了math.h，输出 2.0 */ (2)没有包含math.h，函数调用sqrt(4)不会产生正确的值。,2020/10/13,华中科技大学计算机学院,21,3遗漏函数原型,编译器首次遇到没有声明的函数调用时，将构造一个缺省声明并继续编译： int f(); /*函数是int类型，但不给出参数表信息*/ (1) 函数类型不是int，给出一个错误提示： Type mismatch in redeclaration of f (2) 函数类型是int，就不给出错误提示。编译器对参数类型不作检查，把

14、正确类型的参数传递给函数是程序员的责任。假设函数f只有一个类型为int的参数，函数调用f (2)会产生正确的值，而函数调用f(2.5)将产生错误的运行结果。,2020/10/13,华中科技大学计算机学院,22,良好的编程风格,在函数调用之前必须给出它的函数定义、函数原型或两者都给出。 引入标准头文件的主要原因是它含有函数原型。,2020/10/13,华中科技大学计算机学院,23,5.3 函数调用与参数传递,5.3.1 函数调用 1函数调用的形式 函数名（实参列表） 实参是一个表达式 ,对于无函数，调用形式 ： 函数名（）,2020/10/13,华中科技大学计算机学院,24,函数调用在程序中出现

15、的形式,(1) 作为表达式语句出现。 prn_headings(); putchar(c); (2）作为表达式中的一个操作数出现。例如： c=getchar() sum += power(i,j); (3）作为函数调用的一个实参出现，即嵌套调用。 printf(%10.0f, power(i , j) ); putchar ( getchar() );,2020/10/13,华中科技大学计算机学院,25,2. 函数调用的执行过程,#include int max(int,int); void main(void) int m, a=3, b=4; m=max( a, b ); printf(%

16、d,m); int max( int x, int y ) if(xy) return x; else return y; ,2020/10/13,华中科技大学计算机学院,26,3实参的求值顺序,实参的求值顺序由具体实现确定，有的按从左至右的顺序计算，有的按从右至左的顺序计算 a=1; max (a，a+) -从左至右：max(1,1) -从右至左：max(2,1) (多数 ) 为了保证程序清晰、可移植，应避免使用会引起副作用的实参表达式 . 实参的求值顺序C语言采用从右至左规则,2020/10/13,华中科技大学计算机学院,27,实参的求值顺序C语言采用从右至左规则,#include std

17、io.h void main(void) int x=1; printf(%dt%dt%dn,x,x+,x); 运行结果： 2 1 1,2020/10/13,华中科技大学计算机学院,28,5.3.2 参数的值传递,参数的传递方式是“值传递”，实参的值单向传递给相应的形参。 如果实参、形参都是x，被调用函数不能改变实参x的值。,2020/10/13,华中科技大学计算机学院,29,例 说明值传递概念的程序,#include long fac(int); void main() int n=4; printf(%dn,n); /* 输出4 */ printf(%ldn,fac(n); /* 输出24

18、 */ printf(%dn,n); /* 输出4 */ long fac(int n) /* 计算n的阶乘 */ long f=1; for( ;n0;-n) f *=n ; /* main中的n值未改变 */ printf(%dn,n); /* 输出0 */ return(f); ,2020/10/13,华中科技大学计算机学院,30,5.4 作用域,作用域：程序正文中可以使用该标识符的那部分程序段。根据作用域，变量有两类： 局部变量：在函数内部定义的变量，作用域是定义该变量的程序块，程序块是带有说明的复合语句（包括函数体）。不同函数可同名，同一函数内不同程序块可同名。形式参数是局部变量。

19、外部变量：在函数外部定义的变量，其作用域从其定义处开始一直到其所在文件的末尾，可由程序中的部分或所有函数共享。,2020/10/13,华中科技大学计算机学院,31,关键字extern的作用,int sp=0；/*sp是外部变量 ,main,push和pop均可访问 */ void main() /* val不能用在main中 */ double valMAXVAL; /* val是外部数组 */ void push(double f ) double pop(void) 利用extern对外部变量进行声明可以扩大其作用域，使得外部变量在定义之前可以使用，以及其它源文件中的函数也可以使用。例如

20、void main() extern double valMAXVAL; ,2020/10/13,华中科技大学计算机学院,32,外部变量的声明和定义的区别,外部变量的声明用于通报变量的类型(引用性声明) 外部变量的定义除此以外还引起存储分配(定义性声明) int sp; 这是外部变量的定义，一方面说明了sp类型为int，另一方面系统还要为其分配2B的存储单元。而 extern int sp ; 这是外部变量的声明，仅仅说明了sp类型为int，不会为其分配存储单元。 外部变量只能定义一次，而外部变量的声明可以出现多次。外部变量的初始化只能出现在其定义中。,2020/10/13,华中科技大学计算机

21、学院,33,5.5 存储类型,变量和函数都有两个属性：数据类型和存储类型。 函数的存储类型决定函数的作用域，可使用的关键字有extern和static(5.9节)。 变量的存储类型决定变量的作用域、存储分配方式、生命周期和初始化方式，可使用的关键字有：auto、extern、static和register。 存储分配方式:在何时、何处给变量分配存储单元； 生命周期:变量在内存中的存在期; 初始化方式:在定义变量时如果未显示初始化，是否有缺省初值，如果有显示初始化，赋初值操作如何执行（执行一次还是执行多次）。,2020/10/13,华中科技大学计算机学院,34,5.5.1 存储类型auto,局部

22、变量的缺省存储类型是auto，称自动变量 auto int a; /*等价于int a; 也等价于auto a; */ 作用域：局部于定义它的块，从块内定义之后直到该块结束有效。 存储分配方式：动态分配方式,即在程序运行过程中分配和回收存储单元。 生命周期：短暂的，只存在于该块的执行期间。 初始化方式：定义时没有显示初始化，其初值是不确定的；有显示初始化，则每次进入块时都要执行一次赋初值操作。,2020/10/13,华中科技大学计算机学院,35,例 块多重嵌套时自动变量的作用域,#include void main(void) int a=2,b=4; printf(a=%d,b=%dn,a,

23、b); int a; a=3;b=5; printf(a=%d,b=%dn,a,b); printf(a=%d,b=%dn,a,b); 内外层有同名变量时,外层变量不可见.,输出： a=2,b=4 a=3,b=5 a=2,b=5,2020/10/13,华中科技大学计算机学院,36,5.5.2 存储类型extern,外部变量的存储类型是extern，但在定义时(定义性声明)不使用关键字extern。 外部变量的作用域:从定义之后直到该源文件结束的所有函数，通过用extern做声明，外部变量的作用域可以扩大到整个程序的所有文件。 存储分配方式:静态分配方式,即程序运行之前，系统就为外部变量在静态区

24、分配存储单元，整个程序运行结束后所占用的存储单元才被收回。 生命周期：永久的，存在于整个程序的执行期间。 初始化方式：定义时没有显示初始化，初值0；有显示初始化，只执行一次赋初值操作。,2020/10/13,华中科技大学计算机学院,37,例 说明外部变量的缺省初值和作用域,#include int n; /* 外部变量,等价于int n =0 */ int f1(void ) n+; return n; void f2(int x) n=x; void main(void) int i; printf(global n is %d on entering main n,n); f2(10);

25、for (i=0;i3;i+) printf(%6d,f1(); printf(nglobal n is %d on exiting main n,n); ,global n is 0 on entering main 11 12 13 global n is 13 on exiting main,2020/10/13,华中科技大学计算机学院,38,例 关键字extern的用法,文件file1.c的内容为： #include int n; /* 定义外部变量 */ int f1(void); /* f1的函数原型 */ void f2(int); /* f2的函数原型 */ void main

26、(void) int i; printf(global n is %d on entering main n,n); f2(10); for (i=0;i3;i+) printf(%6d,f1(); printf(nglobal n is %d on exiting main n,n); ,2020/10/13,华中科技大学计算机学院,39,文件file2.c的内容为,extern int n; /* 外部变量n的声明 */ int f1(void) n+; return n; void f2(int x) n=x; ,2020/10/13,华中科技大学计算机学院,40,5.5.3 存储类型s

27、tatic,关键字static有两个重要而截然不同的用法： (1) 用于定义局部变量，称为静态局部变量。 (2) 用于定义外部变量，称为静态外部变量。 存储分配方式:静态分配方式 生命周期: 永久的， 缺省初值: 0,只执行一次 静态局部变量和自动变量有根本性的区别。 静态外部变量和外部变量区别:作用域不同。,2020/10/13,华中科技大学计算机学院,41,1. 静态局部变量,作用域: 和自动变量一样 静态局部变量的值有连续性. #include long fac(int); /* 函数原型 */ void main(void) int i; for(i=1;i5;i+) printf(%

28、d != %ldn, i, fac(i); long fac(int n) static long f=1;/* 静态局部变量只初始化1次 */ f *=n; return f; ,1!=1 2!=2 3!=6 4!=24,2020/10/13,华中科技大学计算机学院,42,将f定义为自动变量,输出结果如何？,#include long fac(int); /* 函数原型 */ void main(void) int i; for(i=1;i5;i+) printf(%d != %ldn, i, fac(i); long fac(int n) long f=1; /* 局部变量 */ f *=

29、n; return f; ,1!=1 2!=2 3!=3 4!=4,2020/10/13,华中科技大学计算机学院,43,2. 静态外部变量,静态外部变量和外部变量的唯一区别是作用域的限制。 静态外部变量只能作用于定义它的文件，其它文件中的函数不能使用， 外部变量用extern声明后可以作用于其它文件。 使用静态外部变量的好处在于：当多人分别编写一个程序的不同文件时，可以按照需要命名变量而不必考虑是否会与其它文件中的变量同名，保证文件的独立性。,2020/10/13,华中科技大学计算机学院,44,5.5.4 存储类型register,用来定义局部变量, register建议编译器把该变量存储在计

30、算机的高速硬件寄存器中，除此之外，其余特性和自动变量完全相同。 使用register的目的是为了提高程序的执行速度。程序中最频繁访问的变量，可声明为register，。 不可多 必要时使用。,2020/10/13,华中科技大学计算机学院,45,5.6 参数数目可变的函数,printf和scanf就是典型的参数数目可变的函数。 int printf(const char *format,); 函数调用时，实参可以有1至多个。 定义参数数目可变的函数，要用到可变参数头文件stdarg.h中定义的宏和类型。 参阅：P148 （1）-（4）,2020/10/13,华中科技大学计算机学院,46,例5.9

31、 函数average的第1个参数是要被求平均值的数据的个数。,#include #include double average(int,); /* 函数原型 */ void main(void) double a=1.5,b=2.6,c=3.7,d=4.8; printf (a=%.1f,b=%.1f,c=%.1f,d=%.1fn,a,b,c,d); printf (The average of a and b is %.2f n,average(2,a,b); printf (The average of a、b and c is %.2f n,average(3,a,b,c); print

32、f (The average of a,b,c and d is %.2f n,average(4,a,b,c,d); double average(int i,) double sum=0; int k; va_list ap; /* 用va_list类型的对象ap来处理不定参数部分 */ va_start(ap,i); /*用va_start初始化ap，使ap指向第一个不定参数 */ for (k=1;k=i;k+ ) sum +=va_arg(ap,double); /*用va_start反复从可变参数列表中检索到每一个不定参数的值 */ va_end(ap); /*使程序能够从可变参数

33、列表的函数中正常返回 */ return(sum/i); ,2020/10/13,华中科技大学计算机学院,47,可变参数有多种数据类型,double average(int,.); void main(void) double a=1.5,b=2.6,c=3.7,d=4.8; printf (a=%.1f,b=%.1f,c=%.1f,d=%.1fn,a,b,c,d); printf (The average of a and b is %.2f n,average(2,a,b,10); printf (The average of a,b and c is %.2f n,average(3,a

34、,b,c,20); printf (The average of a,b,c and d is %.2f n,average(4,a,b,c,d,30); double average(int i,.) double sum=0; int k; va_list ap; va_start(ap,i); for (k=1;k=i;k+ ) sum +=va_arg(ap,double); k=va_arg(ap,int); printf(%dn,k); va_end(ap); return(sum/i); ,2020/10/13,华中科技大学计算机学院,48,5.7 递归,5.7.1 递归函数与递

35、归调用 #include void prn_int(int n) if (n0) printf (%d ,n); prn_int(n-1); /* 递归调用 */ ,void main(void) prn_int(10); ,递归调用：函数直接调用自己或通过另一函数间接调用自己的函数调用方式 递归函数 ：函数定义中含有递归调用的函数,2020/10/13,华中科技大学计算机学院,49,用递归代替循环(ex5_10b.c),#include stdio.h void recursive_add(int a,int b) if(b=10) a=a+b; printf(b=%d, sum=%dn,b

36、,a); b+; recursive_add(a,b); int loop_add(int a,int b) a=a+b; printf(b=%d, sum=%dn,b,a); return a; ,void main(void) int a,b; printf(nrecursive addn); recursive_add(0,1); printf(n loop addn); for(a=0,b=1;b=10;b+) a=loop_add(a,b); 一般而言,循环结构都可以用递 归的方法来实现.,2020/10/13,华中科技大学计算机学院,50,递归的两个要素,（1）递归结束条件。也就是

37、所描述问题的最简单情况，递归如果没有结束条件，递归过程将永不终止，即无穷递归（和无限循环类似）。 （2）递归定义。为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态，这种用自已来定义自己的方法，称为递归定义。递归定义必须能使问题越来越简单，使问题向结束条件转化。,2020/10/13,华中科技大学计算机学院,51,递归算法解决三类问题,（1）数据的定义形式按递归定义。例如， n! =n*(n-1)! ; 0! =1。 f(n)=f(n-1)+f(n-2); f(1)=1; f(2)=1。 （2）数据的结构形式是按递归定义的。如 树的遍历,图的搜索等。 （3）问

38、题解法按递归算法实现。例如回溯法,2020/10/13,华中科技大学计算机学院,52,5.7.2 递归的执行过程,以求n!为例 long fac(int n) if (n=0|=1) return 1; else return (n*fac(n-1); ,2020/10/13,华中科技大学计算机学院,53,简化算法 不节省存储空间，运行效率也不高,2020/10/13,华中科技大学计算机学院,54,例5.12 编写一个递归函数计算Fibonacci数列的第n项(p152)。,/* Recursive fibonacci : Compute the n item */ long fibonacc

39、i (long n ) if ( n = = 1 | n = = 2) return 1; else return fibonacci(n-1)+fibonacci(n-2); ,2020/10/13,华中科技大学计算机学院,55,这种递归方式有损于运行效率,随着n值的增大，对fibonacci的调用次数将急剧增多。 例如， n=5， 需调用9次； n=10，需调用109次； n=20， 需调用13529次。 计算数列的下一个数时，花费的时间会越来越长。 编写一个主函数，在主函数中调用此函数计算Fibonacci数列。另外，可以调用time.h库中的函数time来计算出数列的20项、30项、40项等需要花费的时间，并输出此时间。,2020/10/13,华中科技大学计算机学院,56,5.7.4 汉诺塔问题的递归求解(p152),保证小(上),大(下),问题: 将A塔上n个盘