最新第6章过程封装函数PPT课件

《最新第6章过程封装函数PPT课件》由会员分享，可在线阅读，更多相关《最新第6章过程封装函数PPT课件（136页珍藏版）》请在装配图网上搜索。

1、程序设计 cs.sjtu 2011.9程序设计-1v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法程序设计 cs.sjtu 2011.9程序设计-2v函数是程序设计语言中最重要的部分，是模函数是程序设计语言中最重要的部分，是模块化设计的主要工具。每一个块化设计的主要工具。每一个C+程序都要用程序都要用到函数。到函数。v即使你自己不定义新的函数即使你自己不定义新的函数,在每一

2、个完整的在每一个完整的C+程序中都必须有一个程序中都必须有一个main()函数。函数。v在在C+语言中，字符处理、字符串处理和数学语言中，字符处理、字符串处理和数学计算都是用函数的方式提供的。计算都是用函数的方式提供的。程序设计 cs.sjtu 2011.9程序设计-3v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法程序设计 cs.sjtu 2011.9程序设计-4v函数定

3、义函数定义v函数的返回值：返回值类型应与定义中的类型标识符函数的返回值：返回值类型应与定义中的类型标识符一致。一致。C+的函数只能有一个返回值。的函数只能有一个返回值。v表示一个函数没有返回值，类型标识符用表示一个函数没有返回值，类型标识符用void。没有。没有返回值的函数也称为过程返回值的函数也称为过程 类型标识符类型标识符 函数名（形式参数表）函数名（形式参数表）变量定义部分变量定义部分 语句部分语句部分 return 返回值；返回值；或或 return（返回值）；（返回值）；eg.int max(int a,int b)if(ab)return(a)else return(b);函数体函

4、数体程序设计 cs.sjtu 2011.9程序设计-5v函数名是一个标识符，符合标识符命名函数名是一个标识符，符合标识符命名规范规范v函数名要有意义函数名要有意义v函数名一般是一个动词短语，表示函数函数名一般是一个动词短语，表示函数的行为的行为程序设计 cs.sjtu 2011.9程序设计-6v打印一个由五行组成的三角形打印一个由五行组成的三角形 *void printstar()cout “*n”;cout “*n”;cout “*n”;cout “*n”;cout “*n”;程序设计 cs.sjtu 2011.9程序设计-7v打印一个由打印一个由n行组成的三角形行组成的三角形void pr

5、intstar(int numOfLine)int i,j;for(i=1;i=numOfLine;+i)cout endl;for(j=1;j=numOfLine-i;+j)cout ;for(j=1;j=2*i-1;+j)cout num;if(num=1&num=10)return num;程序设计 cs.sjtu 2011.9程序设计-9v计算计算n!int p(int n)int s=1,i;if(n 0)return(0);for(i=1;i=n;+i)s*=i;return(s);程序设计 cs.sjtu 2011.9程序设计-10v判断某一年是否为润年的函数判断某一年是否为润年

6、的函数bool IsLeapYear(int year)bool leapyear;leapyear=(year%4=0)&(year%100!=0)|(year%400=0);return(leapyear);程序设计 cs.sjtu 2011.9程序设计-11v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法程序设计 cs.sjtu 2011.9程序设计-12v所有函数在

7、使用前必须被声明，以便让编译器知道所有函数在使用前必须被声明，以便让编译器知道用户的用法是否正确。用户的用法是否正确。v函数声明包括下列内容：函数声明包括下列内容：函数名函数名函数的参数类型函数的参数类型函数的返回类型函数的返回类型v函数的声明被称为函数的原型，它的形式为：函数的声明被称为函数的原型，它的形式为：返回类型返回类型 函数名（参数表）；函数名（参数表）；参数表中的每个参数说明可以是类型，也可以是类参数表中的每个参数说明可以是类型，也可以是类型后面再接一个参数名。如：型后面再接一个参数名。如：int max(int,int);int max(int a,int b);程序设计 cs.

8、sjtu 2011.9程序设计-13v库函数在调用前需要库函数在调用前需要include相应的头文件。相应的头文件。v自定义的函数在调用时需要进行函数原型说明。自定义的函数在调用时需要进行函数原型说明。v函数原型说明与函数首部写法上需要保持一致，函数原型说明与函数首部写法上需要保持一致，即函数类型、函数名、参数个数和参数顺序必即函数类型、函数名、参数个数和参数顺序必须相同。须相同。v如果被调函数的定义在主调函数之前，可以不如果被调函数的定义在主调函数之前，可以不必加声明。必加声明。v如果在所有函数定义之前，在函数外部已经做如果在所有函数定义之前，在函数外部已经做了函数声明，则在主调函数中无须再

9、作声明。了函数声明，则在主调函数中无须再作声明。程序设计 cs.sjtu 2011.9程序设计-14#include int max(int a,int b);main()int x,y;cin x y;cout b)return(a);else return(b);函数原型说明函数原型说明函数调用函数调用函数实现函数实现程序设计 cs.sjtu 2011.9程序设计-15#include int max(int a,int b)if(a b)return(a);else return(b);main()int x,y;cin x y;cout x y;cout max(x,y);int p(

