第一章 軟件設(shè)計(jì)概論

1、第一章第一章 軟件設(shè)計(jì)概論軟件設(shè)計(jì)概論第五章第五章 類與對象類與對象第四章第四章 函數(shù)函數(shù)第三章第三章 結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)第二章第二章 C+基礎(chǔ)知識基礎(chǔ)知識第十章第十章 異常處理異常處理第九章第九章 輸入輸入/輸出流類庫輸出流類庫第八章第八章 繼承與多態(tài)繼承與多態(tài)第七章第七章 動態(tài)內(nèi)存分配動態(tài)內(nèi)存分配第六章第六章 指針與數(shù)組指針與數(shù)組第十一章第十一章 標(biāo)準(zhǔn)模板類庫標(biāo)準(zhǔn)模板類庫(STL) 附附 錄錄 目目 錄錄第一章第一章 軟件設(shè)計(jì)概述軟件設(shè)計(jì)概述軟件設(shè)計(jì)軟件設(shè)計(jì)是一個(gè)將是一個(gè)將人類思維人類思維物化為物化為計(jì)算機(jī)思維計(jì)算機(jī)思維的的過程，通過這個(gè)過程計(jì)算機(jī)獲得一定程度的獨(dú)立過程，通過這個(gè)

2、過程計(jì)算機(jī)獲得一定程度的獨(dú)立加工甚至思維的能力，從而將人類思維推向更高加工甚至思維的能力，從而將人類思維推向更高層次。關(guān)于軟件設(shè)計(jì)的概念和方法的研究是隨著層次。關(guān)于軟件設(shè)計(jì)的概念和方法的研究是隨著計(jì)算機(jī)應(yīng)用的深入和所處理問題的復(fù)雜化而不斷計(jì)算機(jī)應(yīng)用的深入和所處理問題的復(fù)雜化而不斷加深的。本章將就軟件設(shè)計(jì)的相關(guān)加深的。本章將就軟件設(shè)計(jì)的相關(guān)概念概念和程序設(shè)和程序設(shè)計(jì)方法的計(jì)方法的演化發(fā)展演化發(fā)展作一簡要介紹。作一簡要介紹。1.1 軟件與軟件危機(jī)軟件與軟件危機(jī)1.2 軟軟 件件 工工 程程1.3 程序設(shè)計(jì)方法程序設(shè)計(jì)方法 1.6 一個(gè)簡單的一個(gè)簡單的C+程序程序1.5 C語言和面向?qū)ο蟮恼Z言和面向

3、對象的C+1.4 算法的設(shè)計(jì)與分析算法的設(shè)計(jì)與分析 第一章第一章 軟件設(shè)計(jì)概述軟件設(shè)計(jì)概述 1.1 軟件與軟件危機(jī)軟件與軟件危機(jī)什么是軟件什么是軟件什么是軟件危機(jī)什么是軟件危機(jī) 軟件 程序軟件危機(jī)首次爆發(fā)于二十世紀(jì)六十年代。在大型程序設(shè)計(jì)中，人們發(fā)現(xiàn)投入大量的人力、物力、時(shí)間開發(fā)出的軟件，其成本、效率、質(zhì)量等方面卻處于失控狀態(tài)，尤其軟件維護(hù)異常困難。程序的修改擴(kuò)充往往需要大量重復(fù)性投入。 1.1 軟件與軟件危機(jī)軟件與軟件危機(jī)軟件危機(jī)產(chǎn)生的原因主要有三個(gè)：軟件危機(jī)產(chǎn)生的原因主要有三個(gè)：2 2 軟件是一種邏輯產(chǎn)品而非物理產(chǎn)品，軟件的軟件是一種邏輯產(chǎn)品而非物理產(chǎn)品，軟件的開發(fā)過程本質(zhì)上是人的思考過程

4、。開發(fā)過程本質(zhì)上是人的思考過程。3 3 人的智力在面對越來越復(fù)雜的問題時(shí)，處理人的智力在面對越來越復(fù)雜的問題時(shí)，處理問題的效率會越來越低。問題的效率會越來越低。1 1 軟件開發(fā)者不熟悉用戶問題的領(lǐng)域，或沒有軟件開發(fā)者不熟悉用戶問題的領(lǐng)域，或沒有理解用戶需求，軟件產(chǎn)品與要求不一致。理解用戶需求，軟件產(chǎn)品與要求不一致。1.2 軟件工程軟件工程軟件危機(jī)的軟件危機(jī)的 出現(xiàn)迫使人們重新認(rèn)識出現(xiàn)迫使人們重新認(rèn)識軟件和軟件開發(fā)過程。軟件和軟件開發(fā)過程。大型軟件開發(fā)也應(yīng)該借鑒建筑、機(jī)械大型軟件開發(fā)也應(yīng)該借鑒建筑、機(jī)械等行業(yè)的發(fā)展過程，由等行業(yè)的發(fā)展過程，由“手工方式手工方式”向向“工程化工程化”方向發(fā)展。方向

