《高级语言程序设计》课件(下)_第1页
《高级语言程序设计》课件(下)_第2页
《高级语言程序设计》课件(下)_第3页
《高级语言程序设计》课件(下)_第4页
《高级语言程序设计》课件(下)_第5页
已阅读5页,还剩137页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第6章

函数目录定义与调用函数函数的参数传递变量的作用域变量的生存期函数的嵌套调用函数的递归调用排列与组合209:58为什么引入函数在设计复杂的大型程序时,通常将其划分为若干模块,每个模块包含一个或多个函数。函数由一段相对独立的程序组成,这段程序能够实现某一方面独立或完整的功能。一个C/C++程序无论大小,均由一个或多个函数组成。函数是实现程序结构模块化的重要手段,不仅使程序设计变得清晰简洁,而且有利于提高程序的可读性、可复用性和可维护性。一个C/C++程序由一个主函数和若干其他函数构成。由主函数调用其他函数,其他函数可互相调用。3

VS.09:581.定义与调用函数(定义函数)C/C++语言提供了极为丰富的标准函数库,但是并不能满足所有的应用需求。在现实情形中,当需要反复执行某些固定的语句序列时,常将其实现为自定义函数,以提高程序的可读性、可复用性和可维护性。定义函数的一般格式为:返回类型函数名([类型参数1,类型参数2…]){

…… //书写具体语句 return返回值;}返回409:58说明:返回类型函数名([类型参数1,类型参数2…]){…}(1)“返回类型”用于指定函数的类型,即函数返回值的类型,表示调用该函数完成后,应向主调程序返回值的数据类型,在函数体的末尾使用return语句返回函数值;若调用该函数无需返回值则函数可定义为void类型。(2)“函数名”用于指定函数的名字,方便编程人员按名调用,由开发者自已定义,函数的命名规则与变量的命名规则相同。(3)“参数列表”用于指定函数参数的类型和名字,是一组用逗号分隔的类型与名称形式,规定了调用函数时需要接收的参数集合,即使参数列表为空小括号“()”也不能省略。(4)“{}”及其中语句为函数体,用于定义函数的具体功能。函数体可为空,即使函数体为空花括号“{}”也不能省略。函数体中语句可直接操作参数列表中的参数。509:58有参函数与无参函数如果函数需要接收用户传递的数据,那么定义时就要带上参数。例如定义一个函数计算从m加到n的结果,并将该结果返回。intsum(intm,intn){ for(inti=m+1;i<=n;i++) m+=i; returnm;}如果函数无需接收用户传递的数据,那么可将其定义为无参函数。例如voidhello(){ printf("Hello,world\n"); //没有返回值就不需要return语句}609:58调用函数调用函数的一般格式为:函数名(实参列表)函数调用常出现在函数调用语句、函数表达式、函数参数等多种场合。(1)函数调用语句:函数调用语句是将函数调用单独作为一个语句,如“printf_star();”,此时不需要函数返回值,只要求函数完成特定的操作。(2)函数表达式:函数调用出现在表达式中就构成函数表达式,如“c=max(a,b);”中函数调用max(a,b)返回值赋给变量c,此时要求函数调用返回确定值参加表达式的运算。(3)函数参数:函数调用也可作为另一函数调用时的实参,如“m=max(a,max(b,c));”中函数调用max(b,c)就是作为一个参数使用,又如“printf(″%d″,max(a,b));”亦是如此。709:58函数必须遵循“先定义、后使用”或“先声明、后调用”的使用原则。#include<iostream>usingnamespacestd;intadd(intx,inty){

//函数定义 returnx+y;}intmain(){ inta=2,b=3,sum; sum=add(a,b); //函数调用 cout<<sum<<endl; return0;}8#include<iostream>usingnamespacestd;intadd(intx,inty);

//函数声明intmain(){

inta=2,b=3,sum; sum=add(a,b);//函数调用 cout<<sum<<endl; return0;}intadd(intx,inty){

//函数定义 returnx+y;}09:58

#include<iostream>#include<cmath>usingnamespacestd;intprime(intn);intmain(){ intm,n; cin>>m>>n; for(inti=m;i<=n;i++){ if(prime(i))cout<<i<<""; }return0;}intprime(intn){ inti,k=sqrt(n); for(i=2;i<=k;i++){ if(n%i==0)break; } if(n!=1&&i>k)return1; elsereturn0;}909:58

#include<iostream>usingnamespacestd;intfact(intn);intmain(){ intm,k; cin>>m>>k; cout<<fact(m)/fact(k)/fact(m-k);return0;}intfact(intn){ if(n==0)return1; intm=1; for(inti=2;i<=n;i++)m=m*i;

returnm;}1009:58例6.3:一个正整数,如果从左向右读和从右向左读是一样的,这样的数就叫回文数。输入两个整数m和n(m<n),输出区间[m,n]之间的回文数。

输入:输入两个正整数m和n,输入保证m<n。

输出:按从小到大的顺序,输出m到n之间的回文数,每个数后面有一个空格。#include<iostream>usingnamespacestd;inthw(intn);intmain(){ intm,n; cin>>m>>n; for(inti=m;i<=n;i++) if(hw(i))cout<<i<<"";

return0;}inthw(intn){ intnum=n,sum=0; while(num){ sum=sum*10+num%10; num=num/10; } if(n==sum)return1; elsereturn0;}1109:58

#include<iostream>usingnamespacestd;stringd2k(intn,intk);intmain(){ intn,k; cin>>n>>k; if(n>=0)cout<<d2k(n,k); elsecout<<"-"<<d2k(-n,k); return0;}

