数据结构 函数.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第七章 函数,第七章 函数,概述,函数的定义,函数的返回值,函数的调用,、,函数的嵌套与递归调用,函数参数及其传递方式,变量的存储属性,数组作为函数参数,7.1,概述,模块化程序设计,基本思想：将一个大的程序按功能分割成一些小模块,特点：,各模块相对独立、功能单一、结构清晰、接口简单,控制了程序设计的复杂性,提高元件的可靠性,缩短开发周期,避免程序开发的重复劳动,易于维护和功能扩充,开发方法,:,自上向下,逐步分解，分而治之,从用户角度,标准函数（库函数）：由系统提供,用户自定义函数,从函数形式,无参函数,有参函数,使用,库函数,应注意：,1,、函数功能,2,、函数参数的数目和顺序，及各参数意义和类型,3,、函数返回值意义和类型,4,、需要使用的包含文件,函数分类,一般格式,合法标识符,函数返回值类型,缺省,int,型,无返回值,void,函数体,函数类型 函数名,（,形参类型说明表,）,说明部分,语句部分,现代风格,:,例 有参函数（现代风格）,int,max,(int,x,int,y,),int,z;,z=xy?x:y;,return(z);,例 有参函数（现代风格）,int,max(,int,x,y,),int,z;,z=xy?x:y;,return(z);,例,空函数,dummy(),函数体为空,例 无参函数,printstar,(),printf,(“*n”);,或,printstar(,void,),printf,(“*n”);,7.2,函数的定义,函数类型 函数名（形参表）,形参类型说明,说明部分,语句部分,传统风格,:,例 有参函数（传统风格）,int,max(,x,y,),int,x,y;,int,z;,z=xy?x:y;,return(z);,函数传统风格和例子,返回语句,形式：,return(,表达式,),；,或,return,表达式,;,或,return;,功能：使程序控制从被调用函数返回到调用函数中，同时把返值带给调用函数,说明：,函数中可有多个,return,语句,若无,return,语句，遇,时，自动返回调用函数,若函数类型与,return,语句中表达式值的类型不一致，按前者为准，自动转换,-,函数调用转换,void,型函数,例 无返回值函数,void,swap(int,x,int,y),int,temp;,temp=x;,x=y;,y=temp;,7.3,函数的返回值,调用形式,函数名,(,实参表,);,说明：,实参与形参,个数相等,，,类型一致,，,按顺序一一对应,实参表求值顺序，因系统而定（,Turbo C,自右向左,）,6.4,函数的调用,函数语句：,例,printstar,();,printf(“Hello,World!n,”);,函数表达式：,例,m=max(a,b)*2;,函数参数：,例,printf(“%d”,max(a,b,);,m=max(a,max(b,c);,函数的调用方式,对被调用函数要求：,必须是,已存在,的函数,库函数,:,#include,用户自定义函数,:,函数类型说明,函数说明,一般形式：,函数类型 函数名,(,形参类型,形参名,.);,或,函数类型 函数名,();,作用：告诉编译系统函数类型、参数个数及类型，以便检验,函数定义,与,函数说明,不同,函数说明位置：,程序的数据说明部分（函数内或外）,下列情况下，可不作函数说明,若函数返值是,char,或,int,型,，系统自动按,int,型处理,被调用函数定义出现在主调函数之前,有些系统,(,如,Borland C+),要求函数说明指出函数返值类型和形参类型，并且对,void,和,int,型函数也要进行函数说明,函数说明,6.4.1,函数的嵌套调用,嵌套调用,C,规定：,函数定义不可嵌套,，但,可以嵌套调用,函数,main(),调用函数,a,结束,a,函数,b,函数,调用函数,b,例,1,求三个数中最大数和最小数的差值,思考：,max,函数,int,max,（,int,x,int,y,int,z,）,功能：求三个数中的最大值,min,函数,int,max,（,int,x,int,y,int,）,功能：求三个数中的最小值,dif,函数,功能：求差值,方式：,max(a,b,c)-min(a,b,c,),（即分别调用,max,函数和,min,函数，求其差值）,程序设计：,int,max(int,x,int,y,int,z),int,r;,r=x,y?x:y,;,return(r,z?r:z,);,int,min(int,x,int,y,int,z),int,r;,r=x,y?x:y,;,return(r,z?r:z,);,int,dif(int,x,int,y,int,z),return,max(x,y,z)-min(x,y,z,);,main(),int,a,b,c,d,;,scanf(%d%d%d,&a,&b,&c,);,d=,dif(a,b,c,);,printf(Max,-Min=%,dn,d,);,求立方函数,long,cn,（,int,n,）,功能：求,n,的立方值,注意：由于立方值比较大，定义为,long,类型,n*n*n=,sq(n,),*n,例,2,：给定一个数，求其平方及立方,思路：,求平方函数,long sq,（,int,n,）,功能：求,n,的平方值,注意：由于平方值比较大，定义为,long,类型,程序设计：,#include,long,sq(int,n),long k;,k=n*n;,return k;,long,cn(int,n),long k;,k=,sq(n,)*n;,return k;,main(),int,n;,scanf(“%d”,&n,);,printf(“sq(%d,)=%,ld,cn(%d,)=%ld,n”,n,sq(n),n,cn(n,);,例,3,：求,1,k,+2,k,+3,k,+,n,k,思路：,求和函数,long f2,（,int,n,，,int,k,）,功能：求,1,k,+2,k,+3,k,+,n,k,注意：由于结果可能比较大，定义为,long,类型,1,k,+2,k,+3,k,+,n,k,=,for(i,=1;i=,n;i,+),sum+=,f1(i,k);,求,i,k,函数,long f1,（,int,i,int,k,）,功能：求,i,的,k,次方（,i,k,）,注意：由于结果可能比较大，定义为,long,类型,程序设计,：,#include,long f1(int,i,int,k),long,mul,=1;,int,j;,for(j,=1;j=,k;j,+),mul,*=i;,return,mul,;,long f2(int,n,int,k),long sum=0;,int,j;,for(j,=1;j=,n;j,+),sum+=f1(j,k);,return sum;,void main(),int,n,k,;,scanf(%d,%d,&n,&k,);,printf(sum,=%ldn,f2(n,k);,例,4,：求,20,以内全部素数的积与全部素数的和的商,思路：,int,isprime,（,int,n),功能：判断,n,是否为素数,若是返回,1,，不是返回,0,求素数和,long sum,（,int,n,）,功能：求,n,以内素数的和,for(i,=2;i=,n;i,+),if(,isprime(i,),)s+=i;,求素数积,long,mul,（,int,n,）,功能：求,n,以内素数的积,for(i,=2;i=,n;i,+),if(,isprime(i,),)m*=i;,float div,（,int,n),功能：求,n,以内素数的积与,n,以内素数的和的商,d=,mul(n,),*1.0/,sum(n,),;程序设计：,#include,int,isprime(int,n),int,k;,for(k,=2;k,n;k,+),if(n%k,=0)return 0;,return 1;,long,sum(int,n),long s=0;int k;,for(k,=2;k=,n;k,+),if(isprime(k,)s+=k;,return s;,long,mul(int,n),long m=1;int k;,for(k,=2;k=,n;k,+),if(isprime(k,)m*=k;,return m;,float,div(int,n),float d;,d=,mul(n,)*1.0/sum(n);return d;,void main(),printf(%.2f,div(20);,思考题一：,编写一程序计算任一输入的整数的各位数之和,课后练习：,编写一个函数，,输入,n,为偶数时，调用函数求,1/2+1/4+.+1/n,输入,n,为奇数时，调用函数,1/1+1/3+.+1/n,6.4.2,函数的递归调用,递归调用,函数直接或间接的调用自身叫函数的递归调用,int,f(int,x),int,y,z;,z=f(y);,.,return(2*z);,直接调用,int,f1(int x),int,y,z;,z=f2(y);,.,return(2*z);,间接调用,int,f2(int t),int,a,c;,c=f1(a);,.,return(3+c);,例 求,n,的阶乘,#include,int,fac(int,n),int,f;,if(n,0),printf(n,0,data error!);,else,if(n,=0|n=1)f=1;,else,f=fac(n-1)*n;,return(f,);,main(),int,n,y;,printf(Input,a integer number:);,scanf(%d,&n,);,y=,fac(n,);,printf(%d,!=%15d,n,y);,例题：,hanoi,塔问题,void move(char x,char y),printf,(“%,c,%cn”,x,y,);,void,hanoi,(,int,n,char one,char two,char three),if(n=1)move(one,three);,else,hanoi,(n-1,one,three,two),move,(one,three);,hanoi,(n-1,two,one,three);,main(),int,m;,scanf(“%d”,&m,);,printf(“The,step to moving%3d,disces:n”,m,);,hanoi,(m,A,BC,);,课后思考：有,5,个人坐在一起，问第五个人多少岁？他说比第,4,个人大2,岁。问第,4,个人岁数，他说比第,3,个人大,2,岁。问第三个人，又说比第,2,人大两岁。问第,2,个人，说比第一个人大两岁。最后问第一个人，他说是,10,岁。请问第五个人多大？,int,age(n,),int,n;,int,c;,if(n,=1)c=10;,else c=,age,(n-1)+2;,return(c,);,main(),printf(%d,age,(5);,思考题：,题目：利用递归调用方式，将所输入的,5,个字符，以相反顺序打印出来。,#include,stdio.h,main(),int,i=5;,void,palin(int,n);,palin(i,);,printf(n,);,void,palin(int,n),char next;,if(n,y?x:y;,return(z);,例 比较两个数并输出大者,main(),int,a,b,c;,scanf(%d,%d,&a,&b,);,c=,max(a,b);,printf(Max,is%d,c);,max(,int,x,int,y,),int,z;,z=xy?x:y;,return(z);,形参,实参,6.5,函数参数及其传递方式,说明：,实参必须有确定的值,形参必须指定类型,形参与实参,类型一致，个数相同,若形参与实参类型不一致，自动按形参类型转换,函数调用转换,形参在函数被调用前不占内存,;,函数调用时为形参分配内存；调用结束，内存释放,形参与实参,形式参数：定义函数时函数名后面括号中的变量名,实际参数：调用函数时函数名后面括号中的表达式,6.5,函数参数及其传递方式,值传递,方式,方式：函数调用时,为形参分配单元,并将实参的值,复制,到形参中；调用结束，形参单元被释放，实参单元仍保留并维持原值,特点：,形参与实参占用,不同,的内存单元,单向,传递,参数传递方式,7,11,x:,y:,调用前：,调用结束：,7,11,x:,y:,/*ch7_2.c*/,#include,main(),int,x=7,y=11;,printf(x,=%,d,ty,=%dn,x,y);,printf(swapped:n,);,swap(x,y);,printf(x,=%,d,ty,=%dn,x,y);,swap(,int,a,int,b,),int,temp;,temp=a;a=b;b=temp;,调用：,7,11,a:,b:,7,11,x:,y:,swap:,7,11,x:,y:,11,7,a:,b:,temp,例 交换两个数,方式：函数调用时，将数据的,存储地址,作为参数传递给形参,特点：,形参与实参占用,同样,的存储单元,“双向”,传递,实参和形参必须是,地址,常量或变量,函数的地址传递,/*ch9_3.c*/,swap(p1,p2),int,*p1,*p2;,int,p;,p=*p1;,*p1=*p2;,*p2=p;,main(),int,a,b;,scanf(%d,%d,&a,&b,);,printf(“a,=%d,b=%dn”,a,b);,printf(“swapped:n,”);,swap(,printf(”a,=%d,b=%dn,a,b);,例 交换两个数,a,5,9,b,调前：,a,5,9,b,调swap：,p1,&a,&b,p2,a,9,5,b,交换：,p1,&a,&b,p2,a,9,5,b,返回：,例子图解,#include,long,sum(int,a,int,b);,long,factorial(int,n);,main(),int,n1,n2;,long a;scanf(%d,%d,a=,sum(n1,n2);,printf(a,=%,1d,a);,long,sum(,int,a,int,b,),long c1,c2;,c1=,factorial(a);,c2=,factorial(b);,return(c1+c2);,long,factorial(int,n),long,rtn,=1;,int,i;,for(i=1;ibi,ai=bi,aik,认为数组,ab,若,nk,认为数组,ab,若,n=k,认为数组,a=b,#include,main(),int,a10,b10,i,n=0,m=0,k=0;,printf(Enter,array a:n)for(i=0;i10;i+),scanf(%d,&ai,);,printf(Enter,array b:n);,for(i=0;i10;i+),scanf(%d,&bi,);,for(i=0;iy)flag=1;,else if(xy)flag=-1;,else flag=0;,return(flag);,地址传递,在主调函数与被调函数分别定义数组,且类型应一致,形参数组大小,(,多维数组第一维,),可不指定,形参数组名是,地址变量,数组名作函数参数,#include,float,average(int,stu10,int,n);,void main(),int,score10,i;,float,av,;,printf(Input,10 scores,：,n);,for(i=0;i10;i+),scanf(%d,av,=,average(,score,10);,printf(Average,is,：,%.2f,av,);,float,average(,int,stu10,int,n),int,i;,float,av,total,=0;,for(i=0;in;i+),total+=,stui,;,av,=total/n;,return,av,;,实参用数组名,形参用数组定义,int,stu,.,.,2,1,0,9,score,56,23,12,.,.,88,stu,例 求学生的平均成绩,1,2,a,调用前,1,2,a,x,调用,2,1,a,x,交换,2,1,a,返回,#include,void,swap2,(int x,),int,z;,z=x0;x0=x1;x1=z;,main(),int,a2=1,2;,swap2(,a,);,printf(a0=%dna1=%dn,a0,a1);,地址传递,例 数组元素与 数组名 作函数参数比较,void,sort(,int,array,int,n),int,i,j,k,t;,for(i=0;in-1;i+),k=i;,for(j=i+1;jn;j+),if(arrayjarrayk)k=j;,if(k!=i),t=arrayi;,arrayi=arrayk;,arrayk=t;,main(),int,a10,i;,for(i=0;i10;i+),scanf(%d,&ai,);,sort(a,10);,for(i=0;i10;i+),printf(%d,ai);,printf(n,);,0,1,2,3,4,5,6,7,8,9,a,49,68,57,32,9,99,27,13,76,88,array,k,j,j,j,k,j,k,j,j,j,j,j,9,49,i=0,例 数组排序,-,简单选择排序,void,sort(,int,array,int,n),int,i,j,k,t;,for(i=0;in-1;i+),k=ifor(j=i+1;jn;j+),if(arrayjarrayk)k=j;,if(k!=i),t=arrayi;,arrayi=arrayk;,arrayk=t;,main(),int,a10,i;,for(i=0;i10;i+),scanf(%d,&ai,);,sort(a,10);,for(i=0;i10;i+),printf(%d,ai);,printf(n,);,k,j,j,k,j,k,j,j,j,j,j,0,1,2,3,4,5,6,7,8,9,a,49,68,57,32,9,99,27,13,76,88,array,9,49,k,k,13,68,i=1,例 数组排序,-,简单选择排序（,1,）,0,1,2,3,4,5,6,7,8,9,a,9,13,27,32,49,57,68,76,88,99,array,i=8,void,sort(,int,array,int,n),int,i,j,k,t;,for(i=0;in-1;i+),k=i;,for(j=i+1;jn;j+),if(arrayjarrayk)k=j;,if(k!=i),t=arrayi;,arrayi=arrayk;,arrayk=t;,main(),int,a10,i;,for(i=0;i10;i+),scanf(%d,&ai,);,sort(a,10);,for(i=0;i10;i+),printf(%d,ai);,printf(n,);,例 数组排序,-,简单选择排序（,2,）,概述,变量是对程序中数据的存储空间的抽象,内存,.,main(),int,a;,a=10;,printf(“%d”,a,);,编译或函数调用时为其分配内存单元,10,2000,2001,程序中使用变量名对内存操作,6.8,变量的存储属性,变量的属性,数据类型：变量所持有的数据的性质（,操作属性,）,存储属性,存储器类型：寄存器、静态存储区、动态存储区,生存期,：变量在某一时刻存在,-,静态变量与动态变量,作用域,：变量在某区域内有效,-,局部变量与全局变量,变量的存储类型,auto -,自动型,register-,寄存器型,static -,静态型,extern -,外部型,变量定义格式,:,存储类型,数据类型 变量表,;,概述,变量是对程序中数据的存储空间的抽象,如,:,int,sum;,auto,int,a,b,c;,register,int,i;,static,float x,y;,6.8,变量的存储属性,局部变量,-,内部变量,定义：在,函数内定义,，,只在本函数内有效,说明：,main,中定义的变量只在,main,中有效,不同函数中同名变量，占不同内存单元,形参属于局部变量,可定义在复合语句中有效的变量,局部变量可用存储类型,：,auto register static,（,默认为,auto,float f1(int a),int,b,c;,.,char f2(int,x,int,y),int,i,j;,main(),int,m,n;,.,a,b,c,有效,x,y,i,j,有效,m,n,有效,例 不同函数中同名变量,main(),int,a,b;,a=3;,b=4;,printf(main:a,=%d,b=%dn,a,b);,sub();,printf(main:a,=%d,b=%dn,a,b);,sub(),int,a,b;,a=6;,b=7;,printf(sub:a,=%d,b=%dn,a,b);,运行结果：,5 4 3 2 1,例 不同函数中同名变量,main(),int,a,b;,a=3;,b=4;,printf(main:a,=%d,b=%dn,a,b);,sub();,printf(main:a,=%d,b=%dn,a,b);,sub(),int,a,b;,a=6;,b=7;,printf(sub:a,=%d,b=%dn,a,b);,运行结果：,main:a=3,b=4,sub:a=6,b=7,main:a=3,b=4,局部变量与全局变量,-,外部变量,定义：在,函数外定义,，可为,本文件所有函数共用,有效范围：从,定义变量的位置开始,到本源文件结束，及有,extern,说明,的其它源文件,应尽量少使用全局变量，因为：,全局变量在程序全部执行过程中占用存储单元,降低了函数的通用性、可靠性，可移植性,降低程序清晰性，容易出错,定义,说明,次数：只能,1,次 可说明多次,位置：所有函数之外 函数内或函数外,分配内存：分配内存,可初始化 不分配内存,不可初始化,外部变量说明：,extern,数据类型 变量表；,外部变量定义与外部变量说明不同,若外部变量与局部变量同名，则外部变量被屏蔽,外部变量可用存储类型,：缺省,或,static,全局变量,float max,min;,float average(float array,int,n),int,i;float sum=array0;,max=min=array0;,for(i=1;imax),max,=arrayi;,else if(arrayiy?x:y;,return(z);,main(),extern,int,a,b;,printf(max,=%d,max(a,b);,int,a=13,b=-8;,运行结果：,max=13,extern,int,a,b;,int,max(),int,z;,z=,ab?a:b;,return(z);,main(),printf(max,=%d,max();,int,a=13,b=-8;,例 外部变量定义与说明,/*ch7_17.c*/,int,a=3,b=5;,max(,int,a,int,b,),int,c;,c=ab?a:b;,return(c);,main(),int,a=8;,printf(max,=%d,max(a,b);,运行结果：,max=8,例 外部变量与局部变量,存储方式,静态存储：程序运行期间分配固定存储空间,动态存储：程序运行期间根据需要动态分配存储空间,内存用户区,程序区,静态存储区,动态存储区,全局变量、局部静态变量,形参变量,局部动态变量（,auto register),函数调用现场保护和返回地址等,生存期,静态变量,:,从程序开始执行到程序结束,动态变量,:,从包含该变量定义的函数开始执行至函数执行结束,动态变量与静态变量,静态,动态,存储方式,程序整个运行期间,函数调用开始至结束,生存期,编译时赋初值，,只赋一次,每次函数调用时,赋初值,自动赋初值,0,或空字符,不确定,未赋初值,静态存储区,动态区,存储区,寄存器,局部变量,外部变量,作用域,定义变量的函数或复合语句内,本文件,其它文件,局部变量默认为,auto,型,register,型变量个数受限,且不能为,long,double,float,型,局部,static,变量具有,全局寿命,和,局部可见性,局部,static,变量具有,可继承性,extern,不是变量定义,可扩展外部变量作用域,register,局部,static,auto,外部,static,外部,存储类别,变量存储类型,#include,int,i=1;,main(),static,int,a;,register,int,b=-10;,int,c=0;,printf(-MAIN-n,);,printf(i:%d,a:%d ,b:%d c:%dn,i,a,b,c);,c=c+8;,other();,printf(-MAIN-n,);,printf(i:%d,a:%d ,b:%d c:%dn,i,a,b,c);,i=i+10;,other();,other(),static,int,a=2;,static,int,b;,int,c=10;,a=a+2;i=i+32;c=c+5;,printf(-OTHER-n,);,printf(i:%d,a:%d ,b:%d c:dn,i,a,b,c);,b=a;,-Main-,i:1 a:0 b:-10 c:0,-Other-,i:33 a:4 b:0 c:15,-Main-,i:33 a:0 b:-10 c:8,-Other-,i:75 a:6 b:4 c:15,全局,i,1,main:a,0,b:-10,register,main:c,0,静态,存储区,动态,存储区,other:a,2,other:b,0,other:c,10,8,4,33,15,4,43,other:c,10,6,75,15,6,例 变量的寿命与可见性,以下程序的运行结果是,_,main(),int,k=4,m=3,p;,p=,func(k,m,);,printf(%d,p,);,p=,func(k,m,);,printf(%dn,p,);,func(a,b,),int,a,b,;,static,int,m=0,i=2;,i+=m+1;,m=,i+a+b,;,return(m,);,4,以下程序的运行结果是,_,static,int,x=500;,main(),auto,int,x=300;,printf(1.x=%,dn,x,);,f();,ff();,printf(4,x=%,dn,x,);,f(),x+=100;,printf(2.x=%,dn,x,);,ff(),int,x=10;,printf(3.x=%,dn,x,);,5,以下程序的运行结果是,_,main(),int,i;,for(i=1;i=5;i+),f(i,);,f(j,),int,j;,static,int,a=100;,auto,int,k=1;,+k;,printf(%d+%d+%d,=%,dn,a,k,j,a+k+j,);,a+=10;,求！的值,main(),int,j,s;,_;,for(j,=1;j=_;j+),s+=_;,printf(“sum,=%,dn”,s,);,fac(a,),int,a;,_;,b*=a;,ruturn,b,;,