5、發(fā)展。19681968年在北年在北大西洋公約組織大西洋公約組織(NATO)(NATO)的年會上的年會上首次首次提出提出軟件工程軟件工程的概念，此后又逐步提的概念，此后又逐步提出出軟件生命期軟件生命期的概念。的概念。1.2 軟件工程軟件工程軟件工程的提出和軟件的定義軟件工程的提出和軟件的定義 軟件軟件是程序、方法、規(guī)則、相關(guān)文檔以及在計(jì)算機(jī)上運(yùn)行是程序、方法、規(guī)則、相關(guān)文檔以及在計(jì)算機(jī)上運(yùn)行所必需的數(shù)據(jù)的集合。而所必需的數(shù)據(jù)的集合。而軟件工程軟件工程是開發(fā)、運(yùn)行、維護(hù)軟件是開發(fā)、運(yùn)行、維護(hù)軟件的系統(tǒng)方法。的系統(tǒng)方法。軟件生命期軟件生命期軟件生命期指從開始研制到廢棄不用的整個(gè)期間，可劃分軟件生命期

6、指從開始研制到廢棄不用的整個(gè)期間，可劃分為五個(gè)階段：為五個(gè)階段：需求分析需求分析、設(shè)計(jì)設(shè)計(jì)、編程編程、測試測試和和運(yùn)行維護(hù)運(yùn)行維護(hù)。 軟件的質(zhì)量標(biāo)準(zhǔn)軟件的質(zhì)量標(biāo)準(zhǔn)正確性正確性 健壯性健壯性 可維護(hù)性可維護(hù)性可用性可用性 可重用性可重用性 效率等效率等1.2 軟件工程軟件工程正確性 軟件的正確性指的是軟件系統(tǒng)在正常條件下能夠正確工作，完成規(guī)定功能。這是軟件的首要指標(biāo)。例如，要求設(shè)計(jì)程序，輸入一批數(shù)據(jù)，計(jì)算它們的累加和。在這里，正確性就是正確能正確計(jì)算累加和。1.2 軟件工程軟件工程健壯性健壯性軟件的健壯性指的是軟件的健壯性指的是在意外情況下在意外情況下（如輸入數(shù)據(jù)不合理或（如輸入數(shù)據(jù)不合理或某些

7、硬件故障），軟件系統(tǒng)仍能適當(dāng)?shù)毓ぷ?，并對意外情況某些硬件故障），軟件系統(tǒng)仍能適當(dāng)?shù)毓ぷ?，并對意外情況進(jìn)行適當(dāng)處理，而不致于導(dǎo)致錯誤結(jié)果甚至系統(tǒng)的癱瘓或死進(jìn)行適當(dāng)處理，而不致于導(dǎo)致錯誤結(jié)果甚至系統(tǒng)的癱瘓或死機(jī)。機(jī)。例如，要求設(shè)計(jì)程序，根據(jù)輸入的三邊例如，要求設(shè)計(jì)程序，根據(jù)輸入的三邊a a、b b、c c的長度判別的長度判別三角形類型。現(xiàn)有如下設(shè)計(jì)思想：若三角形類型?，F(xiàn)有如下設(shè)計(jì)思想：若a a、b b、c c中只有兩個(gè)量相中只有兩個(gè)量相等，則為等腰三角形，若三個(gè)量均相等，則為等邊三角形，等，則為等腰三角形，若三個(gè)量均相等，則為等邊三角形，否則為一般三角形。如果輸入為（否則為一般三角形。如果輸入為（

8、-2-2，-2-2，-2-2）時(shí)，程序輸）時(shí)，程序輸出為：等邊三角形。這個(gè)結(jié)果顯然是錯誤的。這是由于程序出為：等邊三角形。這個(gè)結(jié)果顯然是錯誤的。這是由于程序?qū)Σ缓侠頂?shù)據(jù)不能進(jìn)行適當(dāng)處理，我們就說這個(gè)程序的健壯對不合理數(shù)據(jù)不能進(jìn)行適當(dāng)處理，我們就說這個(gè)程序的健壯性不好。性不好。1.2 軟件工程軟件工程可維護(hù)性可維護(hù)性軟件的維護(hù)包括軟件的維護(hù)包括發(fā)現(xiàn)并改正軟件的錯誤發(fā)現(xiàn)并改正軟件的錯誤，以，以及由于軟件運(yùn)行環(huán)境發(fā)生變化或軟件功能擴(kuò)充及由于軟件運(yùn)行環(huán)境發(fā)生變化或軟件功能擴(kuò)充而而對軟件進(jìn)行的改動對軟件進(jìn)行的改動。 軟件的可維護(hù)性指的是軟件容易維護(hù)的程度。軟件的可維護(hù)性指的是軟件容易維護(hù)的程度。一般地說

