山大課件 數(shù)據(jù)結(jié)構(gòu)_1)

1、3/31/20221Data Structures, Algorithms, and Applications in C+數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用-C+描述Sartaj Sahni著孔蘭菊 139531087553/31/20222數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用-C+語(yǔ)言描述機(jī)械工業(yè)出版社 2002.10 535頁(yè)C+程序設(shè)計(jì)語(yǔ)言(特別版) 美:Bjarne Stroustrup 譯:裘宗燕 機(jī)械工業(yè)出版社 2002.7 936頁(yè)URL:/sahni/dsac參考書籍3/31/20223教學(xué)日歷3/31/20224教學(xué)日歷3/31/20225教學(xué)日歷3/31/20226教學(xué)日

2、歷3/31/20227教學(xué)日歷3/31/202281.計(jì)算機(jī)科學(xué)的重要基礎(chǔ)課程2.基本概念3.C+實(shí)踐引言3/31/202291.軟件設(shè)計(jì)是一種智力的挑戰(zhàn)。程序設(shè)計(jì)技術(shù)是一種組織復(fù)雜性的技術(shù)，是一種控制巨量數(shù)據(jù)的技術(shù)，也是一種盡量回避混亂的技術(shù)。2.高效描述數(shù)據(jù)；設(shè)計(jì)好的算法3.例：查字典，圖書館借書，搜索引擎4.Googol表示“10的100次方，巨大的數(shù)字”。當(dāng)年google公司的創(chuàng)始人選擇了googol的同音異形體google作為公司的大名，意在表現(xiàn)該引擎“搜集和駕御浩瀚無(wú)窮的網(wǎng)絡(luò)信息”的宏圖。 計(jì)算機(jī)科學(xué)的重要基礎(chǔ)課程3/31/2022101969年，美國(guó)科學(xué)家Donald E.Knu

3、th 出版巨著計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第一卷基本算法，全面、系統(tǒng)討論了各種數(shù)據(jù)結(jié)構(gòu)，定義了其上的運(yùn)算和算法?！笆澜鐨v史上最偉大的十種學(xué)科著作”之一。數(shù)據(jù)結(jié)構(gòu)與算法的奠基人。1974年獲圖靈獎(jiǎng)(36歲)數(shù)據(jù)結(jié)構(gòu)發(fā)展歷史3/31/2022111.數(shù)據(jù)是描述客觀事物用到的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號(hào)集合，它是計(jì)算機(jī)程序使用、加工的原料和輸出的結(jié)果。2.算法是一個(gè)有窮規(guī)則的集合，規(guī)定了解決某一特定問題的運(yùn)算序列（輸入、輸出、確定性、有窮性、能行性）。基本概念-數(shù)據(jù)、算法3/31/2022121.數(shù)據(jù)元素間的邏輯結(jié)構(gòu)關(guān)系(面向應(yīng)用) 線性 非線性-層次、網(wǎng)狀2.數(shù)據(jù)的存貯結(jié)構(gòu)(面

4、向存儲(chǔ)) 內(nèi)存-順序，鏈?zhǔn)?，散列，索?物理3.對(duì)數(shù)據(jù)進(jìn)行的運(yùn)算及實(shí)現(xiàn)方法（查找、插入、刪除、更新等）基本概念-數(shù)據(jù)結(jié)構(gòu)3/31/202213線性結(jié)構(gòu)譚維維艾夢(mèng)萌 劉力揚(yáng) 厲娜 REBORN 1 2 3 4 5元素之間為一對(duì)一的線性關(guān)系，第一個(gè)元素?zé)o直接前驅(qū)，最后一個(gè)元素?zé)o直接后繼，其余元素都有一個(gè)直接前驅(qū)和直接后繼。3/31/202214非線性結(jié)構(gòu)1. 元素之間為一對(duì)多非線性關(guān)系的非線性結(jié)構(gòu)稱為樹結(jié)構(gòu)，除根結(jié)點(diǎn)無(wú)直接前驅(qū)、有多個(gè)直接后繼外，其余元素均有一個(gè)直接前驅(qū)或多個(gè)直接后繼。2. 或元素之間為多對(duì)多非線性關(guān)系的非線性結(jié)構(gòu)稱為圖結(jié)構(gòu)，每個(gè)元素均有多個(gè)直接前驅(qū)或多個(gè)直接后繼。3/31/202