stringd2k(intn,intk){ strings; while(n){ charc=n%k+'0'; s=c+s; n=n/k; } returns;}1209:582.

函数的参数传递(形参与实参)C/C++中函数的参数会出现在两个地方,分别是函数定义处和函数调用处。(1)在函数定义处出现的参数可以看做是一个占位符,它没有数据,只能等到函数被调用时接收传递进来的数据,故称为形式参数,简称形参。(2)函数调用处给出的参数包含了实实在在的数据,故称为实际参数,简称实参。形参与实参的功能是传递数据,当发生函数调用时实参的值会传递给形参。形参与实参的区别和联系:(1)形参变量只有在函数被调用时才会分配内存,调用结束后,所占用内存立刻释放,所以形参变量只在本函数内部有效,不能在本函数外部使用。(2)实参可以是常量、变量、表达式、函数等,无论实参是何种类型的数据,在进行函数调用时,它们都必须有确定的值,以便在函数调用时将实参值传递给形参。(3)实参和形参在数量上、类型上、顺序上必须严格一致,否则会发生“类型不匹配”的错误。如果能够进行自动类型转换,或者进行了强制类型转换,等同视为类型匹配。(4)形参和实参虽然可以同名,但它们之间互相独立,互不影响,因为实参起作用的范围是在函数外部,而形参是在函数内部有效。返回1309:58形参和实参虽然可以同名,但它们之间互相独立,互不影响。#include<iostream>usingnamespacestd;intsum(intm,intn){

inti;

for(i=m+1;i<=n;++i)

m+=i;

returnm;}intmain(){

intm,n,total;

cout<<"Inputtwonumbers:"<<endl; cin>>m>>n;

total=sum(m,n);

cout<<"m="<<m<<endl;

cout<<"total="<<total<<endl;

return0;}运行结果:Inputtwonumbers:1100↙m=1total=5050

调用sum()函数后,sum()函数内部形参m的值已经发生了变化,而sum()函数外部的实参m的值依然保持不变,可见它们是相互独立的两个变量,除了实参值传递给形参的一瞬间,其它时候并无关联。1409:58参数的传递:调用有参函数时,主调函数与被调函数之间存在数据传递关系。按参数传递机制的不同,参数传递可分为传值、传地址和传引用三种方式。1.传值:按传值方式,数据仅是从主调函数传递给被调函数,而无法实现双向传递。假设需要编写一个函数swap用于交换两个变量的值,则不能利用传值方式实现。试分析如下程序。#include<iostream>usingnamespacestd;voidswap(intx,inty){ inttemp=x; x=y; y=temp;}intmain(){ inta=1,b=2; swap(a,b); cout<<a<<""<<b<<endl; return0;}函数调用的过程如下:(1)函数调用前形参x,y并不占用内存中的存储单元,当执行函数调用swap(a,b)时,形参x,y才被临时分配内存单元;(2)函数调用时实参a,b的值分别传递给形参x,y,此时即可利用形参x,y进行有关运算;(3)函数调用结束后,形参单元x,y被释放。注意:形参x,y的值发生改变,不会影响到实参a,b的值。因为实参与形参是两个不同的存储单元。在此方式中,数据传递仅是从实参单向传递到形参,称为“传值”方式。1509:582.传地址:按传递值方式,执行函数调用swap(a,b)并不能交换a、b值,因为在函数内部,x、y分别是a、b的一个拷贝,x、y的值改变并不会影响到a、b。正确的swap函数实现方法需要使用指针。试分析如下程序。#include<iostream>usingnamespacestd;voidswap(int*x,int*y){ inttemp=*x; *x=*y; *y=temp;}intmain(){ inta=1,b=2; swap(&a,&b); cout<<a<<""<<b<<endl; return0;}函数调用的过程:(1)当执行函数调用swap(&a,&b)时,作为形参的指针变量x、y分别被赋值为a、b的地址,而不是像值传递那样将实参的值拷贝给形参变量;(2)函数调用执行过程中,指针x和y指向的地址没变,但所指向地址中的值发生改变,即a、b的值发生改变,a和b的值成功实现交换。注意:

此种方式中,数据实现了从主调函数到被调函数、再从被调函数到主调函数的双向传递。这种实参为地址、形参为指针的方式称为“传地址”方式。1609:583.传引用:除此之外,C++扩充C增加了引用的参数传递机制。定义函数时,若在形参类型与形参名之间添加符号“&”,则该形参为引用参数。按传递引用的方式,执行函数调用时实参与形参间采用双向的数据传递机制,此时实参不能是常量或表达式。试分析以下程序。#include<iostream>usingnamespacestd;voidswap(int&x,int&y){ inttemp=x; x=y; y=temp;}intmain(){ inta=1,b=2; swap(a,b); cout<<a<<""<<b<<endl; return0;}在此方式中,形参与实参绑定,故能实现数据从主调函数到被调函数、再从被调函数到主调函数的双向传递。这种形参为实参别名的参数传递方式称为“传引用”。注意:引用创建时必须初始化,不能为空,不能改变指向。1709:58传引用与传地址两种参数传递方式均能实现数据的双向传递,但前者还有其他两个优点:(1)不用为形参额外分配存储空间;(2)程序编写更为简洁方便。不过,也存在一些特定的场合仅适用指针方式,以下为一些适合使用指针的情形:(1)若一个指针指向不定,或者在中途需要改变其指向;(2)有时一个指针可能是空指针,例如当把指针作为函数的参数类型或返回类型时;(3)使用函数指针,由于没有函数引用,所以函数指针无法被引用替代;(4)使用new创建的对象或数组,需要用指针来存储它的地址;(5)以数组形式传递大批量数据时,需要用指针类型接受参数。1809:583.变量的作用域变量的作用域是指变量有效可用的代码范围。有些变量可以在整个程序或其他程序中被引用,而有些变量则只能在局部范围内引用。因此,变量按照作用域范围的不同可分为局部变量和全局变量。返回1909:583.1局部变量局部变量也称为内部变量,局部变量在函数内部定义,其作用域仅限于所定义函数内。定义局部变量的场合有两种情形:在函数内定义、在函数内的复合语句中定义。(1)在函数内定义:函数内部定义的变量只在本函数范围内有效,即只有在本函数内才能引用它们,在此函数之外不能使用这些变量。(2)在函数内的复合语句中定义:复合语句中定义的变量只在本复合语句范围内有效,该复合语句外不能使用这些变量。无论在在函数内定义变量,还是在函数内的复合语句中定义变量,均是在函数内定义变量,此时定义的变量称为局部变量。2009:58

