程序設(shè)計與軟件開發(fā)基礎(chǔ)課件

1、7.1 程序設(shè)計概述 7.2.2 算法的復(fù)雜度7.2.1 算法的基本概念 7.1.3 面向?qū)ο蟪绦蛟O(shè)計 7.1.2 結(jié)構(gòu)化程序設(shè)計7.1.1 程序設(shè)計的風(fēng)格7.2 算法概述第27講 程序設(shè)計與軟件開發(fā)基礎(chǔ)(一)掌握逐步求精的結(jié)構(gòu)化程序設(shè)計方法，初步掌握良好的程序設(shè)計風(fēng)格的內(nèi)涵，掌握算法的基本概念，理解面向?qū)ο蟪绦蛟O(shè)計的基本概念。教學(xué)目標(biāo)及基本要求教學(xué)重點逐步求精的結(jié)構(gòu)化程序設(shè)計方法，算法的基本概念。 第27講 程序設(shè)計與軟件開發(fā)基礎(chǔ)(一)教學(xué)難點面向?qū)ο蟪绦蛟O(shè)計的基本概念，算法的復(fù)雜度。 程序設(shè)計的風(fēng)格結(jié)構(gòu)化程序設(shè)計面向?qū)ο蟪绦蛟O(shè)計算法的基本概念算法的復(fù)雜度教學(xué)內(nèi)容第27講 程序設(shè)計與軟件開發(fā)

2、基礎(chǔ)(一)1學(xué)時 教學(xué)時間第27講 程序設(shè)計與軟件開發(fā)基礎(chǔ)(一)7.1 程序設(shè)計概述7.1.1 程序設(shè)計的風(fēng)格1程序設(shè)計風(fēng)格 程序設(shè)計風(fēng)格是指編寫程序時所表現(xiàn)出的特點、習(xí)慣和邏輯思路。 程序設(shè)計的風(fēng)格總體而言應(yīng)該強(qiáng)調(diào)簡單和清晰，程序必須是可以理解的。 主導(dǎo)的程序設(shè)計風(fēng)格： “清晰第一，效率第二” 。2良好程序設(shè)計風(fēng)格（1）源程序文檔化 符號名的命名見名知意名字不宜太長不要使用相似的名字不要使用關(guān)鍵字做標(biāo)識符 同一個名字不要有多種含義7.1.1 程序設(shè)計的風(fēng)格 功能性注釋：通常位于每個程序的開頭部分，它給出程序的整體說明。主要描述內(nèi)容包括：程序標(biāo)題、程序功能說明、主要算法、接口說明、程序位置、開

3、發(fā)簡歷、程序設(shè)計者、復(fù)審者、復(fù)審日期、修改日期等。一般嵌在源程序體之中，主要描述其后的語句或程序做什么。 程序注釋序言性注釋： 源程序文檔化 視覺組織 在程序中利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻逦?。源程序文檔化（2）數(shù)據(jù)說明的方法 數(shù)據(jù)說明的次序規(guī)范化：數(shù)據(jù)說明次序固定，便程序理解、閱讀和維護(hù)，可以使數(shù)據(jù)的屬性容易查找，也有利于測試、排錯和維護(hù)。良好程序設(shè)計風(fēng)格 說明語句中變量安排有序化：當(dāng)一個說明語句說明多個變量時，變量按照字母順序排序為好。 使用注釋來說明復(fù)雜數(shù)據(jù)的結(jié)構(gòu)。 顯式地說明一切變量。（3）語句的結(jié)構(gòu) 在一行內(nèi)只寫一條語句。 程序編寫應(yīng)優(yōu)先考慮清晰性，除非對效率有特殊要求，即清

4、晰第一，效率第二。 首先要保證程序正確，然后才要求提高速度。 良好程序設(shè)計風(fēng)格 避免使用臨時變量而使程序的可讀性下降。 避免采用復(fù)雜的條件語句和不必要的轉(zhuǎn)移，盡量使用庫函數(shù)。 數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化，程序要模塊化，且要盡量使模塊功能單一化，利用信息隱蔽，確保每一個模塊的獨立性。 盡量只采用3種基本控制結(jié)構(gòu)來編寫程序。語句的結(jié)構(gòu)（4）輸入和輸出 對所有的輸入數(shù)據(jù)都要檢驗數(shù)據(jù)的合法性以及檢查輸入項的各種重要組合的合理性。 輸入格式要簡單，以使輸入的步驟和操作盡可能簡單。 輸入數(shù)據(jù)時，應(yīng)允許使用自由格式和缺省值。 輸入一批數(shù)據(jù)時，最好使用輸入結(jié)束標(biāo)志。 良好程序設(shè)計風(fēng)格 以交互式方式輸入、輸出數(shù)

