It計算機課件 第6章 函數(shù)

第6章過程封裝一一函數(shù)

■函數(shù)A■重載函數(shù)

■自己編寫函數(shù)A■函數(shù)模版A

■函數(shù)的使用A■變量的作用域?

■數(shù)組作為參數(shù)A■變量的存儲類別A

■帶默認值的函數(shù)■遞歸函數(shù)?

■內(nèi)聯(lián)函數(shù)■基于遞歸的算法

函數(shù)的用途

■函數(shù)是程序設(shè)計語言中最重要的部分，是模塊

化設(shè)計的主要工具。每一個C++程序都要用到

函數(shù)。

■即使你自己不定義新的函數(shù)，在每一個完整的

C++程序中都必須有一個main。函數(shù)。

■在C++語言中，字符處理、字符串處理和數(shù)學(xué)

計算都是用函數(shù)的方式提供的。

2

函數(shù)的例子

■我們可以將像sin那

樣的函數(shù)想象成一個

黑盒子，或一個小機

器。如果你在它的上

面放入一個“值”，

在它的下面就會掉出

“結(jié)果”

■上面的值稱為參數(shù)，

下面的值稱為返回值

1.0

3

調(diào)用函數(shù)的一個例子

■如果我們改變了輸

，一例X)/\

入的參數(shù)，函數(shù)就/?\\

/：\/\

能返回不同的值。X\/\

■函數(shù)的參數(shù)可以是\/\/

常數(shù)、變量或表達alpha=90°

式。90°120°alphaalpha*3arguments

■圖中我們將調(diào)用4、:邙門,

次sin的結(jié)果加起

I11iI

來，并將其和存入IllirI

變量total中。1.00.8661.0-1.0returnvalues

total=sin(90)+sin(120)+sin(alpha)+sinfalpha*3)

第6章過程封裝一一函數(shù)

■函數(shù)A■重載函數(shù)

■自己編寫函數(shù)A■函數(shù)模版A

■函數(shù)的使用A■變量的作用域?

■數(shù)組作為參數(shù)A■變量的存儲類別A

■帶默認值的函數(shù)■遞歸函數(shù)?

■內(nèi)聯(lián)函數(shù)■基于遞歸的算法

5

如何寫一個函數(shù)

■函數(shù)定義

類型標識符函數(shù)名(形式參數(shù)表)

{變量定義部分1

語句部分,函數(shù)體

)

■函數(shù)的返回值：返回值類型應(yīng)與定義中的類型標識符

一致

return返回值；或return(返回值);

eg.intmax(inta,intb)

{if(a>b)return(a)elsereturn(b);}

■表示一個函數(shù)沒有返回值，類型標識符用void。沒有

返回值的函數(shù)也稱為過程6

函數(shù)舉例一

無參數(shù)、無返回值的函數(shù)

?打印一個由五行組成的三角形

voidprintstarQ

***

*****cout?"*\n”;

cout?“***\n*;

*******66

*********cout?****%"；

coutw*********\n'‘9

coutvv“**********\n"?

7

函數(shù)舉例一有參數(shù)、無返回值的函數(shù)

■打印一個由n行組成的三角形

voidprintstar(numOfLine)

intnunOfLine;voidprintstar(intnumOfLine)

inti,j;

for(i=1;i<=numOfLine;++i)