9、，軟件的可讀性好，容易理解，維護(hù)一般地說，軟件的可讀性好，容易理解，維護(hù)起來也就比較容易。因此可讀性是可維護(hù)性的起來也就比較容易。因此可讀性是可維護(hù)性的基礎(chǔ)。基礎(chǔ)。 1.3 程序設(shè)計(jì)方法程序設(shè)計(jì)方法1.3.11.3.1 傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì) SP(StructuredSP(Structured Programming) Programming)1.3.21.3.2 面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì) OOP(ObjectOOP(Object Oriented Programming) Oriented Programming)1.3.1 傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)傳統(tǒng)的結(jié)構(gòu)化程

10、序設(shè)計(jì)傳統(tǒng)的程序設(shè)計(jì)方法可以歸結(jié)為傳統(tǒng)的程序設(shè)計(jì)方法可以歸結(jié)為，將程序定義為處理數(shù)據(jù)，將程序定義為處理數(shù)據(jù)的一系列過程。這種設(shè)計(jì)方法的著眼點(diǎn)是的一系列過程。這種設(shè)計(jì)方法的著眼點(diǎn)是，特點(diǎn)是數(shù)據(jù)與程序分離，即，特點(diǎn)是數(shù)據(jù)與程序分離，即數(shù)據(jù)數(shù)據(jù)與數(shù)據(jù)處理分離與數(shù)據(jù)處理分離。 結(jié)構(gòu)化程序設(shè)計(jì)的基本思想是采用結(jié)構(gòu)化程序設(shè)計(jì)的基本思想是采用的設(shè)計(jì)方法和的設(shè)計(jì)方法和的控制的控制結(jié)構(gòu)。結(jié)構(gòu)。1.3.1 傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)模塊模塊 22.12.2模塊模塊 11.21.11.31.3.11.3.21.3.3模塊模塊 33.13.23.1.13.1.2 程程 序序1.3.1 傳統(tǒng)的結(jié)構(gòu)化程序設(shè)

11、傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)計(jì)舉一個(gè)簡單的例子，要求讀入一組整數(shù)，統(tǒng)計(jì)其中舉一個(gè)簡單的例子，要求讀入一組整數(shù)，統(tǒng)計(jì)其中正整數(shù)和負(fù)整數(shù)的個(gè)數(shù)。正整數(shù)和負(fù)整數(shù)的個(gè)數(shù)。該任務(wù)的模塊結(jié)構(gòu)及細(xì)化過程如下：該任務(wù)的模塊結(jié)構(gòu)及細(xì)化過程如下：1.1.讀入數(shù)據(jù)讀入數(shù)據(jù)2.2.統(tǒng)計(jì)正數(shù)、負(fù)數(shù)統(tǒng)計(jì)正數(shù)、負(fù)數(shù)的個(gè)數(shù)的個(gè)數(shù); ; 3. 輸出結(jié)果輸出結(jié)果 2.1 2.1 如數(shù)大于如數(shù)大于0 0，正整數(shù)個(gè)數(shù)加，正整數(shù)個(gè)數(shù)加1 12.2 2.2 如數(shù)小于如數(shù)小于0 0，負(fù)整數(shù)個(gè)數(shù)加，負(fù)整數(shù)個(gè)數(shù)加1 12.3: 2.3: 取下一個(gè)整數(shù)取下一個(gè)整數(shù)正整數(shù)個(gè)數(shù)為正整數(shù)個(gè)數(shù)為0 0；負(fù)整數(shù)個(gè)數(shù)；負(fù)整數(shù)個(gè)數(shù)0 0 取第一個(gè)整數(shù)取第一個(gè)整數(shù)重復(fù)

12、重復(fù)至統(tǒng)至統(tǒng)計(jì)完計(jì)完1.3.1 傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)為處理復(fù)雜問題提供了有力為處理復(fù)雜問題提供了有力手段，但到手段，但到8080年代末，這種設(shè)計(jì)方法逐漸暴年代末，這種設(shè)計(jì)方法逐漸暴露出以下露出以下缺陷缺陷： （1 1）難以適應(yīng)大型軟件的設(shè)計(jì)。）難以適應(yīng)大型軟件的設(shè)計(jì)。 （2 2）程序可重用性差。）程序可重用性差。1.3.2 面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì)為什么要引入面向?qū)ο蟮脑O(shè)計(jì)為什么要引入面向?qū)ο蟮脑O(shè)計(jì)方法方法面向?qū)ο蟮脑O(shè)計(jì)方法與面向過面向?qū)ο蟮脑O(shè)計(jì)方法與面向過程的設(shè)計(jì)方法有什么關(guān)系程的設(shè)計(jì)方法有什么關(guān)系1.3.2 面向?qū)ο蟮某绦蛟O(shè)計(jì)面向

