C程序设计自学辅导ch5-2g.ppt

1,第5章 函数的设计与应用,5.1 5.2 5.3 5.4 5.5 函数的递归 5.6 内联函数 5.7 数组参数及函数间传递数据的五种常用方式(渠道) 5.8 标识符的作用域 5.9 变量与函数的存储类别 5.10 编译预处理,2,问题,1，为什么要用函数 2，使用函数的程序和顺序程序有什么区别？ 课本p116,3,函数调用的堆栈,堆栈,Main(),cuberoot( x ),参数传递、返回值,保护现场、恢复现场,调用,返回,4,5.5 函数的递归,5.5.1 使用递归求累乘积与累加和 5.5.2 “三色冰激凌”程序 5.5.3 Hanoi塔问题,5,C+允许函数自己调用自己(如A函数可以调用A函数本身，称为直接递归)。也允许A函数调用B函数，而后B函数又调用A函数(从而形成间接递归)。但不论使用哪种递归，程序员都应保障递归函数在执行若干次后能够“退出”递归(不再进行递归调用，也即能够实现递归出口)。,6,5.5.1 使用递归求累乘积与累加和,1. 求n的阶乘的递归函数prod - 参看书p124的5.2.6小节的2 使程序执行后的输出结果为: Input a positive integer:6 p=1*.*6=720 在数学中，可按如下方式对n!进行递归定义： 当n=1时， n!=1； 当n1时， n!=n*(n-1)! 这正是我们编写求n的阶乘的递归函数prod的基础。,7,#include long prod(int n) /注意用的是long，课本p131（3） if ( n=1 ) return 1; /n等于1时，递归出口(“退出”递归) else return n * prod(n-1); / n大于1时的返回值(n!)为n乘以n-1的阶乘 / ( 使用自递归调用“prod(n-1)”来求出(n-1)! ),8,void main( ) int n; coutn; /输入的正整数放入n中 long p=prod(n); /求出n的阶乘放入p中 cout“p=1*.*“n“=“pendl; /输出结果p ,9,上述求阶乘的递归函数中，当主函数通过prod(3)对递归函数prod进行调用时，它的返回值为3*prod(2)，此时系统将再一次对prod本身进行调用而形成递归调用。 但注意后一次调用的实参为2，比上一次的实参3“下降”了1。而计算prod(2)时，它的返回值为2*prod(1)，此时系统将再一次对prod本身进行递归调用，但此时的实参又“下降”了1。,10,正是通过这种实参的逐次“下降”，可保障递归函数在执行若干次后(此时的求阶乘问题当“下降”到1时)，能够“退出”递归(不再进行递归调用，也即实现了递归出口)。 由于prod(1)的返回值为1，系统进一步算出2*prod(1)的值（即prod(2)的值）为2*1=2，再进一步算出3*prod(2)的值为3*2=6，这正是prod(3)的调用返回值(也即求出了3!=3*2*1=6)。,11,虽然上述执行过程是由系统自动完成的，但程序员要理解并熟知这种调用机制与系统实现方法，从而才能编写出逻辑正确且简明易懂的递归处理程序。 另外注意，递归处理程序的执行速度通常要比非递归处理方法慢。 问题：为什么会慢？,12,2. 求出1到n之累加和的递归函数sum,使程序执行后的输出结果为: Input a positive integer:100 s=1+.+100=5050,13,#include int sum(int n) /递归函数sum if ( n=1 ) /n等于1时，递归出口 return 1; else return n + sum(n-1); /n大于1时的返回值(累加和)为n加上“从1累加到 /n-1的和”(要使用递归调用求出前n-1个数的累加和),14,void main( ) int n; coutn; int s=sum(n); /求出从1累加到n的和放s中 cout“s=1+.+“n“=“sendl; ,15,5.5.2 “三色冰激凌”程序 - 参看书p130的5.4.1小节,由冰激凌商提出的问题：有28种颜色的原料，可以组合成多少种3色冰激凌。问题归结为计算排列数与组合数。 本示例计算排列数A(elements,selections)及组合数C(elements,selections)。 如：A(3,2)=6, C(3,2)=3; A(28,3)=19656, C(28,3)=3276。,16,由于排列数A(ele,sel)与组合数C(ele,sel)间有如下的关系： C(ele,sel)=A(ele,sel)/sel! 程序中编制了一个求阶乘的递归函数factorial，可用于求出sel的阶乘。 使程序执行后的显示结果如下： Number of selections:3 Out of how many elements:28 A(28,3)=19656 C(28,3)=3276,17,#include long factorial(int number); /函数原型 void main( ) int i,selections,elements; /计算A(elements,selections) /以及C(elements,selections) coutselections; /输入整数selections coutelements; /输入整数elements double answer = elements; int ele = elements;,18,/求排列数A：共进行sel-1次乘法 /A(ele,sel)=ele*(ele-1)*.*(ele-sel+1) for(i=1; iselections; i+) /循环sel-1次 answer*=-ele; /最终的answer值即为所要求的A(ele,sel) cout“A(“elements“,“selections“)=“; coutanswerendl; /输出排列数A(ele,sel)之结果,19,/组合数C的求法： / C(ele,sel)=A(ele,sel)/sel! answer/=factorial(selections); /对递归函数调用，求阶乘 cout“C(“elements“,“selections“)=“; coutanswerendl; /输出组合数C(ele,sel)之结果 ,20,long factorial(int number) /递归函数factorial，用于算出number的阶乘 if(number=1) return 1; /递归出口(“退出”递归) else return number*factorial(number-1); /自递归调用, 注意实参不同(每次降1) ,21,当然也可编出非递归的用于算出 number之阶乘的函数factorial,long factorial(int number) /非递归函数 long p=1; for (int i=2; i p return p; /返回的p即为number之阶乘 ,22,5.5.3 Hanoi塔问题 - 参看书p132的5.4.2小节,古印度的著名智力测验问题：有三个立柱A、B、C，在A柱上穿有大小不等的圆盘64个，较大的圆盘在下，较小者在上。要求借助于B柱将A柱上的64个圆盘移到C柱，规则为： (1) 每次只能把一个柱上最上面的圆盘移至另一个柱的最上面; (2) 每个柱上总保持较大的圆盘在下，较小者在上。 编制程序, 实现将任意n个圆盘从A柱借助于B柱移到C柱, 并显示出全部移动过程。,23,总任务(“度”为n的任务)： 把A柱上的n个圆盘，借助于B柱，按规则移到C柱上(移动规则：一次移一片，大片不可压小片) 。 靠调用自定义函数hanoi来完成：hanoi(n,A,B,C);,24,总任务可分解为与其等价的三个子任务(的“合集”)(“度”小于等于n-1的三个子任务)： (1) 把A柱上最上面n-1个圆盘，借助于C柱，按规则移到B柱上(一次递归调用)； (2) 把A柱上留下的(最大的)圆盘移到C柱上(一步可完成的“本原任务”)； (3) 把B柱上的n-1个圆盘，借助于A柱，按规则移到C柱上(又一次递归调用)。,25,靠下面的三个调用语句来完成： hanoi(n-1,A,C,B); move(A,C); hanoi(n-1,B,A,C);,26,移动次序：1,A B C,27,移动次序：2,A B C,28,移动次序：3,A B C,29,移动次序：4,A B C,30,移动次序：5,A B C,31,移动次序：6,A B C,32,移动次序：7,A B C,33,移动次序：8,A B C,34,使程序执行后的显示结果如下：,Input the number of disks:3 The step of moving 3 disks: A=C A=B C=B A=C B=A B=C A=C,35,具体程序如下：,#include void hanoi(int, char, char, char); /hanoi函数原型 void main( ) int m; /欲移动的圆盘个数m coutm; /输入圆盘个数m coutendl“The step of moving “m“ disks:“; hanoi(m,A,B,C); /调用自定义函数hanoi，移m片，从A，借助B，到C coutendl; ,36,void move (char from, char to) /移1片，从from，到to (“本原任务”) cout“to; /显示“移步信息“ ,37,void hanoi(int n, char a, char b, char c) /自递归函数hanoi，移n片，从a，借助b，到c if(n=1) move(a,c); /“本原任务”，递归出口 else hanoi(n-1,a,c,b); /移n-1片，从a，借助c，到b (递归调用) move(a,c); /移1片，从a，到c (“本原任务”) hanoi(n-1,b,a,c); /移n-1片，从b，借助a，到c (递归调用) ,38,5.6 内联函数 - 参看书p125的5.2.7小节,可在一般的函数说明前冠以关键字inline，称这样的函数为内联函数。按如下的方式来说明： inline ( ) ,39,在编译过程中，凡内联函数，系统均把它的执行代码插入到该函数的每个调用点处(以取代那一函数调用)，从而使程序执行过程中，每次对该函数调用时不需控制转移，可节省执行时间; 但由于每个调用点处均出现那一函数的执行代码拷贝，相对来说使用内联函数后会扩大其代码空间。,40,使用内联函数的简单实例,#include inline int max(int x, int y) /内联函数max return(xy?x:y); ,41,void main(void) int a,b; coutab; cout“max(a,b)=“max(a,b)endl; /对内联函数max的调用 ,42,程序执行后的显示结果如下： Input a,b:123 456 max(a,b)=456 使用内联函数时应注意： 1. 内联函数的函数体一般讲不宜过大, 以1-5行为宜。 2. 凡在类体中定义的成员函数(见第7章)均隐含为内联函数。,43,5.7 数组参数及函数间传递数据的五种常用方式（渠道）,1. 数组参数 数组可作为函数参数，从而把主调函数中的整个数组(实际上是数组的首地址)传给了被调函数。而后可在被调函数中使用或改变传来的那些数组元素的值。但注意，若在被调函数内改变数组元素值的话，返回主调函数后，相应实参数组元素的值也进行了相同的改变（“双向传值”功能）。,44,例1. 读如下程序，看执行 后会显示出什么结果?,#include void ProcessingFunc(int b, int num); /函数原型 /int型数组形参b，通常省去对元素个数的指定 /(当然也可以进行指定!) void main() int A10=0,1,2,3,4,9,8,7,66,88; cout“- before calling, ai= -n“; for(int i=0; i10; i+) coutAi“ “; coutendl;,45,ProcessingFunc(A, 10); /函数调用 cout“- after calling, ai= -n“; for(i=0; i10; i+) coutAi“ “; coutendl; ,46,void ProcessingFunc(int b, int num) /数组形参b，省去了对元素个数的指定! cout“- in ProcessingFunc, bi= -n“; for(int i=0; inum; i+) coutbi“ “; coutendl; int tmp=b0; b0=bnum-1; bnum-1=tmp; b1+=100; ,47,程序执行后的显示结果如下：,- before calling, ai= - 0 1 2 3 4 9 8 7 66 88 - in ProcessingFunc, bi= - 0 1 2 3 4 9 8 7 66 88 - after calling, ai= - 88 101 2 3 4 9 8 7 66 0,48,例2. 求a数组中前n个整数 累加和的递归函数sum,其中使用了数组形参与递归函数。 程序执行后的输出结果为: Input 6 integers: 22 4 -2 9 100 3 s=136,49,#include int sum(int a, int n) if ( n=1 ) return a0; else return ( an-1 + sum(a, n-1) ); ,50,void main() const int n=6; int An; coutAi; int s = sum(A, n); cout“s=“sendl; ,51,2. 函数间传递数据的 五种常用方式(渠道),主调函数A与被调函数B之间主要靠如下五种方式(渠道)来传递数据： 1) 通过全局变量(“双向传递”方式) 可从主调函数A中通过全局变量将值“传入”到被调函数B内(在A中赋值, 进入B内后使用该值)，又可将被调函数B内改变后的全局变量值“传出”到主调函数A中(去接着使用)。也即，传值方向可为：“上层” =“下层”，“下层” =“上层”。,52,2) 通过引用参数(“双向传递”方式， 有关引用的其它使用方法想。详见第6章),传值方向可为：“上层” =“下层”，“下层” =“上层”。即是说，它不仅可向被调函数的形参“传入”值(调用时的实参值)，而且还可通过该形参“传出”值。系统处理方式为: 被调函数中对形参值的使用与改变，就是对主调函数中调用语句处所对应实参变量值的直接使用与改变(形参不具有自己的局部于被调函数的存储空间，它只是实参变量的一个“替身”)。,53,3) 通过数组参数或指针参数(“双向传递” 方式，指针参数的具体使用方法见第6章),传值方向可为：“上层” =“下层”，“下层” =“上层”。 数组作形参，且在被调函数内使用或改变数组元素的值。系统处理方式为: 对形参数组元素的使用与改变，就是对实参数组元素的直接使用与改变。 指针作形参，且在被调函数内使用或改变指针所指变量的值。系统处理方式为: 被调函数中对形参指针所指变量值的使用与改变，就是对实参指针所指变量值的直接使用与改变。,54,4) 通过赋值参数 (“单向传递”方式),传值方向只是：“上层” =“下层”。也即，可从主调函数A中通过赋值参数所对应的实参将值“传入”到被调函数B内(去使用)，但不可将被调函数B内改变后的参数值“传出”到主调函数A中(去接着使用)。系统处理方式为: 被调函数中对形参值的改变不影响主调函数处的任一变量的值(形参分配有自己的局部于被调函数的存储空间，调用入口处将实参表达式的值赋给该局部变量)。,55,5) 通过函数返回值(“单向传递”方式),通过函数内使用的return语句, 可将被调函数B内计算出的最终值“传出”到主调函数A的“调用点”处(去接着使用)。也即，传值方向只是：“下层” =“上层”。,56,5.8 标识符的作用域 5.8.1 作用域问题 5.8.2 与作用域有关的程序实例,57,5.8.1 作用域问题,作用域是指标识符（如变量名、参数名、函数名等）在程序正文中的有效范围。 1. 六种不同级别的作用域 (1) 程序级作用域（也称多文件级作用域） 属于程序级作用域的有通过extern存储类别进行说明的外部变量以及外部函数等。,58,(2) 文件级作用域（也称单文件级作用域） 其有效范围为定义该标识符的那一个文件内。属于此种作用域的有静态函数以及在各函数之外的某一位置进行说明的那些变量等。 (3) 类级作用域 有效范围为所定义的那一个类的类体内。类中的私有成员的作用域仅在其类体内，公有成员以及保护成员的作用域有所不同。关于类级作用域将在后面的章节再进一步讨论。,59,(4) 函数级作用域(也称单函数级作用域) 有效范围为所处的那一个函数的函数体内。属于此种作用域的有函数的形参、在函数体内说明的变量、以及语句标号等。 (5) 块级作用域 块是程序正文中被一对花括号括起来的那一块区域（如, 函数内的某一个复合语句）。C+允许在块中说明局部于该块的变量。,60,(6) 函数原型级作用域,仅指出在函数原型声明时形式参数的作用范围。例如，假设有如下的函数原型声明： double myfunc(int ipara); 此时的形式参数ipara的有效范围(作用域)仅局限于说明该参数的那一对圆括号之间，在程序的其他任何地方都无法引用该标识符。,61,2. 关于重名标识符的作用域,重名标识符指的是在程序中被重复定义的同名标识符。在相同的作用域内，标识符不能被重复定义。但在不同的作用域内，允许对标识符进行重复定义。 重名标识符的作用域遵循如下的规则： (1) 没有包含关系的两个不同作用域 在其中说明的标识符尽管名字相同，但二者毫不相干。,62,(2) 具有包含关系的两个不同作用域 将它们看成是互不相同的名字；进入子范围后, 将屏蔽其父范围的名字。即是说，进入子范围后, 原父范围处定义的那一同名标识符将是不可见的，但它仍然存在；当退出了子范围后，原父范围处定义的那一同名标识符将又成为可见的了。,63,5.8.2 与作用域有关的程序实例,1. 作用域实例1 本实例出现了三个不同的作用域：函数级作用域，被函数级作用域所包含的外层块级作用域，被外层块级作用域所包含的内嵌块级作用域。,64,#include void main() int i=10; /整型变量i, 具有函数级作用域 char ch=1; cout“in main - i,ch=“i“, “chendl; int i=20; /另一整型变量i, 外层块级作用域 char ch=2; cout“in local1 - i,ch=“i“, “chendl;,65,if(i0) double i=30.3; /双精度变量i,内嵌块级作用域 int ch=33; cout“in local2 - i,ch=“i“, “chendl; cout“in local1 - i,ch=“i“, “chendl; cout“in main - i,ch=“i“, “chendl; ,66,程序执行后的显示结果如下： in main - i,ch=10, 1 in local1 - i,ch=20, 2 in local2 - i,ch=30.3, 33 in local1 - i,ch=20, 2 in main - i,ch=10, 1,67,2. 作用域实例2 本实例主要用于说明文件级作用域（全局变量），函数级作用域（局部变量），以及函数原型级作用域的相互关系及其使用。其中还出现了两个具有“平行”关系的函数作用域。,68,#include int x=11; / x具有文件级作用域 char ch=1; void func1(int ipara1); /ipara1仅具有函数原型级作用域 void func2() int i=22222; /函数级i，与func1中i重名但不相干 double ch=202.2; /函数级ch，与文件级ch同名 cout“in func2 - x,ch=“x“, “chendl; cout“in func2 - i=“iendl; ,69,void main() cout“in main - x,ch=“x“, “chendl; func1(x); func2(); void func1(int ii) int i=21111; /函数级i，与func2中i重名但不相干 int x=201; cout“in func1 - ii=“iiendl; cout“in func1 - x,ch=“x“, “chendl; cout“in func1 - i=“iendl; ,70,程序执行后的显示结果如下： in main - x,ch=11, 1 in func1 - ii=11 in func1 - x,ch=201, 1 in func1 - i=21111 in func2 - x,ch=11, 202.2 in func2 - i=22222,71,5.9 变量与函数的存储类别 5.9.1 C+的存储类别 5.9.2 存储类别相关实例,72,5.9.1 C+的存储类别,存储类别主要是针对变量而言的。变量不仅具有数据类型（存储空间大小）, 而且还具有存储类别（所占存储空间的期限，即生命期）。 变量的存储类别可分为以下四种：自动(auto)型、寄存器(register)型、外部(extern)型、静态(static)型。,73,使用显式存储类别时，变量说明的一般格式变为： , . , ; 其中的“”可以是auto、register、extern、static四个关键字之一。 C+程序的数据主要存放在如下两个数据区之中，一个称为静态数据区（也称全局数据区 - “一旦分配，一直拥有”），另一个称为动态数据区（也称堆栈数据区 - “入时分配并拥有，出时归还两手空”）。,74,具有程序级作用域以及文件级作用域的那些变量被分配在静态数据区之中。另外，具有static存储类别的变量也均被分配在静态数据区之中。在程序执行时，就为这种变量分配空间并进行隐式初始化（将数值量初始化为0，将字符量初始化为空格），直到程序执行结束时才释放这些存储空间。,75,具有其它局部作用域的那些变量被分配在动态数据区之中。在程序执行时，每遇这种变量的作用域开始时就为其分配一次存储空间（但并不进行隐式初始化），而后, 在每遇这种变量的作用域结束时就立即释放它们所占据的存储空间。 函数也分为两种存储类别，一种是外部（extern）存储类别，另一种是静态（static）存储类别。外部存储类别的函数具有程序级作用域；而静态存储类别的函数只具有文件级作用域。,76,1. 变量的存储类别,(1) 自动（auto）变量与寄存器（register）变量 这两类变量都是局部变量。均被分配在动态数据区之中。它们的“生命期”仅在其作用域之内。即是说，这两类变量的作用域与“生命期”具有一致性。 由于C+编译器默认所有在函数或块内说明的局部变量均为自动（auto）变量, 所以实用程序中根本不需要使用关键字auto。 说明寄存器（register）变量时，必须使用存储类别register。如果没有足够多的通用寄存器，则编译器将它们按自动（auto）变量来处理。,77,(2) 外部（extern）变量 外部（extern）变量具有程序级作用域。它们被分配在静态数据区之中。即是说，它们是作用域最大且“生命期”最长的一种变量，其可见性与存在性是相互一致的。 (3) 静态(static)变量 又可分为局部静态变量和全局静态变量。局部静态变量是指在函数或块的内部说明的静态变量，它的作用域是局部的；而全局静态变量指的是在所有函数的外部说明的具有单文件级全局性的静态变量。两种静态变量都被分配在静态数据区之中，即是说，它们的“生命期”都与整个程序的执行期相同。,78,2. 函数的存储类别,函数也分为两种存储类别，一种是外部（extern）存储类别，另一种是静态（static）存储类别。 (1) 外部(extern)函数 具有外部（extern）存储类别的函数称为外部（extern）函数。这种函数具有程序级作用域。当函数定义时没给出存储类别时，系统默认它为外部（extern）存储类别，所以实用程序中几乎从不使用extern来说明外部函数。,79,例如，如下的两个函数说明是完全等价的。 int func() extern int func() (2) 静态(static)函数 具有静态（static）存储类别的函数称为静态（static）函数（有时也称为内部函数）。这种函数只具有文件级作用域，即是说, 这样的函数只能在本文件的内部被调用，在其它文件中均不可见。,80,5.9.2 存储类别相关实例,1. 存储类别实例1 - 外部（extern）变量 本实例程序由两个文件构成,下面分别叙述它们。 (1)程序文件1 本文件中对外部变量x及ch进行定义，并通过调用处于另一文件中的函数来“传递”与使用这些外部变量的具体值。,81,/file_1.cpp（源程序文件1，含有2个函数）,#include int x=11; char ch=A; void func1(); /函数原型 void func2(); /函数原型，具体定义在另一个文件中 void main() func1(); func2(); cout“In file1_main: x, ch=“x“, “chendl; void func1() cout“In file1_func1: x, ch=“x“, “chendl; ,82,(2)程序文件2 本文件通过extern关键字来对外部变量x及ch进行说明（不再分配存储空间，与另一文件定义处的那一同名变量共享同一存储空间），并通过使用与修改这些外部变量的值来达到文件间相互通讯的目的。,83,/file_2.cpp（源程序文件2，含有1个函数）,#include extern int x; extern char ch; void func2() cout“In file2_func2: x, ch=“x“, “chendl; x=22; ch=B; 程序执行后的显示结果如下： In file1_func1: x, ch=11, A In file2_func2: x, ch=11, A In file1_main: x, ch=22, B,84,2. 存储类别实例2 - 局部静态(static)变量,局部静态（static）变量与局部自动（auto）变量的使用区别是: 它们的作用域都是局部的，作用域外都是不可见的；但局部静态（static）变量在其作用域外仍是存在的，而局部自动（auto）变量在其作用域外则不复存在。,85,#include void f1(); void main() int i; for (i=1; i=3; i+) f1(); void f1() int a=1; /局部自动变量a static int s=1; /局部静态变量s cout“In f1 - pos1: a(auto)=“a“ s(static)=“sendl; a+=2; s+=2; cout“In f1 - pos2: a(auto)=“a“ s(static)=“s“nn“; ,86,程序执行后的显示结果如下： In f1 - pos1: a(auto)=1 s(static)=1 In f1 - pos2: a(auto)=3 s(static)=3 In f1 - pos1: a(auto)=1 s(static)=3 In f1 - pos2: a(auto)=3 s(static)=5 In f1 - pos1: a(auto)=1 s(static)=5 In f1 - pos2: a(auto)=3 s(static)=7,87,5.10 编译预处理 5.10.1 文件包含指令 5.10.2 宏定义指令 5.10.3 条件编译指令,88,5.10 编译预处理 - 参看书p41的2.4.2小节,允许在程序中包含若干编译预处理指令，用于指出在对该程序进行编译之前应做的“预处理”工作。每条编译预处理指令都以“#”符号开头而且每条均单独占一行。,89,5.10.1 文件包含指令,文件包含指令要求系统在编译之前将另一个源文件（的全部内容）嵌入到当前源文件的该包含指令所在位置处（以取代该包含指令）。该指令有如下两种使用格式： #include #include “FILE_NAME“ 其中的FILE_NAME