(

cout?endl;

for(j=1;j<=numOfLine-i;++j)

cout?，'；

for(j=l;j<=2*i-l;++j)

cout?

8

函數(shù)舉例一

有參數(shù)、有返回值的函數(shù)

■計算n!

intp(intn)

(

ints=l,i;

if(n<0)return(O);

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

s*=i;

return(s);

9

函數(shù)舉例一返回布爾量的函數(shù)

■判斷某一年是否為潤年的函數(shù)

boollsLeapYear(intyear)

(

boolleapyear;

leapyear=(((year%4==0)&&(year%100!=0))

||(year%400==0);

return(leapyear);

)10

第6章過程封裝一一函數(shù)

■函數(shù)A■重載函數(shù)

■自己編寫函數(shù)A■函數(shù)模版A

■函數(shù)的使用A■變量的作用域?

■數(shù)組作為參數(shù)A■變量的存儲類別A

■帶默認值的函數(shù)■遞歸函數(shù)?

■內(nèi)聯(lián)函數(shù)■基于遞歸的算法

11

■所有函數(shù)在使用前必須被聲明，以便讓編譯器知道用

戶的用法是否正確。

■函數(shù)聲明包括下列內(nèi)容：

□函數(shù)名

□函數(shù)的參數(shù)類型

□函數(shù)的返回類型

■函數(shù)的聲明被稱為函數(shù)的原型，它的形式為：

返回類型函數(shù)名（參數(shù)表）；

參數(shù)表中的每個參數(shù)說明可以是類型，也可以是類

型后面再接一個參數(shù)名。如：

intmax(int,int);

intmax(inta,intb);12

函數(shù)說明規(guī)則

■庫函數(shù)在調(diào)用前需要#include相應(yīng)的頭文件。

■自定義的函數(shù)在調(diào)用時需要進行函數(shù)原型說明。

■函數(shù)原型說明與函數(shù)首部寫法上需要保持一致，

即函數(shù)類型、函數(shù)名、參數(shù)個數(shù)和參數(shù)順序必須

相同。

■如果被調(diào)函數(shù)的定義在主調(diào)函數(shù)之前，可以不必

加聲明。

■如果在所有函數(shù)定義之前，在函數(shù)外部已經(jīng)做了

函數(shù)聲明，則在主調(diào)函數(shù)中無須再作聲明。

13

#include<iostream.h>(------------------

函數(shù)原型說明

intmax(inta,int

main()

intx,y;

函數(shù)調(diào)用

cin?x?y;

cout?max(x+5,y-3);

intmax(inta,intb)函數(shù)實現(xiàn)

if(a>b)return(a);elsereturn(b);

14

#include<iostream.h>函數(shù)實現(xiàn)，無

.，?.須函數(shù)聲明

intmax(inta,intb)^^===:=::=:^--------------)

(

if(a>b)return(a);elsereturn(b);

main()—=J函數(shù)調(diào)用)

{

intx,y;

cin?x?y;

coutVVmax(x+5,y?3);建議用前一種方式??！

}

15

■函數(shù)調(diào)用形式

函數(shù)名(實際參數(shù)表)

eg.max(x,y)；

■注意：

□形式參數(shù)和實際參數(shù)的個數(shù)、排列次序、類型要完

全相同。

□實際參數(shù)可以是常量、變量、表達式，甚至是另一

個函數(shù)調(diào)用

□傳遞方式：值傳遞

□值傳遞：函數(shù)獲得了主調(diào)程序參數(shù)變量值的拷貝。

被調(diào)程序可以改變這些拷貝，但這對主調(diào)程序的環(huán)

境沒有影響。

函數(shù)調(diào)用

■調(diào)用方式

1.作為語句:printstar();

2.作為表達式的一部分

如要計算5!+4!+7!

x=p(5)+p(4)+p(7)

3.作為函數(shù)的參數(shù)

Printstar(p(5)+p(4)+p(7));

17

函數(shù)執(zhí)行過程

■在主程序中計算每個實際參數(shù)值

■將實際參數(shù)賦給對應(yīng)的形式參數(shù)。在賦值的過程

中完成自動類型轉(zhuǎn)換。

■依次執(zhí)行函數(shù)體的每個語句，直到遇見return語

句或函數(shù)體結(jié)束

■計算return后面的表達式的值，如果表達式的值

與函數(shù)的返回類型不一致，則完成類型的轉(zhuǎn)換。

■用函數(shù)的返回值置換函數(shù)，繼續(xù)主程序的執(zhí)行

18

infp(inf);mainx(2)y(3)

infmax(intQ,intb)

mainx(2)y(3)

main()

maxa(2)b(3)nln2

{intx,y;

cin?x?y;

mainx(2)y(3)

cout?max(x,y);}

maxa(2)b(3)nln2

intp(intn)*

n(2)s1

{ints=1,i;P

if(n<0)return(O);mainx(2)y(3)

for(i=l;i<=n;++i)

maxa(2)b(3)nl(2)n2

s*=i;return(s);}*

Pn(3)s1

intmax(intazintb)mainx(2)y(3)

{intnl,n2;

nl=p(a);n2=p(b);maxa(2)b(3)nl(2)n2(6)

return(n1>n2?nl:n2);}

mainx(2)y(3)

第6章過程封裝一一函數(shù)

■函數(shù)A■重載函數(shù)

■自己編寫函數(shù)A■函數(shù)模版A

■函數(shù)的使用A■變量的作用域?

■數(shù)組作為參數(shù)A■變量的存儲類別A

■帶默認值的函數(shù)■遞歸函數(shù)?

■內(nèi)聯(lián)函數(shù)■基于遞歸的算法

20

數(shù)組作為函數(shù)的參數(shù)

■設(shè)一程序有下列要求：

口讀入一組數(shù)據(jù)到一數(shù)組，直到輸入為。為止

□將數(shù)組的元素倒過來排

存在的問題：

□顯示數(shù)組元素

?輸入的數(shù)據(jù)量是可變的，如何

main()設(shè)置數(shù)組的大??？

{intarray[MAX_NUM];?函數(shù)GetlntegerArray和

GetlntegerArray(array);ReverselntegerArrayX能修改

自己的形式參數(shù)，而不能修改

everselntegerArray(array);

實際參數(shù)。

PrintlntegerArray(list);

?函數(shù)的參數(shù)是數(shù)組，函數(shù)如何

)知道數(shù)組中有效的元素個數(shù)？

21

問題一的解決方案

■在main函數(shù)中定義一個足夠大的數(shù)組。不管

GetlntegerArray中輸入多少數(shù)據(jù)都不會下標

超界

■定義一個變量，指出數(shù)組中真正有多少元素。

這樣在PrintlntegerArray和

ReverselntegerArray函數(shù)中可以根據(jù)這個值

進行操作。因此，要增加一個整型的形式參

數(shù)

22

問題二的解決方案

數(shù)組參數(shù)的傳遞機制

■C++語言規(guī)定，數(shù)組作為參數(shù)傳遞時，傳遞的

是數(shù)組元素的首地址。當用實際參數(shù)array調(diào)

用函數(shù)GerlntegerArray時，是把array的首

地址作為形式參數(shù)數(shù)組的首地址。如array的

首地址為1000,在函數(shù)中形參數(shù)組的首地址

也為1000。因此在函數(shù)中對形參數(shù)組的修改

就是對數(shù)組array的修改。

23

函數(shù)原型的確定

■PrintlntegerArrayReverseIntegerArray需要矢口道哪一個

數(shù)組和數(shù)組里有多少元素。而GetlntegerArray需要知道哪

一個數(shù)組、允許輸入的最大元素個數(shù)，以及輸入結(jié)束字符。

該函數(shù)執(zhí)行結(jié)束后應(yīng)能返回有效的數(shù)據(jù)個數(shù)。

■數(shù)組傳遞本質(zhì)上傳遞的是數(shù)組的起始地址，真正的元素個

數(shù)是通過另一個參數(shù)表示，因此形式參數(shù)中不需要說明數(shù)

組的大小。

voidPrintlntegerArray(intarray[],intCurrentsize);

voidReverselntegerArray(intarray[],intCurrentsize);

intGetlntegerArray(intarray[],intmax,intflag);

24

Main函數(shù)

intmain()

{intlntegerArray[MAX+1],flag,Currentsize;

coutvv”請輸入結(jié)束標記：”；

cin?flag;

Currentsize=ReadIntegerArray(IntegerArray,MAX,flag);

ReverselntegerArray(lntegerArray,Currentsize);

PrintlntegerArray(IntegerArray,Currentsize);

return0;

)

25

ReadlntegerArray

intReadIntegerArray(intarray[],intmax,intflag)

{intsize=0;

cout?”請輸入數(shù)組元素，以"?flag?"結(jié)束：";

while(size<=max){

cin?array[size];

if(array[size]==flag)break;else++size;

}

if(size>max){

cout?”超ii數(shù)組規(guī)?！?endl;

return0;

}

returnsize;

}

26

ReverseIntegerArray

voidReverseIntegerArray(intarray[],intsize)

{inti,tmp;

for(i=0;i<size/2;i++){

tmp=array[i];

array[i]=array[size-i-1];

array[size-i-1]=tmp;

)

)

27

PrintlntegerArray

voidPrintlntegerArray(intarray[],intsize)

{inti;

if(size==0)return;

cout?"逆序是："wendl;

for(i=0;i<size;++i)cout?array[i]?'\t';

cout?endl;

)

28

數(shù)組作為函數(shù)的參數(shù)小結(jié)

■可以將整個數(shù)組傳遞給函數(shù)，這時實際參數(shù)用的

是數(shù)組名。

■數(shù)組傳遞的實質(zhì)是傳遞地址。把實際參數(shù)中的數(shù)

組首地址作為形式參數(shù)中的數(shù)組的首地址

■數(shù)組在函數(shù)中的定義：函數(shù)原型應(yīng)該體現(xiàn)參數(shù)是

一個數(shù)組，所以用無數(shù)組大小定義的方括號表示

數(shù)組。

■對形式參數(shù)數(shù)組指定規(guī)模是沒有意義的。

29

第6章過程封裝一一函數(shù)

■函數(shù)A■重載函數(shù)

■自己編寫函數(shù)A■函數(shù)模版A

■函數(shù)的使用A■變量的作用域?

■數(shù)組作為參數(shù)A■變量的存儲類別A

■帶默認值的函數(shù)A■遞歸函數(shù)?

■內(nèi)聯(lián)函數(shù)■基于遞歸的算法

30

默認參數(shù)

■對于某些函數(shù)，程序往往會用一些固定的值去調(diào)用它.例如

對于以某種數(shù)制輸出整型數(shù)的函數(shù)print：

voidprint(intvalue,intbase);

在大多數(shù)情況下都是以十進制輸出，因此base的值總是

為10。

■C++在定義或聲明函數(shù)時可以為函數(shù)的某個參數(shù)指定默認

值。當調(diào)用函數(shù)時沒有為它指定實際參數(shù)時，系統(tǒng)自動將

默認值賦給形式參數(shù)。例如，可以將print函數(shù)聲明為

voidprint(intvalue,intbase=10);

調(diào)用print(20)等價于print(20,10)

31

帶有默認參數(shù)的函數(shù)的使用

C++在說明函數(shù)原型時，可以為一個或多個參

數(shù)指定缺省值。調(diào)用此函數(shù)時，若缺省某一參

數(shù)，C++自動以缺省值作為此參數(shù)的值。如：

intspecial(intx=2,floaty=l.5)

調(diào)用時可用:

special(5,3.2)//x=5;y=3.2

special(6)//x=6;y=l.5

special()//x=2;y=l.5

32

囂

勺函數(shù)

■缺省參數(shù)無論有幾個，都必須放在參數(shù)序

列的最后，

例如：IntSaveName(charirst,

Charsecond'"'，char*third=,,,\char

*fouth=,n,);

■在函數(shù)調(diào)用時，若某個參數(shù)省略，則其后

的參數(shù)皆應(yīng)省略而取其缺省值

33

帶有默認參數(shù)的函數(shù)

一注意事項

■對參數(shù)默認值的指定只有在函數(shù)聲明處有意義。

因為函數(shù)的默認值是提供給調(diào)用者使用的。

■在不同的源文件中，可以對函數(shù)的參數(shù)指定不同

的默認值。例如對于上面的print函數(shù)，如果在某

一個功能模塊中輸出的大多是十進制數(shù)，那么在

此功能對應(yīng)的源文件中可以指定base的默認值為

10o如果在另一個功能最模塊中經(jīng)常要以二進制

輸出，那么在此功能模塊對應(yīng)的源文件中可以指

定默認值是2。

34

第6章過程封裝一一函數(shù)

■函數(shù)A■重載函數(shù)

■自己編寫函數(shù)A■函數(shù)模版A

■函數(shù)的使用A■變量的作用域?

■數(shù)組作為參數(shù)A■變量的存儲類別A

■帶默認值的函數(shù)A■遞歸函數(shù)?

■內(nèi)聯(lián)函數(shù)A■基于遞歸的算法

35

內(nèi)聯(lián)函數(shù)

■在C程序中，可以用帶參數(shù)的宏。宏本身不是函數(shù)，但

使用起來象函數(shù)。用復(fù)制宏代碼的方式代替函數(shù)調(diào)用可

以提高速度。最大缺點是容易出錯。

■函數(shù)內(nèi)聯(lián)用于取代c語言中帶參數(shù)的宏，其目的是為了

提高執(zhí)行效率。對于任何內(nèi)聯(lián)函數(shù)，編譯器在符號表里

放入函數(shù)的聲明（包括名字、參數(shù)類型、返回值類型）。

如果編譯器沒有發(fā)現(xiàn)內(nèi)聯(lián)函數(shù)存在錯誤，那么該函數(shù)的

代碼也被放入符號表里。在調(diào)用內(nèi)聯(lián)函數(shù)時，編譯器直

接用內(nèi)聯(lián)函數(shù)的代碼替換函數(shù)調(diào)用，于是省去了函數(shù)調(diào)

用的開銷。36

內(nèi)聯(lián)函數(shù)

■目的：減少函數(shù)調(diào)用的開銷

■作用：函數(shù)代碼復(fù)制到程序中

#include<iostream.h>

inlinefloatcube(constfloats)

{returns*s*s;}

intmain()

{floatside;

cin?side;

cout?cube(side)?endls;

return0;}

37

慎用內(nèi)聯(lián)函數(shù)

■內(nèi)聯(lián)以代碼復(fù)制（膨脹）為代價，省去了函數(shù)調(diào)

用的開銷，提高函數(shù)的執(zhí)行效率。如果相比于

執(zhí)行函數(shù)體內(nèi)代碼的時間，函數(shù)調(diào)用的開銷可

以忽略不計，那么效率的收獲會很小。

■以下情況不宜用內(nèi)聯(lián)：

□如果函數(shù)體內(nèi)的代碼比較長，使用內(nèi)聯(lián)將導(dǎo)致

內(nèi)存消耗代價較高。

口如果函數(shù)體內(nèi)出現(xiàn)循環(huán)，那么執(zhí)行函數(shù)體內(nèi)代

碼的時間要比函數(shù)調(diào)用的開銷大。

38

第6章過程封裝一一函數(shù)

■函數(shù)A■重載函數(shù)A

■自己編寫函數(shù)A■函數(shù)模版r>

■函數(shù)的使用A■變量的作用域?

■數(shù)組作為參數(shù)A■變量的存儲類別A

■帶默認值的函數(shù)A■遞歸函數(shù)?

■內(nèi)聯(lián)函數(shù)■基于遞歸的算法

39

重載函數(shù)

■在傳統(tǒng)的C語言中，不允許出現(xiàn)同名函數(shù)。當要

求寫一組功能類似、參數(shù)類型或參數(shù)個數(shù)不同的

函數(shù)時，必須給它們?nèi)〔煌暮瘮?shù)名

■例如某個程序要求找出一組數(shù)據(jù)中的最大值，這

組數(shù)據(jù)最多有5個數(shù)據(jù)。我們必須寫四個函數(shù)：

求兩個值中的最大值、求三個值中的最大值、求

四個值中的最大值和求五個值中的最大值。我們

必須為這四個函數(shù)取四個不同的函數(shù)名，例如：

max2,max3,max4和max5。

40

函數(shù)重載

■使參數(shù)個數(shù)不同、參數(shù)類型不同或兩者兼而

有之的兩個以上的函數(shù)取相同的函數(shù)名

■如

intmax(inta1,inta2);

intmax(inta1,inta2,inta3);

intmax(inta1,inta2,inta3,inta4);

intmax(inta1,inta2,inta3,inta4,inta5);

函數(shù)重載的實現(xiàn)

■由編譯器確定某一次函數(shù)調(diào)用到底是調(diào)用了哪一

個具體的函數(shù)。這個過程稱之為綁定（binding,

又稱為聯(lián)編或捆綁）。

■編譯器首先會為這一組重載函數(shù)中的每個函數(shù)取

一個不同的內(nèi)部名字。當發(fā)生函數(shù)調(diào)用時，編譯

器根據(jù)實際參數(shù)和形式參數(shù)的匹配情況確定具體

調(diào)用的是那個函數(shù)，將這個函數(shù)的內(nèi)部函數(shù)名取

代重載的函數(shù)名。

42

第6章過程封裝一一函數(shù)

■函數(shù)A■重載函數(shù)

■自己編寫函數(shù)A■函數(shù)模版A

■函數(shù)的使用A■變量的作用域?

■數(shù)組作為參數(shù)A■變量的存儲類別A

■帶默認值的函數(shù)A■遞歸函數(shù)?

■內(nèi)聯(lián)函數(shù)■基于遞歸的算法

43

函數(shù)模板

■如果一組重載函數(shù)僅僅是參數(shù)的類型不一樣，程序的

邏輯完全一樣，那么這一組重載函數(shù)可以寫成一個函

數(shù)模板。

■所謂的函數(shù)模板就是實現(xiàn)類型的參數(shù)化（泛型化），

即把函數(shù)中某些形式參數(shù)的類型定義成參數(shù)，稱為模

板參數(shù)

■在函數(shù)調(diào)用時，編譯器根據(jù)實際參數(shù)的類型確定模板

參數(shù)的值，生成不同的模板函數(shù)。

函數(shù)模板的定義

■一般的定義形式

templatev模板形式參數(shù)表〉

返回類型FunctionName（形式參數(shù)表）

{

〃函數(shù)定義體

}

■模板形式參數(shù)表可以包含基本數(shù)據(jù)類型，也可以包

含類類型（需加前綴class）

template<classT>

Tmax(Ta,Tb)

{returna>b?a:b；}

45

第6章過程封裝一一函數(shù)

■函數(shù)A■重載函數(shù)

■自己編寫函數(shù)A■函數(shù)模版A

■函數(shù)的使用A■變量的作用域A

■數(shù)組作為參數(shù)A■變量的存儲類別A

■帶默認值的函數(shù)A■遞歸函數(shù)?

■內(nèi)聯(lián)函數(shù)■基于遞歸的算法

46

標識符的作用域

■一個標識符能被存取

的程序部分，稱為標Intmain(void)

識符的作用域{inta=2,b=3;

cout?a?b;

■標識符的作用域與程

{inta=4;

序塊有關(guān)。所謂的程cout?a?b;

序塊是帶有聲明的復(fù))

合語句cout?a?b;

)

■如右框中有兩塊

47

標識符的作用域一續(xù)

■在塊中說明的標識符是局部的，僅能在本塊中

和內(nèi)部的塊中存取。

■當內(nèi)部塊與外部塊有同名標識符時，在內(nèi)部塊

中屏蔽外部塊的同名標識符。

■在一個函數(shù)中，我們不能存取主調(diào)程序的變量,

即使知道該變量的名字。

■函數(shù)參數(shù)對該函數(shù)也是局部的，可以將它看成

在塊內(nèi)，即函數(shù)體內(nèi)說明的變量。

48

局部變量和全局變量

■局部變量：在塊內(nèi)定義的變量稱為局部變量，即

使是main函數(shù)中定義的變量也是局部的。

■全局變量：在所有的函數(shù)外面定義的變量稱為全

局變量

口作用范圍：從定義位置到文件結(jié)束。如在作用范圍外

的函數(shù)要使用此變量，用關(guān)鍵詞extern在函數(shù)內(nèi)說明

此全局變量。

□作用：方便函數(shù)間的數(shù)據(jù)傳遞

■請寫出下列程序的執(zhí)行結(jié)果:

49

#include<iostream>結(jié)果：

usingnamespacestd;

f3:p,q,r=l76

intp=1,q=5,r=3;

voidfl()afterf3:p,q,r=l56

{intp=3,r=2;

q=p+q+r;cout?"fl:p,q,r="?p?q?r;fl:p,q,r=3102

)

voidf2()afterfl:p,q,r=l106

p=p+q+r;cout?“f2:p,q,r="<<P<<q?八f2:p,q,r=17106

)

