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

第27講程序設(shè)計與軟件開發(fā)基礎(chǔ)(一)教課目的及基本要求掌握逐漸求精的構(gòu)造化程序設(shè)計方法，初步掌握優(yōu)秀的程序設(shè)計風(fēng)格的內(nèi)涵，掌握算法的基本觀點，理解面向?qū)ο蟪绦蛟O(shè)計的基本觀點。教課要點逐漸求精的構(gòu)造化程序設(shè)計方法，算法的基本觀點。教課難點面向?qū)ο蟪绦蛟O(shè)計的基本觀點，算法的復(fù)雜度。教課內(nèi)容程序設(shè)計的風(fēng)格構(gòu)造化程序設(shè)計面向?qū)ο蟪绦蛟O(shè)計算法的基本觀點算法的復(fù)雜度教課時間學(xué)時7.1程序設(shè)計概括程序設(shè)計的風(fēng)格1．程序設(shè)計風(fēng)格程序設(shè)計風(fēng)格是指編寫程序時所表現(xiàn)出的特色、習(xí)慣和邏輯思路。程序設(shè)計的風(fēng)格整體而言應(yīng)當(dāng)重申簡單和清楚，程序一定是能夠理解的。主導(dǎo)的程序設(shè)計風(fēng)格：“清楚第一，效率第二”。2．優(yōu)秀程序設(shè)計風(fēng)格1）源程前言檔化①符號名的命名見名知意名字不宜太長不要使用相像的名字不要使用要點字做表記符同一個名字不要有多種含義②程序說明前言性說明：往常位于每個程序的開頭部分，它給出程序的整體說明。主要描繪內(nèi)容包含：程序標(biāo)題、程序功能說明、主要算法、接口說明、程序地點、開發(fā)簡歷、程序設(shè)計者、復(fù)審者、復(fù)審日期、修他日期等。功能性說明：一般嵌在源程序體之中，主要描繪后來的語句或程序做什么。視覺組織在程序中利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻宄?）數(shù)聽說明的方法①數(shù)聽說明的序次規(guī)范化：數(shù)聽說明序次固定，便程序理解、閱讀和保護(hù)，能夠使數(shù)據(jù)的屬性簡單查找，也有益于測試、排錯和保護(hù)。②說明語句中變量安排有序化：當(dāng)一個說明語句說明多個變量時，變量依據(jù)字母次序排序為好。③使用說明來說明復(fù)雜數(shù)據(jù)的構(gòu)造。④顯式地說明全部變量。（3）語句的構(gòu)造①在一行內(nèi)只寫一條語句。②程序編寫應(yīng)優(yōu)先考慮清楚性，除非對效率有特別要求，即清楚第一，效率第二。③第一要保證程序正確，而后才要求提升速度。④防止使用暫時變量而使程序的可讀性降落。⑤防止采納復(fù)雜的條件語句和不用要的轉(zhuǎn)移，盡量使用庫函數(shù)。⑥數(shù)據(jù)構(gòu)造要有益于程序的簡化，程序要模塊化，且要盡量使模塊功能單調(diào)化，利用信息隱蔽，保證每一個模塊的獨立性。⑦盡量只采納3種基本控制構(gòu)造來編寫程序。4）輸入和輸出對全部的輸入數(shù)據(jù)都要查驗數(shù)據(jù)的合法性以及檢查輸入項的各樣重要組合的合理性。②輸入格式要簡單，以使輸入的步驟和操作盡可能簡單。③輸入數(shù)據(jù)時，應(yīng)同意使用自由格式和缺省值。④輸入一批數(shù)據(jù)時，最好使用輸入結(jié)束標(biāo)記。⑤以交互式方式輸入、輸出數(shù)據(jù)時，要在屏幕上有明確的提示符，數(shù)據(jù)輸入結(jié)束時，應(yīng)在屏幕上給出狀態(tài)信息。⑥當(dāng)程序設(shè)計語言對輸入格式有嚴(yán)格要求時，應(yīng)保持輸入格式與輸入語句的一致性；給全部的輸出加說明，并設(shè)計優(yōu)秀的輸出報表格式。構(gòu)造化程序設(shè)計1．構(gòu)造化程序設(shè)計的原則自頂向下、逐漸求精、模塊化、限制使用GOTO語句。1）自頂向下先整體，后細(xì)節(jié)；先全局目標(biāo)，后局部目標(biāo)。2）逐漸求精設(shè)計一些子目標(biāo)作為過渡，逐漸細(xì)化。3）模塊化把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為詳細(xì)的小目標(biāo)，把每個小目標(biāo)稱為一個模塊。（4）限制使用GOTO語句使用GOTO語句有時會使程序履行效率較高，但也簡單造成程序雜亂，程序不易理解、不易排錯、不易保護(hù)，因此要盡量限制使用GOTO語句。2．構(gòu)造化程序的基本構(gòu)造與特色構(gòu)造化程序的基本構(gòu)造只有3種：次序、選擇和循環(huán)（1）次序構(gòu)造如圖7-1所示,次序構(gòu)造是次序履行構(gòu)造。所謂次序履行，就是依據(jù)程序語句行的自然次序，一條語句一條語句（A→B→C）地履行程序。ABC圖7-1次序構(gòu)造（2）選擇構(gòu)造選擇構(gòu)造又稱為分支構(gòu)造，它包含簡單項選擇擇和多分支選擇構(gòu)造，的條件，判斷應(yīng)當(dāng)選擇哪一條分支來履行相應(yīng)的語句序列。圖7-2單項選擇擇構(gòu)造。