21a,b,c有效范围x,y,i,j有效范围m,n有效范围

a,b在此有效范围c在此复合语句内有效09:583.2全局变量

22全局变量p,q,n的作用域全局变量d,e的作用域注意:若局部变量和全局变量同名,则在该局部变量的作用域中,起作用的是局部变量,全局变量不起作用。例如main函数中定义的局部变量n和全局变量n同名,那么主函数中语句“n++;”是将局部变量n的值改为7,全局变量n的值仍为1不会受到影响。09:58全局变量增加了函数间数据联系的渠道。由于同一文件中的所有函数都能引用全局变量的值,因此如果在一个函数中改变了全局变量的值,就能影响到其他函数中的全局变量取值。相当于函数间有直接的数据传递通道。但是非必要不建议使用全局变量,原因如下:(1)全局变量在程序全部执行过程中均占用存储单元,而不是仅在需要时开辟单元。(2)各函数均可引用全局变量,导致了函数间的强耦合性,降低了函数的通用性。(3)全局变量降低程序的清晰性,难以清晰地判断每个瞬时各个全局变量的取值。(4)若全局变量与局部变量同名,则在该局部变量作用域内,同名全局变量被屏蔽。若要引用全局变量,则须在变量名前加上域限定符“::”。2309:584.变量的生存期变量的生存期是指变量从生成到被撤销的这段时间,实际上就是变量占用内存的时间。生存期和作用域是从时间和空间这两个不同的角度来描述变量的特性,两者之间既存在联系、又相互区别。一个变量的生存期如何,并不能仅从其作用域来判断,还应有明确的存储类型说明。C语言中变量的存储类型有四种:auto,static,register,extern。返回2409:584.1自动变量自动变量用关键字auto作存储类别声明。自动变量属于动态存储方式,动态存储是指在程序运行期间根据需要动态分配存储空间的方式。若某程序中包含若干函数,在程序执行过程中先后调用各个函数,则调用函数时会动态地分配和释放存储空间。例如:intf(inta){ autointb=3; //定义b为自动变量

……}a是形参,b是自动变量,均为动态存储方式。执行完f函数后,自动释放a,b所占的存储单元。关键字auto可以省略,auto不写则隐含默认为“自动存储类型”。2509:584.2静态变量静态变量用关键字static作存储类别声明。静态变量属于静态存储方式,静态存储方式是指在程序运行期间分配固定的存储空间的方式。对于静态全局变量,在程序开始执行时为其分配存储空间,程序执行完毕才释放该空间,在程序执行过程中它们占据固定的存储单元。有时希望函数中的局部变量的值在函数调用结束后不消失而继续保留原值,即其占用的存储单元不释放,在下一次再调用该函数时,该变量已有值(就是上一次函数调用结束时的值)。这时就应指定该局部变量为“静态局部变量”,用关键字static进行声明。2609:58考查静态局部变量的值#include<stdio.h>intmain(){ intf(int); //函数声明 inta=2,i; //自动局部变量 for(i=0;i<3;i++) printf("%d\n",f(a)); return0;}intf(inta){ autointb=0; //自动局部变量 staticintc=3; //静态局部变量 b=b+1; c=c+1; return(a+b+c);}27静态变量与自动变量的值的比较分析第几次调用调用时初值调用结束时的值bcbca+b+c第1次03147第2次04158第3次0516909:58静态局部变量说明(1)静态局部变量属于静态存储类别,在静态存储区内分配存储单元,程序整个运行期间不释放。动态局部变量属于动态存储类别,分配在动态存储区,函数调用结束后即释放。(2)静态局部变量在编译时赋初值,只赋初值一次,在程序运行时它已有初值。以后每次调用函数时不再重新赋初值而只是保留上次函数调用结束时的值。而对自动变量赋初值不是在编译时进行,而是在函数调用时进行,每调用一次函数重新赋一次初值。(3)如果在定义局部变量时不赋初值,则对静态局部变量来说,编译时自动赋初值0(对数值型变量)或空字符′\0′(对字符变量)。而对自动变量来说,每次函数调用结束后存储单元已释放,下次调用时又重新分配存储单元,故所分配单元中的内容不确定。(4)虽然静态局部变量在函数调用结束后仍然存在,但其他函数是不能引用它。因为它是局部变量,只能被本函数引用,而不能被其他函数引用。2809:58将外部变量的作用域限制在本文件中有时在程序设计中希望某些外部变量只限于被本文件引用,而不能被其他文件引用。这时可以在定义外部变量时加一个static声明。这种加上static声明、只能用于本文件的外部变量称为静态外部变量。在程序设计中,常由若干人分别完成各个模块,各人可以独立地在其设计的文件中使用相同的外部变量名而互不相干。只须在每个文件中定义外部变量时加上static即可。这就为程序的模块化、通用性提供方便。如果已确认其他文件不需要引用本文件的外部变量,就可以对本文件中的外部变量都加上static,成为静态外部变量,以免被其他文件误用。至于在各文件中的函数内部定义的局部变量,本来就不能被函数外引用,更不能被其他文件引用。29