5、215樹形結(jié)構(gòu)14131211234567891098745623113/31/202216圖結(jié)構(gòu)125643125436113318146651619213/31/202217順序存貯(向量存貯) : 依次、連續(xù)所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存仍然相鄰。存貯結(jié)構(gòu)-順序存貯3/31/202218存貯結(jié)構(gòu)-順序存貯設(shè)有數(shù)據(jù)元素a1、a2 、 、an ，順序存貯形為： a1 a2 an3/31/202219鏈?zhǔn)酱尜A :邏輯上依次、內(nèi)存中未必連續(xù) 所有元素存放在可以不連續(xù)的存貯單元中，元素之間的關(guān)系通過指針(地址)表示。存貯結(jié)構(gòu)-鏈?zhǔn)酱尜Aa0a1a2a3a4 fi

6、rst3/31/202220使用附加的索引表，索引表中的每一項(xiàng)稱為索引項(xiàng)，其一般形式是：(關(guān)鍵字，地址)，其中的關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。存貯結(jié)構(gòu)-索引存貯3/31/202221存貯結(jié)構(gòu)-索引存貯 k1 k2 kn索引表索引表 an a1 a2 3/31/202222通過構(gòu)造散列函數(shù)，用函數(shù)的值來(lái)確定元素存放的地址。即： 元素ai 的地址=Hash(ai)存貯結(jié)構(gòu)-散列存貯3/31/202223存貯結(jié)構(gòu)-散列存貯 an a1 a2 Hash(a1 )Hash(a2 )Hash(an )3/31/202224算法定義3/31/2022251.運(yùn)算的定義直接依賴于邏輯結(jié)構(gòu)。2.運(yùn)算的

7、實(shí)現(xiàn)依賴于存貯結(jié)構(gòu)。3.例：順序查找、折半查找算法和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)3/31/2022261.注重實(shí)踐2.正確、易讀、易維護(hù)、性能、通用C+實(shí)踐3/31/2022271.Introduction2.Functions and Parameters 3.Dynamic Memory Allocation4.Classes5.Testing and DebuggingChapter 1 Programming in C+ (第1章 C+程序設(shè)計(jì))3/31/2022281.它正確嗎？2.它容易讀懂嗎？3.它有完善的文檔嗎？4.它容易修改嗎？5.它在運(yùn)行時(shí)需要多大內(nèi)存？6.它的運(yùn)行時(shí)間有多長(zhǎng)？7.它的

8、通用性如何？能不能不加修改就可以用它來(lái)解決更大范圍的問題？8.它可以在多種機(jī)器上編譯和運(yùn)行嗎？或者說(shuō)需要經(jīng)過修改才能在不同的機(jī)器上運(yùn)行嗎？1.1 Introduction3/31/202229本課程目標(biāo)旨在提供一些程序正確性的驗(yàn)證方法以及公認(rèn)的一些良好的程序設(shè)計(jì)習(xí)慣3/31/2022301.Value Parameters 2.Template Functions 3.Reference Parameters4.Const Reference Parameters 5.Return Values 6.遞歸函數(shù)(Recursive Functions)1.斐波那契數(shù)列(Fibonacci num

9、bers)2.階乘(Factorial)3.排列(Permutations)1.2 Functions and Parameters 3/31/202231程序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)1.形式參數(shù)( formal parameter)2.實(shí)際參數(shù)(actual parameter)3.復(fù)制構(gòu)造函數(shù)( copy constructor)4.析構(gòu)函數(shù)(destructor)傳值參數(shù)(Value Parameters)3/31/202232傳值傳遞模式- 1存儲(chǔ)器狀

10、態(tài)int Abc(int a, int b, int c)return a+b+b*c+4;A在 Abc方法前A代碼m=20;x = 10;y = 15;z=Abc(m,x,y);x x1010y1015m1020z10？3/31/202233傳值傳遞模式- 2存儲(chǔ)器狀態(tài)Values are copied atBint Abc(int a, int b, int c)return a+b+b*c+4;代碼m=20;x = 10;y = 15;z=Abc(m,x,y);Bm1020 x1010a1020b1010c1015y1015z10？3/31/202234傳值傳遞模式- 3C存儲(chǔ)器狀態(tài)執(zhí)行