5、據(jù)時，要在屏幕上有明確的提示符，數(shù)據(jù)輸入結(jié)束時，應(yīng)在屏幕上給出狀態(tài)信息。 當(dāng)程序設(shè)計語言對輸入格式有嚴(yán)格要求時，應(yīng)保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設(shè)計良好的輸出報表格式。輸入和輸出7.1.2 結(jié)構(gòu)化程序設(shè)計1結(jié)構(gòu)化程序設(shè)計的原則自頂向下、逐步求精、模塊化、限制使用GOTO語句。（1）自頂向下 先總體，后細(xì)節(jié)；先全局目標(biāo)，后局部目標(biāo)。（2）逐步求精 設(shè)計一些子目標(biāo)作為過渡，逐步細(xì)化。結(jié)構(gòu)化程序設(shè)計的原則（3）模塊化 把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個小目標(biāo)稱為一個模塊。（4）限制使用GOTO語句 使用GOTO語句有時會使程序執(zhí)行效率較高，但

6、也容易造成程序混亂，程序不易理解、不易排錯、不易維護(hù)，因而要盡量限制使用GOTO語句。結(jié)構(gòu)化程序設(shè)計的原則2結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點結(jié)構(gòu)化程序的基本結(jié)構(gòu)只有3種:順序、選擇和循環(huán)（1）順序結(jié)構(gòu) 如圖7-1所示,順序結(jié)構(gòu)是順序執(zhí)行結(jié)構(gòu)。所謂順序執(zhí)行，就是按照程序語句行的自然順序，一條語句一條語句（ABC）地執(zhí)行程序。7.1.2 結(jié)構(gòu)化程序設(shè)計ABC圖7-1 順序結(jié)構(gòu)順序結(jié)構(gòu)（2）選擇結(jié)構(gòu) 選擇結(jié)構(gòu)又稱為分支結(jié)構(gòu)，它包括簡單選擇和多分支選擇結(jié)構(gòu)，這種結(jié)構(gòu)可以根據(jù)設(shè)定的條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列。圖7-2列出了包含2個分支的簡單選擇結(jié)構(gòu)。結(jié)構(gòu)化程序設(shè)計的基本結(jié)構(gòu)與特點 條件

7、T F A B圖7-2 選擇結(jié)構(gòu)選擇結(jié)構(gòu)（3）循環(huán)結(jié)構(gòu) 循環(huán)結(jié)構(gòu)又稱為重復(fù)結(jié)構(gòu)，它根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行某一相同的或類似的程序段。分為兩類:直到型循環(huán)結(jié)構(gòu)：先判斷后執(zhí)行循環(huán)體（圖7-3）先執(zhí)行循環(huán)體后判斷（圖7-4）當(dāng)型循環(huán)結(jié)構(gòu)： 結(jié)構(gòu)化程序設(shè)計的基本結(jié)構(gòu)與特點圖7-3 當(dāng)型循環(huán)結(jié)構(gòu)圖7-4 直到型循環(huán)結(jié)構(gòu)判斷條件 循環(huán)體 循環(huán)體判斷條件循環(huán)結(jié)構(gòu)3結(jié)構(gòu)化程序設(shè)計原則和方法的運(yùn)用（1）使用順序、選擇、循環(huán)三種結(jié)構(gòu)表示程序的控制邏輯。（2）選用的控制結(jié)構(gòu)只準(zhǔn)許有一個入口和一個出口。7.1.2 結(jié)構(gòu)化程序設(shè)計（3）復(fù)雜結(jié)構(gòu)應(yīng)用嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來實現(xiàn)，語言中所沒有的控制結(jié)構(gòu)

8、，應(yīng)該采用前后一致的方法來模擬。（4）嚴(yán)格控制GOTO語句的使用。結(jié)構(gòu)化程序設(shè)計原則和方法的運(yùn)用7.1.3 面向?qū)ο蟪绦蛟O(shè)計1面向?qū)ο蟪绦蛟O(shè)計方法的產(chǎn)生系統(tǒng)的需求總是處于不斷變化之中，因此，需要設(shè)計對變化有彈性的系統(tǒng) 。面向?qū)ο蟪绦蛟O(shè)計方法學(xué)的產(chǎn)生傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計方法主要是面向過程的，也就是在分析設(shè)計時更多地從過程處理的角度進(jìn)行，系統(tǒng)框架結(jié)構(gòu)，系統(tǒng)模塊的劃分、設(shè)計都是基于系統(tǒng)所實現(xiàn)的功能，而功能是系統(tǒng)中最易變的部分，這樣，如果系統(tǒng)需求發(fā)生一些變化（如系統(tǒng)某些功能的改進(jìn)或擴(kuò)充新功能），系統(tǒng)的結(jié)構(gòu)就會受到破壞。 利用傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計方法設(shè)計的系統(tǒng)不易擴(kuò)充。在實際系統(tǒng)中，最穩(wěn)定的部分是系統(tǒng)對

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

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