13、對象的程序設(shè)計(jì)面向過程程序設(shè)計(jì)缺點(diǎn)的根源在于面向過程程序設(shè)計(jì)缺點(diǎn)的根源在于數(shù)據(jù)與數(shù)據(jù)處理數(shù)據(jù)與數(shù)據(jù)處理分離分離。面向?qū)ο蟪绦蛟O(shè)計(jì)模擬自然界認(rèn)識和處理事物的方面向?qū)ο蟪绦蛟O(shè)計(jì)模擬自然界認(rèn)識和處理事物的方法，將法，將數(shù)據(jù)數(shù)據(jù)和和對數(shù)據(jù)的操作方法對數(shù)據(jù)的操作方法放在一起，形成一個(gè)相放在一起，形成一個(gè)相對獨(dú)立的整體對獨(dú)立的整體對象（對象（objectobject），同類對象還可抽象，同類對象還可抽象出出共性共性，形成，形成類（類（class class ）。一個(gè)類中的數(shù)據(jù)。一個(gè)類中的數(shù)據(jù)通常只能通常只能通過本類提供的方法進(jìn)行處理，這些方法成為該類與外通過本類提供的方法進(jìn)行處理，這些方法成為該類與外部的

14、部的接口接口。對象之間通過。對象之間通過消息（消息（messagemessage）進(jìn)行通訊。進(jìn)行通訊。1.3.2 面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì)1 基基 本本 概概 念念3 “面向?qū)ο竺嫦驅(qū)ο蟆背绦蛟O(shè)計(jì)的特點(diǎn)程序設(shè)計(jì)的特點(diǎn)2 面向?qū)ο蟮能浖_發(fā)方法面向?qū)ο蟮能浖_發(fā)方法1基基 本本 概概 念念1 基基 本本 概概 念念屬性屬性行為行為表針表針旋鈕旋鈕其他機(jī)械機(jī)構(gòu)其他機(jī)械機(jī)構(gòu)調(diào)節(jié)旋鈕調(diào)節(jié)旋鈕對 象1 基基 本本 概概 念念是一個(gè)抽象的概念，用來描述某一類對象所共是一個(gè)抽象的概念，用來描述某一類對象所共有的、本質(zhì)的屬性和類行為。有的、本質(zhì)的屬性和類行為。 類類類的一個(gè)具體實(shí)現(xiàn)，稱為實(shí)例類的一

15、個(gè)具體實(shí)現(xiàn)，稱為實(shí)例手表手表 一塊手表一塊手表類類 對象對象描述這類對象共有的、本質(zhì)的屬性和行為描述這類對象共有的、本質(zhì)的屬性和行為手表共有的屬性（表針、旋鈕、內(nèi)部結(jié)構(gòu)）手表共有的屬性（表針、旋鈕、內(nèi)部結(jié)構(gòu)）和行為（調(diào)節(jié)旋鈕）和行為（調(diào)節(jié)旋鈕）具體到一只圓形的或方形的手表具體到一只圓形的或方形的手表1基基 本本 概概 念念我們把對象之間產(chǎn)生我們把對象之間產(chǎn)生相互作用相互作用所傳遞的所傳遞的信息信息稱做消息。稱做消息。 消消 息息啟啟 動動發(fā)送消息發(fā)送消息接收并響應(yīng)消息接收并響應(yīng)消息轉(zhuǎn)轉(zhuǎn) 向向2面向?qū)ο蟮能浖_發(fā)方法面向?qū)ο蟮能浖_發(fā)方法面向?qū)ο筌浖_發(fā)的根本面向?qū)ο筌浖_發(fā)的根本合理性合理性在

16、于它符在于它符合客觀世界的組成方式和大腦的思維方式。合客觀世界的組成方式和大腦的思維方式。在大型程序開發(fā)過程中，編碼只是其中很在大型程序開發(fā)過程中，編碼只是其中很小一部分，應(yīng)當(dāng)采用工程化的方法，并將面小一部分，應(yīng)當(dāng)采用工程化的方法，并將面向?qū)ο蟮乃枷胴灤┯谲浖_發(fā)全過程，這就向?qū)ο蟮乃枷胴灤┯谲浖_發(fā)全過程，這就是是面向?qū)ο蟮能浖こ堂嫦驅(qū)ο蟮能浖こ獭Ｃ嫦鄬ο蟮能浖こ掏瑯幼裱嫦鄬ο蟮能浖こ掏瑯幼裱謱映橄蠓謱映橄?、逐步?xì)化逐步細(xì)化的原則。軟件開發(fā)過程包括以下五的原則。軟件開發(fā)過程包括以下五個(gè)階段：個(gè)階段： 2 面向?qū)ο蟮能浖_發(fā)方法面向?qū)ο蟮能浖_發(fā)方法測試的任務(wù)在于發(fā)現(xiàn)并改正程序中的