10、int n)int s=1,i;if(n 0)return(0);for(i=1;in2?n1:n2);mainx(2)y(3)mainx(2)y(3)maxa(2)b(3)n1n2mainx(2)y(3)maxa(2)b(3)n1n2pn(2)simainx(2)y(3)maxa(2)b(3)n1(2)n2pn(3)simainx(2)y(3)maxa(2)b(3)n1(2)n2(6)mainx(2)y(3)程序设计 cs.sjtu 2011.9程序设计-20v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v

11、重载函数重载函数v函数模板函数模板v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法程序设计 cs.sjtu 2011.9程序设计-21v设计一函数，统计设计一函数，统计10位同学的平均成绩位同学的平均成绩v设计考虑：如何传递参数设计考虑：如何传递参数参数是参数是10位同学的考试成绩，可以用位同学的考试成绩，可以用10个整型个整型数来表示。所以有数来表示。所以有10个整型的形式参数个整型的形式参数一组同类数据可以用一个数组来描述，所以参一组同类数据可以用一个数组来描述，所以参数也可以是一个数也可以是一个10个元素的整型数组个元素的整型数组第

12、二种方法更加简练第二种方法更加简练返回值是平均成绩返回值是平均成绩程序设计 cs.sjtu 2011.9程序设计-22int average(int array10)int i,sum=0;for(i=0;i 10;+i)sum+=arrayi;return sum/10;程序设计 cs.sjtu 2011.9程序设计-23int main()int i,score10;cout 请输入请输入10个成绩：个成绩：endl;for(i=0;i scorei;cout 平均成绩是：平均成绩是：average(score)endl;return 0;注意：形式参数是注意：形式参数是数组，实际参数也数

13、组，实际参数也是一个数组是一个数组程序设计 cs.sjtu 2011.9程序设计-24v在函数在函数average的的return语句前增加一个对语句前增加一个对array3赋值的语句，如赋值的语句，如array3=90。v在在main函数的函数的average函数调用后，即函数调用后，即return语句前增加一个输出语句前增加一个输出score3的语句的语句v结果是什么？结果是什么？v你会发现输出的值你会发现输出的值90而不是而不是80。程序设计 cs.sjtu 2011.9程序设计-25vC+语言规定，数组名是数组的起始地址语言规定，数组名是数组的起始地址v参数传递时，实际参数是数组名，形

14、式参数也是数参数传递时，实际参数是数组名，形式参数也是数组名组名v按照值传递，当用实际参数按照值传递，当用实际参数score调用函数调用函数 average时，是用时，是用score 初始化形式参数数组初始化形式参数数组array。如。如 score 的首地址为的首地址为1000，在函数中形参数组，在函数中形参数组array的的首地址也为首地址也为1000。v形式参数和实际参数是同一数组！形式参数和实际参数是同一数组！程序设计 cs.sjtu 2011.9程序设计-26v在函数中并没有定义新的数组在函数中并没有定义新的数组v对形式参数数组指定规模是没有意义的对形式参数数组指定规模是没有意义的v

15、形式参数数组不需要指定大小，所以方括号形式参数数组不需要指定大小，所以方括号中为空中为空v函数如何知道数组的规模？用另一个整型参函数如何知道数组的规模？用另一个整型参数表示数表示v总结：数组传递需要两个参数，数组名和数总结：数组传递需要两个参数，数组名和数组规模组规模程序设计 cs.sjtu 2011.9程序设计-27v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法程序设计

16、 cs.sjtu 2011.9程序设计-28v对于某些函数，程序往往会用一些固定的值去调用它对于某些函数，程序往往会用一些固定的值去调用它.例例如对于以某种数制输出整型数的函数如对于以某种数制输出整型数的函数print：void print(int value,int base);在大多数情况下都是以十进制输出，因此在大多数情况下都是以十进制输出，因此base的值总是的值总是为为10。vC+在定义或声明函数时可以为函数的某个参数指定默在定义或声明函数时可以为函数的某个参数指定默认值。当调用函数时没有为它指定实际参数时，系统自认值。当调用函数时没有为它指定实际参数时，系统自动将默认值赋给形式参数

17、。例如，可以将动将默认值赋给形式参数。例如，可以将print函数声明函数声明为为 void print(int value,int base=10);调用调用print(20)等价于等价于 print(20,10)程序设计 cs.sjtu 2011.9程序设计-29 C+C+在说明函数原型时，可以为一个或多个参在说明函数原型时，可以为一个或多个参数指定缺省值。调用此函数时，若缺省某一数指定缺省值。调用此函数时，若缺省某一参数，参数，C+C+自动以缺省值作为此参数的值。如：自动以缺省值作为此参数的值。如：int special(int x=2,float y=1.5)int special(in

18、t x=2,float y=1.5)调用时可用：调用时可用：special(5,3.2)/x=5;y=3.2special(5,3.2)/x=5;y=3.2 special(6)/x=6;y=1.5 special(6)/x=6;y=1.5 special()/x=2;y=1.5 special()/x=2;y=1.5程序设计 cs.sjtu 2011.9程序设计-30v缺省参数无论有几个，都必须放在参数序列缺省参数无论有几个，都必须放在参数序列的最后，的最后，例如：例如：Int SaveName(char Int SaveName(char*first,char first,char sec

19、ond=second=“”,char,char*third=third=“”,char,char*fouth=fouth=“”););v在函数调用时，若某个参数省略，则其后的在函数调用时，若某个参数省略，则其后的参数皆应省略而取其缺省值参数皆应省略而取其缺省值程序设计 cs.sjtu 2011.9程序设计-31v对参数默认值的指定只有在函数声明处有意义。对参数默认值的指定只有在函数声明处有意义。因为函数的默认值是提供给调用者使用的。因为函数的默认值是提供给调用者使用的。v在不同的源文件中，可以对函数的参数指定不同在不同的源文件中，可以对函数的参数指定不同的默认值。例如对于上面的的默认值。例如对

20、于上面的print函数，如果在某函数，如果在某一个功能模块中输出的大多是十进制数，那么在一个功能模块中输出的大多是十进制数，那么在此功能对应的源文件中可以指定此功能对应的源文件中可以指定base的默认值为的默认值为10。如果在另一个功能最模块中经常要以二进制。如果在另一个功能最模块中经常要以二进制输出，那么在此功能模块对应的源文件中可以指输出，那么在此功能模块对应的源文件中可以指定默认值是定默认值是2。程序设计 cs.sjtu 2011.9程序设计-32v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数

21、重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法程序设计 cs.sjtu 2011.9程序设计-33v目的是为了提高执行效率。目的是为了提高执行效率。v对于任何内联函数，编译器在符号表里放入函对于任何内联函数，编译器在符号表里放入函数的声明（包括名字、参数类型、返回值类数的声明（包括名字、参数类型、返回值类型）。如果编译器没有发现内联函数存在错误，型）。如果编译器没有发现内联函数存在错误，那么该函数的代码也被放入符号表里。在调用那么该函数的代码也被放入符号表里。在调用内联函数时，编译器直接用内联函数的代码替内联函

22、数时，编译器直接用内联函数的代码替换函数调用，于是省去了函数调用的开销。换函数调用，于是省去了函数调用的开销。程序设计 cs.sjtu 2011.9程序设计-34v内联函数的定义：在函数头部前加保留词内联函数的定义：在函数头部前加保留词inline#includeinline float cube(float s)return s*s*s;int main()float side;cin side;cout cube(side)endls;return 0;程序设计 cs.sjtu 2011.9程序设计-35v内联以代码复制内联以代码复制(膨胀膨胀)为代价，省去了函数调为代价，省去了函数调用的

23、开销，提高函数的执行效率。如果相比用的开销，提高函数的执行效率。如果相比于执行函数体内代码的时间，函数调用的开于执行函数体内代码的时间，函数调用的开销可以忽略不计，那么效率的收获会很小。销可以忽略不计，那么效率的收获会很小。v以下情况不宜用内联以下情况不宜用内联:如果函数体内的代码比较长，使用内联将导如果函数体内的代码比较长，使用内联将导致内存消耗代价较高。致内存消耗代价较高。如果函数体内出现循环，那么执行函数体内如果函数体内出现循环，那么执行函数体内代码的时间要比函数调用的开销大。代码的时间要比函数调用的开销大。程序设计 cs.sjtu 2011.9程序设计-36v函数函数v自己编写函数自己

24、编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法程序设计 cs.sjtu 2011.9程序设计-37v在传统的在传统的C语言中，不允许出现同名函数。当要语言中，不允许出现同名函数。当要求写一组功能类似、参数类型或参数个数不同求写一组功能类似、参数类型或参数个数不同的函数时，必须给它们取不同的函数名的函数时，必须给它们取不同的函数名 v例如某个程序要求找出一组数据中的最大值，例如某个程序要求找出一组数据

25、中的最大值，这组数据最多有这组数据最多有5个数据。我们必须写四个函数：个数据。我们必须写四个函数：求两个值中的最大值、求三个值中的最大值、求两个值中的最大值、求三个值中的最大值、求四个值中的最大值和求五个值中的最大值。求四个值中的最大值和求五个值中的最大值。我们必须为这四个函数取四个不同的函数名，我们必须为这四个函数取四个不同的函数名，例如：例如：max2,max3,max4和和max5。程序设计 cs.sjtu 2011.9程序设计-38v使参数个数不同、参数类型不同或两者兼使参数个数不同、参数类型不同或两者兼而有之的两个以上的函数取相同的函数名而有之的两个以上的函数取相同的函数名 v如如i

26、nt max(int a1,int a2);int max(int a1,int a2,int a3);int max(int a1,int a2,int a3,int a4);int max(int a1,int a2,int a3,int a4,int a5);程序设计 cs.sjtu 2011.9程序设计-39v由编译器确定某一次函数调用到底是调用了哪一由编译器确定某一次函数调用到底是调用了哪一个具体的函数。这个过程称之为绑定（个具体的函数。这个过程称之为绑定（binding，又称为联编或捆绑）。又称为联编或捆绑）。v编译器首先会为这一组重载函数中的每个函数取编译器首先会为这一组重载函数

27、中的每个函数取一个不同的内部名字。当发生函数调用时，编译一个不同的内部名字。当发生函数调用时，编译器根据实际参数和形式参数的匹配情况确定具体器根据实际参数和形式参数的匹配情况确定具体调用的是那个函数，将这个函数的内部函数名取调用的是那个函数，将这个函数的内部函数名取代重载的函数名。代重载的函数名。程序设计 cs.sjtu 2011.9程序设计-40v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递

28、归的算法基于递归的算法程序设计 cs.sjtu 2011.9程序设计-41v如果一组重载函数仅仅是参数的类型不一样，程如果一组重载函数仅仅是参数的类型不一样，程序的逻辑完全一样，那么这一组重载函数可以写序的逻辑完全一样，那么这一组重载函数可以写成一个函数模板。成一个函数模板。v所谓的函数模板就是实现类型的参数化（泛型所谓的函数模板就是实现类型的参数化（泛型化），即把函数中某些形式参数的类型定义成参化），即把函数中某些形式参数的类型定义成参数，称为模板参数数，称为模板参数 v在函数调用时，编译器根据实际参数的类型确定在函数调用时，编译器根据实际参数的类型确定模板参数的值，生成不同的模板函数。模板

29、参数的值，生成不同的模板函数。程序设计 cs.sjtu 2011.9程序设计-42v一一 般的定义形式般的定义形式 template 返回类型返回类型 FunctionName(形式参数表形式参数表)/函数定义体函数定义体 v模板形式参数表可以包含基本数据类型，也可以包模板形式参数表可以包含基本数据类型，也可以包含类类型（需加前缀含类类型（需加前缀class）template T max(T a,T b)return ab?a:b；程序设计 cs.sjtu 2011.9程序设计-43vmaxNum=max(3,7);maxNum=max(3,7);vmaxChar=max(maxChar=ma

30、x(z z,a a););vmaxDouble=max(3.5,4.6);maxDouble=max(3.5,4.6);v函数模板的实例化：函数模板的实例化：根据实际参数确定模板参数的值根据实际参数确定模板参数的值将模板参数的值代入函数模板，形成一个真将模板参数的值代入函数模板，形成一个真正的函数正的函数程序设计 cs.sjtu 2011.9程序设计-44v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数

31、v基于递归的算法基于递归的算法程序设计 cs.sjtu 2011.9程序设计-45v一个标识符能被存一个标识符能被存取的程序部分，称取的程序部分，称为标识符的作用域为标识符的作用域v标识符的作用域与标识符的作用域与程序块有关。所谓程序块有关。所谓的程序块是带有声的程序块是带有声明的复合语句明的复合语句v如右框中有两块如右框中有两块Int main(void)int a=2,b=3;cout a b;int a=4;cout a b;cout a b;程序设计 cs.sjtu 2011.9程序设计-46v在块中说明的标识符是在块中说明的标识符是局部局部的，仅能在本块的，仅能在本块中和内部的块中存

32、取。中和内部的块中存取。v当内部块与外部块有同名标识符时，在内部当内部块与外部块有同名标识符时，在内部块中屏蔽外部块的同名标识符。块中屏蔽外部块的同名标识符。v在一个函数中，我们不能存取主调程序的变在一个函数中，我们不能存取主调程序的变量，即使知道该变量的名字。量，即使知道该变量的名字。v函数参数对该函数也是局部的，可以将它看函数参数对该函数也是局部的，可以将它看成在块内，即函数体内说明的说明的变量。成在块内，即函数体内说明的说明的变量。程序设计 cs.sjtu 2011.9程序设计-47v局部变量：在块内定义的变量称为局部变量，局部变量：在块内定义的变量称为局部变量，即使是即使是main函数

33、中定义的变量也是局部的。函数中定义的变量也是局部的。v全局变量：在所有的函数外面定义的变量称为全局变量：在所有的函数外面定义的变量称为全局变量全局变量作用范围：从定义位置到文件结束。如在作用范围作用范围：从定义位置到文件结束。如在作用范围外的函数要使用此变量，用关键词外的函数要使用此变量，用关键词extern在函数内说在函数内说明此全局变量。明此全局变量。作用：方便函数间的数据传递作用：方便函数间的数据传递v请写出下列程序的执行结果：请写出下列程序的执行结果：程序设计 cs.sjtu 2011.9程序设计-48int p=1,q=5，r=3;int f1()int p=3,r=2;q=p+q+

34、r;cout “f1:p,q,r=“p q r;int f2()p=p+q+r;cout “f2:p,q,r=“p q r p q r;int f3()int q;r=2*r;q=r+p;cout “f3:p,q,r=“p q r;main()f3();cout “after f3:p,q,r=”p q r p q r;f1();cout “after f1:p,q,r=“p q r;f2();cout “after f2:p,q,r=”p q r p q r;结果：结果：f3:p,q,r=1 7 6 after f3:p,q,r=1 5 6 f1:p,q,r=3 10 2 after f1:

35、p,q,r=1 10 6 f2:p,q,r=17 10 6 after f2:p,q,r=17 10 6 程序设计 cs.sjtu 2011.9程序设计-49v全局变量破坏了模块化，建议尽量少使全局变量破坏了模块化，建议尽量少使用用v当全局变量和局部变量同名时，在局部当全局变量和局部变量同名时，在局部变量的作用范围中全局变量被屏蔽。变量的作用范围中全局变量被屏蔽。v全局变量的使用将在模块化设计中详细全局变量的使用将在模块化设计中详细介绍介绍程序设计 cs.sjtu 2011.9程序设计-50v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默

36、认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法程序设计 cs.sjtu 2011.9程序设计-51v在在C+语言中，每个变量有两个属性：语言中，每个变量有两个属性：类型：变量所存储的数据类型类型：变量所存储的数据类型存储类型：变量所存储的区域：存储类型：变量所存储的区域：v标准的变量定义：标准的变量定义：存储类型存储类型 数据类型数据类型 变量名；变量名；v存储类型：存储类型：自动变量：自动变量：auto寄存器变量：寄存器变量：register外部变量：外部变量：exter

37、n静态变量：静态变量：static程序设计 cs.sjtu 2011.9程序设计-52v在函数内或块内定义的变量缺省时是在函数内或块内定义的变量缺省时是auto。如。如auto int i；v当进入块时，系统为自动变量分配空间。当进入块时，系统为自动变量分配空间。当退出块时，系统释放分配给自动变量当退出块时，系统释放分配给自动变量的值。因此自动变量的值就消失了。当的值。因此自动变量的值就消失了。当再次进入该块时，系统重新分配空间。再次进入该块时，系统重新分配空间。程序设计 cs.sjtu 2011.9程序设计-53v存储在寄存器中，代替自动变量或形参，存储在寄存器中，代替自动变量或形参，可以提

38、高变量的访问速度。可以提高变量的访问速度。v如无合适的寄存器可用，则编译器把它如无合适的寄存器可用，则编译器把它设为自动变量。设为自动变量。程序设计 cs.sjtu 2011.9程序设计-54v声明一个不在本模块作用范围内的全局变量。如：声明一个不在本模块作用范围内的全局变量。如：extern int num;num为一个的全局变量。为一个的全局变量。v用途：用途：在某函数中引用了一个声明在本函数后的全局变量时，在某函数中引用了一个声明在本函数后的全局变量时，需要在函数内用需要在函数内用extern声明此全局变量。声明此全局变量。当一个程序有多个源文件组成时，用当一个程序有多个源文件组成时，用

39、extern可引用另一可引用另一文件中的全局变量。文件中的全局变量。程序设计 cs.sjtu 2011.9程序设计-55/#include using namespace std;void f();extern int x;/外部变量的声明外部变量的声明int main()f();cout in main():x=“x endl;return 0;/#include using namespace std;int x;/全局变量的定义全局变量的定义void f()cout in f():x=“x endl;程序设计 cs.sjtu 2011.9程序设计-56v为在整个程序的运行期间都存在的变量

40、为在整个程序的运行期间都存在的变量限定访问范围。限定访问范围。v两类静态变量：两类静态变量：静态的局部变量静态的局部变量静态的外部变量静态的外部变量程序设计 cs.sjtu 2011.9程序设计-57v允许局部允许局部变量保存变量保存它的原有它的原有值，以便值，以便在次进入在次进入块时还可块时还可以使用此以使用此值。值。eg.int f(int a)int b=0;static int c=3;b=b+1;c=c+1;return(a+b+c);void main()int a=2,i;for(i=0;i3;+i)cout f(a);运行结果为：运行结果为：7 8 9 程序设计 cs.sjtu

41、 2011.9程序设计-58v用用static说明的全局变量其他源文件不能说明的全局变量其他源文件不能用用extern引用它引用它v用用extern还可以用在函数定义或说明中。还可以用在函数定义或说明中。该函数只能被用于本源文件中，其他源该函数只能被用于本源文件中，其他源文件不能调用此函数。文件不能调用此函数。程序设计 cs.sjtu 2011.9程序设计-59v未被程序员初始化的静态变量都由系统初未被程序员初始化的静态变量都由系统初始化为始化为0。v局部静态变量的初值是编译时赋的。当运局部静态变量的初值是编译时赋的。当运行时重复调用此函数时，不重复赋初值。行时重复调用此函数时，不重复赋初值。

42、v虽然局部静态变量在函数调用结束后仍然虽然局部静态变量在函数调用结束后仍然存在，但其他函数不能引用它。存在，但其他函数不能引用它。程序设计 cs.sjtu 2011.9程序设计-60void a();void b();void c();void d();main()int x=6;cout“x in main is“x endl;a();b();c();d(x);x+;a();b();c();d(x);cout “x in main is”x endl;void a()int x=25;cout “x in a is”x endl;void b()static int x=50;cout “x

43、 in b is”x+endl;void c()extern int x;x*=10;cout “x in c is”x endl;int x=2;void d(int x)cout “x in d is”+x endl;结果：结果：x in main is 6 x in a is 25 x in b is 50 x in c is 20 x in d is 7 x in a is 25 x in b is 51 x in c 200 x in d is 8 x in main is 7 程序设计 cs.sjtu 2011.9程序设计-61v函数函数v自己编写函数自己编写函数v函数的使用函数的

44、使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法程序设计 cs.sjtu 2011.9程序设计-62v递归程序设计：将一个大问题简化为递归程序设计：将一个大问题简化为同样形同样形式式的较小问题。的较小问题。在一个递归求解中，分解的子问题与最初的问题在一个递归求解中，分解的子问题与最初的问题具有一样的形式具有一样的形式 作为处理问题的工具，递归技术是一种非常有力作为处理问题的工具，递归技术是一种非常有力的工具。利用递归不但可以使

45、得书写复杂度降低，的工具。利用递归不但可以使得书写复杂度降低，而且使程序看上去更加美观而且使程序看上去更加美观v递归调用：在一个函数中直接或间接地调用递归调用：在一个函数中直接或间接地调用函数本身函数本身程序设计 cs.sjtu 2011.9程序设计-63v必须有递归终止的条件必须有递归终止的条件 v函数有与递归终止条件相关的参数函数有与递归终止条件相关的参数v在递归过程中，决定终止条件的参数有在递归过程中，决定终止条件的参数有规略地递增或递减规略地递增或递减 程序设计 cs.sjtu 2011.9程序设计-64v有可对函数的入口进行有可对函数的入口进行测试的基本情况测试的基本情况 if (条

46、件条件)return(不需要递归的简单答案不需要递归的简单答案);else return(递归调用同一函数递归调用同一函数)；基本情况基本情况程序设计 cs.sjtu 2011.9程序设计-65n!=1*2*3*4*(n-1)*n(n-1)!递归形式：递归形式：其他)!1(*01!nnnn递归终止条件递归终止条件long p(int n)if(n=0)return 1;else return n*p(n-1);程序设计 cs.sjtu 2011.9程序设计-66int RaiseIntToPower(int n,int k)if (k=0)return(1);else return(n*Rai

47、seIntToPower(n,k-1);程序设计 cs.sjtu 2011.9程序设计-6700112132435568其他)2()1(1100)(nFnFnnnFint f(int n)if (n=0)return 0;elseif(n=1)return 1;else return(f(n-1)+f(n-2);程序设计 cs.sjtu 2011.9程序设计-68v问题：求解问题：求解n!可以用循环的方法，即从可以用循环的方法，即从1开始，乘开始，乘2，再，再乘乘3-.一直乘到一直乘到n。这种方法容易理解，。这种方法容易理解，也容易实现也容易实现由于由于n!=n(n-1)!(n-1)!数学里定

48、义数学里定义0！1，从而从而n!可以用下面的递归公式表示：可以用下面的递归公式表示：)1()!1()1,0(1!nnnnn程序设计 cs.sjtu 2011.9程序设计-69 int p(int n)if(n=0)return(1);else return(n*p(n-1);程序设计 cs.sjtu 2011.9程序设计-70求求p(4)1)0(*1)1(*2)2(*3)3(*4)4(ppppp递归过程回溯程序设计 cs.sjtu 2011.9程序设计-71v对于大多数常用的递归都有简单、等价对于大多数常用的递归都有简单、等价的迭代程序。究竟使用哪一种，凭你的的迭代程序。究竟使用哪一种，凭你的

49、经验选择。经验选择。v迭代程序复杂，但效率高。迭代程序复杂，但效率高。v递归程序逻辑清晰，但往往效率较低。递归程序逻辑清晰，但往往效率较低。程序设计 cs.sjtu 2011.9程序设计-72int f(int n)if (n=0)return 0;elseif(n=1)return 1;else return(f(n-1)+f(n-2);v实现效率分析：消费的时间是灾难性的！实现效率分析：消费的时间是灾难性的！程序设计 cs.sjtu 2011.9程序设计-73int f(int n)int i,fn,fn_1=0,fn_2=1;if(n=0)return 0;if(n=1)return 1

50、;for(i=2;i=n;+i)fn=fn_1+fn_2;fn_2=fn_1;fn_1=fn;return fn;消耗的时间：执消耗的时间：执行行n n次加法和次加法和3n3n次次赋值！赋值！程序设计 cs.sjtu 2011.9程序设计-74 对递归函数的每次调用都需要内存空间。对递归函数的每次调用都需要内存空间。由于很多调用的活动都是同时进行的，操由于很多调用的活动都是同时进行的，操作系统可能会耗尽可用的内存作系统可能会耗尽可用的内存,避免在处理避免在处理过大的过大的n时产生溢出问题。时产生溢出问题。程序设计 cs.sjtu 2011.9程序设计-75v数字旋转方阵如右数字旋转方阵如右图所

51、示。编程输出图所示。编程输出任意任意N*N的蛇阵。的蛇阵。120 19 18 17 16221 32 31 30 15322 33 36 29 14423 34 35 28 13524 25 26 27 12678910 11程序设计 cs.sjtu 2011.9程序设计-76v先填最外圈，然后再填内部内部的填法同上。先填最外圈，然后再填内部内部的填法同上。也是先填最外圈，再填内部。也是先填最外圈，再填内部。v根据上述思想，可以设计一个递归函数根据上述思想，可以设计一个递归函数fill。该。该函数先填外圈，然后递归调用自己填内部。函数先填外圈，然后递归调用自己填内部。v函数原型：函数原型：vo

52、id fill(int number,int begin,int size)number：表示要填入的起始数据：表示要填入的起始数据 begin：表示要填的起始位置：表示要填的起始位置 size：蛇阵的规模：蛇阵的规模v要生成一个要生成一个6*6的蛇阵只要调用：的蛇阵只要调用：fill(1,0,6)程序设计 cs.sjtu 2011.9程序设计-77int p2020;void fill(int,int,int);int main()int row,col,size;cout size;fill(1,0,size);for(row=0;row size;+row)cout endl;for(c

53、ol=0;col size;+col)cout prowcol t;return 0;程序设计 cs.sjtu 2011.9程序设计-78v自上而下填最左列自上而下填最左列v自左而右填最下行自左而右填最下行v自下而上填最右列自下而上填最右列v自右而左填最上行自右而左填最上行v递归调用递归调用fill，规模减，规模减2，起始位置为原，起始位置为原来的下一行下一列，填入的起始数字为来的下一行下一列，填入的起始数字为填入一圈后的第一个数字。填入一圈后的第一个数字。程序设计 cs.sjtu 2011.9程序设计-79Void fill(int number,int begin,int size)int

54、 i,row=begin,col=begin;if(size=0)return;if(size=1)pbeginbegin=number;return;prowcol=number;+number;for(i=0;isize-1;+i)+row;prowcol=number;+number;for(i=0;isize-1;+i)+col;prowcol=number;+number;for(i=0;isize-1;+i)-row;prowcol=number;+number;for(i=0;isize-2;+i)-col;prowcol=number;+number;fill(number,b

55、egin+1,size-2);程序设计 cs.sjtu 2011.9程序设计-80目标：将A上的盘子全部移到B上规则：每次只能移动一个盘子不允许大盘子放在小盘子上 A B C程序设计 cs.sjtu 2011.9程序设计-81vn4（最开始的情况）（最开始的情况）n4（完成情（完成情况）况）程序设计 cs.sjtu 2011.9程序设计-82v第第1步：从开始的杆到辅助杆（步：从开始的杆到辅助杆（src到到aux）v第第2步：从开始杆到目的杆（步：从开始杆到目的杆（src到到dst）程序设计 cs.sjtu 2011.9程序设计-83v第第3步：从辅助杆到目的杆（步：从辅助杆到目的杆（aux到

56、到dst）v第第4步：从开始的杆到辅助杆（步：从开始的杆到辅助杆（src到到aux）程序设计 cs.sjtu 2011.9程序设计-84v第第5步：从目的杆到开始杆（步：从目的杆到开始杆（dst 到到src）v第第6步：从目的杆到辅助杆（步：从目的杆到辅助杆（dst到到aux）程序设计 cs.sjtu 2011.9程序设计-85v第第7步：从开始杆到目的杆（步：从开始杆到目的杆（src 到到dst）v第第8步：从开始杆到目的杆（步：从开始杆到目的杆（src到到dst）程序设计 cs.sjtu 2011.9程序设计-86v第第9步：从辅助杆到目的杆（步：从辅助杆到目的杆（aux 到到dst）v第

57、第10步：从辅助杆到开始的杆（步：从辅助杆到开始的杆（aux到到src）程序设计 cs.sjtu 2011.9程序设计-87v第第11步：从目的杆到开始杆（步：从目的杆到开始杆（dst 到到src）v第第12步：从辅助杆到目的杆（步：从辅助杆到目的杆（aux 到到dst）程序设计 cs.sjtu 2011.9程序设计-88v第第13步：从开始的杆到辅助杆（步：从开始的杆到辅助杆（src到到aux）v第第14步：从开始杆到目的杆（步：从开始杆到目的杆（src到到dst）程序设计 cs.sjtu 2011.9程序设计-89v第第15步：从辅助杆到目的杆（步：从辅助杆到目的杆（aux 到到dst）程

58、序设计 cs.sjtu 2011.9程序设计-90v最简单的情况，只有一个盘子：将盘子最简单的情况，只有一个盘子：将盘子直接从直接从A移到移到Bv大于一个盘子的情况：大于一个盘子的情况：将除了最下面一个盘子外的所有盘子从将除了最下面一个盘子外的所有盘子从A移到移到C将最下面的盘子从将最下面的盘子从A移到移到B将将C上的盘子移回上的盘子移回B程序设计 cs.sjtu 2011.9程序设计-91void Hanoi(int n,char start,char finish,char temp)if(n=1)cout start finish t;else Hanoi(n-1,start,temp,

59、finish);cout start finish t;Hanoi(n-1,temp,finish,start);程序设计 cs.sjtu 2011.9程序设计-92v只能用递归解决的问题只能用递归解决的问题v引出了可计算性问题：有解决方案的问引出了可计算性问题：有解决方案的问题不一定是可解的题不一定是可解的程序设计 cs.sjtu 2011.9程序设计-93v如给定三个字母如给定三个字母“ABC”，那么可形成，那么可形成的全排列为：的全排列为：ABC,ACB,BAC,BCA,CAB,CBA。试设计一个函数，输入一。试设计一个函数，输入一个字符串，输出该字符串中所有字母的个字符串，输出该字符串

60、中所有字母的全排列全排列程序设计 cs.sjtu 2011.9程序设计-94v如排列如排列“ABCDE”，用递归的思想可以看成：，用递归的思想可以看成：第一个字母为第一个字母为A，后面是，后面是“BCDE”的全排列的全排列l第一个字母为第一个字母为B，后面是，后面是“CDE”的全排列的全排列l第一个字母为第一个字母为C，后面是，后面是“BDE”的全排列的全排列l第一个字母为第一个字母为D，后面是，后面是“BCE”的全排列的全排列l第一个字母为第一个字母为E，后面是，后面是“BCD”的全排列的全排列第一个字母为第一个字母为B，后面是，后面是“ACDE”的全排列的全排列第一个字母为第一个字母为C，

61、后面是，后面是“BADE”的全排列的全排列第一个字母为第一个字母为D，后面是，后面是“BCAE”的全排列的全排列第一个字母为第一个字母为E，后面是，后面是“BCDA”的全排列的全排列程序设计 cs.sjtu 2011.9程序设计-95v用一个字符串存储排列。用一个字符串存储排列。v对对n个字符的排列来讲，第一个元素有个字符的排列来讲，第一个元素有n 种选择，种选择，对每种选择，排列后面对每种选择，排列后面n-1个元素。个元素。vn-1个元素的排列：固定第二个元素个元素的排列：固定第二个元素(n-1种选种选择），排列后面择），排列后面n-2个元素。依此类推。个元素。依此类推。v函数原型可选为：函

62、数原型可选为：void permu(char str,int k)表示排列字符串表示排列字符串str中从中从 k 开始的元素开始的元素v函数的调用：排列字符串中的所有元素可调用函数的调用：排列字符串中的所有元素可调用 permu(char str,0);程序设计 cs.sjtu 2011.9程序设计-96Void PermuteWithFixedPrefix(char str,int k)int i;if(k=strlen(str)cout str endl;else for(i=k;istrlen(str);+i)s,k,i);PermuteWithFixedPrefix(str,k+1);

63、s,k,i);程序设计 cs.sjtu 2011.9程序设计-97void ListPermutations(char str)PermuteWithFixedPrefix(str,0);程序设计 cs.sjtu 2011.9程序设计-98v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法程序设计 cs.sjtu 2011.9程序设计-99v回溯法回溯法 v分治法分治法 v动

64、态规划动态规划 程序设计 cs.sjtu 2011.9程序设计-100v首先暂时放弃问题规模大小的限制，并将问题的首先暂时放弃问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现候选候选解按某种顺序逐一枚举和检验。当发现候选解不可能是解时，就选择下一候选解。如果当前解不可能是解时，就选择下一候选解。如果当前候选解除了不满足规模要求外，满足其他所有要候选解除了不满足规模要求外，满足其他所有要求时，继续扩大当前候选解的规模，并继续试探。求时，继续扩大当前候选解的规模，并继续试探。如果当前的候选解满足包括问题规模在内的所有如果当前的候选解满足包括问题规模在内的所有要求时，该候选解就是

65、问题的一个解。要求时，该候选解就是问题的一个解。v寻找下一候选解的过程成为回朔。寻找下一候选解的过程成为回朔。v扩大当前候选解的规模，并继续试探的过程称为扩大当前候选解的规模，并继续试探的过程称为向前试探。向前试探。v分书问题和八皇后都是典型的回溯法问题分书问题和八皇后都是典型的回溯法问题 程序设计 cs.sjtu 2011.9程序设计-101v在一个在一个8 8*8 8的棋盘上放的棋盘上放8 8个皇后，使个皇后，使8 8个个皇后中没有两个以上的皇后会在同一行、皇后中没有两个以上的皇后会在同一行、同一列或同一对角线上同一列或同一对角线上程序设计 cs.sjtu 2011.9程序设计-102v求

66、解过程从空配置开始，在第一列到第求解过程从空配置开始，在第一列到第m m列为合理配置的基础上再配置列为合理配置的基础上再配置m+1m+1列，直列，直到第到第n n列的配置也时合理时，就找到了一列的配置也时合理时，就找到了一个解。另外在一列上也有个解。另外在一列上也有n n种配置。开始种配置。开始时配置在第一行，以后改变时，顺序选择时配置在第一行，以后改变时，顺序选择第二行、第三行、。、第第二行、第三行、。、第n n行。当配置行。当配置到第到第n n行时还找不到一个合理的配置时，行时还找不到一个合理的配置时，就要回朔，去改变前一列的配置。就要回朔，去改变前一列的配置。程序设计 cs.sjtu 2011.9程序设计-103queen_all(k)for(i=1;i=8;+i)if(皇后放在第皇后放在第i行是可行的行是可行的)在第在第i行放入皇后；行放入皇后；if（k=8）输出解；输出解；else queen_all(k+1);程序设计 cs.sjtu 2011.9程序设计-104v比较直观的方法是采用一个二维数组，但仔细考察，就会比较直观的方法是采用一个二维数组，但仔细考察，就会发现，这种