C++程序設(shè)計(jì) -1

1、山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 數(shù)據(jù)結(jié)構(gòu) 第1章 C+程序設(shè)計(jì)1第1章C+程序設(shè)計(jì)程序設(shè)計(jì)山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 數(shù)據(jù)結(jié)構(gòu) 第1章 C+程序設(shè)計(jì)2本章內(nèi)容：C+特性：參數(shù)傳遞方式（如傳值、引用和常量引用）。函數(shù)返回方式（如返值、引用和常量引用）。模板函數(shù)。遞歸函數(shù)。常量函數(shù)。內(nèi)存分配和釋放函數(shù)：new與delete。異常處理結(jié)構(gòu)：try,catch和throw。類(lèi)與模板類(lèi)。類(lèi)的共享成員、保護(hù)成員和私有成員。友元。操作符重載。4/30/20223Value Parameters Template Functions Reference ParametersConst Reference Pa

2、rameters Return Values 遞歸函數(shù)(Recursive Functions)斐波那契數(shù)列(Fibonacci numbers)階乘(Factorial)排列(Permutations)1.2 Functions and Parameters 4/30/20224程序1-1 計(jì)算一個(gè)整數(shù)表達(dá)式int Abc(int a, int b, int c)return a+b+b*c+4;X=10;Y=20;z=Abc(2,x,y)形式參數(shù)( formal parameter)實(shí)際參數(shù)(actual parameter)復(fù)制構(gòu)造函數(shù)( copy constructor)1.析構(gòu)函數(shù)(

3、destructor)1.2.1傳值參數(shù)(Value Parameters)4/30/20225傳值傳遞模式- 1存儲(chǔ)器狀態(tài)int Abc(int a, int b, int c)return a+b+b*c+4;AA. 在執(zhí)行方法前，局部量的不存在。在 Abc方法前A代碼m=20;x = 10;y = 15;z=Abc(m,x,y);x x1010y1015m1020z10？4/30/20226傳值傳遞模式- 2存儲(chǔ)器狀態(tài)B. 調(diào)用方法時(shí)首先給形式參數(shù)分配空間，然后把實(shí)際參數(shù)的值賦給對(duì)應(yīng)的形式參數(shù)。Values are copied atBint Abc(int a, int b, int

4、c)return a+b+b*c+4;代碼m=20;x = 10;y = 15;z=Abc(m,x,y);Bm1020 x1010a1020b1010c1015y1015z10？4/30/20227傳值傳遞模式- 3C存儲(chǔ)器狀態(tài)C. 在方法體中，使用形式參數(shù)運(yùn)算。執(zhí)行 后Cint Abc(int a, int b, int c)return a+b+b*c+4;代碼m=20;x = 10;y = 15;z=Abc(m,x,y);m1020 x1010y1015a1020b1010c1015z10？4/30/20228傳值傳遞模式- 4代碼D存儲(chǔ)器狀態(tài)D. 方法體執(zhí)行完，形式參數(shù)失去了意義，在方

5、法體中沒(méi)有改變實(shí)際參數(shù)的值，計(jì)算植被返回。. 執(zhí)行方法后Dint Abc(int a, int b, int c)return a+b+b*c+4;m=20;x = 10;y = 15;z=Abc(m,x,y);m1020 x1010y1015z101844/30/20229程序1-2 計(jì)算一個(gè)浮點(diǎn)數(shù)表達(dá)式float Abc(float a, float b, float c)return a+b+b*c+4;重新編寫(xiě)一個(gè)相應(yīng)的函數(shù)？1.2.2模板函數(shù)(Template Functions)4/30/202210實(shí)際上不必對(duì)每一種可能的形式參數(shù)的類(lèi)型都重新編寫(xiě)一個(gè)相應(yīng)的函數(shù)。可以編寫(xiě)一段通用的

6、代碼，將參數(shù)的數(shù)據(jù)類(lèi)型作為一個(gè)變量，它的值由編譯器來(lái)確定。templateT Abc(T a, T b, T c)return a+b+b*c+4;1.2.3模板函數(shù)(Template Functions)模板函數(shù)使用示例main()int n=1; int k=1; int j=2; int m=abc(n,k,j);/ 4/30/2022114/30/202212傳值參數(shù)形式參數(shù)的用法會(huì)增加程序的運(yùn)行開(kāi)銷(xiāo)。程序1-3中，在函數(shù)被調(diào)用時(shí)，類(lèi)型T 的復(fù)制構(gòu)造函數(shù)把相應(yīng)的實(shí)際參數(shù)分別復(fù)制到形式參數(shù)a，b 和c 之中，以供函數(shù)使用；而在函數(shù)返回時(shí)，類(lèi)型T的析構(gòu)函數(shù)會(huì)被喚醒，以便釋放形式參數(shù)a，b