11、 后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？3/31/202235傳值傳遞模式- 4代碼D存儲(chǔ)器狀態(tài). 執(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 x1010y1015z101843/31/202236程序1-2 計(jì)算一個(gè)浮點(diǎn)數(shù)表達(dá)式float Abc(float a, fl

12、oat b, float c)return a+b+b*c+4;模板函數(shù)(Template Functions)3/31/202237實(shí)際上不必對(duì)每一種可能的形式參數(shù)的類型都重新編寫一個(gè)相應(yīng)的函數(shù)。可以編寫一段通用的代碼，將參數(shù)的數(shù)據(jù)類型作為一個(gè)變量，它的值由編譯器來(lái)確定。templateT Abc(T a, T b, T c)return a+b+b*c+4;模板函數(shù)(Template Functions)模板函數(shù)使用示例main()int n=1; int k=1; int j=2; int m=abc(n,k,j);/ 3/31/2022383/31/2022391.傳值參數(shù)形式參數(shù)的用

13、法會(huì)增加程序的運(yùn)行開銷。2.程序1-3中，在函數(shù)被調(diào)用時(shí)，類型T 的復(fù)制構(gòu)造函數(shù)把相應(yīng)的實(shí)際參數(shù)分別復(fù)制到形式參數(shù)a，b 和c 之中，以供函數(shù)使用；而在函數(shù)返回時(shí)，類型T的析構(gòu)函數(shù)會(huì)被喚醒，以便釋放形式參數(shù)a，b 和c。傳值參數(shù)？3/31/202240程序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;引用參數(shù)(Reference Parameters)3/31/202241如果用語(yǔ)句Abc(x,y,z)來(lái)調(diào)用函數(shù)Abc，其中x、y和z是相同的數(shù)據(jù)類型，那么這些

14、實(shí)際參數(shù)將被分別賦予名稱a，b和c。因此，在函數(shù)Abc執(zhí)行期間，x、y和z被用來(lái)替換對(duì)應(yīng)的a，b和c。與傳值參數(shù)的情況不同，在函數(shù)被調(diào)用時(shí)，本程序并沒有復(fù)制實(shí)際參數(shù)的值，在函數(shù)返回時(shí)也沒有調(diào)用析構(gòu)函數(shù)。引用參數(shù)(Reference Parameters)3/31/202242傳引用傳遞模式- 2存儲(chǔ)器狀態(tài)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？abc3/31/20224

15、3傳引用傳遞模式- 4代碼D存儲(chǔ)器狀態(tài). 執(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 x1010y1015z101843/31/202244templateT Abc(const T& a, const T& b, const T& c)return a+b+b*c+(a+b-c)/(a+b)+4;這種模式指出函數(shù)不得修改引用參數(shù)。常量引用參數(shù)(Const Reference Parameters)3/31/20

16、2245使用關(guān)鍵字const 來(lái)指明函數(shù)不可以修改引用參數(shù)的值，這在軟件工程方面具有重要的意義。這將立即告訴用戶該函數(shù)并不會(huì)修改實(shí)際參數(shù)。編程建議:對(duì)于諸如i n t、float 和char 的簡(jiǎn)單數(shù)據(jù)類型，當(dāng)函數(shù)不會(huì)修改實(shí)際參數(shù)值的時(shí)候我們可以采用傳值參數(shù)；對(duì)于所有其他的數(shù)據(jù)類型（包括模板類型），當(dāng)函數(shù)不會(huì)修改實(shí)際參數(shù)值的時(shí)候可以采用常量引用參數(shù)。常量引用參數(shù)(Const Reference Parameters)3/31/2022461.函數(shù)可以返回值，引用或常量引用。2.在前面的例子中，函數(shù)Abc 返回的都是一個(gè)具體值，在這種情況下，被返回的對(duì)象均被復(fù)制到調(diào)用（或返回）環(huán)境中。3.如果需

17、要返回一個(gè)引用，可以為返回類型添加一個(gè)前綴&。如：T& X(int i, T& z)返回值(Return Values)3/31/2022471.遞歸：一個(gè)事物部分地由它自身構(gòu)成或由自身來(lái)定義。2.遞歸調(diào)用是解決某類特殊問題的好方法。有一個(gè)廣為流傳的故事，倒是可以看出點(diǎn)“遞歸”的樣子。“從前有座山，山里有座廟，廟里有個(gè)老和尚，老和尚對(duì)小和尚說(shuō)故事：從前有座山”。在講述故事的過程中，又嵌套講述了故事本身。遞歸3/31/2022481.遞歸函數(shù)是一個(gè)自己調(diào)用自己的函數(shù)。2.遞歸函數(shù)包括兩種：直接遞歸(direct recursion)和間接遞歸(indirect recur

18、sion)。直接遞歸是指函數(shù)F的代碼中直接包含了調(diào)用F的語(yǔ)句，而間接遞歸是指函數(shù)F調(diào)用了函數(shù)G，G又調(diào)用了H，如此進(jìn)行下去，直到F又被調(diào)用。遞歸函數(shù)(Recursive Functions)3/31/202249在數(shù)學(xué)中經(jīng)常用一個(gè)函數(shù)本身來(lái)定義該函數(shù)。例如階乘函數(shù)令f(n)=n！:數(shù)學(xué)函數(shù)的遞歸定義時(shí)時(shí)當(dāng)當(dāng)時(shí)時(shí)當(dāng)當(dāng) 1 ,)!1( 0 , 1!nnnnn3/31/202250對(duì)于函數(shù)f(n)的一個(gè)遞歸定義(假定是直接遞歸)，要想使它成為一個(gè)完整的定義，必須滿足如下條件：1.定義中必須包含一個(gè)基本部分(base)，其中對(duì)于n的一個(gè)或多個(gè)值，f(n)必須是直接定義的(即非遞歸)。為簡(jiǎn)單起見，我們假

19、定基本部分包含了nk的情況，其中k為常數(shù)。2.在遞歸部分(recursive component)中，右側(cè)所出現(xiàn)的所有f的參數(shù)都必須有一個(gè)比n小，以便重復(fù)運(yùn)用遞歸部分來(lái)改變右側(cè)出現(xiàn)的f，直至出現(xiàn)f的基本部分。數(shù)學(xué)函數(shù)的遞歸定義3/31/202251在階乘函數(shù)公式中，基本部分是：當(dāng)n1時(shí)f(n)=1；遞歸部分是f(n)=nf(n-1)，其中右側(cè)f的參數(shù)為n-1，比n要小。重復(fù)應(yīng)用遞歸部分可把f(n-1)變換成對(duì)f(n-2)，f(n-3)，. ，直到f(1)的調(diào)用。例如：f(5)=5f(4)=20f(3)=60f(2)=120f(1)每次應(yīng)用遞歸部分的結(jié)果是更趨近于基本部分，最后，根據(jù)基本部分的定

20、義可以得到f(5)=120。數(shù)學(xué)函數(shù)的遞歸定義3/31/202252斐波那契數(shù)列的定義：F0=0，F(xiàn)1=1，F(xiàn)n=Fn-1+Fn-2 (n1)基本部分: ?遞歸部分: ?數(shù)學(xué)函數(shù)的遞歸定義3/31/202253證明方法可以歸納為三個(gè)部分1.歸納初值(induction base)2.歸納假設(shè)(induction hypothesis)3.歸納步證明(induction step)歸納證明3/31/202254像遞歸定義并不是循環(huán)定義一樣，歸納證明并不是循環(huán)證明。每個(gè)正確的歸納證明都會(huì)有一個(gè)基本值驗(yàn)證部分，它與遞歸定義的基本部分相類似，在歸納證明時(shí)我們利用了比n值小時(shí)結(jié)論的正確性來(lái)證明取值為n時(shí)

21、結(jié)論的正確性。重復(fù)應(yīng)用歸納證明，可以減少對(duì)基本值驗(yàn)證的應(yīng)用。歸納證明3/31/2022551.C+允許編寫遞歸函數(shù)。2.一個(gè)正確的遞歸函數(shù)必須包含一個(gè)基本部分。函數(shù)中遞歸調(diào)用部分所使用的參數(shù)值應(yīng)比函數(shù)的參數(shù)值要小，以便函數(shù)的重復(fù)調(diào)用能最終獲得基本部分所提供的值。C+中的遞歸函數(shù)3/31/202256程序1-7計(jì)算n！的遞歸函數(shù)int Factorial(int n)/計(jì)算n！if(n=1) return 1;return n*Factorial(n-1);階乘(Factorial)3/31/202257遞歸調(diào)用過程中：程序的狀態(tài)(如局部變量、傳值形式參數(shù)的值、引用形式參數(shù)的值以及代碼的執(zhí)行位置

22、等)被保留在遞歸棧中。遞歸調(diào)用過程3/31/202258遞歸過程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。層層向下遞歸，退出時(shí)的次序正好相反3/31/202259遞歸工作棧每一次遞歸調(diào)用，需要分配存儲(chǔ)空間，來(lái)保留程序的狀態(tài)(如局部變量、參數(shù)值、代碼的執(zhí)行位置等) 。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。遞歸遞歸工作記錄工作記錄3/31/202260n遞歸簡(jiǎn)潔、易編寫、易懂n易證明正確性3/31/202261n遞歸效率低，重復(fù)計(jì)算多n改為非遞歸的目的是提高效率n單向遞歸可直接用迭代實(shí)現(xiàn)非遞歸n其他情形必須借助棧實(shí)現(xiàn)非遞歸3/31/202262計(jì)算n！的非遞歸函數(shù)int Factoria

23、l(int n)/計(jì)算n！if(n=1) return 1;int f=2;for(int i=3;i=n;i+)f*=i;return f;階乘非遞歸實(shí)現(xiàn)3/31/202263斐波那契數(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; twoback = oneback; oneback = Current; return Current;3/31/2

24、02264templateT Sum(T a,int n)/計(jì)算a0:n-1的和T tsum = 0;for(int i=0;i0時(shí)，n個(gè)元素的和是前面n-1個(gè)元素的和加上最后一個(gè)元素。程序1-8累加a0：n-13/31/202265templateTRsum(T a,int n)/計(jì)算a0:n-1的和 if(n0) return Rsum(a,n-1)+an-1; return 0;程序1-9遞歸計(jì)算a0：n-13/31/202266上樓梯遞歸思想3/31/2022671.a，b和c的排列方式有：abc,acb,bac,bca,cab和cba。2.n個(gè)元素的排列方式共有n！種。3.采用非遞歸

25、的C+函數(shù)來(lái)輸出n個(gè)元素的所有排列方式很困難。排列(Permutations)3/31/202268令E=e1,.,en表示n個(gè)元素的集合，令Ei為E中移去元素i以后所獲得的集合，perm(X)表示集合X中元素的排列方式，ei.perm(X)表示在perm(X)中的每個(gè)排列方式的前面均加上ei以后所得到的排列方式。例如，如果E=a,b,c，那么E1=b,c，perm(E1)=(bc,cb)，e1.perm(E1)=(abc,acb)。定義3/31/202269對(duì)于遞歸的基本部分，采用n=1。當(dāng)只有一個(gè)元素時(shí)，只可能產(chǎn)生一種排列方式，所以perm(E)=(e)，其中e是E中的唯一元素。遞歸部分:

26、當(dāng)n1時(shí)，perm(E)=e1.perm(E1) +e2.perm(E2)+e3.perm(E3)+en.perm(En)。這種遞歸定義形式是采用n個(gè)perm(X)來(lái)定義perm(E),其中每個(gè)X包含n-1個(gè)元素。排列遞歸思路3/31/202270當(dāng)n=3并且E=(a,b,c)時(shí)，按照前面的遞歸定義可得perm(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.pe

27、rm(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,cab,cba)。排列遞歸模擬3/31/202271程序程序1-101-10使用遞歸函數(shù)生成排列使用遞歸函數(shù)生成排列前綴為前綴為list0list0：k-1,k-1,后邊為后邊為listklistk：mm的全排列的全排列templatetemplateVoid Perm(T list,int k,int m)Void Perm(T li

28、st,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+) coutlisti; 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(lis

29、t,k+1,m);Perm(list,k+1,m);Swap(listk,listi);Swap(listk,listi); 排列遞歸實(shí)現(xiàn)3/31/202272程序1-11交換兩個(gè)值templateinline void Swap(T&a,T&b)/交換a和bT temp = a;a = b;b = temp;Swap函數(shù)3/31/2022731.The Operator new2.One-Dimensional Arrays3.Exception Handling4.The Operator delete5.Two-Dimensional Arrays1.3 Dynamic

30、Memory Allocation3/31/202274C/C+定義了如下幾個(gè)內(nèi)存區(qū)間:1.棧，就是那些由編譯器在需要的時(shí)候分配，在不需要的時(shí)候自動(dòng)清除的變量存儲(chǔ)區(qū)。里面的變量通常是局部變量、函數(shù)參數(shù)等。 2.堆，就是那些由new分配的內(nèi)存塊，他們的釋放編譯器不去管，由我們的應(yīng)用程序去控制，一般一個(gè)new就要對(duì)應(yīng)一個(gè)delete。如果程序員沒有釋放掉，那么在程序結(jié)束后，操作系統(tǒng)會(huì)自動(dòng)回收。 3.全局/靜態(tài)存儲(chǔ)區(qū)，全局變量和靜態(tài)變量被分配到同一塊內(nèi)存中，在C+里面沒有這個(gè)區(qū)分了，他們共同占用同一塊內(nèi)存區(qū)。4.常量存儲(chǔ)區(qū)，這是一塊比較特殊的存儲(chǔ)區(qū)，他們里面存放的是常量，不允許修改（當(dāng)然，你要通過非

31、正當(dāng)手段也可以修改） C+內(nèi)存分配3/31/202275棧的概念現(xiàn)代計(jì)算機(jī)(串行執(zhí)行機(jī)制)，都直接在代碼底層支持棧的數(shù)據(jù)結(jié)構(gòu)。這體現(xiàn)在，有專門的寄存器指向棧所在的地址，有專門的機(jī)器指令完成數(shù)據(jù)入棧出棧的操作。這種機(jī)制的特點(diǎn)是效率高，支持的數(shù)據(jù)有限，一般是整數(shù)，指針，浮點(diǎn)數(shù)等系統(tǒng)直接支持的數(shù)據(jù)類型，并不直接支持其他的數(shù)據(jù)結(jié)構(gòu)。因?yàn)闂５倪@種特點(diǎn)，對(duì)棧的使用在程序中是非常頻繁的。對(duì)子程序的調(diào)用就是直接利用棧完成的。機(jī)器的call指令里隱含了把返回地址推入棧，然后跳轉(zhuǎn)至子程序地址的操作，而子程序中的ret指令則隱含從堆棧中彈出返回地址并跳轉(zhuǎn)之的操作。C/C+中的自動(dòng)變量是直接利用棧的例子，這也就是為什

32、么當(dāng)函數(shù)返回時(shí)，該函數(shù)的自動(dòng)變量自動(dòng)失效的原因。3/31/202276w當(dāng)程序運(yùn)行到需要一個(gè)動(dòng)態(tài)分配的變量或?qū)ο髸r(shí)，必須向系統(tǒng)申請(qǐng)取得堆中的一塊所需大小的存貯空間，用于存貯該變量或?qū)ο?。w當(dāng)不再使用該變量或?qū)ο髸r(shí)，也就是它的生命結(jié)束時(shí)，要顯式釋放它所占用的存貯空間，這樣系統(tǒng)就能對(duì)該堆空間進(jìn)行再次分配，做到重復(fù)使用有限的資源。堆的概念3/31/202277棧和堆的比較棧是系統(tǒng)提供的功能，特點(diǎn)是快速高效，缺點(diǎn)是有限制，數(shù)據(jù)不靈活；而堆（編者按：原為是棧，因?yàn)楣P誤）是函數(shù)庫(kù)提供的功能，特點(diǎn)是靈活方便，數(shù)據(jù)適應(yīng)面廣泛，但是效率有一定降低。棧是系統(tǒng)數(shù)據(jù)結(jié)構(gòu)，對(duì)于進(jìn)程/線程是唯一的；堆是函數(shù)庫(kù)內(nèi)部數(shù)據(jù)結(jié)構(gòu)

