第27講程序的設(shè)計(jì)與軟件開(kāi)發(fā)基礎(chǔ)

1、第 27 講 程序設(shè)計(jì)與軟件開(kāi)發(fā)基礎(chǔ) （ 一 ）教學(xué)目標(biāo)及基本要求 掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法， 初步掌握良好的程序設(shè)計(jì)風(fēng)格的內(nèi)涵， 掌握算法 的基本概念，理解面向?qū)ο蟪绦蛟O(shè)計(jì)的基本概念。教學(xué)重點(diǎn) 逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法，算法的基本概念。教學(xué)難點(diǎn) 面向?qū)ο蟪绦蛟O(shè)計(jì)的基本概念，算法的復(fù)雜度。教學(xué)內(nèi)容? 程序設(shè)計(jì)的風(fēng)格? 結(jié)構(gòu)化程序設(shè)計(jì)? 面向?qū)ο蟪绦蛟O(shè)計(jì)? 算法的基本概念? 算法的復(fù)雜度教學(xué)時(shí)間1 學(xué)時(shí)7.1 程序設(shè)計(jì)概述7.1.1 程序設(shè)計(jì)的風(fēng)格1程序設(shè)計(jì)風(fēng)格? 程序設(shè)計(jì)風(fēng)格是指編寫(xiě)程序時(shí)所表現(xiàn)出的特點(diǎn)、習(xí)慣和邏輯思路。? 程序設(shè)計(jì)的風(fēng)格總體而言應(yīng)該強(qiáng)調(diào)簡(jiǎn)單和清晰，程序必須是可以理

2、解的。? 主導(dǎo)的程序設(shè)計(jì)風(fēng)格： “清晰第一，效率第二” 。2良好程序設(shè)計(jì)風(fēng)格（1）源程序文檔化 符號(hào)名的命名? 見(jiàn)名知意? 名字不宜太長(zhǎng)? 不要使用相似的名字? 不要使用關(guān)鍵字做標(biāo)識(shí)符? 同一個(gè)名字不要有多種含義 程序注釋? 序言性注釋?zhuān)和ǔＮ挥诿總€(gè)程序的開(kāi)頭部分， 它給出程序的整體說(shuō)明。 主要描述內(nèi)容包括： 程 序標(biāo)題、程序功能說(shuō)明、主要算法、接口說(shuō)明、程序位置、開(kāi)發(fā)簡(jiǎn)歷、程序設(shè)計(jì)者、 復(fù)審者、復(fù)審日期、修改日期等。? 功能性注釋?zhuān)?一般嵌在源程序體之中，主要描述其后的語(yǔ)句或程序做什么。 視覺(jué)組織 在程序中利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻逦?。?2）數(shù)據(jù)說(shuō)明的方法 數(shù)據(jù)說(shuō)明的次序規(guī)范化

3、：數(shù)據(jù)說(shuō)明次序固定，便程序理解、閱讀和維護(hù)，可以使 數(shù)據(jù)的屬性容易查找，也有利于測(cè)試、排錯(cuò)和維護(hù)。 說(shuō)明語(yǔ)句中變量安排有序化：當(dāng)一個(gè)說(shuō)明語(yǔ)句說(shuō)明多個(gè)變量時(shí)，變量按照字母順 序排序?yàn)楹谩?使用注釋來(lái)說(shuō)明復(fù)雜數(shù)據(jù)的結(jié)構(gòu)。 顯式地說(shuō)明一切變量。(3) 語(yǔ)句的結(jié)構(gòu) 在一行內(nèi)只寫(xiě)一條語(yǔ)句。 程序編寫(xiě)應(yīng)優(yōu)先考慮清晰性，除非對(duì)效率有特殊要求，即清晰第一，效率第二。 首先要保證程序正確，然后才要求提高速度。 避免使用臨時(shí)變量而使程序的可讀性下降。 避免采用復(fù)雜的條件語(yǔ)句和不必要的轉(zhuǎn)移，盡量使用庫(kù)函數(shù)。 數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡(jiǎn)化，程序要模塊化，且要盡量使模塊功能單一化，利 用信息隱蔽，確保每一個(gè)模塊的獨(dú)立性。

