數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用-c++語言描述（清晰版）

1、下載第1章 C + +程序設(shè)計大家好！現(xiàn)在我們將要開始一個穿越“數(shù)據(jù)結(jié)構(gòu)、算法和程序”這個抽象世界的特殊旅程，以解決現(xiàn)實生活中的許多難題。在程序開發(fā)過程中通常需要做到如下兩點：一是高效地描述數(shù)據(jù)；二是設(shè)計一個好的算法，該算法最終可用程序來實現(xiàn)。要想高效地描述數(shù)據(jù)，必須具備數(shù)據(jù)結(jié)構(gòu)領(lǐng)域的專門知識；而要想設(shè)計一個好的算法，則需要算法設(shè)計領(lǐng)域的專門知識。在著手研究數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計方法之前，需要你能夠熟練地運用 C + +編程并分析程

2、序，這些基本的技能通常是從 C + +課程以及其他分散的課程中學(xué)到的。本書的前兩章旨在幫助你回顧一下這些技能，其中的許多內(nèi)容你可能已經(jīng)很熟悉了。本章我們將回顧C(jī)++ 的一些特性。因為不是針對 C++ 新手，因此沒有介紹諸如賦值語句、if 語句和循環(huán)語句（如for 和w h i l e）等基本結(jié)構(gòu)，而是主要介紹一些可能已經(jīng)被你忽略的 C + +特性：? 參數(shù)傳遞方式（如傳值、引用和常量引用） 。? 函數(shù)返回方式（如返值、引

3、用和常量引用） 。? 模板函數(shù)。? 遞歸函數(shù)。? 常量函數(shù)。? 內(nèi)存分配和釋放函數(shù)：n e w與d e l e t e。? 異常處理結(jié)構(gòu)：t r y, c a t c h和t h r o w。? 類與模板類。? 類的共享成員、保護(hù)成員和私有成員。? 友元。? 操作符重載。本章中沒有涉及的其他C + +特性將在后續(xù)章節(jié)中在需要的時候加以介紹。本章還給出了如下應(yīng)用程序的代碼：? 一維和二維數(shù)組的動態(tài)分

4、配與釋放。? 求解二次方程。? 生成n 個元素的所有排列方式。? 尋找n個元素中的最大值。此外，本章還給出了如何測試和調(diào)試程序的一些技巧。1.1 引言在檢查程序的時候我們應(yīng)該問一問：? 它正確嗎？第一部分 預(yù) 備 知 識1.2.2 模板函數(shù)假定我們希望編寫另外一個函數(shù)來計算與程序 1 - 1相同的表達(dá)式，不過這次 a，b和c是f l o a t類型，結(jié)果也是f l o a t類型。程序1 - 2中給出了具

5、體的代碼。程序1 - 1和1 - 2的區(qū)別僅在于形式參數(shù)以及函數(shù)返回值的數(shù)據(jù)類型。程序1-2 計算一個浮點數(shù)表達(dá)式float Abc(float a, float b, float c){return a+b+b*c+(a+b-c)/(a+b)+4;}實際上不必對每一種可能的形式參數(shù)的類型都重新編寫一個相應(yīng)的函數(shù)?？梢跃帉懸欢瓮ㄓ玫拇a，將參數(shù)的數(shù)據(jù)類型作為一個變量，它的值由編譯器來確定。程序 1 - 3中給出了這樣一段

6、使用t e m p l a t e語句編寫的通用代碼。程序1-3 利用模板函數(shù)計算一個表達(dá)式templateT Abc(T a, T b, T c){return a+b+b*c+(a+b-c)/(a+b)+4;}利用這段通用代碼，通過把T替換為i n t，編譯器可以立即構(gòu)造出程序1 - 1，把T 替換為f l o a t又可以立即構(gòu)造出程序 1 - 2。事實上，通過把T替換為d o u

7、 b l e或l o n g，編譯器又可以構(gòu)造出函數(shù)A b c的雙精度型版本和長整型版本。把函數(shù) Abc 編寫成模板函數(shù)可以讓我們不必了解形式參數(shù)的數(shù)據(jù)類型。1.2.3 引用參數(shù)程序1 - 3中形式參數(shù)的用法會增加程序的運行開銷。例如，我們來考察一下函數(shù)被調(diào)用以及返回時所涉及的操作。假定a，b 和c 是傳值參數(shù)，在函數(shù)被調(diào)用時，類型T 的復(fù)制構(gòu)造函數(shù)把相應(yīng)的實際參數(shù)分別復(fù)制到形式參數(shù)a，b 和c 之中，以供函數(shù)使

8、用；而在函數(shù)返回時，類型T的析構(gòu)函數(shù)會被喚醒，以便釋放形式參數(shù)a，b 和c。假定數(shù)據(jù)類型為用戶自定義的 M a t r i x，那么它的復(fù)制構(gòu)造函數(shù)將負(fù)責(zé)復(fù)制其所有元素，而析構(gòu)函數(shù)則負(fù)責(zé)逐個釋放每個元素（假定 Matrix 已經(jīng)定義了操作符 +，*和 /） 。如果我們用具有1 0 0 0個元素的Matrix 作為實際參數(shù)來調(diào)用函數(shù) A b c，那么復(fù)制三個實際參數(shù)給 a，b 和c將需要3 0 0 0次操作。當(dāng)函

9、數(shù) A b c返回時，其析構(gòu)函數(shù)又需要花費額外的 3 0 0 0次操作來釋放 a，b和c。在程序 1 - 4所示的代碼中， a，b 和c 是引用參數(shù)（ reference parameter） 。如果用語句A bc (x,y, z) 來調(diào)用函數(shù)A b c，其中x、y 和z 是相同的數(shù)據(jù)類型，那么這些實際參數(shù)將被分別賦予名稱a，b 和c，因此，在函數(shù)Abc 執(zhí)行期間，x、y 和z 被用來替換對應(yīng)的a，b 和c。與傳值參