17、錯誤。測試的任務(wù)在于發(fā)現(xiàn)并改正程序中的錯誤。面向?qū)ο蟮姆治雒嫦驅(qū)ο蟮姆治?OOA)面向?qū)ο蟮脑O(shè)計(jì)面向?qū)ο蟮脑O(shè)計(jì)(OOD)面向?qū)ο蟮木幊堂嫦驅(qū)ο蟮木幊?OOP)面向?qū)ο蟮臏y試面向?qū)ο蟮臏y試(OOT)分析階段的主要任務(wù)是按照面向?qū)ο蟮母拍詈头椒?，從問題中分析階段的主要任務(wù)是按照面向?qū)ο蟮母拍詈头椒?，從問題中識識別別出有意義的出有意義的對象對象，以及對象的，以及對象的屬性屬性、行為行為和對象間的和對象間的通信通信，進(jìn)而，進(jìn)而抽象抽象出類結(jié)構(gòu)，最終將它們描述出來，形成一個(gè)出類結(jié)構(gòu)，最終將它們描述出來，形成一個(gè)需求模型需求模型。設(shè)計(jì)階段從需求模型出發(fā)，分別進(jìn)行類的設(shè)計(jì)和應(yīng)用程序的設(shè)計(jì)。設(shè)計(jì)階段從需求模型

18、出發(fā)，分別進(jìn)行類的設(shè)計(jì)和應(yīng)用程序的設(shè)計(jì)。編程階段實(shí)現(xiàn)由設(shè)計(jì)表示到面向?qū)ο蟪绦蛟O(shè)計(jì)語言描述的轉(zhuǎn)換。編程階段實(shí)現(xiàn)由設(shè)計(jì)表示到面向?qū)ο蟪绦蛟O(shè)計(jì)語言描述的轉(zhuǎn)換。面向?qū)ο蟮木S護(hù)面向?qū)ο蟮木S護(hù)(OOSM)3“面向?qū)ο竺嫦驅(qū)ο蟆背绦蛟O(shè)計(jì)的特點(diǎn)程序設(shè)計(jì)的特點(diǎn)(1)封裝性封裝性(2) 繼承與派生性繼承與派生性(3) 多態(tài)性多態(tài)性3 “面向?qū)ο竺嫦驅(qū)ο蟆背绦蛟O(shè)計(jì)的特點(diǎn)程序設(shè)計(jì)的特點(diǎn)封裝性封裝性內(nèi)內(nèi)外外機(jī)械零件機(jī)械零件動作動作調(diào)節(jié)旋鈕調(diào)節(jié)旋鈕讀表盤讀表盤對象是一個(gè)對象是一個(gè)封裝體封裝體，在其中封裝了該，在其中封裝了該對象的屬性和操作。通過限制對屬性和操對象的屬性和操作。通過限制對屬性和操作的訪問權(quán)限，可以將屬性作的

19、訪問權(quán)限，可以將屬性“隱藏隱藏”在對在對象內(nèi)部，對外提供一定的象內(nèi)部，對外提供一定的接口接口，在對象之，在對象之外只能通過接口對對象進(jìn)行操作。外只能通過接口對對象進(jìn)行操作。C+C+通過建立數(shù)據(jù)類型通過建立數(shù)據(jù)類型類類來支持封來支持封裝和數(shù)據(jù)隱藏。裝和數(shù)據(jù)隱藏。封裝性增加了封裝性增加了對象的獨(dú)對象的獨(dú)立性立性，從而保證了，從而保證了數(shù)據(jù)的可靠性數(shù)據(jù)的可靠性。一個(gè)。一個(gè)定義完好的類可以作為定義完好的類可以作為獨(dú)立模塊獨(dú)立模塊使用。使用。汽車汽車客車客車貨車貨車小轎車小轎車大客車大客車載貨載貨載人載人小，速度快小，速度快大，速度慢大，速度慢3 “面向?qū)ο竺嫦驅(qū)ο蟆背绦蛟O(shè)計(jì)的特點(diǎn)程序設(shè)計(jì)的特點(diǎn)繼承與派

20、生繼承與派生以汽車為例看客觀世界描述事物的方式：以汽車為例看客觀世界描述事物的方式：當(dāng)定義了一個(gè)類后，又需定義當(dāng)定義了一個(gè)類后，又需定義一個(gè)新類，這個(gè)新類與原來的類一個(gè)新類，這個(gè)新類與原來的類相比，只是增加或修改了部分屬相比，只是增加或修改了部分屬性和操作，這時(shí)可以用原來的類性和操作，這時(shí)可以用原來的類派生派生出新類，新類中只需描述自出新類，新類中只需描述自己所特有的屬性和操作。己所特有的屬性和操作。面向?qū)ο蟪绦蛟O(shè)計(jì)提供了類似的機(jī)制：面向?qū)ο蟪绦蛟O(shè)計(jì)提供了類似的機(jī)制：繼承性大大簡化了對問題的描述，大大提高了程序的可重繼承性大大簡化了對問題的描述，大大提高了程序的可重用性，從而提高了程序設(shè)計(jì)、修