33、，不一定唯一。棧空間分靜態(tài)分配和動(dòng)態(tài)分配兩種。靜態(tài)分配是編譯器完成的，比如自動(dòng)變量(auto)的分配。動(dòng)態(tài)分配由alloca函數(shù)完成。棧的動(dòng)態(tài)分配無(wú)需釋放(是自動(dòng)的)，也就沒有釋放函數(shù)。為可移植的程序起見，棧的動(dòng)態(tài)分配操作是不被鼓勵(lì)的！堆空間的分配總是動(dòng)態(tài)的，雖然程序結(jié)束時(shí)所有的數(shù)據(jù)空間都會(huì)被釋放回系統(tǒng)，但是精確的申請(qǐng)內(nèi)存/ 釋放內(nèi)存匹配是良好程序的基本要素。 3/31/202278存在的問題1.碎片問題：對(duì)于堆來(lái)講，頻繁的new/delete勢(shì)必會(huì)造成內(nèi)存空間的不連續(xù)，從而造成大量的碎片，使程序效率降低。對(duì)于棧來(lái)講，則不會(huì)存在這個(gè)問題，因?yàn)闂Ｊ窍冗M(jìn)后出的隊(duì)列，他們是如此的一一對(duì)應(yīng)，以至于永遠(yuǎn)