file1.c

file2.c09:58不要误认为对外部变量加static声明后才采取静态存储方式(存放在静态存储区中),而不加static的是采取动态存储(存放在动态存储区)。声明局部变量的static存储类型和声明全局变量的static存储类型的含义是不同的。对于局部变量来说,声明存储类型的作用是指定变量存储的区域(静态存储区或动态存储区)以及由此产生的生存期的问题,而对于全局变量来说,由于都是在编译时分配内存的,都存放在静态存储区,声明存储类型的作用是变量作用域的扩展问题。用static声明一个变量的作用是:(1)对局部变量用static声明,把它分配在静态存储区,该变量在整个程序执行期间不释放,其所分配的空间始终存在。(2)对全局变量用static声明,则该变量的作用域只限于本文件模块(即被声明的文件中)。3009:584.3寄存器变量C/C++中使用关键字register来声明局部变量为寄存器变量。寄存器变量的值会被存放在CPU的寄存器中,当需要时CPU就可以直接使用,而无须再通过控制器从内存中获取。由于操作寄存器的速度远高于操作内存,所以使用寄存器变量可有效地提高程序运行效率。注意:①只有局部自动变量和形式参数才能够被定义为寄存器变量,全局变量和局部静态变量都不能被定义为寄存器变量。②一个计算机中寄存器数量是有限的,寄存器变量的数量不能太多,否则编译程序会自动地将寄存器变量变为自动变量。③受硬件限制,寄存器变量只能是char、int或指针型,而不能使其他复杂数据类型。④因register变量使用的是CPU中的寄存器,故不能使用取地址运算符"&"求寄存器变量的地址。现今的优化编译系统能够识别使用频繁的变量,从而自动地将这些变量放在寄存器中,而无需程序设计者指定,因此,实际上使用register变量的必要性不大。3109:584.4extern变量一般来说,外部变量是在函数的外部定义的全局变量,它的作用域是从变量的定义处开始,到本程序文件的末尾。在此作用域内,全局变量可以为程序中各个函数所引用。但有时程序设计人员希望能扩展外部变量的作用域。如果外部变量不在文件的开头定义,其有效的作用范围只限于定义处到文件结束。在定义点之前的函数不能引用该外部变量。若需要在定义点之前的函数引用该外部变量,则应该在引用之前用关键字extern对该变量作“外部变量声明”,表示把该外部变量的作用域扩展到此位置。有了此声明,就可以从“声明”处起合法地使用该外部变量。3209:58调用函数,求3个整数中的大者#include<stdio.h>intmain(){ intmax();

externintA,B,C; //把外部变量A,B,C的作用域扩展到从此处开始 printf("Pleaseenterthreeintegernumbers:"); scanf("%d%d%d",&A,&B,&C); //输入3个整数给A,B,C printf("maxis%d\n",max()); return0;}intA,B,C; //定义外部变量A,B,Cintmax(){ intm=A>B?A:B; //把A和B中的大者放在m中 if(C>m)m=C; //将A,B,C三者中的大者放在m中 return(m); //返回m的值}3309:58如果一个程序包含两个文件,在两个文件中都要用到同一个外部变量Num,不能分别在两个文件中各自定义一个外部变量Num,否则在进行程序的连接时会出现“重复定义”的错误。正确的做法是:在任一个文件中定义外部变量Num,而在另一文件中用extern对Num作“外部变量声明”,即“externNum;”。在编译和连接时,系统会由此知道Num有“外部链接”,可以从别处找到已定义的外部变量Num,并将在另一文件中定义的外部变量Num的作用域扩展到本文件,在本文件中可以合法地引用外部变量Num。

3409:585.函数的嵌套调用在定义函数时,一个函数内不能再定义另一个函数,即不能嵌套定义函数,但可以嵌套调用函数,即在调用一个函数的过程中,又调用另一个函数。例6.5:输入三个整数a、b、c,求三个整数中的最大数。输入:输入三个整数a、b、c。输出:输出三个整数中的最大数。#include<iostream>usingnamespacestd;intmax2(inta,intb){ returna>b?a:b;}intmax3(inta,intb,intc){ returnmax2(max2(a,b),c);}intmain(){inta,b,c,max;cin>>a>>b>>c;max=max3(a,b,c);cout<<max<<endl;return0;}返回3509:58例6.15:输入多个测试用例,每个测试用例为一日期,输出该日期是所在年的第几天。

输入:输入多个测试用例,每个测试用例为一日期,每个测试用例占一行。

输出:对每个测试用例输出该日期是所在年的第几天,每个输出占一行。#include<iostream>usingnamespacestd;boolIsLeap(intyear){return(year%4==0&&year%100!=0||year%400==0);}intGetDay(intyear,intmonth,intday){ intleap=IsLeap(year); intshift[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31}, {0,31,29,31,30,31,30,31,31,30,31,30,31}}; for(inti=1;i<month;i++) day+=shift[leap][i]; returnday;}intmain(){ intyear,month,day; while(cin>>year>>month>>day) cout<<GetDay(year,month,day)<<endl; return0;}36main函数

GetDay函数IsLeap函数①

②

③

④调用GetDay调用IsLeap ⑤⑨

⑧

⑦