21、改、擴(kuò)充的效率。用性，從而提高了程序設(shè)計(jì)、修改、擴(kuò)充的效率。新類稱為新類稱為子類子類或或派生類派生類，原來的類稱為，原來的類稱為基類基類。派生可以一直。派生可以一直進(jìn)行下去，形成一個(gè)派生樹。進(jìn)行下去，形成一個(gè)派生樹。3“面向?qū)ο竺嫦驅(qū)ο蟆背绦蛟O(shè)計(jì)的特點(diǎn)程序設(shè)計(jì)的特點(diǎn)語文、數(shù)學(xué)、英語、政治、語文、數(shù)學(xué)、英語、政治、物理、化學(xué)、生物物理、化學(xué)、生物多態(tài)性多態(tài)性多態(tài)性指，多態(tài)性指，同一個(gè)同一個(gè)消息消息被被不同對象不同對象接收時(shí)，接收時(shí)，產(chǎn)生產(chǎn)生不同結(jié)果不同結(jié)果，即實(shí)現(xiàn)，即實(shí)現(xiàn)同一接口，不同方法同一接口，不同方法。高中生計(jì)計(jì) 算算平均成績平均成績大學(xué)生高數(shù)、英語、計(jì)算機(jī)、線高數(shù)、英語、計(jì)算機(jī)、線性代數(shù)

22、性代數(shù)3 “面向?qū)ο竺嫦驅(qū)ο蟆背绦蛟O(shè)計(jì)的特點(diǎn)程序設(shè)計(jì)的特點(diǎn)繼承繼承和和多態(tài)多態(tài)性組合，可以生成很多相性組合，可以生成很多相似但又獨(dú)一無二的對象。似但又獨(dú)一無二的對象。繼承繼承性使得這性使得這些對象可以共享許多相似特性，而些對象可以共享許多相似特性，而多態(tài)多態(tài)又使同一個(gè)操作對不同對象產(chǎn)生不同表又使同一個(gè)操作對不同對象產(chǎn)生不同表現(xiàn)形式。這樣不僅提高了程序設(shè)計(jì)的靈現(xiàn)形式。這樣不僅提高了程序設(shè)計(jì)的靈活性，而且減輕了分別設(shè)計(jì)的負(fù)擔(dān)?；钚?，而且減輕了分別設(shè)計(jì)的負(fù)擔(dān)。1.4 算法的設(shè)計(jì)與分析算法的設(shè)計(jì)與分析1.4.1 算算 法法 的的 概概 念念 1.4.3 常常 用用 算算 法法 介介 紹紹 1.4.2

23、算算 法法 的的 表表 示示1.4.1 算算 法法 的的 概概 念念 通俗地說，算法就是解決問題的步驟。通俗地說，算法就是解決問題的步驟。算法是程序設(shè)計(jì)學(xué)習(xí)的重點(diǎn)。算法是程序設(shè)計(jì)學(xué)習(xí)的重點(diǎn)。用計(jì)算機(jī)解決問題的算法應(yīng)具有以下特征：用計(jì)算機(jī)解決問題的算法應(yīng)具有以下特征：(1)(1) 可執(zhí)行性可執(zhí)行性(2)(2) 確定性確定性(3)(3) 有窮性有窮性(4)(4) 可輸入輸出信息可輸入輸出信息1.4.2算法的表示及三種基本結(jié)構(gòu)算法的表示及三種基本結(jié)構(gòu)3 循循 環(huán)環(huán) 結(jié)結(jié) 構(gòu)構(gòu)1 1 順順 序序 結(jié)結(jié) 構(gòu)構(gòu)2 分分 支支 結(jié)結(jié) 構(gòu)構(gòu)num115；1.4.2算法的表示及三種基本結(jié)構(gòu)算法的表示及三種基本結(jié)

24、構(gòu)(1) 順序結(jié)構(gòu)順序結(jié)構(gòu)【例【例1 11 1】 求兩求兩數(shù)之和。數(shù)之和。塊1塊2塊3流程圖 寄存器35顯示結(jié)果：顯示結(jié)果：35 num115 num220 sum35num220；sumnum1+num2; 演示算法執(zhí)行過程演示算法執(zhí)行過程輸出輸出sum;1.4.2算法的表示及三種基本結(jié)構(gòu)算法的表示及三種基本結(jié)構(gòu)(2) 分支結(jié)構(gòu)分支結(jié)構(gòu)【例【例12】 輸入三個(gè)數(shù)，輸出其中的最大數(shù)。輸入三個(gè)數(shù)，輸出其中的最大數(shù)。 x7;y12;z10;if(xy) maxx;else max y;if (zmax) maxz;輸出輸出max;x7y12z10CPUmax12比較比較比較比較顯示結(jié)果：顯示結(jié)果：

25、12流程圖流程圖條件塊1塊2真假演示算法執(zhí)行過程演示算法執(zhí)行過程1.4.2算法的表示及三種基本結(jié)構(gòu)算法的表示及三種基本結(jié)構(gòu)(3) 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)流程圖流程圖條件塊真假【例【例1 13 3】求】求4 4個(gè)整數(shù)的和。個(gè)整數(shù)的和。 0sum4count12x顯示結(jié)果：顯示結(jié)果：59演示算法執(zhí)行過程演示算法執(zhí)行過程123142621642118600count4; /整數(shù)個(gè)數(shù)整數(shù)個(gè)數(shù)sum0; /累加和的初值累加和的初值while (count0) x輸入一個(gè)整數(shù)輸入一個(gè)整數(shù); s u m s u m + x ; countcount-1;輸出輸出sum;1.4.3 常用算法介紹常用算法介紹1. 直