void0()afterfl:p,q,r=17106

{intq;r=2*r;q=r+p;

cout?p,q,r="?p?q?r;

)

main()

{B();cout?66afterB:p,q,r=,9<<p<<q<r;

fl();cout?"afterfl:p,q,r="?p?q?r;

6<,9

f2();cout?afterf2:p,q,r=<<p<<q<<r;}50

全局變量的使用說明

■全局變量破壞了模塊化，建議盡量少使用

■當全局變量和局部變量同名時，在局部變

量的作用范圍中全局變量被屏蔽。

■全局變量的使用將在模塊化設(shè)計中詳細介

紹

51

第6章過程封裝一一函數(shù)

■函數(shù)A■重載函數(shù)

■自己編寫函數(shù)A■函數(shù)模版A

■函數(shù)的使用A■變量的作用域A

■數(shù)組作為參數(shù)A■變量的存儲類別A

■帶默認值的函數(shù)A■遞歸函數(shù)?

■內(nèi)聯(lián)函數(shù)■基于遞歸的算法

52

存儲類型

■在C++語言中，每個變量有兩個屬性:

□類型：變量所存儲的數(shù)據(jù)類型

存儲類型：變量所存儲的區(qū)域：

■標準的變量定義：

存儲類型數(shù)據(jù)類型變量名；

