第6章 函数与指针.

Presentation on theme: "第6章 函数与指针."— Presentation transcript:

1 第6章 函数与指针

2 函数与指针 函数是模块化设计的一种实现。对于一个大的复杂的问题，如果不采用模块化设计的方法进行设计，那么进行维护和修改操作会变得非常困难。比如做软件。一个大型的软件很少只由一个人完成，通常将一个问题分解成为若干个小问题，如果问题还不够小，还可以再细分。当所有的小问题都解决之后，软件设计的系统工程师完成各部分的组装工作。 实际上，我们的日常生活中到处都可以看到模块化设计的实例：组装活动房的各个组件、食堂工作的人员分配、工厂中各个加工部门的设立等…… 在程序设计中，程序的模块化设计的实现是通过函数来实现的。每个函数解决一个子问题，而主函数去调用这些函数。（这里主函数的作用类似软件设计的系统工程师）。函数分为库函数和自定义的函数。

3 函数与指针 6.1 函数的定义与调用 6.2 函数的参数传递 6.3 指针作为函数参数

4 6.1函数的定义和调用 1.编写一个名为Hello的函数，该函数的目的是输出“Hello，world!”。
2.编写一个名为findAbs的函数，接收一个传递给它的单精度数，并且返回它的绝对值。 3.编写一个名为powfun的函数，自乘一个传递给它的整数到一个正整数幂和显示结果。

5 1 函数的定义 任何函数在调用之前都要先定义。函数定义的基本模式： { 函数体 } 返值类型 函数名（函数参数表列）
返值类型 函数名（函数参数表列） { 函数体 } 形式参数，其值由主调函数传送

6 在函数定义过程中，要注意 （1）函数定义中，返回值的类型可以是空类型void，可以是其他任意定义过的类型（整型(int),实型（float,double），字符型（char）,结构体型（struct ……）等，也可以是指针。 （2）函数中可以有参数，也可以没有参数。参数可以是1个，也可以是多个，具体由函数要解决的问题而定。 （3）由return带回函数的返回值。要注意的是，return最多只能带回1个返回值。 （4）函数体中的语句是根据形参表列中的参数作为变量描述要解决问题的过程。

7 课堂练习 1.编写一个名为Transf的函数，该函数将一个十进制数转换成为r进制数，并输出转换后的结果。
2.编写一个名为tempConvert函数，接收一个温度和一个字符作为参数。如果传递给这个函数的字符是字母f，函数应该把传递来的温度从华氏温度转换为摄氏温度，否则函数应该是把传递过来的温度从摄氏温度转化为华氏温度。（c=5*(f-32)/9） 3.编写一个名为distance的函数，接受两点x1,y1和x2,y2的坐标，计算和返回两点之间的距离。

8 课堂练习（续） 4.编写一个名为fac函数，接收一个正整数，计算并返回所传递数的阶乘。
5.一个x的二次多项式由ax2+bx+c给定，式中a,b和c是已知数，且a不等于0.编写一个名为Polytwo函数，计算和返回这个二次多项式的数值，使用任何被传递的a,b,c和x的数值。

9 课堂练习（续） 编写程序，实现电话簿的管理。要求有如下几个功能：输入（Input）、修改（Amend）、删除（Delete）、查询（Search）和浏览（Browse）。

10 如何根据问题定义函数？ 1.弄清楚问题的需求。 2.确定输入项（有无参数？参数的类型和个数？）
3.期望的输出（通过return返回还是当时输出？） 4.具体实现步骤（算法）

11 2 函数的调用 函数调用的方法： m=函数名（实参表列）； 如果所定义的函数没有返回值，则函数调用的方式为： 函数名（实参表列）；
实参表列中的参数类型和参数的个数要与被调用函数定义时的形参的参数类型和个数完全一致。 m用来存放函数由return带回来的返回值，该变量的类型要和被调用函数的返值类型一致，有时也可以不用。 如果所定义的函数没有返回值，则函数调用的方式为： 函数名（实参表列）；

12 函数的调用 例如： 1) Hello( );//无参、无返值函数 2) int n=6;
m=IsPrime(n)；//1个整型参数，有返回值，根据返回值判断n是否是素数 if(m==1)printf(“%d是素数”,n); else printf（”%d不是素数”,n）; 也可以不用变量m，直接使用函数的返回值： if(IsPrime(n)= =1) printf(“%d是素数”,n); else printf（”%d不是素数”,n）;