26、接法直接法2.枚舉法枚舉法3.遞推法遞推法解決的問題的種類與復(fù)雜程度各不相同決定了算解決的問題的種類與復(fù)雜程度各不相同決定了算法的多樣性，但從其思想方法上可以將其歸為以下幾法的多樣性，但從其思想方法上可以將其歸為以下幾種：直接法、枚舉法、遞推法、遞歸法、回溯法等等。種：直接法、枚舉法、遞推法、遞歸法、回溯法等等。本節(jié)本節(jié) 將介紹以下三種：將介紹以下三種：1.4.3 常用算法介紹常用算法介紹1 直接法直接法 直接法就是根據(jù)問題給出的條直接法就是根據(jù)問題給出的條件直接求解，前面的很多例子都件直接求解，前面的很多例子都是這種算法的運(yùn)用。這里不再舉是這種算法的運(yùn)用。這里不再舉例。例。1.4.3 常用算

27、法介紹常用算法介紹2 枚舉法枚舉法枚舉法也稱枚舉法也稱窮舉法窮舉法，基本思想是，在有限范，基本思想是，在有限范圍內(nèi)圍內(nèi)列舉所有可能列舉所有可能的結(jié)果，找出其中符合要求的結(jié)果，找出其中符合要求的解。的解。枚舉法適合求解的問題是：問題可能的答案枚舉法適合求解的問題是：問題可能的答案是有限個(gè)且答案是可知的，但又難以用解析法是有限個(gè)且答案是可知的，但又難以用解析法描述。這種算法通常需要用描述。這種算法通常需要用循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)來完成。來完成。請看下例：請看下例：【例【例14】 給定一個(gè)正整數(shù)，判斷其非給定一個(gè)正整數(shù)，判斷其非負(fù)整數(shù)立方根是否存在，若存在，輸出負(fù)整數(shù)立方根是否存在，若存在，輸出該立方根。

28、該立方根。1.4.3 常用算法介紹常用算法介紹算法如下：算法如下：分析：設(shè)某正整數(shù)為分析：設(shè)某正整數(shù)為2727，則非負(fù)整數(shù)立方根，則非負(fù)整數(shù)立方根的取值范圍為的取值范圍為1 12727，因此可在這一范圍內(nèi)對，因此可在這一范圍內(nèi)對所有整數(shù)進(jìn)行檢測，滿足立方根為所有整數(shù)進(jìn)行檢測，滿足立方根為2727的就是的就是所求整數(shù)。所求整數(shù)?！纠纠?4】求非負(fù)整數(shù)立方根算法：】求非負(fù)整數(shù)立方根算法：1.4.3 常用算法介紹常用算法介紹numcube_root271顯示結(jié)果：顯示結(jié)果：3演示算法執(zhí)行過程演示算法執(zhí)行過程比比較較c*c*c2比比較較c*c*c3比比較較c*c*cnum27；cube_root1；

29、/立方根初值立方根初值while (cube_rootnum) 輸出輸出 “無整數(shù)立方根無整數(shù)立方根”;1.4.3 常用算法介紹常用算法介紹【例【例15】 判斷一個(gè)正整數(shù)是否素?cái)?shù)，給出相應(yīng)結(jié)果。判斷一個(gè)正整數(shù)是否素?cái)?shù)，給出相應(yīng)結(jié)果。分析：假設(shè)正整數(shù)分析：假設(shè)正整數(shù)numnum, , 如果如果numnum不是不是2 2，需要檢測它是否含有除需要檢測它是否含有除1 1和它本身之外的和它本身之外的其他因子，如果有，就不是素?cái)?shù)。檢測其他因子，如果有，就不是素?cái)?shù)。檢測方法是在方法是在2 2 num-1num-1范圍內(nèi)逐個(gè)驗(yàn)證。實(shí)際范圍內(nèi)逐個(gè)驗(yàn)證。實(shí)際上可以證明在上可以證明在2 2 numnum平方根范圍

30、內(nèi)逐個(gè)平方根范圍內(nèi)逐個(gè)驗(yàn)證即可。驗(yàn)證即可。假定假定numnum為為9 9，算法如下：，算法如下：num1.4.3 常用算法介紹常用算法介紹【例【例15】 判斷判斷9是否素?cái)?shù)算法是否素?cái)?shù)算法num9i2k3顯示結(jié)果：不是素?cái)?shù)顯示結(jié)果：不是素?cái)?shù)演示算法執(zhí)行過程演示算法執(zhí)行過程比比較較求求余余為為0比比較較求求余余不為不為03為為0比比較較求求余余num9; if (num=2) 輸出輸出 “是素?cái)?shù)是素?cái)?shù)”；else i2; ksqrt(num)； /平方根取整平方根取整 while (ik)輸出輸出 “是素?cái)?shù)是素?cái)?shù)”； else 輸出輸出 “不是素?cái)?shù)不是素?cái)?shù)”；1.4.3 常用算法介紹常用算法介紹