這類構(gòu)造能夠依據(jù)設(shè)定列出了包含2個分支的簡條件TFAB圖7-2選擇構(gòu)造（3）循環(huán)構(gòu)造循環(huán)構(gòu)造又稱為重復(fù)構(gòu)造，它依據(jù)給定的條件，判斷能否需要重復(fù)履行某一相同的或類似的程序段。分為兩類:?當(dāng)型循環(huán)構(gòu)造：先判斷后履行循環(huán)體（圖7-3）?直到型循環(huán)構(gòu)造：先履行循環(huán)體后判斷（圖7-4）判斷條件循環(huán)體循環(huán)體判斷條件圖7-3當(dāng)型循環(huán)構(gòu)造圖7-4直到型循環(huán)構(gòu)造3．構(gòu)造化程序設(shè)計原則和方法的運用1）使用次序、選擇、循環(huán)三種構(gòu)造表示程序的控制邏輯。2）采納的控制構(gòu)造只允許有一個進(jìn)口和一個出口。（3）復(fù)雜構(gòu)造應(yīng)用嵌套的基本控制構(gòu)造進(jìn)行組合嵌套來實現(xiàn)，語言中所沒有的控制構(gòu)造，應(yīng)當(dāng)采納前后一致的方法來模擬。（4）嚴(yán)格控制GOTO語句的使用。面向?qū)ο蟪绦蛟O(shè)計1．面向?qū)ο蟪绦蛟O(shè)計方法的產(chǎn)生?系統(tǒng)的需求老是處于不停變化之中，所以，需要設(shè)計對變化有彈性的系統(tǒng)?利用傳統(tǒng)的構(gòu)造化程序設(shè)計方法設(shè)計的系統(tǒng)不易擴(kuò)大。