13 函数的调用 3） int a=45,r=2;调用进制转换函数，将45转换为二进制并输出结果，其调用为：
trans(45,2);//2个整型参数，无返回值

14 函数的调用 一般地，函数在调用时，调用其他函数的函数称为主调函数，被调用的函数称为被调函数。很多时候，主函数main是最大的主调函数。
函数在调用的时候，其调用和返回的示意图如下：

15 函数的调用 void main( ) { …… prime(67); trans(45,2); int prime(int n)
return } void trans(int a,int r) ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨

16 课堂练习 在主函数main中调用上述的练习中的所定义的函数。

17 3 函数的嵌套调用与递归 主调函数未必一定是主函数。比如进制转换函数trans中调用了输出函数printf（）。这里trans是主调函数，printf是被调函数。 例：编写函数combine()，求从n个数中取r个数的组合数。该问题的解决可以通过借助练习4来完成。因为组合公式为：

18 函数的嵌套调用 函数的嵌套调用示意图： void main( ) { { …… …… combine(8,5); }
其中，③、④、⑤部分分别重复三次，因为函数combine调用函数fac三次。 void main( ) { …… combine(8,5); } long combine(int n,int r) { …… fac(n)/(fac(n-r)*fac(r)) } long fac(int n) { …… } ③ ① ② ④ ⑥ ⑤ ⑦

19 函数的嵌套调用 主函数main( )调用函数combine（），而函数combine又调用函数fac( )。这就是嵌套调用。在嵌套调用中，最后被调用的函数最先带回返回值。

20 函数的递归调用 在函数调用过程中，如果主调函数和被调函数都是同一个函数，这样的调用称为递归调用。递归调用可以把规模较大的问题转化成为同种类型但规模小一点的问题加以解决。即递归中，子问题和原问题必须具有相同的形式。

21 函数的递归调用 通用递归函数体表示如下： if（递归结束条件） return (递归公式的初值)； else

22 函数的递归调用 根据上述的这个通用的递归函数的表现形式我们注意到，每个递归调用的函数都必须要有一个出口，就如同递推式需要有初始值一样的道理。如果没有出口，就会造成无法返回的局面。例如下面的这个函数： int f1（int n） { return （n+f1(n-1)）; }

23 函数的递归调用 例：用递归调用求解n!. 数学中求n！的递归（递推）： 1 n=0或1//递归结束条件 n!=

24 函数的递归调用 函数描述： long fac(int n) { if(n==0||n==1)return 1;
else return n*fac(n-1); }

25 函数的递归调用 递归调用与嵌套调用类似的地方是，最后被调用的函数最先返回其值。是一种“后进先出”法则 fac(5) 5！=5*4！
4！=4*3! 3!=3*2! 2!=2*1! 1!=1 返回5！=120 递归中“递”的过程 递归中“归”的过程 返回4！=24 返回3！=6 返回2！=2 返回1！=1

26 函数的递归调用 例：用递归调用将十进制数a转化为2进制数 void Binary(int n) {
if(n==0||n==1) //递归结束条件，出口 printf("%d",n); return; } else Binary(n/2); //递归调用 printf("%d",n%2);

27 函数的递归调用 例：用递归调用将十进制数a转化为16进制数。 void Hex(int n)
{ if(n<=9) // 递归结束条件之一 { printf("%d",n); return; } else if(n>=10&&n<=15) //递归结束条件之二 { printf("%c",n-10+'A'); else //递归调用 { Hex(n/16); if(n%16<10)printf("%d",n%16); else printf("%c",n%16-10+'A');

28 函数的递归调用 例：通过观察二进制的转化过程和输出顺序，以及递归的先递后归的规律，对于递归的方法实现进制转换的问题还可以进行简化。
Binary(13)---->Binary(6)---->Binary(3)---->Binary(1) printf(13%2) printf(6%2) printf(3%2) printf(1%2) D2 D1 D3 G1 G3 G2 S1 S3 S2 S4

29 函数的递归调用 例：用递归调用将十进制数a转化为2进制数和16进制数。 void Binary(int n) {
if(n/2!=0)Binary(n/2); printf(“%d”,n%2); } void Hex(int n) { char c; if(n/16!=0)Hex(n/16); c=n%16; printf(“%c”,c>=0&&c<=9?c+’0’:c+’A’-10); }

30 函数的递归调用 上面的两个例子中输出函数printf的位置非常重要，要放在递归调用之后，不能放在递归调用之前，但是并不是所有的问题都要这么做。请看习题6-14，该题与求解二进制数或者16进制数的共同之处和差别在哪里呢？ void Inverse(int m) { if(m<10) { printf("%d",m); return; } else { printf("%d",m%10); Inverse(m/10);

31 本结作业 6.2 写两个函数，分别求两个整数的最大公约数和最小公倍数。 6.13 采用递归的方法实现下列函数的值。
Px(x,n)=x-x2+x3-x4+…+(-1)nxn (n>0) 6.14 输入一个多位正整数，要求用递归的方法实现按其各位数字相反的顺序输出新的整数。

32 6.2 函数的参数传递 6.2.1 变量的作用域 局部变量：在函数内部定义的变量称为局部变量。其作用范围仅限于该函数。
全局变量：在函数外面定义的变量称为全局变量，其作用的范围为从定义的位置开始一直到文件的结束。 若全局变量个某个函数中的局部变量同名，则在该函数中，这个全局变量被屏蔽，在函数内访问的是局部变量，与同名的全局变量不发生任何关系。

33 自动变量：auto int i； 静态变量：static int i; 寄存器变量：register int a; 全局变量也是静态变量。 在函数调用时，先分配形参、局部自动关变量的空间，函数执行结束立即释放这些空间。

34 举例： 请观察下列两个函数，分别写出运行结果： void f(int a) void f(int a) { static int m=0 ;
m+=a; printf(“%d”,m); } void f(int a) { int m=0 ; m+=a; printf(“%d”,m); } void main() { int k=4; f(k); f(k); }

35 举例： 利用静态变量求解n！。

36 6.2.2 值传递与地址传递 主调函数A与被调函数B之间存在着数据传递关系。在C语言中，A函数和B函数之间有如下几种数据传递方式：
值传递与地址传递 主调函数A与被调函数B之间存在着数据传递关系。在C语言中，A函数和B函数之间有如下几种数据传递方式： （1）传值 将函数A中的实参单向复制给函数B中的形参。但函数B运行完毕，并不会将形参的结果回传给函数A。调用函数的结果（如果需要）会通过return带回。 例如：求两个数的最大值函数、最小值函数、最大公约数、最小公倍数等等问题都是通过值传递的方式来实现的。

37 （2）传地址： 本质上讲，传地址方式是一种特殊的传值方式。传地址时传递的不是数据本身，而是存储该数据的地址，因为同一地址指向相同的数据。在被调函数B中修改该地址的数据，显然其作用会返回到调用的函数中。 在这种方式中，被调函数B的形参必须是可以接受地址值的指针变量，并且它的数据类型必须与主调函数A中被传递数据的数据类型相同。 通过地址传递的方法，我们可以带回来多个返回值。 例如：编写函数实现交换两个数。

38 6.3 指针作为函数参数 指针作为参数 通过地址传递的方式，我们可以带回多个返回值。此时要求被调函数B的形参必须是指针变量。而主调函数A中的实参既可以是变量的地址&变量名，还可以是指向该变量的指针变量。因此不管是主调函数还是被调函数都可以使用指针变量作为参数。

39 例：编写函数PassWord，实现将键盘输入的不超过20位的密码数据依次显示为*，并且将密码保存。
输入项：1个字符串； 期望的输出：一串* 算法： 1）依次从键盘接收字符 2）所接收的字符不回显，只显示* 3）保存所输入的字符数据

40 #include<stdio.h>
#include<stdlib.h> #include<conio.h> #define N 21 //写密码函数 void PassWord(char *str) { char c; int i=0; printf("请输入密码,不超过20位\n"); while((c=getch())!=13) putchar('*'); str[i]=c; i++; } str[i]=0; void main() char pw[N]; PassWord(pw); getch(); puts("\n"); puts(pw);

41 例6-6 判断一个字符串t是否包含在另外一个字符串s中，如果是，则输出串t在串s中第一次出现的位置。
分析： 输入项：两个字符串； 期望的输出：如果t是s的子串，则输出t第一次出现在s中的位置，否则输出-1； 匹配算法： 1）初始时，i=0,j=0. 2）依次比较字符s[i+j]和t[j]，如果s[i+j]==t[j],则比较下一对字符,即j++。当j=strlen（t）时，算法结束，返回i。当j<strlen(t)但是i>=strlen(s)-strlen(t)时，算法结束，返回-1。如果s[i]!=t[j]，转入3） 3）i为上一趟比较的下一个位置，即i++，j回到初始状态0.转入2）

42 例如：母串为s=”aababcbabc”,子串t=”abc”，则匹配过程如下：
i=1 i=0 i=2 a b c j=2 j=1 j=0 j=1 j=0 j=0 a b c

43 分析下面的程序，说出该程序的功能： void PR() {     char c = getchar();     if(c!='\n')     {         PR();     }     printf("%c",c); } 编写函数实现两个字符串的连接。即如有两个字符串S=“ABCD”和T=“12345”，将字符串T连接在字符串S的后面，使得S变为S=“ABCD12345”。

44 编写函数实现对10个整数按照从小到大的顺序排序，又该如何写呢？
练习：分别说出下面两个函数的功能： void swap(int *pt1,int *pt2) { int p; p=*pt1; *pt1=*pt2; *pt2=p; } void exchange(int *q1,int *q2,int *q3) if(*q1<*q2) swap(q1,q2); if(*q1<*q3) swap(q1,q3); if(*q2<*q3) swap(q2,q3); 编写函数实现对10个整数按照从小到大的顺序排序，又该如何写呢？

45 数组名作为函数参数 数组名也可以作为参数，它传递的是数组的首地址。 数组名作为函数参数时，实参和形参既可以是数组名，亦可以是指针变量。
例如：编写函数实现求解数组中的最大数、对数组元素进行排序、将数组元素逆置等问题都是属于数组名作为函数参数的问题。（实参、形参依次分别数组名和指针变量）

46 练习： 1.编写函数实现求解数组中最小数。 2.编写一个函数，实现求解数组中最大和最小数。
3.编写一个函数，实现求解数组中的最大数、最小数以及它们在数组中的下标。 4.编写函数实现求解数组中的次大数和次小数。

47 数组名作为函数参数时也可结合递归来解决一些问题。比如利用二分法查找的问题。
二分查找：当数组中的数据有序（比如递增）的时候，采用二分查找可以节省时间。其基本思想是： 1）如果待查找的数据元素个数为0，则查找失败。否则 2）让数据数组的中间的值与待查找的关键值比较，如果两者相等，则查找成功。否则 3）如果关键字比中间的值小，则按同样的方法在中间值的前面的部分数组中查找，否则 4）如果关键字比中间的值大，则按同样的方法在中间值的后面的部分数组中查找。

48 int *Bins(int a[],int n,int key)
{ int mid=n/2,i; for(i=0;i<n;i++)//输出当前查找的子序列 printf(" %d",a[i]); printf("(数组长度%d)\n",n); if(n==0)return NULL; if(key==a[mid])return a+mid; else if(key<a[mid]) return Bins(a,mid,key); else return Bins(a+mid+1,n-(mid+1),key); }

49 上述的问题我们还可以不用递归，而用迭代的方法来解决，同样还是用数组名作为函数参数。
int *Binsearch (int a[],int n,int key) { int low=0,high=n-1; int mid,i; while(low<=high) printf("当前的查找区间是[%d %d] \n",low,high); for(i=low;i<=high;i++)//输出当前查找的子序列 printf(" %d",a[i]); printf("\n"); mid=(low+high)/2; if(key==a[mid]) return a+mid; else if(key<a[mid])high=mid-1; else low=mid+1; } return NULL;

50 6.3.2 函数作为参数 指向函数的指针变量的定义： 数据类型 （*变量名）（参数类型）； 例如： int（*pf1）（int，int）；
数据类型 （*变量名）（参数类型）； 例如： int（*pf1）（int，int）； 与指针变量定义个使用的规则一样，此时指针变量pf1只能指向返值类型为整型（int），函数形参只有2个且数据类型为整型的函数。 例如函数max就是一个符合上述形式的函数，我们就可以通过指针变量pf1间接访问函数max如下： pf1=max; 如果要求解两个数a和b的最大值，通过pf1来调用max如下： c=pf1（a,b）;即可，见下页。

51 int max(int a,int b) { if(a>=b)return a; else return b; } void main() int a=9,b=21,c; int (*pf1)(int,int); pf1=max; c=pf1(a,b); printf("最大值是%d\n",c);

52 6.3.2 函数作为参数 问题：用区间二分法求多个函数的根。 f(b) y x a b f(a) b f(b) y x a f(a) m
f(m) m f(m)

53 问题分析： 解题分析： 1）只有当区间端点的函数值f(a)和f(b)满足f(a)*f(b)<0时，方可使用区间二分法。
2）对于不同的连续函数都可适用。 3）所求函数的根是一个近似值，所以有误差，误差大小可以自己规定。 解题分析： 输入：需要求解根的函数和区间以及精确度； 期望的输出：输出近似解（函数的根） 算法：区间二分法： 1）判断该区间是否有根存在（f(a)*f(b)<0?)若有，则转入2） 2）取中点 m=(a+b)/2，对区间[a,m]和[m,b]做判断，看看根存在于哪个区间，更新区间[a,b]，继续执行2）直到区间长度足够小为止，此时(a+b)/2即为所求的根。

54 {printf("函数在区间[a,b]上没有根\n"); return -1000;} while(fabs(a-b)>eps)
函数描述： double root(double(*f)double ,double a,double b,double eps) { double m; if(f(a)*f(b)>0) {printf("函数在区间[a,b]上没有根\n"); return -1000;} while(fabs(a-b)>eps) m=(a+b)/2; if(f(a)*f(m)<0)b=m; else a=m; } return (a+b)/2;

55 字符串型指针数组，可以理解为接收多个字符串，可以写为char **argc
6.3.3 主函数的参数 主函数的参数有固定的格式要求： void main(int argc, char *argc[]); 字符串型指针数组，可以理解为接收多个字符串，可以写为char **argc 一个整型变量，表示参数的个数 主函数的参数值是由谁来传递的呢？ 主函数的参数又叫做命令行参数，是通过类似Dos命令的方式执行程序。

56 查看如下程序，并尝试运行一下该程序，看结果为什么？
#include <stdio.h> void main(int argc ,char *argv[]) { int i; for(i=0;i<argc;i++) puts(argv[i]); printf("%d\n",argc); }

57 6.4 函数的综合应用 例6-11 青蛙过河。 该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下：
一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用1，2，…，n编号。规定初始时这队青蛙只能趴在左岸的石头L上，按编号一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有S个石柱，有y片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求按编号一个落一个，大的在下，小的在上，而且必须编号相邻。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下，且编号相邻。当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。 问在已知溪中有S根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？

58 青蛙过河 分析： 定义函数 简化问题，探索规律 Jump ( s ,y ) —— 最多可跳过河的青蛙数
青蛙过河　分析： 定义函数 Jump ( s ,y ) —— 最多可跳过河的青蛙数 其中：S —— 河中柱子数, y —— 荷叶数 简化问题，探索规律 先从个别再到一般，对多个因素作分解，孤立出一个一个因素来分析，化难为易 河中无柱子 河中有柱子

59 1. 简单情况，河中无柱子：S = 0 Jump ( 0 , y ), 当 y = 1 时，Jump ( 0 , 1 ) = 2 ； y 1
L y R

60 当 y = 2 时， Jump ( 0 , 2 ) = 3 ； 采用归纳法：Jump ( 0 , y ) = y+1 y2 y1 1 2 3
L R

61 2.Jump( S, y ) 最简单情况： S = 1，y = 1 需要 9 步，跳过 4 只青蛙 1 2 S 3 4 y R L

62 2 1 3 R L y S L-y-S ,将 L上的一半青蛙转移到 S 上
L-y-R,将 L上的青蛙转移到 R 上，相当于Jump(0,1) S-y-R,将 S 上的青蛙转移到 R 上，相当于Jump(0,1) 两个系统之和为2*Jump(0,1)，因此有： Jump(1,1)=2*Jump(0,1)=2*2=4

63 S=2，y=1 Jump(2,1) 1 2 3 4 5 6 S1 S2 7 8 y L R

64 3 1 2 S1 S2 y L R L S1 S2 y R 系统分解为 ： （L S2 y R 系统） + （S1 S2 y R 系统） = 2 * （L S2 y R 系统）= 2 * Jump(1,1)=2*4=8 用归纳法: Jump(S, y)=2*Jump(S-1, y)

65 3. 递归形式的与或结点图为 求Jump(3,4)

66 // * 主要功能：青蛙过河 #include <stdio.h> int Jump(int, int); //声明有被调用函数 int main() { int S=0,y=0,sum=0; //s为河中石柱数,y为荷叶数 scanf(“%d”,&S); scanf(“%d”,& y); sum = Jump ( S , y ) ; //最多可跳过河的青蛙数 printf("Jump(%d,%d)=%d\n“,S,y,sum); return 0; } int Jump ( int r, int z ) { int k=0; if (r==0) k = z + 1; //直接可解结点, k 值为 z + 1 else k=2*Jump(r-1,z);　//要调用Jump( r-1, z ) return k;