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

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

2、序，這些基本的技能通常是從 C + +課程以及其他分散的課程中學(xué)到的。本書(shū)的前兩章旨在幫助你回顧一下這些技能，其中的許多內(nèi)容你可能已經(jīng)很熟悉了。本章我們將回顧C(jī)++ 的一些特性。因?yàn)椴皇轻槍?duì) C++ 新手，因此沒(méi)有介紹諸如賦值語(yǔ)句、if 語(yǔ)句和循環(huán)語(yǔ)句（如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ù)成員和私有成員。? 友元。? 操作符重載。本章中沒(méi)有涉及的其他C + +特性將在后續(xù)章節(jié)中在需要的時(shí)候加以介紹。本章還給出了如下應(yīng)用程序的代碼：? 一維和二維數(shù)組的動(dòng)態(tài)分

4、配與釋放。? 求解二次方程。? 生成n 個(gè)元素的所有排列方式。? 尋找n個(gè)元素中的最大值。此外，本章還給出了如何測(cè)試和調(diào)試程序的一些技巧。1.1 引言在檢查程序的時(shí)候我們應(yīng)該問(wèn)一問(wèn)：? 它正確嗎？第一部分 預(yù) 備 知 識(shí)1.2.2 模板函數(shù)假定我們希望編寫(xiě)另外一個(gè)函數(shù)來(lái)計(jì)算與程序 1 - 1相同的表達(dá)式，不過(guò)這次 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 計(jì)算一個(gè)浮點(diǎn)數(shù)表達(dá)式float Abc(float a, float b, float c){return a+b+b*c+(a+b-c)/(a+b)+4;}實(shí)際上不必對(duì)每一種可能的形式參數(shù)的類型都重新編寫(xiě)一個(gè)相應(yīng)的函數(shù)?？梢跃帉?xiě)一段通用的代碼，將參數(shù)的數(shù)據(jù)類型作為一個(gè)變量，它的值由編譯器來(lái)確定。程序 1 - 3中給出了這樣一段

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

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

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

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