⑥结束09:58例6.16:二代身份证由18位组成,最后一位为校验位。其计算方法是:前17位分别乘以权重Wi(从左边开始数各位的Wi分别为{7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2,1}),乘积之和除11得余数,再将余数0-10分别转换为{1,0,X,9,8,7,6,5,4,3,2}(即0转换为1,1转换为0,2转换为X,3转换为9……),即为校验位的值。编写程序,输入一个身份证号,计算其检验位的值,与最后一位比较验证其是否正确,若正确输出出生日期,错误则输出“Fail”。#include<iostream>usingnamespacestd;intcheck(char*s){ intsum=0,w[20]={7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2,1}; chara[15]="10X98765432"; for(inti=0;i<17;i++)sum+=(s[i]-'0')*w[i]; sum%=11; returna[sum]==c[17];}intmain(){

chars[20];

gets(s); if(check(c))for(inti=6;i<14;i++)cout<<s[i]; elsecout<<"Fail"<<endl; return0;}3709:58例6.17:编写toArray函数,其函数原型为inttoArray(char*str,charc,intarr[]);将字符串str用c所指定的分隔符分割并转换为整型数后填入整型数组arr,函数值为该数组元素个数。例如将“512,34,288”用’,’分割的结果是:整型数组中包含512,34,288三个元素。编写测试程序,输入字符串,调用toArray函数,打印输出该字符串及转换结果。#include<iostream>#include<cstring>usingnamespacestd;intcnt;inttoArray(char*str,charc,intarr[]){ intlen=strlen(str); for(inti=0;i<len;){ arr[cnt]=0; while(str[i]!=c&&str[i]!='\0') arr[cnt]=arr[cnt]*10+str[i++]-'0'; i++;cnt++; } returncnt;}intmain(){ charc=',';

charstr[100];

gets(str); intarr[20]; toArray(str,c,arr); for(inti=0;i<cnt;i++) cout<<arr[i]<<""; return0; }3809:58例6.18:编写一解码程序Hex2Dec把4位16进制字符串转换为整型数,如“FFF8”=-8。

输入:一个4位16进制字符串。

输出:与字符串对应的十进制整数。#include<iostream>usingnamespacestd;intHex2Dec(char*s){ inti,sum=0,flag=1;

if(s[0]>='8'&&s[0]<='9'||s[0]>='A'&&s[0]<='F')flag=-1; for(i=0;i<4;i++)

if(s[i]>='0'&&s[i]<='9')sum=sum*16+s[i]-'0'; elsesum=sum*16+s[i]-'A'+10; if(flag==1)returnsum; elsereturnsum-65536; }intmain(){

chars[5];

gets(s); cout<<Hex2Dec(c)<<endl; return0;}3909:586.函数的递归调用若一个函数的内部操作(函数体)直接或间接地调用了自身,则称此函数称为递归函数。递归函数的函数体包含递进和回归两个部分。(1)为避免无限的递进调用,通常先定义回归部分再定义递进部分;(2)若先定义递进部分,则必须增加条件判断控制递进调用。返回4009:58例6.6:输入一个正整数n,求n!。

输入:输入一个正整数n。

输出:输出n!。#include<iostream>usingnamespacestd;intfac(intn){ if(n==1)return1; returnfac(n-1)*n;}intmain(){ intn; cin>>n; cout<<fac(n)<<endl; return0;}4109:58注意程序中的变量是int型,如果用devC++、GCC以及多数C编译系统为int型数据分配4个字节,能表示的最大数为2147483647,当n=12时,运行正常,输出为479001600。如果输入13,企图求13!,是得不到预期结果的,因为求出的结果超过了int型数据的最大值。可将f,y和fac函数定义为float或double型。例6.7:古代有一个梵塔,塔内有3个座A,B,C。开始时A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个老和尚想把这64个盘子从A座移到C座,但规定每次只允许移动一个盘,并且移动过程中3个座上都始终保持大盘在下,小盘在上。在移动过程中可以利用B座。编程输出移动盘子的步骤。解题思路:

老和尚会这样想:假如有另外一个和尚能有办法将上面63个盘子从一个座移到另一座。那么,问题就解决了。此时老和尚只须这样做:

①命令第2个和尚将63个盘子从A座移到B座;

②自己将1个盘子(最底下的、最大的盘子)从A座移到C座;

③再命令第2个和尚将63个盘子从B座移到C座。第2个和尚又想如果有人能将62个盘子从一个座移到另一座,我就能将63个盘子从A座移到B座,他是这样做的:

①命令第3个和尚将62个盘子从A座移到C座;

②自己将1个盘子从A座移到B座;

③再命令第3个和尚将62个盘子从C座移到B座。4209:58A B CA B C63个盘子①③②例6.7:古代有一个梵塔,塔内有3个座A,B,C。开始时A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个老和尚想把这64个盘子从A座移到C座,但规定每次只允许移动一个盘,并且移动过程中3个座上都始终保持大盘在下,小盘在上。在移动过程中可以利用B座。编程输出移动盘子的步骤。

43A B CA B C63个盘子①③②09:58例6.8:输入两个正整数a、b,求a、b的最大公约数。

输入:输入两个正整数a、b。

输出:输出a、b的最大公约数。#include<iostream>usingnamespacestd;intgcd(inta,intb){ if(b==0)returna; returngcd(b,a%b);}intmain(){ inta,b; cin>>a>>b; cout<<gcd(a,b)<<endl; return0;}4409:58应用:求线段上格点的个数(横纵坐标均为整数的点为格点)