4、 盡量只采用3種基本控制結(jié)構(gòu)來(lái)編寫(xiě)程序。(4) 輸入和輸出 對(duì)所有的輸入數(shù)據(jù)都要檢驗(yàn)數(shù)據(jù)的合法性以及檢查輸入項(xiàng)的各種重要組合的合理 性。 輸入格式要簡(jiǎn)單，以使輸入的步驟和操作盡可能簡(jiǎn)單。 輸入數(shù)據(jù)時(shí)，應(yīng)允許使用自由格式和缺省值。 輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志。 以交互式方式輸入、輸出數(shù)據(jù)時(shí)，要在屏幕上有明確的提示符，數(shù)據(jù)輸入結(jié)束時(shí), 應(yīng)在屏幕上給出狀態(tài)信息。 當(dāng)程序設(shè)計(jì)語(yǔ)言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語(yǔ)句的一致性；給所有的輸出加注釋?zhuān)⒃O(shè)計(jì)良好的輸出報(bào)表格式。7.1.2 結(jié)構(gòu)化程序設(shè)計(jì)1 結(jié)構(gòu)化程序設(shè)計(jì)的原則自頂向下、逐步求精、模塊化、限制使用GOTO語(yǔ)句。(1 )自頂

5、向下先總體，后細(xì)節(jié)；先全局目標(biāo)，后局部目標(biāo)。(2 )逐步求精設(shè)計(jì)一些子目標(biāo)作為過(guò)渡，逐步細(xì)化。(3)模塊化把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱(chēng)為一個(gè)模塊。(4 )限制使用GOTO句使用GOTO語(yǔ)句有時(shí)會(huì)使程序執(zhí)行效率較高，但也容易造成程序混亂，程序不易理解、 不易排錯(cuò)、不易維護(hù)，因而要盡量限制使用GOTOg句。2 結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點(diǎn)結(jié)構(gòu)化程序的基本結(jié)構(gòu)只有3種：順序、選擇和循環(huán)(1 )順序結(jié)構(gòu)如圖7-1 所示，順序結(jié)構(gòu)是順序執(zhí)行結(jié)構(gòu)。所謂順序執(zhí)行，就是按照程序語(yǔ)句行的自然 順序，一條語(yǔ)句一條語(yǔ)句( At 4 C)地執(zhí)行程序。圖7-1順序結(jié)構(gòu)(2

6、)選擇結(jié)構(gòu)選擇結(jié)構(gòu)又稱(chēng)為分支結(jié)構(gòu)，它包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu)，這種結(jié)構(gòu)可以根據(jù)設(shè)定的條件，判斷應(yīng)該選擇哪一條分支來(lái)執(zhí)行相應(yīng)的語(yǔ)句序列。圖7-2列出了包含2個(gè)分支的簡(jiǎn)單選擇結(jié)構(gòu)。圖7-2 選擇結(jié)構(gòu)(3 )循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)又稱(chēng)為重復(fù)結(jié)構(gòu)，它根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行某一相同的或類(lèi)似的程序段。分為兩類(lèi)：? 當(dāng)型循環(huán)結(jié)構(gòu)：先判斷后執(zhí)行循環(huán)體(圖 7-3)? 直到型循環(huán)結(jié)構(gòu)：先執(zhí)行循環(huán)體后判斷(圖 7-4)判斷條件循環(huán)體圖7-3 當(dāng)型循環(huán)結(jié)構(gòu)循環(huán)體判斷條件圖7-4直到型循環(huán)結(jié)構(gòu)3結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的運(yùn)用(1) 使用順序、選擇、循環(huán)三種結(jié)構(gòu)表示程序的控制邏輯。(2) 選用的控制結(jié)構(gòu)只準(zhǔn)

7、許有一個(gè)入口和一個(gè)岀口。(3) 復(fù)雜結(jié)構(gòu)應(yīng)用嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來(lái)實(shí)現(xiàn)，語(yǔ)言中所沒(méi)有的控制結(jié)構(gòu)，應(yīng)該 采用前后一致的方法來(lái)模擬。(4) 嚴(yán)格控制 GOT(語(yǔ)句的使用。7.1.3 面向?qū)ο蟪绦蛟O(shè)計(jì)1 面向?qū)ο蟪绦蛟O(shè)計(jì)方法的產(chǎn)生? 系統(tǒng)的需求總是處于不斷變化之中，因此，需要設(shè)計(jì)對(duì)變化有彈性的系統(tǒng)。? 利用傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)方法設(shè)計(jì)的系統(tǒng)不易擴(kuò)充。傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)方法主要是面向過(guò)程的，也就是在分析設(shè)計(jì)時(shí)更多地從過(guò)程處理的角度進(jìn)行，系統(tǒng)框架結(jié)構(gòu)，系統(tǒng)模塊的劃分、設(shè)計(jì)都是基于系統(tǒng)所實(shí)現(xiàn)的功能，而功能是系統(tǒng)中最易變的部分，這樣，如果系統(tǒng)需求發(fā)生一些變化（如系統(tǒng)某些功能的改進(jìn)或擴(kuò)充新 功能）