34、都不可能有一個(gè)內(nèi)存塊從棧中間彈出，在他彈出之前，在他上面的后進(jìn)的棧內(nèi)容已經(jīng)被彈出，詳細(xì)的可以參考數(shù)據(jù)結(jié)構(gòu)，這里我們就不再一一討論了。 2.分配方式：堆都是動(dòng)態(tài)分配的，沒有靜態(tài)分配的堆。棧有2種分配方式：靜態(tài)分配和動(dòng)態(tài)分配。靜態(tài)分配是編譯器完成的，比如局部變量的分配。動(dòng)態(tài)分配由alloca函數(shù)進(jìn)行分配，但是棧的動(dòng)態(tài)分配和堆是不同的，他的動(dòng)態(tài)分配是由編譯器進(jìn)行釋放，無(wú)需我們手工實(shí)現(xiàn)。 3/31/2022793.分配效率：棧是機(jī)器系統(tǒng)提供的數(shù)據(jù)結(jié)構(gòu)，計(jì)算機(jī)會(huì)在底層對(duì)棧提供支持：分配專門的寄存器存放棧的地址，壓棧出棧都有專門的指令執(zhí)行，這就決定了棧的效率比較高。堆則是C/C+函數(shù)庫(kù)提供的，它的機(jī)制是很