45小三角形边长(4/gcd(4,8),8/gcd(4,8))09:58例6.9:由A,B,C这3个字母就可以组成许多串,比如:"A","AB","ABC","ABA","AACBB"…。现在小明思考一个问题:输入三个正整数a、b、c,代表最多可以选择a个A,b个B,c个C字母,能组成多少个不同的长度为n的字符串呢?输入:输入三个正整数a、b、c、n。输出:输出能组成多少个不同的长度为n的串。#include<iostream>usingnamespacestd;intf(inta,intb,intc,intn){ if(a<0||b<0||c<0)return0; if(n==0)return1; returnf(a-1,b,c,n-1)+f(a,b-1,c,n-1)+f(a,b,c-1,n-1);}intmain(){ inta,b,c,n; cin>>a>>b>>c>>n; cout<<f(a,b,c,n)<<endl; return0;}4609:58例6.10:小明面前有n级台阶,如果要求同时满足两个约束条件:①每步1阶或2阶;②必须是偶数步。那么小明从0阶上到n级台阶共有多少种不同的方案数?

输入:输入一个正整数n。

输出:输出同时满足两个条件,上到n级台阶的不同方案数。没有偶数步限制:f(n)=f(n-1)+f(n-2)f(n):必须偶数步g(n):必须奇数步f(n)=g(n-1)+g(n-2)g(n)=f(n-1)+f(n-2)出口:f(n)n==1:0n==2:1g(n)n==1:1n==2:1#include<iostream>usingnamespacestd;intg(intn); //奇数步上到n级台阶intf(intn); //偶数步上到n级台阶intg(intn){ if(n==1||n==2)return1; returnf(n-1)+f(n-2);} intf(intn){ if(n==1)return0; if(n==2)return1; returng(n-1)+g(n-2);}intmain(){ intn; cin>>n; cout<<f(n)<<endl; return0;}4709:58例6.11:小明与其他3人玩牌。一副扑克牌(去掉大小王共52张)均匀发给4个人,每个人13张。这时小明不禁突然想:如果不考虑花色,只考虑点数,也不考虑自己得到的牌的先后顺序,自己手里能拿到的初始牌型组合一共有多少种呢?#include<iostream>usingnamespacestd;intans=0; voidf(intc,intn){ if(n>0&&c<13) for(inti=0;i<=4;i++) f(c+1,n-i); if(n==0){ans++;return;}}intmain(){ f(0,13); cout<<ans<<endl; return0;}4809:58递归结论与思考构成递归需要具备的条件:(1)子问题须与原始问题为同样的事情,且规模更小;(2)不能无限制递归调用,必须有出口使之结束调用。注意:可以用if语句来控制,只有在某条件成立时才继续执行递归调用,否则就不再继续。优缺点:很多不理解递归的人,总认为递归完全没必要,用循环就可以实现,其实这是一种很肤浅的理解。递归调用化繁为简,结构清晰;递归算法相对常用的其它算法运行效率较低;需要保护现场,递归次数过多易造成栈溢出;尽量避免使用递归,除非适合递归的特定情况。4909:58第7章

指针目录定义与引用指针指针与一维数组指针与字符串指针数组与多重数组指针与函数动态内存分配5109:58什么是指针所谓指针,就是内存地址;所谓指针变量,也就是其值为内存地址的变量。不同类型的变量占用不同长度的存储空间,而不同类型的指针变量占用相同长度的存储单元。指针可赋予不同的地址,通过指针可以间接操作其指向的变量。在C/C++语言中,指针变量存储的内容的是其所指向对象的首地址,指向的对象可以是变量、数组、函数等占据存储空间的实体。5209:581.定义与引用指针程序运行时,每个变量都被存放在从某个内存地址开始的若干字节中。所谓“指针”,也称作“指针变量”,其存储内容是它所指向对象的首地址。指针变量的定义方法与普通变量基本相同,唯一的区别是必须在变量前加上一个“*”,表示该变量为指针变量。定义指针变量的一般格式为:类型*指针变量名;例如:inta=1; //①:定义一个整型变量a,赋初值为1int*p; //②:定义一个整型指针变量pp=&a; //③:p指向整型变量a;

②③int*p=&a;*p=3; //④:将p所指向的变量赋值为3,即将a赋值为3返回5309:58例7.1:用指针方法编写一个程序,输入3个整数,将它们按由小到大的顺序输出。

输入:输入以空格分隔的3个整数。

输出:将三个整数按从小到大顺序输出。#include<iostream>usingnamespacestd;voidswap(int*pa,int*pb){ inttemp; temp=*pa; *pa=*pb; *pb=temp;}intmain(){ inta,b,c,temp;

cin>>a>>b>>c; if(a>b)swap(&a,&b); if(a>c)swap(&a,&c); if(b>c)swap(&b,&c); cout<<a<<“”<<b<<“”<<c; return0;}5409:582.

指针与一维数组(2.1指针指向数组元素)一个数组的名字实际上就是一个指针,该指针指向这个数组存放的起始地址。如果定义如下数组:intarray[10];那么标识符“array”的类型就是int*,可以用array给一个int*类型的指针变量赋值。不过,数组名array代表数组的首地址,其值是编译时已确定的常量,不允许对array赋值。返回5509:58例7.2:编写一个使用指针的函数,交换数组a和数组b中的对应元素。

输入:输入包括三行,第一行为一个正整数n,第二行为数组a的n个元素,第三行为数组b的n个元素。

输出:将数组a和数组b中对应的n个元素交换后,输出两行,第一行为数组a的n个元素(以空格分隔),第二行为数组b的n个元素。#include<iostream>usingnamespacestd;constintN=10;voidexchange(int*a,int*b,intn){ inttmp; for(inti=0;i<n;i++){ tmp=a[i];a[i]=b[i];b[i]=tmp; }}intmain(){ intx[N],y[N]; intn; cin>>n;5609:58例7.2:编写一个使用指针的函数,交换数组a和数组b中的对应元素。