7、和c。T : Matrix(10*10)Abc 被調(diào)用時(shí) :300次操作 (copy constructors)Abc 返回時(shí): 300 次操作 (destructors)1.2.3引用參數(shù)(Reference Parameters)4/30/202213程序1-4 利用引用參數(shù)計(jì)算一個(gè)表達(dá)式templateT Abc(T& a, T& b, T& c)return a+b+b*c+(a+b-c)/(a+b)+4;Abc(x,y,z):Abc 被調(diào)用時(shí) :實(shí)際參數(shù)（x、y 和z）將被分別賦予名稱(chēng)a，b 和cAbc(x,y,z):在函數(shù)Abc 執(zhí)行期間，x、y 和z 被用來(lái)替換對(duì)應(yīng)的a，b 和c

8、。與傳值參數(shù)的情況不同，在函數(shù)被調(diào)用時(shí)，本程序并沒(méi)有復(fù)制實(shí)際參數(shù)的值，在函數(shù)返回時(shí)也沒(méi)有調(diào)用析構(gòu)函數(shù)。 1.2.3引用參數(shù)(Reference Parameters)4/30/202214傳引用傳遞模式- 2存儲(chǔ)器狀態(tài)B.調(diào)用參數(shù)的值，這里是一個(gè)地址，被復(fù)制給形式參數(shù)。Values are copied atBint Abc(int a, int b, int c)return a+b+b*c+(a+b-c)/(a+b)+4;代碼m=3;x = 10;y = 20;z=Abc(m,x,y);Bm1020 x1010y1015z10？abc4/30/202215傳引用傳遞模式- 4代碼D存儲(chǔ)器狀

9、態(tài)D. 方法體執(zhí)行完，形式參數(shù)失去了意義，在方法體中沒(méi)有改變實(shí)際參數(shù)的值，計(jì)算植被返回。. 執(zhí)行方法后Dint Abc(int a, int b, int c)return a+b+b*c+(a+b-c)/(a+b)+4;m=3;x = 10;y = 20;z=Abc(m,x,y);m1020 x1010y1015z101844/30/202216templateT Abc(const T& a, const T& b, const T& c)return a+b+b*c+(a+b-c)/(a+b)+4;這種模式指出函數(shù)不得修改引用參數(shù)。1.2.4常量引用參數(shù)(Const Reference

10、Parameters)4/30/202217對(duì)于諸如i n t、float 和char 的簡(jiǎn)單數(shù)據(jù)類(lèi)型，當(dāng)函數(shù)不會(huì)修改實(shí)際參數(shù)值的時(shí)候我們可以采用傳值參數(shù)；對(duì)于所有其他的數(shù)據(jù)類(lèi)型（包括模板類(lèi)型），當(dāng)函數(shù)不會(huì)修改實(shí)際參數(shù)值的時(shí)候可以采用常量引用參數(shù)。編程建議:4/30/202218函數(shù)可以返回值，引用或常量引用。返回值，在這種情況下，被返回的對(duì)象均被復(fù)制到調(diào)用（或返回）環(huán)境中。返回引用，可以為返回類(lèi)型添加一個(gè)前綴&， 返回值是對(duì)一個(gè)實(shí)際參數(shù)的引用，不會(huì)復(fù)制值到返回環(huán)境中。 T &X(int i,T& z) Return z; 常量引用返回，返回的結(jié)果是一個(gè)不變化的對(duì)象。 Const T &X(i

11、nt i,T& z)1.2.5返回值(Return Values)4/30/202219遞歸函數(shù)是一個(gè)自己調(diào)用自己的函數(shù)。遞歸函數(shù)包括兩種：直接遞歸(direct recursion)和間接遞歸(indirect recursion)。l直接遞歸是指函數(shù)F的代碼中直接包含了調(diào)用F的語(yǔ)句 F Fl間接遞歸是指函數(shù)F調(diào)用了函數(shù)G，G又調(diào)用了H，如此進(jìn)行下去，直到F又被調(diào)用 FGHF1.2.6遞歸函數(shù)(Recursive Functions)4/30/2022201. 數(shù)學(xué)函數(shù)的遞歸定義階乘函數(shù) f(n)=n！完整的遞歸定義，必須包含：n基本部分 （一般包含了nk 的情況） f(n)=1 n 1 f