。傳統(tǒng)的構(gòu)造化程序設(shè)計方法主假如面向過程的，也就是在剖析設(shè)計時更多地從過程辦理的角度進(jìn)行，系統(tǒng)框架構(gòu)造，系統(tǒng)模塊的區(qū)分、設(shè)計都是鑒于系統(tǒng)所實現(xiàn)的功能，而功能是系統(tǒng)中最易變的部分，這樣，假如系統(tǒng)需求發(fā)生一些變化（如系統(tǒng)某些功能的改良或擴(kuò)大新功能），系統(tǒng)的構(gòu)造就會遇到損壞。在實質(zhì)系統(tǒng)中，最穩(wěn)固的部分是系統(tǒng)對象，它直接描繪問題域。面向?qū)ο蟮南到y(tǒng)能夠有效提升系統(tǒng)構(gòu)造的穩(wěn)固性。較復(fù)雜的系統(tǒng)將為每個對象類定義一些更復(fù)雜的功能（如“飛機”對象類中增添自動跟蹤功能）或許增添一些新的對象類（如“雷達(dá)”），可是系統(tǒng)的核心部分（問題域中的對象）即便在系統(tǒng)功能范圍發(fā)生變化的狀況下，仍保持不變。傳統(tǒng)的構(gòu)造化剖析和設(shè)計方法中存在截然不一樣的表示方法。在剖析階段采納DFD表示，而在設(shè)計階段采納構(gòu)造圖的表示方法。在面向?qū)ο蠓椒ㄖ校瑥钠饰觯∣OA）、設(shè)計（OOD）到編程實現(xiàn)（OOP）采納的都是相同的表示方法。2．面向?qū)ο蟪绦蛟O(shè)計方法學(xué)的長處可重用性繼承是面向?qū)ο蠓椒ǖ囊粋€重要體制，用面向?qū)ο蠓椒ㄔO(shè)計的系統(tǒng)的基本對象類能夠被其余新系統(tǒng)重用，往常這是經(jīng)過一個包含類和子類層次構(gòu)造的類庫來實現(xiàn)的，面向?qū)ο蠓椒ń?jīng)過從一個項目向另一個項目供給一些重用類而能明顯提升生產(chǎn)率。?可保護(hù)性?表示方法的一致性3．面向?qū)ο蟪绦蛟O(shè)計方法學(xué)的基本觀點（1）對象觀點：在現(xiàn)實世界中，對象指的是任何一個實體。它可能是一個人、一部車。對象的構(gòu)成：對象名：用來表記對象對象的屬性：是實體所擁有的性質(zhì)（外形與狀態(tài)）。對象的方法：是實體所擁有的行為。2）信息觀點：對象之間進(jìn)行通訊的一種構(gòu)成叫做信息。信息傳達(dá)：當(dāng)一個信息發(fā)送給某個對象時，包含要求接收對象去履行某些活動的信息。接收到信息的對象經(jīng)過解說，而后予以響應(yīng)。這類通訊體制叫做信息傳達(dá)。發(fā)送信息的對象不需要知道接收信息的對象怎樣響應(yīng)當(dāng)懇求。（3）類觀點：類是對象的抽象。（4）繼承?觀點：繼承是父類和子類之間共享數(shù)據(jù)和方法的體制。能夠在一個已經(jīng)存在的類的基礎(chǔ)上來進(jìn)行，把這個已經(jīng)存在的類所定義的內(nèi)容作為自己的內(nèi)容，并加入若干新的內(nèi)容。繼承的分類單重繼承：子類只從一個父類獲得繼承多重繼承：子類從多個父類獲得繼承（5）多態(tài)性觀點：相同的信息被不一樣的對象接受時可致使完好不一樣的行動，該現(xiàn)象稱為多態(tài)性。?多態(tài)性的作用：多態(tài)性體制不單增添了面向?qū)ο筌浖到y(tǒng)的靈巧性，進(jìn)一步減少了信息冗余，并且明顯地提升了軟件的可重用性和可擴(kuò)大性。算法的基本觀點1．算法的基本觀點算法是指解題方案的正確而完好的描繪，并且擁有以下特征：1）有窮性：一個算法一定在履行有窮步驟以后結(jié)束，且每一步都可在有窮時間內(nèi)達(dá)成。2）確立性：算法的每一步一定是切實定義的，不可以有歧義。3）可行性：算法應(yīng)當(dāng)是可行的。4）輸入：一個算法有零個或多個輸入。5）輸出：一個算法有一個或多個輸出。2．算法的基本因素對數(shù)據(jù)對象的運算和操作:算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸算法的控制構(gòu)造:算法中各操作之間的履行次序3．算法設(shè)計的要求正確性可讀性強健性效率評論一個算法好壞的主要標(biāo)準(zhǔn)是算法的履行效率和儲存需求。間復(fù)雜度（TimeComplexity），儲存需求指的是空間復(fù)雜度（算法的復(fù)雜度