输入:输入包括三行,第一行为一个正整数n,第二行为数组a的n个元素,第三行为数组b的n个元素。

输出:将数组a和数组b中对应的n个元素交换后,输出两行,第一行为数组a的n个元素(以空格分隔),第二行为数组b的n个元素。 for(inti=0;i<n;i++) cin>>x[i]; for(inti=0;i<n;i++) cin>>y[i]; exchange(x,y,n); for(inti=0;i<n;i++) cout<<x[i]<<“”; cout<<endl; for(inti=0;i<n;i++) cout<<y[i]<<“”; cout<<endl;}5709:582.2指针的运算指针方式引用数组元素时,常使用指针的算术运算操作。指针可进行以下算术运算操作:(1)同类型的指针之间可以比较大小;(2)同类型的指针可以进行相减;(3)指针变量可以加减整型变量或常量;(4)指针变量可以自增、自减。如果p1、p2是两个同类型“T*”的指针,那么当“地址p1<地址p2”时表达式“p1<p2”为真,反之为假。p1>p2、p1==p2含义类推。如果p1和p2是两个同类型“T*”的指针,那么表达式“p2–p1”表示在地址p1和p2之间能够存放多少个T类型的变量。即p2–p1=(地址p2-地址p1)/sizeof(T)。如果p是一个“T*”类型的指针,n是一个整型变量或常量,那么表达式“p+n”是一个类型为T*的指针,该指针指向的地址是:p+n*sizeof(T);“p-n”,“p++”,“p--”类推。5809:58例7.3:编写一个使用指针的程序,输入一个字符串,找出其中的大写字母,小写字母,空格,数字,及其他字符的个数。

输入:输入一个字符串。

输出:输出该字符串中大写字母,小写字母,空格,数字,及其他字符的个数。#include<iostream>usingnamespacestd;intmain(){ inta=0,b=0,c=0,d=0,e=0; char*p,s[100]; cin.getline(s,100);

p=s; while(*p!=0){ if(*p>='A'&&*p<='Z')a++; elseif(*p>='a'&&*p<='z')b++; elseif(*p=='')c++; elseif(*p>='0'&&*p<='9')d++; elsee++; p++; } cout<<a<<""<<b<<""<<c<<""<<d<<""<<e; return0;}5909:582.3指针变量作为函数参数数组、动态分配的内存等均是系列数据的集合,无法将其通过一个基本数据类型参数全部传入函数内部。此时可以将该系列数据的起始地址作为实参,将该实参传递给函数定义中的指针变量形参,然后在函数内部通过指针运算符与指针变量访问该系列数据。对于整数、小数、字符等基本类型数据的操作有时也必须要借助指针,一个典型的例子就是交换两个变量的值。该例使用指针变量作为函数形参,以接收发生函数调用时从函数外部传入的地址实参,从而可在函数内部以指针方式间接访问函数外部的数据,这些数据不会随着函数调用的结束而被销毁。6009:58

≡例7.4:编写一个使用指针作为形参的函数,实现数组元素的逆置。

输入:输入两行,第一行为一个正整数n,第二行为a数组的n个元素,以空格分隔。

输出:将a数据元素逆置后输出,元素间以空格分隔。#include<iostream>usingnamespacestd;constintN=10;voidinverse(int*x,intn);intmain(){ intn,a[N]; cin>>n; for(inti=0;i<n;i++)cin>>a[i]; inverse(a,n); for(inti=0;i<n;i++)cout<<a[i]<<""; return0;}voidinverse(int*x,intn){ int*p,*i,*j; intt; intm=(n-1)/2; i=x;j=x+n-1;p=x+m; for(;i<=p;i++,j--) t=*i,*i=*j,*j=t;}6109:583.指针与字符串字符串常量的类型是char*,字符数组名的类型当然也是char*。因此可以用一个字符串或一个字符数组名,给一个char*类型的指针变量赋值。返回6209:58#include<stdio.h>intmain(){ charstring[]="IloveChina!"; //定义字符数组sting printf("%s\n",string); //用%s格式声明输出string,可以输出整个字符串

printf("%c\n",string[7]); //用%c格式输出一个字符数组元素

return0;}#include<stdio.h>intmain(){ char*string="IloveChina!";

//定义字符指针变量string并初始化

printf("%s\n",string);

//输出字符串

return0;}例7.5:编写函数实现两个字符串的比较。函数原型为:intstrcmp(char*p1,char*p2)

设置p1指向字符串s1,p2指向字符串s2。要求:当s1=s2时返回值为0;当s1不等于s2时返回它们两者的第一个不同字符的ASCII码差值(如”boy”与”bad”,第二个字母不同,’o’与’a’之差为79-65=14);如果s1>s2则输出正值,如果s1<s2则输出负值。#include<iostream>usingnamespacestd;intstrcmp(char*p1,char*p2);intmain(){ intm; chars1[100],s2[100],*p1,*p2; scanf(“%s”,str1); scanf(“%s”,str2); p1=&s1[0]; p2=&s2[0]; m=strcmp(p1,p2); cout<<m; return0;}intstrcmp(char*p1,char*p2){ inti=0; while(*(p1+i)==*(p2+i)) i++; if(*(p1+i)==0&&*(p2+i)==0)return0;

return*(p1+i)-*(p2+i);}6309:58例7.6:使用指针实现字符串复制函数voidstrcpy(char*s1,char*s2)。

输入:输入包括两行,分别为字符串s1和s2。