12、(n) 是直接定義的（即非遞歸） n遞歸部分: （右側(cè)所出現(xiàn)的所有f 的參數(shù)都必須有一個(gè)比n 小 ） f(n)=nf(n-1) n1 1.2.6 遞歸函數(shù)4/30/2022212. C+遞歸函數(shù)一個(gè)正確的遞歸函數(shù)必須包含：l一個(gè)基本部分l遞歸調(diào)用部分(所使用的參數(shù)值應(yīng)比函數(shù)的參數(shù)值要小)例 1-1 (程序 1-7)int Factorial(int n) /計(jì)算 n！ if (n=1) return 1; else return n*Factorial(n-1);1.2.6 遞歸函數(shù)4/30/202222遞歸過(guò)程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。層層向下遞歸，退出時(shí)的次序正好相反4/30/20222

13、3遞歸工作棧每一次遞歸調(diào)用，需要分配存儲(chǔ)空間，來(lái)保留程序的狀態(tài)(如局部變量、參數(shù)值、代碼的執(zhí)行位置等) 。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。遞歸遞歸工作記錄工作記錄4/30/202224例1-2 模板函數(shù)Sum 計(jì)算元素a 0至an-1 的和程序 1-9templateT Rsum(T a, int n) if (n 0) return Rsum(a, n-1) + an-1; return 0;1.2.6 遞歸函數(shù)4/30/202225例1-3 斐波納西Fib斐波那契數(shù)列的定義：F0=0，F(xiàn)1=1，F(xiàn)n=Fn-1+Fn-2 (n1)int Fib(int n)/計(jì)

14、算n！if(n=0) return 0; if(n=1) return 1;return fibo1(n-1)+fibo1(n-2);1.2.6 遞歸函數(shù)4/30/202226例1-3 排列 E=e1, e2, en-1, en，Ei= e1, ei-1, ei+1, en-1, enPerm(X)=集合X 中元素的排列方式 。ei Perm(X)=在perm (X) 中的每個(gè)排列方式的前面均加上ei以后所得到的排列方式。E=a,b,cE1= b,c, E2= a,c, E3= a,bPerm(E1)=(bc,cb)a Perm(E1)=(abc,acb)Perm(E)=?1.2.6 遞歸函數(shù)

15、4/30/202227E=a,b,cperm(E)=a.perm(b,c)+b.perm(a,c)+c.perm(a,b)。同樣，按照遞歸定義有perm(b,c)=b.perm(c)+c.perm(b),所以a.perm(b,c)=ab.perm(c)+ac.perm(b) =ab.c+ac.b=(abc,acb)。同理可得b.perm(a,c)=ba.perm(c)+bc.perm(a) =ba.c+bc.a=(bac,bca)，c.perm(a,b)=ca.perm(b)+cb.perm(a) =ca.b+cb.a=(cab,cba)。所以perm(E)=(abc,acb,bac,bca,

16、cab,cba)。排列遞歸模擬4/30/202228程序程序1-101-10使用遞歸函數(shù)生成排列使用遞歸函數(shù)生成排列前綴為前綴為list0list0：k-1,k-1,后邊為后邊為listklistk：mm的全排列的全排列templatetemplateVoid Perm(T list,int k,int m)Void Perm(T list,int k,int m)/生成生成listklistk：mm的所有排列方式的所有排列方式int i;int i;if(k = m)if(k = m)/輸出一個(gè)排列方式輸出一個(gè)排列方式for(i=0;i=m;i+)for(i=0;i=m;i+) coutli

17、sti; coutlisti;coutendl;coutendl; else/else/listklistk：mm有多個(gè)排列方式，遞歸地產(chǎn)生這些排列方式有多個(gè)排列方式，遞歸地產(chǎn)生這些排列方式for(i=k;i=m;i+)for(i=k;i=m;i+)Swap(listk,listi);Swap(listk,listi);Perm(list,k+1,m);Perm(list,k+1,m);Swap(listk,listi);Swap(listk,listi); 排列遞歸實(shí)現(xiàn)4/30/202229n遞歸優(yōu)點(diǎn)：遞歸簡(jiǎn)潔、易編寫(xiě)、易懂易證明正確性n遞歸缺點(diǎn)：遞歸效率低重復(fù)計(jì)算多1.2.6 遞歸函數(shù)4/

18、30/202230n遞歸函數(shù)改為非遞歸n改為非遞歸的目的是提高效率n單向遞歸可直接用迭代實(shí)現(xiàn)非遞歸n其他情形必須借助棧實(shí)現(xiàn)非遞歸1.2.6 遞歸函數(shù)4/30/202231階乘非遞歸實(shí)現(xiàn)計(jì)算n！的非遞歸函數(shù)int Factorial(int n)/計(jì)算n！if(n=1) return 1;int f=2;for(int i=3;i=n;i+)f*=i;return f;1.2.6 遞歸函數(shù)4/30/202232斐波那契數(shù)列非遞歸實(shí)現(xiàn)long Fib ( long n ) if ( n = 1 ) return n; long twoback = 0, oneback = 1, Current; for ( int i = 2; i = n; i+ ) Current = twoback + oneback