35、復(fù)雜的，例如為了分配一塊內(nèi)存，庫(kù)函數(shù)會(huì)按照一定的算法（具體的算法可以參考數(shù)據(jù)結(jié)構(gòu)/操作系統(tǒng)）在堆內(nèi)存中搜索可用的足夠大小的空間，如果沒有足夠大小的空間（可能是由于內(nèi)存碎片太多），就有可能調(diào)用系統(tǒng)功能去增加程序數(shù)據(jù)段的內(nèi)存空間，這樣就有機(jī)會(huì)分到足夠大小的內(nèi)存，然后進(jìn)行返回。顯然，堆的效率比棧要低得多。3/31/202280C+操作符new可用來(lái)進(jìn)行動(dòng)態(tài)存儲(chǔ)分配，該操作符返回一個(gè)指向所分配空間的指針。int *y ； -說(shuō)明yy = new int; -分配空間*y = 10; -賦值操作符new分配了一塊能存儲(chǔ)一個(gè)整數(shù)的空間，并將指向該空間的指針返回給y，y是對(duì)整數(shù)指針的引用，而*y則是對(duì)整數(shù)本

36、身的引用。1.3.1The Operator new3/31/202281動(dòng)態(tài)存儲(chǔ)分配方法:為了在運(yùn)行時(shí)創(chuàng)建一個(gè)一維浮點(diǎn)數(shù)組x，首先必須把x說(shuō)明成一個(gè)指向float的指針，然后為數(shù)組分配足夠的空間。例如，一個(gè)大小為n的一維浮點(diǎn) 數(shù)組可以按如下方式來(lái)創(chuàng)建：float *x=new floatn;操作符new分配n個(gè)浮點(diǎn)數(shù)所需要的空間，并返回指向第一個(gè)浮點(diǎn)數(shù)的指針?？梢允褂萌缦抡Z(yǔ)法來(lái)訪問每個(gè)數(shù)組元素：x0,x1,.,xn-1。1.3.2 One-Dimensional Arrays3/31/2022821.3.3異常處理不能分配足夠的空間，引發(fā)異常try catch(xalloc) catch()