输出:将s1赋值为s2后,分两行输出s1和s2。#include<iostream>usingnamespacestd;voidstrcpy(char*s1,char*s2){ while(*s2!='\0'){ *s1=*s2; s1++; s2++; } *s1='\0';}intmain(){ chars1[100],s2[100]; cin.getline(s1,100); cin.getline(s2,100); strcpy(s1,s2); cout<<s1<<endl; cout<<s2<<endl; return0;}6409:58例7.7:字符串连接。用指针方式实现字符串连接函数char*StrCat(char*dest,char*src)。

输入:输入包括两行,分别为字符串s1和s2。

输出:把字符串s2复制到字符串s1后面(删除s1原来末尾的“\0”),分两行输出s1和s2。#include<iostream>usingnamespacestd;char*StrCat(char*dest,char*src){

char*pdest=dest;while(*dest){dest++;}

while(*src){*dest=*src;dest++;src++;}*dest='\0';returnpdest;}

6509:58例7.7:字符串连接。用指针方式实现字符串连接函数char*StrCat(char*dest,char*src)。

输入:输入包括两行,分别为字符串s1和s2。

输出:把字符串s2复制到字符串s1后面(删除s1原来末尾的“\0”),分两行输出s1和s2。

intmain(){chars1[200],s2[100];//增大s1的大小以容纳连接后的字符串cin.getline(s1,100); cin.getline(s2,100);StrCat(s1,s2);cout<<s1<<endl;cout<<s2<<endl;return0;}6609:58例7.8:设计函数voidinsert(char*s1,char*s2,char*s,intn),用指针实现在字符串s1中的指定位置n处插入字符串s2得到字符串s。

输入:输入包括三行,前两行分别为字符串s1和s2,第三行为一非负整数n。

输出:s1在位置n处插入s2后的字符串s。#include<iostream>usingnamespacestd;voidinsert(char*s1,char*s2,char*s,intn){ intj=0; for(inti=0;i<n;i++)*s++=*s1++; while(*s2!='\0')*s++=*s2++; while(*s1!='\0')*s++=*s1++; *s='\0';}intmain(){ chars1[100],s2[100],s[200]; cin.getline(s1,100); cin.getline(s2,100); intn; cin>>n; insert(s1,s2,s,n); cout<<s<<endl; return0;}6709:58例7.9:每到月末,小明就会统计本月支出账单,请编程帮助他完成任务。

输入:第一行是整数n(n<100)。然后是n行的账单信息,每一行由物品的名字name和对应的花费c组成,长度不超过200。中间会有一个或多个空格,而每一行的开头和结尾没有空格。0.0<c<1000.0。

输出:输出总的花费,小数点后保留一位数字。#include<iostream>usingnamespacestd;intmain(){ inti,n; doublef,sum=0; stringstr; char*p; cin>>n; getchar(); //吸收整数后面的回车 for(i=0;i<n;i++){ getline(cin,str); p=&str[str.find_last_of("")]; //从后向前查找空格 p++; //指向空格后的数字 sscanf(p,"%lf",&f); //将字符串p转换为实数

//f=atof(p); sum=sum+f; } cout<<sum<<endl; return0;}68输入样例:3Apple2.3Buyclothesforgirlfriends260.5Gotocinema30输出样例:292.809:58doubleatof(char*p){ doublesum=0; while(*p!='\0'&&*p!='.'){ sum=sum*10+*p-'0'; p++; } if(*p=='.'){ p++; intnum=10; while(*p!='\0'){ sum=sum+(*p-'0')*1.0/num; num=num*10; p++; } } returnsum;}sscanf(p,“%lf”,&f); //从字符串p中进行格式化输入sprintf(str,“%d”,n);

//把格式化的数据输出到字符串str中。

6909:584.指针数组与多重数组(4.1指向指针的指针)若一个指针变量存放的是另一个指针变量的地址,则称其为指向指针的指针变量。定义指针的指针的一般格式为:类型**指针变量名;例如:int**p; 语句“int**p;”定义了一个指针变量p,p的类型是“int**”。在此情况下,通常称p为“指针的指针”,因为p指向的是类型为“int*”的指针。同理,“int***p;”…,无论中间多少个“*”都是合法的定义。注意,不论p是几级指针变量,在devc++中均占用4个字节内存空间。返回7009:584.2指针数组一个数组的各个元素均为指针类型数据,则称该数组为指针数组。也就是说,指针数组中的每一个元素都是指针变量。定义指针数组的一般格式为:类型*数组名[常量表达式];例如:char*s[10];因为运算符[]的优先级高于运算符*,所以上述定义也可写成“char*(s[10]);”,即s先和[10]结合,形成s[10]形式,该形式为一个数组格式,共有10个元素;然后再和s前面的*结合,*表示指针类型,即每个数组元素均为一个指向字符数据的指针变量。7109:58例7.10:编写程序,用指针数组在主函数中输入n(n<10)个等长(长度<10)的字符串。用另一函数对它们排序,然后在主函数中输出n个已排好序的字符串。

输入:第一行为1个正整数n(n<10),然后是n行,每行一个字符串。

输出:n行排序后的字符串。#include<iostream>#include<cstring>usingnamespacestd;voidsort(char*s[],intn){ char*temp; inti,j; for(i=0;i<n-1;i++) for(j=0;j<n-1-i;j++) if(strcmp(*(s+j),*(s+j+1))>0)temp=*(s+j),*(s+j)=*(s+j+1),*(s+j+1)=temp;}intmain(){ intn; cin>>n; charstr[10][10],*p[10]; for(inti=0;i<n;i++)p[i]=str[i]; //将第i个字符串的首地址赋给指针数组p的第i个元素 for(inti=0;i<n;i++)scanf("%s",p[i

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论