《程序设计技术》PPT课件.ppt

程序设计技术,程序设计语言和算法描述 C程序设计入门 C程序的控制结构 函数与程序结构 指针与函数 构造数据类型与指针 位运算 文件 C语言应用,第四章模块化程序设计基础,4.1 模块化基本概念 4.2 程序设计中实现模块化的方法 4.3 程序设计中标识符的作用域和生存期 4.4 递归方法的实现,4.1 模块化基本概念,模块化概念 模块化就是将一个大的复杂的程序根据“分而治之， 各个击破”的原则划分成为若干个模块，每个模块完 成一个相对独立的子功能，将这些模块按某种方式搭 接起来就构成了解决总体问题的程序。,4.1 模块化基本概念,对软件进行模块化可以得到如下好处： (1)软件具有模块化结构，所有软件开发工作可以如同搭积木 那样，把各个功能模块进行组合。模块相对独立，任一模块中 的错误不易扩散到其他模块中去，从而提高了软件开发的效率 和软件的可靠性。 (2)由于模块的功能是单一完整、相对独立的，所以每个模块都可以单独地设计它的算法，单独进行编写和调试。对于大型软件的开发，采用模块化结构，可以由多个程序设计人员参与进行集体性开发，从而加快软件开发速度、缩短软件开发周期。 (3)采用模块化程序设计技术开发的计算机软件投入运行后，在进行软件维护时，能够进行整个系统的调试，也可以进行单一模块的调试。对单一模块的调试和修改不会影响到其它模块的功能。当软件系统需要扩充时，只需增加相应功能模块，而不会涉及到整个软件系统。因此，采用模块化程序设计技术开发的计算机软件具有良好的维护性。,4.1 模块化基本概念,信息隐蔽和局部化概念 信息的隐蔽指的是在设计和确定模块时，应该使得模块内包含的所有信息（数据和执行代码）对于那些不需要这些信息的其他模块来说是不可访问的。也就是说，应该将模块与模块之间的关系尽可能限制在最小的范围之内。 信息的局部化指的是在划分和确定模块时，将那些关系密切的软件元素在物理位置上尽可能靠近。例如，在程序设计对数据元素的局部化以保证数据元素只能在程序的局部范围内使用。,4.2 程序设计中实现模块化的方法,#include“stdio.h“ void main() int a,b; int fac(int); for(a=1;a=5;a+) b=fac(a);printf(“%d!=%dn“,a,b); ,int fac(int c) int m,s; s=1; for(m=1;m=c;m+) s=s*m; return(s); ,4.2 程序设计中实现模块化的方法,一、函数的定义和声明 C语言函数定义的现代风格形式如下： 返回值类型说明符 函数名(形式参数表及其说明) 函数的操作对象（数据）定义和说明部分 函数的执行语句部分 ,4.2 程序设计中实现模块化的方法,类型名 函数名（类型名 形参1，类型名 形参2，） 说明语句； 执行语句； ,函数体：中的内容，包括说明语句和执行语句。 空函数：函数体为空的函数，例，便于扩充和细化程序。 注：(1)函数的定义是平行的，不允许在一个函数的内部再定义一个函数。 (2)函数值的类型为int或char时，可省略；不需返回函数值时，可用类型名void。 (3)多个形参以逗号分隔。 (4)不同函数中的局部变量可以同名。,4.2 程序设计中实现模块化的方法,从上面例子可以看出函数的定义内容为： 1 函数类型（既函数值类型） 2 函数名 3 形式参数的数目、类型 4 函数体内容,4.2 程序设计中实现模块化的方法,函数的返回值类型说明符规定了函数返回值的数据类型。例如，上面例子中double数据类型说明了函数fac被执行后可以得到一个double数据类型的数据。 C语言规定，如函数的返回值是整型（int）或者是字符型（char ）时，函数的返回值类型说明符可以缺省；如果所定义的函数没有（或不需要有）返回值，则函数的返回值类型为void（空类型）。,4.2 程序设计中实现模块化的方法,函数名 函数名是为所定义的函数取的名字，函数名是C语言中 合法的标识符。函数名后的圆括号是函数的标志，即 使函数没有形式参数也不能省略。除主函数main() 外，其余的函数名均可以由用户自己取名，但在同一 程序的各个源文件中的函数不能重名。,4.2 程序设计中实现模块化的方法,形式参数 函数定义时填入的参数我们称之为形式参数，简称形参，它们同函数内部的局部变量作用相同。形式参数写在函数名后面的一对圆括号内，它主要有两个作用： （1） 表示将从主调函数中接收的信息。函数的形式参数及其说明表是为函数接收外来数据提供变量名称以便在函数中使用，它规定了传递数据的类型和数目。如：int f(int a,float b)表示将从主调函数中接收一个int型和一个float型数据。形式参数之间应以调号相隔。无形式参数时，圆括号可以为空，也可以使用void声明它为空。如 int f（ ）与 int f（void）两者完全等价，但是圆括号不能省掉。 （2）在函数体中形式参数是可以被引用的，可以输入、输出、被赋以新值或参与运算。,4.2 程序设计中实现模块化的方法,函数体 函数体是由变量定义部分和C语句组成。在函数体中定义的变量 只有在执行该函数时才存在。函数体中也可以不定义变量，而 只有语句。也可以二者皆无。如： void nothing() 这是一个空函数，调用它不产生任何有效操作，但却是一个符 合C语言语法的合法函数。,4.2 程序设计中实现模块化的方法,函数执行的最后一个操作是返回。函数返回的基本格式有如下两种： 第一种即有返回值格式： return ； 第二种即无返回值格式：（函数必须定义为void类型，也可省略返回语句return） return;,对于第一种有返回值的语句其执行过程如下： 先计算出表达式的值； 若表达式的类型和函数类型不同时，将表达式的类型自动转换为函数类型，这种转换是强制性的，可能出现不保值的现象； 将计算出表达式的值传给主调函数，然后将程序控制权交给主调函数。此时主调函数接管控制权，继续执行主调函数后的语句。,对于第二种无返回值的语句其执行过程如下： 当被调函数执行到return；语句时，若无return语句，在执行完函数的最后一个语句之后，从概念上讲，是遇到了函数的结束符“ ”（当然这个花括号实际上并不会出现在目标码中，但我们可以这样理解），将程序控制权交回给主调函数，此时主调函数接管控制权，继续执行主调函数中调用该被调函数的后继语句。,有时在函数中设立了多个终止点以简化函数、提高效率。切记，一个函数可以有多个返回语句，但函数执行到任何一个return语句都会将程序控制权交给主调函数。此时主调函数接管控制权，继续执行主调函数后的语句。如下所示，函数在s1、s2相等时返回1，不相等时返回- 1。 int find_char (char s 1 ，char s 2 ) if ( s1 = s2 ) return 1； else return -1； ,4.2 程序设计中实现模块化的方法,函数的申明 在主调函数中，要对本函数将要调用的函数的特征事 先进行必要的声明。所谓“声明”是指向编译系统提供 必要的信息：函数名，函数的返回值的类型，函数参 数的个数、类型及排列次序，以便编译系统对函数的 调用进行检查。例如，检查形参与实参类型是否一 致，使用函数返回值的类型是否正确。,4.2 程序设计中实现模块化的方法,(1)如何申明 系统函数的申明 使用标准的库函数时，由于系统定义的标准库函数的说明都 集中在一些称为“头文件”的文本文件中，在程序中如果要调用 系统的标准库函数时，也要在程序的适当位置写上：#include 或#include “相应头文件”将调用有关库函数 时的必要信息包含的本源文件中来。例如： #include 或 #inlcude “stdio.h” 用户自定义函数的申明,4.2 程序设计中实现模块化的方法,自定义的函数其声明的一般格式为： 类型标识符 函数名（类型标识符 形参，类型标识符 形参，）； 这些信息就是函数定义中的第一行（称函数头）的内容，也称函数模型（或函数原型）。设有一函数的定义为： double funa(double a, int b, float c) 函数体 ,4.2 程序设计中实现模块化的方法,正确完整的函数声明应为： double funa(double a, int b, float c)；（注意末尾的分号） 这里的形参的名字并不重要，重要的是形参类型，故函数声明又可以不写形参名，即 double funa(double, int, float); 但不能只写形参名，不写形参的类型。如： double funa(a, b, c);（错） 一般也不能不写函数的类型，如： funa(double a, int b, float c)；（错） 只有函数返回值为I n t或char时，函数标识符才可以省掉。 形参的次序也不能写错，如： double funa( int b, float c, double a); （错）,4.2 程序设计中实现模块化的方法,例4-1 对被调函数的声明示例。 #include void main() long fac(int x); /*对函数fa c的声明*/ int n; printf(“Input the number n:“); scanf(“%d“, ,4.2 程序设计中实现模块化的方法,（2）何时不对被调函数进行声明： 被调函数的返回值数据类型是整型或字符型时，此时系统自动按整型进行隐式声明； 被调函数的定义出现在主调函数之前时，其原因是编译系统此时已经知道了被调函数的所有特征；,4.2 程序设计中实现模块化的方法,例4-2 对被调函数不必声明的示例。 #include long fac(int x) /*函数fac的定义出现在主调函数之前*/ long y; for(y=1;x0;-x) y*=x; return y; void main() int n; printf(“Input the number n:“); scanf(“%d“, ,4.2 程序设计中实现模块化的方法,（3）申明的位置 在所有的函数之前； 在所有函数的外部； 在调用函数的内部的说明部分；,4.2 程序设计中实现模块化的方法,函数调用时的参数传递方式 传值调用 传引用（传地址值）调用 传值调用方式 传值方式是一种数据复制的方式，在这种方式下，实际参数通过复制的方式传递给形式参数，因此被传递的数据在被调函数中无论怎样变化，都不会影响该数据在主调函数中的值。,函数调用时的步骤： 1、建立形式参数和局部变量 2、实际参数拷贝到对应形式参数 3、控制转到被调函数执行 4、退出被调函数时撤消其形式参数和局部变量,二、函数的调用和数据传递,4.2 程序设计中实现模块化的方法,例4-3 函数调用时值参数传递示例。 #include int change(int x,int y); void main() int m=10,n=20; printf(“m=%d, n=%dn“,m,n); printf(“%dn“,change(m,n); printf(“m=%d, n=%dn“,m,n); int change(int x,int y) x+,y+; printf(“x=%d,y=%dn”,x,y); return x+y; 程序运行的结果为： m=10, n=20 32 m=10, n=20 /*请仔细分析并回答为什么输出这个结果*/,4.2 程序设计中实现模块化的方法,调用时,图4.2,4.2 程序设计中实现模块化的方法,Question? 在语言中，可以用几种方式调用函数：,（1）函数表达式。函数作为表达式的一项，出现在表达式中，以函数返回值参与表达式的运算。这种方式要求函数是有返回值的。 （2）函数语句。C语言中的函数可以只进行某些操作而不返回函数值，这时的函数调用可作为一条独立的语句。 （3）函数实参。函数作为另一个函数调用的实际参数出现。这种情况是把该函数的返回值作为实参进行传送，因此要求该函数必须是有返回值的。,4.2 程序设计中实现模块化的方法,函数的调用应注意的几点： （1）调用函数时，函数名称必须与具有该功能的自定义函数名称完全一致。 （2）实参在类型上按顺序与形参，必须一一对应和匹配。如果类型不匹配，C编译程序将按赋值兼容的规则进行转换。如果实参和形参的类型不赋值兼容，通常并不给出出错信息，且程序仍然继续执行，只是得不到正确的结果。 （3）如果实参表中包括多个参数，对实参的求值顺序随系统而异。有的系统按自左向右顺序求实参的值，有的系统则相反。Turbo C和MS C是按自右向左的顺序进行的 。,4.2 程序设计中实现模块化的方法,例4-4 编程求出所有的两位的“绝对素数”，所谓“绝对素数”是指一个素数，当它的数字位置对换后仍然是素数。,解题思想：对于任意两位数n，首先调用函数prime判 断n是否是素数，如果n是素数，则调用函数reverse求 数字位置对换后的数，函数prime判断其是否是素 数，如果reverse（n）也是素数，n是“绝对素数”，输 出n。 函数prime（）是一个判断素数的通用函数，返回值 为0时表示非素数，返回值为1时表示为素数。其算法 描述如下：,4.2 程序设计中实现模块化的方法,算法：prime(a) /*表示prime从主调函数接收a */ 算法开始 定义标志量b，循环变量k； If(a=2) then 返回值 1； else if(a能被2整除) then 返回值 0； Else b=1, k=3 while（k=a的平方根 并且b=1） if（a能被k整除）then,b=0 k=k+2 返回b； 算法结束,4.2 程序设计中实现模块化的方法,reverse(int a)函数是求a各位数字前后位置对换后的整数的通用函数,如12345各位数字前后位置对换后转换为54321,其本思路:采用a%10求出a的个位,然后a=a/10,重复前面的操作,直到a=0。同时注意：如12345转换为54321,而54321=（5*10+4）*10+3）*10+2）*10+1。 算法描述如下：,算法：reverse（a）算法开始 定义 s=0； while（a0） s= s+a%10,a= a/10 if(a0) then s= s*10 返回s； 算法结束,4.2 程序设计中实现模块化的方法,#include #include void main( ) int reverse(int a); int prime(int a); int n; for(n=11;n=99;n+) if(prime(n) ,4.2 程序设计中实现模块化的方法,int prime(int a) int b,k; if(a%2=0) return(0); else b=1; k=3; while(k=sqrt(1.0*a) ,4.2 程序设计中实现模块化的方法,int reverse(int a) int s=0; while(a!=0) s=s+a%10; a=a/10; if(a) s=s*10; return s; ,4.2 程序设计中实现模块化的方法,C语言规定，在C程序中所有的函数都是平行的，即在C程序中函数不能嵌套定义。但C语言允许函数嵌套调用，即一个函数在被调用的过程中又调用了另外的一个函数。一个两层嵌套函数调用的过程如图所示：,图中主函数在执行的过程中调用了函数f1，在函数f1执行的过程中又调用了函数f2；当执行完函数f2后，程序控制流程转回函数f1对f2调用语句的后面第一条可执行C语句继续执行；当函数f1执行完后，程序控制流程转回主函数继续执行。,三、函数的嵌套调用,例4-5 问题分析：,4.2 程序设计中实现模块化的方法,例4.6 计算s=1k+2k+3k+N k 程序设计思路：可以把问题分解为两个模块：求幂次 方模块和求和模块，在求和模块中要包含求幂模块 f1()函数的参数为n和k，其返回值是n的k次方 f2()函数的参数为n和k,返回值是幂次方的累加和。,4.2 程序设计中实现模块化的方法,#include long f1(int n,int k); long power=n; int i; for(i=1;ik;i+) power *= n; return power; long f2(int n,int k) long sum=0; int i; for(i=1;i=n;i+) sum += f1(i, k); return sum; ,void main() int n,k; scanf(“%d,%d”, ,4.2 程序设计中实现模块化的方法,递归方法的实现 用“辗转除法”求最大公约数时使用了递推方法，其算 法和C函数可以描述为： m除以n得到余数r(0rn)。 若r=0则算法结束，n为最大公约数。否则做。 mn，nr，转回到。,4.2 程序设计中实现模块化的方法,函数的递归调用 一个函数直接地或间接地自己调用自己，称为函数的 递归调用。递归调用可以看成是一种特殊的嵌套调 用，它与一般的嵌套调用相比较有以下特点： （1）每次嵌套调用的函数都是该函数本身； （2）嵌套调用不会无限制进行下去，即调用总会在某 种条件下结束； （3）每次调用时，本次的函数体并没有执行完毕。故 必须依靠系统提供一个特殊部件（堆栈）存放未完成 的操作，以保证当递归调用结束回溯时不会丢失任何 应该执行而没有执行操作；,4.2 程序设计中实现模块化的方法,一个问题要用递归的方法解决，必须满足3个条 件： （1）要解决的问题可以转换为一个新的问题，而这 个新的问题的解法与原来问题的解法相同，只是处 理的对象有规律的变化，一般是递减。 （2）可以应用这个转换过程使问题得到解决 （3）要有一个明确的递归结束条件。,4.2 程序设计中实现模块化的方法,例 使用递归调的方法反向输出字符串。 #include void main() void reverse(); reverse(); void reverse() char ch; ch=getchar(); if(ch=#) putchar(c h); else reverse(); /*递归调用*/ putchar(c h); ,4.2 程序设计中实现模块化的方法,4.2 程序设计中实现模块化的方法,ch=#,ch=c,ch=b,ch=a,main(),输出a,输出b,输出c,输出#,（颠倒字符串）,4.2 程序设计中实现模块化的方法,例 求两个正整数的最大公约数。 分别用迭代和递归的方法实现 递归的条件：,4.2 程序设计中实现模块化的方法,/*迭代方式，使用循环结构实现*/ #include void main() int GCD(int m,int n); int num1,num2; printf(“Input num1 ,4.2 程序设计中实现模块化的方法,/*递归方式，使用分支结构实现。主函数与上面程序相同*/ #include void main() int GCD(int m,int n); int num1,num2; printf(“Input num1 ,4.2 程序设计中实现模块化的方法,例12 求一个正整数的各位数字之和 分别用迭代和递归的方法实现 递归的条件：,4.2 程序设计中实现模块化的方法,/*迭代方式，使用循环结构实现*/ #include void main() int num_sum(int n); int num; printf(“Input the num:“); scanf(“%d“, ,4.2 程序设计中实现模块化的方法,/*递归方式，使用分支结构实现。主函数与上面程序相同*/ int num_sum(int n) if(n10) return n; else return n%10+num_sum(n/10); ,4.2 程序设计中实现模块化的方法,例15 求斐波纳契数列中第n个数。,4.2 程序设计中实现模块化的方法,/*迭代方式，使用循环结构实现*/ #include void main() long fib(int n); int n; printf(“Input the n:“); scanf(“%d“, ,4.2 程序设计中实现模块化的方法,long fib(int n) if(n=0|n=1) return n; else return fib(n-1)+fib(n-2); ,4.2 程序设计中实现模块化的方法,例16汉诺塔(Tower of Hanoi)问题。,4.2 程序设计中实现模块化的方法,分析（1）考虑A座上有n个盘子的一般情况。将n个盘子从A座移到C座算作一个大问题，可以分解为3个小问题： 第一步：将A座上面的n-1个盘子借助C座移到B座上。这是整体粗略的考虑，不管实现的细节。只有这样，C座上空了，A座的第n个盘子才能直接移到C上。 第二步：将A座上的第n个盘子移到C上。 第三步：再将B座上的n-1个盘子借助A座移到C座上。 （2）对大问题和第1步、第3步的小问题作对比，它们都是把若干个盘子从一个座借助一个座移到另一个座上，只是源座、借助座、目标座不同。符合递归的条件1：要解决的问题可以转换为一个新的问题，而这个新的问题的解法和原来问题相同。 （3）递归函数可以描述为： hanoi(盘子个数，源座，借助座，目标座） 大问题描述为：hanoi(n,left,middle,right),4.2 程序设计中实现模块化的方法,第一个问题：hanoi(n-1,left,right,middle) 第一个问题：hanoi(n-1,middle,left,right) (4)第2步可以编写一个移动函数： move(源座，目标座）,4.3 程序设计中标识符的作用域和生存期,C程序的一般结构如图,4.3 程序设计中标识符的作用域和生存期,在一个完整的C程序中，函数将程序划分为若干个相 对独立的区域。对于在不同的区域范畴之内声明或定 义的标识符（特别是变量）必须要考虑以下几个方面 的问题： 标识符（特别是变量）的作用范围如何确定； 标识符（特别是变量）的存在期间如何确定； 怎样使用或限制在同一程序的其它源程序文件中定义的标识符（变量）；,4.3 程序设计中标识符的作用域和生存期,对于一个标识符的性质可以从两方面进行分析，一是其能够起作用的空间范围，即标识符的作用域；二是其值存在的时间范围，即标识符的生存期。,4.3 程序设计中标识符的作用域和生存期,在C语言中，变量定义的完整形式如下： 存储类别符 变量表; 数据类型符说明标识符（变量）的取值范围和可以对 该变量进行的操作；存储类别符用于指定数据对象在 系统内存中存放的方法。变量的存储类别有四种，它 们是：自动型（auto）、寄存器型（register）、静态 型（static）和外部参照型（extern）。,标识符的作用域,4.3 程序设计中标识符的作用域和生存期,标识符的作用域 从变量的作用域概念上可以将变量分为“全局变量”和“局部变量”两类。 C语言使用存储类别关键字extern和auto来表示变量的作用域属性。 全局变量是指定义在所有函数外面的变量，其定义的形式如下： extern 变量表;,4.3 程序设计中标识符的作用域和生存期,例 全局变量的作用域示例。 #include int i; void main() void incre(); i+; incre(); printf(“i=%dn“,i); /*程序运行结果为：i=2，为什么？*/ void incre() i+; ,4.3 程序设计中标识符的作用域和生存期,局部变量是定义在函数内部的变量，局部变量的作用域被限定在它们所定义的范围之内，在C函数中定义自动变量的地方有三个： 函数形式参数表部分； 函数体内部； 复合语句内部；局部变量的存储类别符是auto，所以在C语言中局部变量又称为自动变量。,4.3 程序设计中标识符的作用域和生存期,例 局部变量的作用域示例。 #include void main() void incre(); int i=10; i+; incre(); incre(); printf(“i=%dn“,i); /*程序运行结果为：i=11，为什么？*/ void incre() int i=20; i+; printf(“i=%dn“,i); /*函数两次别调用时的运行结果为：i=21，为什么？*/ ,4.3 程序设计中标识符的作用域和生存期,4.3 程序设计中标识符的作用域和生存期,C语言中规定按“定义就近原则”来确定使用的变量，具体说就是如下两条原则： 在函数中如果定义有与全局变量同名的局部变量，则当程序的控制流程进入到函数的作用范围时，使用在函数中定义的局部同名变量； 在程序的一个更小局部范围（复合语句）中如果定义有与较大范围（函数局部或全局）变量同名的变量，则当程序的控制流程进入到这个小的局部范围时，