■存儲類型：

自動變量：auto

寄存器變量：register

外部變量：extern

靜態(tài)變量：static

53

auto

■在函數(shù)內(nèi)或塊內(nèi)定義的變量缺省時是

autOo如

autointi；

■當進入塊時，系統(tǒng)為自動變量分配（棧）空

間。當退出塊時，系統(tǒng)釋放分配給自動

變量的值。因此自動變量的值就消失了。

當再次進入該塊時，系統(tǒng)重新分配空間。

54

static

■為在整個程序的運行期間都存在的變量限

定訪問范圍。

■兩類靜態(tài)變量：

匚靜態(tài)的局部變量

□靜態(tài)的外部變量

55

靜態(tài)的局部變量

eg.f(a)

inta;

允許

變

部

局

{intb=0;

保

量

的

存運行結(jié)果為:

它staticintc=3;

有

原

以

值b=b+l;789

，

次

便

塊

進-Ac=c+l;

return(a+b+c);

還

時

使

可

以}

此

用

值main()

。{inta=2,i;

for(i=0;i<3;++i)

cout?f(a);

}

56

靜態(tài)的外部變量

■用static說明的全局變量其他源文件不能用

extern引用它

■用static還可以用在函數(shù)定義或說明中。該

函數(shù)只能被用于本源文件中，其他源文件