8、，系統(tǒng)的結(jié)構(gòu)就會(huì)受到破壞。在實(shí)際系統(tǒng)中，最穩(wěn)定的部分是系統(tǒng)對(duì)象，它直接描述問(wèn)題域。 面向?qū)ο蟮南到y(tǒng)能夠有效提高系統(tǒng)結(jié)構(gòu)的穩(wěn)定性。較復(fù)雜的系統(tǒng)將為每個(gè)對(duì)象類(lèi)定義一些更復(fù)雜的功能（如“飛機(jī)”對(duì)象類(lèi)中增加自動(dòng)跟蹤功能）或者增加一些新的對(duì)象類(lèi)（如“雷達(dá)”），但是系統(tǒng)的核心部分 （問(wèn)題域中的對(duì)象）即使在系統(tǒng)功能范圍發(fā)生變化的情況下，仍保持不變。? 傳統(tǒng)的結(jié)構(gòu)化分析和設(shè)計(jì)方法中存在迥然不同的表示方法。在分析階段采用 DFD表示，而在設(shè)計(jì)階段采用結(jié)構(gòu)圖的表示方法。在面向?qū)ο蠓椒ㄖ?，從分析?0A、設(shè)計(jì)（00D到編程實(shí)現(xiàn)（OOP采用的都是同樣的 表示方法。2. 面向?qū)ο蟪绦蛟O(shè)計(jì)方法學(xué)的優(yōu)點(diǎn)可重用性繼承是面向?qū)?/p>

9、象方法的一個(gè)重要機(jī)制，用面向?qū)ο蠓椒ㄔO(shè)計(jì)的系統(tǒng)的基本對(duì)象類(lèi)可以被其他新系統(tǒng)重用，通常這是通過(guò)一個(gè)包含類(lèi)和子類(lèi)層次結(jié)構(gòu)的類(lèi)庫(kù)來(lái)實(shí)現(xiàn)的，面向?qū)ο蠓椒ㄍㄟ^(guò)從一個(gè)項(xiàng)目向另一個(gè)項(xiàng)目提供一些重用類(lèi)而能顯著提高生產(chǎn)率。? 可維護(hù)性? 表示方法的一致性3面向?qū)ο蟪绦蛟O(shè)計(jì)方法學(xué)的基本概念（1、對(duì)象 概念：在現(xiàn)實(shí)世界中，對(duì)象指的是任何一個(gè)實(shí)體。它可能是一個(gè)人、一部車(chē)。 對(duì)象的組成：對(duì)象名：用來(lái)標(biāo)識(shí)對(duì)象對(duì)象的屬性：是實(shí)體所具有的性質(zhì)（外形與狀態(tài)）。對(duì)象的方法：是實(shí)體所擁有的行為。（2、消息 概念：對(duì)象之間進(jìn)行通信的一種構(gòu)成叫做消息。消息傳遞：當(dāng)一個(gè)消息發(fā)送給某個(gè)對(duì)象時(shí)，包含要求接收對(duì)象去執(zhí)行某些活動(dòng)的信息。 接收到

10、信息的對(duì)象經(jīng)過(guò)解釋?zhuān)缓笥枰皂憫?yīng)。這種通信機(jī)制叫做消息傳遞。發(fā)送消息的對(duì)象不需要知道接收消息的對(duì)象如何響應(yīng)該請(qǐng)求。（3）類(lèi) 概念：類(lèi)是對(duì)象的抽象。（4）繼承 概念：繼承是父類(lèi)和子類(lèi)之間共享數(shù)據(jù)和方法的機(jī)制?？梢栽谝粋€(gè)已經(jīng)存在的類(lèi)的基礎(chǔ)上來(lái)進(jìn)行，把這個(gè)已經(jīng)存在的類(lèi)所定義的內(nèi)容作為自己的內(nèi)容，并加入若干新的內(nèi) 容。 繼承的分類(lèi)單重繼承：子類(lèi)只從一個(gè)父類(lèi)得到繼承 多重繼承：子類(lèi)從多個(gè)父類(lèi)得到繼承（5）多態(tài)性概念：同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)，該現(xiàn)象稱(chēng)為多態(tài)性。多態(tài)性的作用：多態(tài)性機(jī)制不僅增加了面向?qū)ο筌浖到y(tǒng)的靈活性，進(jìn)一步減少了信息冗余，而且顯著地提高了軟件的可重用性和可擴(kuò)充性

11、。7.2.1 算法的基本概念1. 算法的基本概念算法是指解題方案的準(zhǔn)確而完整的描述，并且具有下列特性：(1) 有窮性：一個(gè)算法必須在執(zhí)行有窮步驟之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成。(2) 確定性：算法的每一步必須是確切定義的，不能有歧義。(3) 可行性：算法應(yīng)該是可行的。(4) 輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。(5) 輸岀：一個(gè)算法有一個(gè)或多個(gè)輸岀。2. 算法的基本要素對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸算法的控制結(jié)構(gòu)：算法中各操作之間的執(zhí)行順序3算法設(shè)計(jì)的要求正確性可讀性健壯性效率評(píng)價(jià)一個(gè)算法優(yōu)劣的主要標(biāo)準(zhǔn)是算法的執(zhí)行效率和存儲(chǔ)需求。算法的執(zhí)行效率指的是時(shí)間復(fù)雜