11、給某個對象時，包含要求接收對象去執(zhí)行某些活動的信息。接收到信息的對象經(jīng)過解釋，然后予以響應(yīng)。這種通信機(jī)制叫做消息傳遞。發(fā)送消息的對象不需要知道接收消息的對象如何響應(yīng)該請求。面向?qū)ο蟪绦蛟O(shè)計方法學(xué)的基本概念（3）類概念：類是對象的抽象。 （4）繼承概念：繼承是父類和子類之間共享數(shù)據(jù)和方法的機(jī)制 ?？梢栽谝粋€已經(jīng)存在的類的基礎(chǔ)上來進(jìn)行，把這個已經(jīng)存在的類所定義的內(nèi)容作為自己的內(nèi)容，并加入若干新的內(nèi)容 。面向?qū)ο蟪绦蛟O(shè)計方法學(xué)的基本概念繼承的分類單重繼承：多重繼承：子類只從一個父類得到繼承 子類從多個父類得到繼承 面向?qū)ο蟪绦蛟O(shè)計方法學(xué)的基本概念（5）多態(tài)性概念：同樣的消息被不同的對象接受時可導(dǎo)致完

12、全不同的行動，該現(xiàn)象稱為多態(tài)性。 多態(tài)性的作用：多態(tài)性機(jī)制不僅增加了面向?qū)ο筌浖到y(tǒng)的靈活性，進(jìn)一步減少了信息冗余，而且顯著地提高了軟件的可重用性和可擴(kuò)充性。面向?qū)ο蟪绦蛟O(shè)計方法學(xué)的基本概念7.2 算法概述7.2.1 算法的基本概念1算法的基本概念 算法是指解題方案的準(zhǔn)確而完整的描述，并且具有下列特性： （1）有窮性：一個算法必須在執(zhí)行有窮步驟之后結(jié)束，且每一步都可在有窮時間內(nèi)完成。 算法的特性（2）確定性：算法的每一步必須是確切定義的，不能有歧義。（3）可行性：算法應(yīng)該是可行的。（4）輸入：一個算法有零個或多個輸入。（5）輸出：一個算法有一個或多個輸出。7.2.1 算法的基本概念2算法的基本

13、要素對數(shù)據(jù)對象的運(yùn)算和操作 算法的控制結(jié)構(gòu) 算術(shù)運(yùn)算、 邏輯運(yùn)算、 關(guān)系運(yùn)算、 數(shù)據(jù)傳輸算法中各操作之間的執(zhí)行順序7.2.1 算法的基本概念3算法設(shè)計的要求正確性可讀性健壯性效率評價一個算法優(yōu)劣的主要標(biāo)準(zhǔn)是算法的執(zhí)行效率和存儲需求。算法的執(zhí)行效率指的是時間復(fù)雜度（Time Complexity），存儲需求指的是空間復(fù)雜度（Space Complexity）。 7.2.1 算法的復(fù)雜度7.2.2 算法的復(fù)雜度1算法的時間復(fù)雜度概念算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。因為基本運(yùn)算反映了算法運(yùn)算的主要特征，因而可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量。算法的時間復(fù)雜

14、度算法的工作量計算公式算法的工作量=f(n) 其中n是問題的規(guī)模兩個n階矩陣相乘所需的基本運(yùn)算（即兩個實數(shù)的乘法）次數(shù)為n3，即計算工作量為n3，也就是時間復(fù)雜度為n3。 算法的時間復(fù)雜度注意事項在同一個問題規(guī)模下，如果算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于某一特定輸入時，可以用平均性態(tài)和最壞情況復(fù)雜性方法來分析算法的工作量。算法的時間復(fù)雜度平均性態(tài)平均性態(tài)分析是指用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來度量算法的工作量。 在長度為n的一維數(shù)組中查找值為x的元素，若采用順序搜索法，在平均情況下需要檢查數(shù)組中一半的元素。 算法的時間復(fù)雜度最壞情況分析 最壞情況分析是指在規(guī)模為n時，算法所執(zhí)行的基本

15、運(yùn)算的最大次數(shù)。 在長度為n的一維數(shù)組中查找值為x的元素，若采用順序搜索法，在最壞情況下最壞情況需查找n次。 7.2.2 算法的復(fù)雜度2算法的空間復(fù)雜度一個算法的空間復(fù)雜度一般是指執(zhí)行這個算法所需要的內(nèi)存空間。包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間。 例 題【例7.1】討論用選擇法對數(shù)組中n個整數(shù)按由小到大排序的時間復(fù)雜度。1.選擇法: 先將n個數(shù)中最小的數(shù)與a0對換，再將a1到an-1中最小的數(shù)與a1對換每比較一輪，找出一個未經(jīng)排序的數(shù)中最小的一個，共比較n1輪。

16、 2.算法:（1）從鍵盤輸入n個數(shù)，并將其存儲在一個有n個元素的整型數(shù)組a中。（2）進(jìn)行選擇排序： int i=0；/每一輪比較起始元素的下標(biāo) int k=0；/每一輪比較得到的最小元素的下標(biāo) 通過循環(huán)求出aian中最小數(shù)的下標(biāo)k 如果i不等于k，將ai與ak對換 i=i+1，轉(zhuǎn)到（3）輸出排序的結(jié)果。3.C+程序代碼void 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; /

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