37、3/31/202283Javafloat x=new floatn;One-Dimensional Arrays3/31/202284動(dòng)態(tài)分配的存儲(chǔ)空間不再需要時(shí)應(yīng)該被釋放，所釋放的空間可重新用來(lái)動(dòng)態(tài)創(chuàng)建新的結(jié)構(gòu)?？梢允褂肅+ 操作符delete來(lái)釋放由操作符new所分配的空間。下面的語(yǔ)句可以釋放分配給* y的在以及一維數(shù)組x：delete y;delete x;1.3.4The Operator delete3/31/202285void f() int* p=new int5; 3/31/202286分析看到new，我們首先就應(yīng)該想到，我們分配了一塊堆內(nèi)存；指針p呢？他分配的是一塊棧內(nèi)存；

38、所以這句話的意思就是：在棧內(nèi)存中存放了一個(gè)指向一塊堆內(nèi)存的指針p。在程序會(huì)先確定在堆中分配內(nèi)存的大小，然后調(diào)用operator new分配內(nèi)存，然后返回這塊內(nèi)存的首地址，放入棧中 3/31/202287釋放那么該怎么去釋放呢？是delete p么？澳，錯(cuò)了，應(yīng)該是delete p。這是為了告訴編譯器：我刪除的是一個(gè)數(shù)組 3/31/202288可以看成是由若干行組合起來(lái)的，每一行都是一個(gè)一維數(shù)組。1.3.5Two-Dimensional Arrays3/31/202289x0, x1, x2分別指向第0行，第1行和第2行的第一個(gè)元素。如果x是一個(gè)字符數(shù)組，那么x 0:2是指向字符的指針，而x本身