不能調(diào)用此函數(shù)。

57

靜態(tài)變量的使用

■未被程序員初始化的靜態(tài)變量都由系統(tǒng)初

始化為0。

■局部靜態(tài)變量的初值是編譯時賦的。當運

行時重復(fù)調(diào)用此函數(shù)時，不重復(fù)賦初值。

■雖然局部靜態(tài)變量在函數(shù)調(diào)用結(jié)束后仍然

存在，但其他函數(shù)不能引用它。

58

voidb();

voidc();

voidd(int);結(jié)果：

main()

{intx=6;xinmainis6

coutw“xinmainis"?x?endl;xinais25

a();b();c();d(x);x++;

a()；b();c();d(x);xinbis50

cout?"xinmainis"?x?endl;}xincis20

voida()

{intx=25;cout?"xinais9,?x?endl;}xindis7

voidb()xinais25

{staticintx=50;

cout?"xinbis9,?x++?endl;}xinbis51

voidc()xinc200

{externintx;

x*=10;cout?"xincisw?x?endl;}xindis8

intx=2;

voidd(intx)xinmainis7

{cout?"xindis"?++x?endl;}59

register

■存儲在寄存器中，代替自動變量或形參，

可以提高變量的訪問速度。

■如無合適的寄存器可用，則編譯器把它設(shè)

為自動變量。

60

extern

■聲明一個不在本模塊作用范圍內(nèi)的全局變量。如:

externintnum;

num為一個的全局變量。

■用途：

□在某函數(shù)中引用了一個聲明在本函數(shù)后的全局變量時，

需要在函數(shù)內(nèi)用extern聲明此全局變量。

□當一個程序有多個源文件組成時，用extern可引用另一

文件中的全局變量。

61

//filel.cpp//file2.cpp

#include<iostream>#include<iostream>

usingnamespacestd;

usingnamespacestd;

voidf();

externintx;〃外部變量的聲明intx;〃全局變量的定義

intmain()voidf()

(

(

f()；

cout?"inmain():x="cout?"inf():x="

?x?endl;?x?endl;

return0;}

)

62

第6章過程封裝一一函數(shù)

■函數(shù)A■重載函數(shù)

■自己編寫函數(shù)A■函數(shù)模版A

■函數(shù)的使用A■變量的作用域A

■數(shù)組作為參數(shù)A■變量的存儲類別A

■帶默認值的函數(shù)A■遞歸函數(shù)?

■內(nèi)聯(lián)函數(shù)■基于遞歸的算法

63

遞歸用途

■遞歸程序設(shè)計：將一個大問題簡化為同樣形式的較

小問題。

□在一個遞歸求解中，分解的子問題與最初的問題具有一樣

的形式

□作為處理問題的工具，遞歸技術(shù)是一種非常有力的工具。

利用遞歸不但可以使得書寫復(fù)雜度降低，而且使程序看上

去更加美觀

■遞歸調(diào)用：在一個函數(shù)中直接或間接地調(diào)用函數(shù)本

身

64

遞歸條件

■必須有遞歸終止的條件

■函數(shù)有與遞歸終止條件相關(guān)的參數(shù)

■在遞歸過程中，決定終止條件的參數(shù)有

規(guī)律地遞增或遞減

65

遞歸的標準模式

■對函數(shù)的入口進行測試的基本情況

if（條件）----------基本情況

return（不需要遞歸的簡單答案）；

else

return（遞歸調(diào)用同一函數(shù)）;

66

典型的遞歸函數(shù)一階乘函數(shù)

n!=l*2*3*4*???*(n?l)*n

___________________________________________/

(n-1)!

遞歸形式：

fl〃=o-

加=1--------一

—D!其他

longp(intn)

{if(n==0)return1;

elsereturnn*p(n-l);

}67

簡單應(yīng)用——求n的k次事

intRaiselntToPower(intn,intk)

{if(k==0){

return(1);

)

else{

return(n*RaiselntToPower(n,k-1));

)

)

68

Fibonacci函類

0123456

0112358

On=0

尸(〃)=v1n=1

F(n-1)+F{n-2)其他

I

intf(intn)

{if(n==0)return0;

elseif(n==l)return1;

elsereturn(f(n-l)+f(n-2));

69

理解遞歸

■問題：求解n!

□可以用循環(huán)的方法，即從1開始，乘2,再乘

3-..…一直乘到n。這種方法容易理解，也容易

實現(xiàn)

由于n!=nX(n-1)!數(shù)學(xué)里定義0!=1,從而

n!可以用下面的遞歸公式表示：

1(H=0,1)

n\—{

n?(n—1)!(H>1)

70

遞歸函數(shù)設(shè)計

intp(intn)

{if(n==0)

return(1);

else

return(n*p(n-1));

}

71

求p(4)

遞歸過程

「4*

「3*

「2*

|A|

|AO「1*

“1)<f

回溯

72

遞歸與迭代的選擇

■對于大多數(shù)常用的遞歸都有簡單、等價的

迭代程序。究竟使用哪一種，憑你的經(jīng)驗

選擇。

■迭代程序復(fù)雜，但效率高。

■遞歸程序邏輯清晰，但往往效率較低。

73

Fibonacci函數(shù)的遞歸實現(xiàn)

intf(intn)

{if(n==0)return0;

elseif(n==1)return1;

elsereturn(f(n-1)+f(n-2));

)

■實現(xiàn)效率分析：消費的時間是災(zāi)難性的！?。?/p>

74

Fibonacci函數(shù)的迭代實現(xiàn)

intf(intn)消耗的時間：執(zhí)

{inti,fn,fn_1=0,fn_2=1;行n次加法和3n次

if(n==0)return0;賦值?。?！

if(n==1)return1;

for(i=2;i<=n;++i)

{fn=fn_1+fn_2;

fn2=fn1;fn1=fn;}

returnfn;

}75

系統(tǒng)考慮

對遞歸函數(shù)的每次調(diào)用都需要內(nèi)存空間。

由于很多調(diào)用的活動都是同時進行的，操

作系統(tǒng)可能會耗盡可用的內(nèi)存，避免在處理

過大的n時產(chǎn)生溢出問題。

76

遞歸過程-打印三角形

■設(shè)計一函數(shù)，可以在屏幕上的任意地方畫一個任

意大小的由任意字符（如：*）組成的倒三角形。

■函數(shù)的原型可為

voiddisplay(charsymbol,

intoffset,intlength)

***********

■如調(diào)用display，*',0,11),顯示如下圖像*******

***

77

Display的設(shè)計

■從遞歸的觀點來看，在某一位置畫一倒三

角形可以分成兩步：

■在指定位置畫出長度為length的一行符號。

■在指定位置的下一行、下二列畫一個大小

為length-4的有同樣的符號組成的倒三角

形

78

Display函數(shù)

voiddisplay(charsymbol,intoffset,intlength)

{if(length>0)

{draw('offset);

draw(symbol,length);

putchar(5\n,);

display(symble,offset+2,length-4);

)

)

79

Draw函數(shù)

■畫由k個字符組成的一行符號

■該函數(shù)同樣可以看成遞歸。畫k個符號可以看成先

畫一個符號，然后再畫k-1個字符組成的一行。

voiddraw(charc,intk)

{jf(k>0){

putchar(c);

draw(c,k-1);

)

)

80

Main函數(shù)

■#include<stdio.h>

#defineSYMBOL

#defineOFFSET0

#defineLENGTH19

voiddisplay(char,int,int)；

voiddraw(char,jnt);

intmain(void)

{display(SYMBOL,OFFSET,LENGTH)；

return0;

}

81

遞歸過程-數(shù)字旋轉(zhuǎn)方陣（蛇陣）

■數(shù)字旋轉(zhuǎn)方陣如右圖12019181716

所示。編程輸出任意22132313015

N*N的蛇陣。

32233362914

42334352813

52425262712

67891011

82

用遞歸的觀點看問題

■先填最外圈，然后再填內(nèi)部內(nèi)部的填法同上。也

是先填最外圈，再填內(nèi)部。

■根據(jù)上述思想，可以設(shè)計一個遞歸函數(shù)fill。該函

數(shù)先填外圈，然后遞歸調(diào)用自己填內(nèi)部。

■函數(shù)原型：

voidfill(intnumber,intbegin,intsize)

number：表示要填入的起始數(shù)據(jù)

begin：表示要填的起始位置

size：蛇陣的規(guī)模

■要生成一個6*6的蛇陣只要調(diào)用：血(1,0,6)83

Main函數(shù)

intp[20][20];

voidfill(int,int,int);

intmain()

{introw,col,size;

coutvv”請輸入蛇陣的規(guī)模：

cin?size;

fill(1,0,size);

for(row=0;row<size;++row)

{cout?endl;

for(col=0;col<size;++col)

cout?p[row][col]?'\t';

}

return0;

}84

Fill函數(shù)的設(shè)計

■自上而下填最左列

■自左而右填最下行

■自下而上填最右列

■自右而左填最上行

■遞歸調(diào)用劑，規(guī)模減2,起始位置為原來的

下一行下一列，填入的起始數(shù)字為填入一

圈后的第一個數(shù)字。

85

Voidfill(intnumber,intbegin,intsize)

{inti,row=begin,col=begin;

if(size==0)return;

if(size==1){p[begin][begin]=number;return;}

p[row][col]=number;++number;

for(i=0;i<size-1;++i)

{++row;p[row][col]=number;++number;}

for(i=0;i<size-1;++i)

{++col;p[row][col]=number;++number;}

for(i=0;i<size-1;++i)

{-row;p[row][col]=number;++number;}

for(i=0;i<size-2;++i)

{-col;p[row][col]=number;++number;}

fill(number,begin+1,size-2);

)86

遞歸過程一Hanoi塔問題

ABC

目標：

將A上的盤子全部移到B上

規(guī)則：

每次只能移動一個盤子

不允許大盤子放在小盤子上

87

Hannoi塔

■n=4（最開始的情況）n=4（完成情況）

Hannoi塔

■第1步：從開始的桿到輔助桿（src到aux）

■第2步：從開始桿到目的桿（src到dst）

Hannoi塔

■第3步:從輔助桿到目的桿（aux到dst）

■第4步：從開始的桿到輔助桿（src到aux）

Hannoi塔

■第5步：從目的桿到開始桿（dst到src）

■第6步：從目的桿到輔助桿（dst到aux）

Hannoi塔

■第7步：從開始桿到目的桿（src至Udst）

■第8步：從開始桿到目的桿（src到dst）

Hannoi塔

■第9步：從輔助桿到目的桿（aux至Udst）

■第10步:從輔助桿到開始的桿（aux到src）

Hannoi塔

■第11步：從目的桿到開始桿（dst至Usrc）

■第12步：從輔助桿到目的桿（aux至Udst）

Hannoi塔

■第13步：從開始的桿到輔助桿（src到aux）

■第14步：從開始桿到目的桿（src到dst）

Hannoi塔

■第15步：從輔助桿到目的桿（aux至Udst）

96

解題思路

■最簡單的情況，只有一個盤子：將盤子直

接從A移到B

■大于一個盤子的情況：

口將除了最下面一個盤子外的所有盤子從A移到C

口將最下面的盤子從A移到B

□將C上的盤子移回B

97

Hanoi塔函數(shù)

voidHanoi(intn,charstart,charfinish,chartemp)

{if(n==1)cout?start??finish?'\t';

else{Hanoi(n-1,start,temp,finish);

cout?start??finish?'\t';

Hanoi(n-1,temp,finish,start);

)

)

98

全排列問題

■如給定三個字母"ABC”,那么可形成的全

排列為:ABC,ACB,BAC,BCA,CAB,

CBAo試設(shè)計一個函數(shù)，輸入一個字符串,

輸出該字符串中所有字母的全排列

99

用遞歸的思想分析問題

■如排列“ABCDE”，用遞歸的思想可以看成:

□第一個字母為后面是“BCDE”的全排列

■第一個字母為'B，，后面是“CDE”的全排列

■第一個字母為后面是“BDE”的全排列

-第一個字母為后面是“BCE”的全排歹U

-第一個字母為'E，,后面是“BCD”的全排列

□第一個字母為出,后面是“ACDE”的全排列

□第一個字母為后面是“BADE”的全排列

□第一個字母為0后面是“BCAE”的全排列

□第一個字母為后面是“BCDA”的全排列

100

■用一個字符串存儲排列。

■對n個字符的排列來講，第一個元素有n種選擇,

對每種選擇，排列后面n-1個元素。

■n-1個元素的排列：固定第二個元素(n-1種選擇)，

排列后面n-2個元素。依此類推。

■函數(shù)原型可選為：voidpermu(charstr[],intk)

表示排列字符串str中從k開始的元素

■函數(shù)的調(diào)用：排列字符串中的所有元素可調(diào)用

permu(charstr[],0);