12、度(Time Complexity ),存儲(chǔ)需求指的是空間復(fù)雜度( Space Complexity )。7.2.2 算法的復(fù)雜度1. 算法的時(shí)間復(fù)雜度概念算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。因?yàn)榛具\(yùn)算反映了算法運(yùn)算的主要特征，因而可以用算法在執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量算法的工作量。算法的工作量計(jì)算公式算法的工作量=f(n)其中n是問(wèn)題的規(guī)模兩個(gè)n階矩陣相乘所需的基本運(yùn)算(即兩個(gè)實(shí)數(shù)的乘法)次數(shù)為n3,即計(jì)算工作量為n3,也就是時(shí)間復(fù)雜度為 n3。注意事項(xiàng)在同一個(gè)問(wèn)題規(guī)模下，如果算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于某一特定輸入時(shí)，可以用平均性態(tài)和最壞情況復(fù)雜性方法來(lái)分析算

13、法的工作量。平均性態(tài)平均性態(tài)分析是指用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來(lái)度量算法的工作 量。在長(zhǎng)度為n的一維數(shù)組中查找值為 x的元素，若采用順序搜索法，在平均情況下需要檢 查數(shù)組中一半的元素。最壞情況分析最壞情況分析是指在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。在長(zhǎng)度為n的一維數(shù)組中查找值為 x的元素，若采用順序搜索法，在最壞情況下最壞情 況需查找n次。2. 算法的空間復(fù)雜度一個(gè)算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過(guò)程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需

14、要的附加存儲(chǔ)空間。例題【例 7.1 】討論用選擇法對(duì)數(shù)組中 n 個(gè)整數(shù)按由小到大排序的時(shí)間復(fù)雜度。1. 選擇法 :先將n個(gè)數(shù)中最小的數(shù)與a0對(duì)換，再將a1到an-1中最小的數(shù)與a1對(duì)換每比較 一輪，找出一個(gè)未經(jīng)排序的數(shù)中最小的一個(gè)，共比較 n-1 輪。2. 算法 :(1)從鍵盤(pán)輸入n個(gè)數(shù)，并將其存儲(chǔ)在一個(gè)有n個(gè)元素的整型數(shù)組 a中。( 2 )進(jìn)行選擇排序： int i=0； / 每一輪比較起始元素的下標(biāo)int k=0；/ 每一輪比較得到的最小元素的下標(biāo) 通過(guò)循環(huán)求出 aian 中最小數(shù)的下標(biāo) k 如果i不等于k,將ai與ak對(duì)換 i=i+1 ，轉(zhuǎn)到(3)輸出排序的結(jié)果。3. C+程序代碼voi

15、d select_sort(int array, int n) /第 1 行 int i,j,k,t; /第 2 行for(i=0;in-1;i+) /第 3行 k=i; / 第 4行for(j=i+1;jn;j+) /第 5行if(arrayjarrayk) /第 6 行k=j; /第 7 行if(k!=i) / 第 8行/ 第 9 行t=arrayk;arrayk=arrayi;arrayi=t; /第 10 行 / 第 11 行 / 第 12 行 / 第 13 行4. 時(shí)間復(fù)雜度算法中第 3行的 for 循環(huán)的循環(huán)體要執(zhí)行 n-1 次,而第 5行的 for 循環(huán)的循環(huán)體每次分 別執(zhí)行n-1 , n-2 , n-3，2, 1次，該算法的時(shí)間復(fù)雜度為：n-1+ n-2+2+1= n(n -1)/2。小結(jié)程序設(shè)計(jì)語(yǔ)言經(jīng)歷了機(jī)器語(yǔ)言、匯編語(yǔ)言、高級(jí)語(yǔ)言等多個(gè)階段,程序設(shè)計(jì)方法也經(jīng)歷了早期手工作坊式的程序設(shè)計(jì)、 結(jié)構(gòu)化程序設(shè)計(jì)、 面向?qū)ο蟪绦蛟O(shè)計(jì)等發(fā)展階段。 結(jié)構(gòu)化 程序設(shè)計(jì)方法的主要原則可以概括為自頂向下、逐步求精、模塊化、限制使用GOT(語(yǔ)句。結(jié)構(gòu)化程序設(shè)計(jì)方法是僅僅使用順序、 選擇和循環(huán) 3種基本控制結(jié)構(gòu), 它雖然成功但是它并 不總是有