31、3.遞推法遞推法遞推算法是通過問題的一個(gè)或多個(gè)已知解，遞推算法是通過問題的一個(gè)或多個(gè)已知解，用同樣的方法逐個(gè)推算出其他解，如數(shù)列問題用同樣的方法逐個(gè)推算出其他解，如數(shù)列問題以及一些近似計(jì)算問題等。通常也要借助于循以及一些近似計(jì)算問題等。通常也要借助于循環(huán)。環(huán)。請看下例：請看下例：1.4.3 常用算法介紹常用算法介紹【例【例1】求】求n! 分析：分析：n!=1 2 3n，因此可以從，因此可以從1開開 始，由始，由1!乘以乘以2得到得到2!，再乘以，再乘以3得得到到3!，以此推出，以此推出n!。假定假定n n4 4，算法如下：，算法如下：ni2factorial1.4.3 常用算法介紹常用算法介紹

32、【例【例1】求】求n!算法：算法：顯示結(jié)果：顯示結(jié)果：24演示算法執(zhí)行過程演示算法執(zhí)行過程124比比較較23比比較較64比比較較24比比較較5factorial1; /階乘初值階乘初值i2;n 4;while (i=n) factorialfactorial*i ;ii+1;輸出輸出 factorial;1.5 C語言與面向?qū)ο蟮恼Z言與面向?qū)ο蟮腃 C C語言是七十年代初貝爾實(shí)驗(yàn)室的語言是七十年代初貝爾實(shí)驗(yàn)室的Dennis Dennis RichieRichie 等人在等人在B B語言基礎(chǔ)上開發(fā)出來的。語言基礎(chǔ)上開發(fā)出來的。C C最初是作最初是作為為UNIXUNIX操作系統(tǒng)的開發(fā)語言為人們所認(rèn)

33、識。七十年操作系統(tǒng)的開發(fā)語言為人們所認(rèn)識。七十年代末，隨著微型計(jì)算機(jī)的發(fā)展，代末，隨著微型計(jì)算機(jī)的發(fā)展，C C語言開始移植到非語言開始移植到非UNIXUNIX環(huán)境中，并逐步脫離環(huán)境中，并逐步脫離UNIXUNIX系統(tǒng)成為一種獨(dú)立的系統(tǒng)成為一種獨(dú)立的程序設(shè)計(jì)語言。程序設(shè)計(jì)語言。C C 語言版本很多，為了讓開發(fā)出來語言版本很多，為了讓開發(fā)出來的代碼能夠在多種平臺上運(yùn)行，的代碼能夠在多種平臺上運(yùn)行，19881988年美國國家標(biāo)年美國國家標(biāo)準(zhǔn)協(xié)會準(zhǔn)協(xié)會ANSIANSI對對C C語言進(jìn)行了標(biāo)準(zhǔn)化，產(chǎn)生了語言進(jìn)行了標(biāo)準(zhǔn)化，產(chǎn)生了ANSI CANSI C。1.5 C語言與面向?qū)ο蟮恼Z言與面向?qū)ο蟮腃 （1 1

34、）C C語言既具備高級語言的結(jié)構(gòu)和編程環(huán)境，又提供類似于匯語言既具備高級語言的結(jié)構(gòu)和編程環(huán)境，又提供類似于匯編語言那樣的系統(tǒng)資源操縱能力及程序執(zhí)行效率。編語言那樣的系統(tǒng)資源操縱能力及程序執(zhí)行效率。適合解決有實(shí)時(shí)要適合解決有實(shí)時(shí)要求的問題求的問題。C語言的主要特點(diǎn)：（2 2）有豐富的運(yùn)算符和數(shù)據(jù)類型，表達(dá)式類型多樣化，可以方）有豐富的運(yùn)算符和數(shù)據(jù)類型，表達(dá)式類型多樣化，可以方便地實(shí)現(xiàn)在其他語言中較難實(shí)現(xiàn)的運(yùn)算，對各種不同類型的程序設(shè)計(jì)便地實(shí)現(xiàn)在其他語言中較難實(shí)現(xiàn)的運(yùn)算，對各種不同類型的程序設(shè)計(jì)都有良好的適應(yīng)性。都有良好的適應(yīng)性。（3 3）以函數(shù)為基礎(chǔ)實(shí)現(xiàn)程序的結(jié)構(gòu)化設(shè)計(jì)，支持大型程序的多）以函數(shù)為基礎(chǔ)實(shí)現(xiàn)程序的結(jié)構(gòu)化設(shè)計(jì)，支持大型程序的多文件構(gòu)成及單個(gè)文件獨(dú)立編譯，適合大型復(fù)雜程序的設(shè)計(jì)。文件構(gòu)成及單個(gè)文件獨(dú)立編譯，適合大型復(fù)雜程序的設(shè)計(jì)。（4）語言簡潔、緊湊，使用方便、靈活，書寫形式自由。）語言簡潔、緊湊，使用方便、靈活，書寫形式自由。（5）可移植性