39、是一個(gè)指向指針的指針?？捎萌缦抡Z(yǔ)法來(lái)說(shuō)明x :char *x;Two-Dimensional Arrays3/31/202290template void Make2DArray( T * &x, int rows, int cols) / 創(chuàng)建一個(gè)二維數(shù)組/創(chuàng)建行指針x = new T*rows;/為每一行分配空間for (int i = 0 ; irows; i+)xi = new Tcols;程序1-13 創(chuàng)建一個(gè)二維數(shù)組3/31/202291template void Delete2DArray(T * &x, int rows)/ 刪除二維數(shù)組x/釋放為每一行所分配的

40、空間for (int i = 0 ; i 99) /美分?jǐn)?shù)目過多cerr Cents should be100endl;exit (1) ; sgn = s; dollars = d; cents = c;類的方法實(shí)現(xiàn)3/31/2022103程序1-19 IncrementCurrency& Currency:Increment(const Currency& x) / 增加量x .*this = Add(x);return *this;類的方法實(shí)現(xiàn)3/31/2022104#include #include curr1.hvoid main (void)Currency g,

41、h(plus, 3, 50), i, j;g.Set(minus, 2, 25);i . Set( -6.4 5 ) ;j = h.Add(g);j.Output(); cout endl;i . Increment( h ) ;i.Output(); cout endl;j = i.Add(g).Add(h);j.Output(); cout endl;j = i.Increment(g).Add(h);j.Output(); cout endl;i.Output(); cout endl;程序1-20 Currency類應(yīng)用示例3/31/2022105問題本例中： 有哪些類？ 有哪些對(duì)象？

42、 發(fā)送了哪些消息？3/31/2022106程序1-25 + , 的代碼Currency Currency:operator+(const Currency& x) const / 把x 累加至* t h i s .Currency y;y.amount = amount + x.amount;return y;/ 重載 全局函數(shù)ostream& operator(ostream& out, const Currency& x)x.Output(out); return out;Operator Overloading3/31/2022107程序1-26 操作符重

43、載的應(yīng)用#include #include curr3.hvoid main(void)Currency g, h(plus, 3, 50), i, j;g.Set(minus, 2, 25);i . Set(-6 . 4 5 ) ;j = h + g;cout j endl;i += h;cout i endl;j = i + g + h;cout j endl;Operator Overloading3/31/2022108n軟件工程實(shí)踐告訴我們，數(shù)據(jù)成員應(yīng)盡量保持為private成員。n通過增加保護(hù)類成員來(lái)訪問和修改數(shù)據(jù)成員的值，派生類可以間接訪問基類的數(shù)據(jù)成員。同時(shí)，可以修改基類的實(shí)現(xiàn)

44、細(xì)節(jié)而不會(huì)影響派生類。建議3/31/20221091.What Is Testing? (數(shù)學(xué)證明困難)2.Designing Test Data 3.Debugging1.5 Testing and Debugging3/31/2022110錯(cuò)誤與缺陷分類輕微 詞語(yǔ)拼寫錯(cuò)誤中等 誤導(dǎo)或重復(fù)信息使人不悅 被截?cái)嗟拿Q影響使用 有些交易沒有處理嚴(yán)重 丟失交易3/31/2022111錯(cuò)誤與缺陷分類（續(xù)）非常嚴(yán)重 不正確的交易處理極為嚴(yán)重 經(jīng)常出現(xiàn)“非常嚴(yán)重”錯(cuò)誤無(wú)法忍受 數(shù)據(jù)庫(kù)破壞災(zāi)難性 系統(tǒng)停機(jī)容易傳染 擴(kuò)展到其他系統(tǒng)停機(jī)3/31/20221121.由于采用嚴(yán)格的數(shù)學(xué)證明方法來(lái)證明一個(gè)程序的正確性是非常困難的，所以轉(zhuǎn)而求助于程序測(cè)試（program test）過程來(lái)實(shí)施這項(xiàng)工作。2.所謂程序測(cè)試是指在目標(biāo)計(jì)算機(jī)上利用輸入數(shù)據(jù)，也稱之為測(cè)試數(shù)據(jù)（ test data）來(lái)實(shí)際運(yùn)行該程序，把程序的實(shí)際行為與所期望的行為進(jìn)行比較。如果兩種行為不同，就可判定程序中有問題存在。3.然而，不幸的是，即使兩種行為相同，也不能夠斷定程序就是正確的，因?yàn)閷?duì)于其他的測(cè)試數(shù)據(jù)，兩種行為又可能不一樣。What Is Testing?3/31/20221131.如果使用了許多組測(cè)試數(shù)據(jù)都能夠看到這兩種行為是一樣的，我們可以增加對(duì)程序正確性的信心。通過使用所用可能的測(cè)試數(shù)據(jù)，可以驗(yàn)證一個(gè)程序是