算法的履行效率指的是時SpaceComplexity）。1．算法的時間復(fù)雜度觀點算法的時間復(fù)雜度是指履行算法所需要的計算工作量。由于基本運算反應(yīng)了算法運算的主要特色，因此能夠用算法在履行過程中所需基本運算的履行次數(shù)來胸懷算法的工作量。算法的工作量計算公式算法的工作量=f(n)此中n是問題的規(guī)模兩個n階矩陣相乘所需的基本運算（即兩個實數(shù)的乘法）次數(shù)為n3，也就是時間復(fù)雜度為n3。

n3，即計算工作量為注意事項在同一個問題規(guī)模下，假如算法履行所需的基本運算次數(shù)取決于某一特定輸入時，能夠用均勻性態(tài)和最壞狀況復(fù)雜性方法來剖析算法的工作量。均勻性態(tài)均勻性態(tài)剖析是指用各樣特定輸入下的基本運算次數(shù)的加權(quán)均勻值來胸懷算法的工作量。在長度為n的一維數(shù)組中查找值為x的元素，若采納次序搜尋法，在均勻狀況下需要檢查數(shù)組中一半的元素。最壞狀況剖析最壞狀況剖析是指在規(guī)模為n時，算法所履行的基本運算的最大次數(shù)。在長度為n的一維數(shù)組中查找值為x的元素，若采納次序搜尋法，在最壞狀況下最壞狀況需查找n次。2．算法的空間復(fù)雜度一個算法的空間復(fù)雜度一般是指履行這個算法所需要的內(nèi)存空間。包含算法程序所占的空間、輸入的初始數(shù)據(jù)所占的儲存空間以及算法履行過程中所需要的額外空間。此中額外空間包含算法程序履行過程中的工作單元以及某種數(shù)據(jù)構(gòu)造所需要的附帶儲存空間。例題【例7.1】議論用選擇法對數(shù)組中n個整數(shù)按由小到大排序的時間復(fù)雜度。1.選擇法

:先將n個數(shù)中最小的數(shù)與a[0]對調(diào)，再將a[1]到a[n-1]中最小的數(shù)與一輪，找出一個未經(jīng)排序的數(shù)中最小的一個，共比較n-1輪。2.算法:

a[1]

對調(diào)每比較（1）從鍵盤輸入n個數(shù)，并將其儲存在一個有n個元素的整型數(shù)組a中。2）進(jìn)行選擇排序：inti=0；//每一輪比較開端元素的下標(biāo)intk=0；//每一輪比較獲得的最小元素的下標(biāo)②經(jīng)過循環(huán)求出a[i]~a[n]中最小數(shù)的下標(biāo)k③假如i不等于k，將a[i]與a[k]對調(diào)i=i+1，轉(zhuǎn)到②3）輸出排序的結(jié)果。3.C++程序代碼voidselect_sort(intarray[],

intn)//

第1行{inti,j,k,t;//for(i=0;i<n-1;i++)//

第2行第3行{k=i;//

第4行for(j=i+1;j<n;j++)//if(array[j]<array[k])//

第5行第6行k=j;//第7行if(k!=i)//第8行{//第9行t=array[k];array[k]=array[i];array[i]=t;//

第10行}//第11行}//第12行}//第13行時間復(fù)雜度算法中第3行的for循環(huán)的循環(huán)體要履行n-1次，而第5行的for循環(huán)的循環(huán)體每次分別履行n-1，n-2，n-3，，2，1次，該算法的時間復(fù)雜度為：n-1+n-2++2+1=n(n-1)/2。小結(jié)程序設(shè)計語言經(jīng)歷了機器語言、匯編語言、高級語言等多個階段，程序設(shè)計方法也經(jīng)歷了初期手工作坊式的程序設(shè)計、構(gòu)造化程序設(shè)計、面向?qū)ο蟪绦蛟O(shè)計等發(fā)展階段。構(gòu)造化程序設(shè)計方法的主要原則能夠歸納為自頂向下、逐漸求精、模塊化、限制使用GOTO語句。構(gòu)造化程序設(shè)計方法是只是使用次序、選擇和循環(huán)3種基本控制構(gòu)造，它固然成功可是它并不老是有效的。面向?qū)?/p>