第5章 程序設(shè)計(jì)基礎(chǔ)

1、5.1 程序設(shè)計(jì)概述程序設(shè)計(jì)概述5.2 算法概述算法概述5.3 軟件工程概述軟件工程概述第第5 5章章 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ)5.1.1 程序設(shè)計(jì)的基本過(guò)程程序設(shè)計(jì)的基本過(guò)程5.1.2 程序設(shè)計(jì)的方法程序設(shè)計(jì)的方法5.1.3 程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言5.1 程序設(shè)計(jì)概述程序設(shè)計(jì)概述5.1.1 程序設(shè)計(jì)的基本過(guò)程程序設(shè)計(jì)的基本過(guò)程w 程序設(shè)計(jì)：編寫程序的過(guò)程w 程序設(shè)計(jì)過(guò)程包括分析、設(shè)計(jì)、編碼、測(cè)試、編寫文檔等不同階段5.1.2 程序設(shè)計(jì)的方法程序設(shè)計(jì)的方法w 結(jié)構(gòu)化程序設(shè)計(jì)方法w 面向?qū)ο蟪绦蛟O(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)w 結(jié)構(gòu)化程序設(shè)計(jì)的原則n自頂向下n逐步細(xì)化n模塊化n限制使用g

2、oto語(yǔ)句結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)w 結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)n順序結(jié)構(gòu)n選擇結(jié)構(gòu)n循環(huán)結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)w順序結(jié)構(gòu)n按照程序語(yǔ)句的書寫順序一條一條的執(zhí)行n最基本、最常用的結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)w選擇結(jié)構(gòu)（分支結(jié)構(gòu)）n根據(jù)設(shè)定的條件，判斷應(yīng)該執(zhí)行哪一條語(yǔ)句n包括單分支結(jié)構(gòu)、雙分支結(jié)構(gòu)和多分支結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)w循環(huán)結(jié)構(gòu)（重復(fù)結(jié)構(gòu)）n根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行相同的程序段n分為當(dāng)型循環(huán)結(jié)構(gòu)和直到型循環(huán)結(jié)構(gòu) 面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蟪绦蛟O(shè)計(jì)w 結(jié)構(gòu)化程序設(shè)計(jì)又稱為面向過(guò)程的程序設(shè)計(jì)w 面向?qū)ο蟪绦蛟O(shè)計(jì)方法模擬人們理解和處理客觀世界的方式來(lái)分析問(wèn)題

3、，把系統(tǒng)視為一系列對(duì)象的集合，分析者、設(shè)計(jì)者和編程者都可以使用相同的概念，從而使面向?qū)ο蟮某绦蛟O(shè)計(jì)方法能比較自然地模擬客觀世界的活動(dòng)，使問(wèn)題描述空間與解空間在結(jié)構(gòu)上盡可能一致。面向?qū)ο蟮幕靖拍蠲嫦驅(qū)ο蟮幕靖拍顆 對(duì)象：客觀世界中的任何實(shí)體，既可以是具體的物理實(shí)體的抽象，也可以是人為的概念，或者是任何有明確邊界和意義的東西。w 對(duì)象的特點(diǎn)：n標(biāo)識(shí)唯一性n分類型n多態(tài)性n封裝性n模塊獨(dú)立性面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蟪绦蛟O(shè)計(jì)w 類：n類是對(duì)象的抽象，它描述了該對(duì)象類型的所有對(duì)象的性質(zhì)，而一個(gè)對(duì)象則是其對(duì)應(yīng)類的一個(gè)實(shí)例w 消息n面向?qū)ο蟮氖澜缡峭ㄟ^(guò)對(duì)象與對(duì)象間彼此的相互合作來(lái)推動(dòng)的，對(duì)象間的這種相互

4、合作需要一個(gè)機(jī)制來(lái)協(xié)助完成，這種機(jī)制稱為“消息”面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蟪绦蛟O(shè)計(jì)w 繼承n使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)n已有的類可當(dāng)做基類來(lái)引用，新類可當(dāng)做派生類來(lái)引用n繼承具有傳遞性面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蟪绦蛟O(shè)計(jì)w 封裝性n所謂封裝，指的就是類中定義的數(shù)據(jù)只能被類中定義的方法所訪問(wèn)，除此之外別無(wú)它法n封裝的結(jié)果實(shí)際上隱蔽了復(fù)雜性，并提供了代碼重用性，從而降低了軟件開(kāi)發(fā)的難度。w 多態(tài)性n對(duì)象根據(jù)所接收的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象接收時(shí)，可導(dǎo)致完全不同的行動(dòng)，該現(xiàn)象稱為多態(tài)性面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蟪绦蛟O(shè)計(jì)w 面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)：n與人類習(xí)慣的思維方法一致n穩(wěn)定性好

5、n可重用性好n易于開(kāi)發(fā)大型軟件產(chǎn)品n可維護(hù)性好5.1.3 程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言w 程序設(shè)計(jì)語(yǔ)言就是用于書寫計(jì)算機(jī)程序的一組記號(hào)和一組規(guī)則。w 分類：n機(jī)器語(yǔ)言n匯編語(yǔ)言n高級(jí)語(yǔ)言 由由0 0、1 1代碼組成，代碼組成，能被計(jì)算機(jī)硬件系統(tǒng)能被計(jì)算機(jī)硬件系統(tǒng)直接識(shí)別和執(zhí)行的計(jì)算機(jī)語(yǔ)言，不需要翻譯。直接識(shí)別和執(zhí)行的計(jì)算機(jī)語(yǔ)言，不需要翻譯。 占用空間小、執(zhí)行速度快占用空間小、執(zhí)行速度快 不易學(xué)習(xí)和修改不易學(xué)習(xí)和修改 不同類型不同類型的機(jī)器語(yǔ)言不同，的機(jī)器語(yǔ)言不同，通用性差通用性差機(jī)器語(yǔ)言程序機(jī)器語(yǔ)言程序注釋注釋10110000 00001000把8存放到累加器A中00101100 00001010

6、將10與累加器中的8相加，結(jié)果存在A中11110100程序結(jié)束機(jī)器語(yǔ)言實(shí)例機(jī)器語(yǔ)言實(shí)例 用助記符代替機(jī)器語(yǔ)言中的指令和數(shù)據(jù)用助記符代替機(jī)器語(yǔ)言中的指令和數(shù)據(jù)易修改，保持速度快，占用空間小易修改，保持速度快，占用空間小不同類型不同類型機(jī)器機(jī)器的的匯編語(yǔ)言不同，匯編語(yǔ)言不同，通用性差通用性差8+10加法題加法題MOV AX, 8HMOV AX, 8HMOV BX, 0AHMOV BX, 0AHADD BX, AXADD BX, AX 由貼近自然語(yǔ)言的由貼近自然語(yǔ)言的“詞詞”和和“數(shù)學(xué)公數(shù)學(xué)公式式”組成組成 易學(xué)、易讀，易修改易學(xué)、易讀，易修改 通用性好，不依賴于機(jī)器通用性好，不依賴于機(jī)器 具有很強(qiáng)

7、的具有很強(qiáng)的通用性通用性和和可移植性可移植性c=8+10常用的程序設(shè)計(jì)語(yǔ)言常用的程序設(shè)計(jì)語(yǔ)言w 面向過(guò)程語(yǔ)言nFortran、Pascal、C等w 面向?qū)ο笳Z(yǔ)言nC+、java語(yǔ)言處理系統(tǒng)的作用就是把程序語(yǔ)言編寫的程序變換成計(jì)算機(jī)上執(zhí)行的程序匯編語(yǔ)言匯編語(yǔ)言匯編程序匯編程序高級(jí)語(yǔ)言高級(jí)語(yǔ)言 高級(jí)語(yǔ)言高級(jí)語(yǔ)言 編譯程序編譯程序連接程序連接程序數(shù)據(jù)數(shù)據(jù)解釋程序解釋程序數(shù)據(jù)數(shù)據(jù)編譯程序：編譯程序：執(zhí)行速度快，但占用內(nèi)存多，可執(zhí)行速度快，但占用內(nèi)存多，可脫離編譯程序和源程序獨(dú)立存在并反復(fù)使用脫離編譯程序和源程序獨(dú)立存在并反復(fù)使用. .如：如： C/C+C/C+、PascalPascal、FORTRAN

8、FORTRAN等等解釋程序：解釋程序：邊解釋邊執(zhí)行，便于查錯(cuò)，占用內(nèi)邊解釋邊執(zhí)行，便于查錯(cuò)，占用內(nèi)存少，執(zhí)行效率低、速度慢。如：存少，執(zhí)行效率低、速度慢。如：BASICBASIC語(yǔ)言語(yǔ)言編譯程序與解釋程序的區(qū)別編譯程序與解釋程序的區(qū)別5.2.1 算法的概念算法的概念5.2.2 算法的表示算法的表示5.2.3 常用算法介紹常用算法介紹5.2 算法概述算法概述算法算法算法算法( (AlgorithmAlgorithm) )：算法就是一個(gè)有窮規(guī)：算法就是一個(gè)有窮規(guī)則的集合，其中的規(guī)則確定了一個(gè)解決某則的集合，其中的規(guī)則確定了一個(gè)解決某一特定類型問(wèn)題的運(yùn)算序列。一特定類型問(wèn)題的運(yùn)算序列。5.2.1 算

9、法的概念算法的概念算法的特性算法的特性 有限性有限性 確定性確定性 可行性可行性 輸入輸入 輸出輸出算法的表示方法算法的表示方法算法的表示方法：算法的表示方法：l自然語(yǔ)言；自然語(yǔ)言；l程序流程圖；程序流程圖；lN-S流程圖；流程圖；l偽代碼；偽代碼；自然語(yǔ)言自然語(yǔ)言w 使用自然語(yǔ)言描述求解sum=1+2+3+4+5+（n-1）+n的方法。 確定一個(gè)n的值； 設(shè)等號(hào)右邊的算式項(xiàng)中的初始值i為1； 設(shè)sum的初始值為0； 如果in時(shí)，執(zhí)行，否則轉(zhuǎn)出執(zhí)行； 計(jì)算sum加上i的值后，重新賦值給sum； 計(jì)算i加1，然后將值重新賦值給i； 轉(zhuǎn)去執(zhí)行； 輸出sum 的值，算法結(jié)束。自然語(yǔ)言自然語(yǔ)言w 自然

10、語(yǔ)言描述方法的缺點(diǎn)：n自言語(yǔ)言的歧異性容易導(dǎo)致算法執(zhí)行的不確定性。n自然語(yǔ)言的語(yǔ)句一般太長(zhǎng)，從而導(dǎo)致了用自然語(yǔ)言描述的算法太長(zhǎng)。n由于自然語(yǔ)言表示的串行性，因此，當(dāng)一個(gè)算法中循環(huán)和分支較多時(shí)就很難清晰地表示出來(lái)。n自然語(yǔ)言表示的算法不便翻譯成計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言理解的語(yǔ)言。程序流程圖程序流程圖程程序序流流程程圖圖符符號(hào)號(hào)程序流程圖程序流程圖w 以求解sum=1+2+3+4+5+（n-1）+n為例來(lái)介紹算法的流程圖描述方法N-S流程圖流程圖w N-S流程圖簡(jiǎn)稱N-S圖，也被稱為盒圖。N-S圖是在1973年，由美國(guó)學(xué)者I.Nassi 和 B.Shneiderman提出來(lái)的，并分別取兩人名字的首字母來(lái)

11、進(jìn)行命名。N-S圖是在程序流程圖的基礎(chǔ)上去掉流程線，將全部算法寫在一個(gè)矩形框內(nèi)，在該框內(nèi)還可以包含其他的從屬于它的框的一種算法表示方法。即由一些基本的框組成的一個(gè)大框。N-S流程圖流程圖w N-S流程圖的三大結(jié)構(gòu)w 順序結(jié)構(gòu)w 選擇結(jié)構(gòu)w 循環(huán)結(jié)構(gòu)N-S流程圖流程圖寫出求sum=1+2+3+4+5+（n-1）+n的 N-S圖的描述方法偽代碼偽代碼w 用流程圖或N-S圖來(lái)描述算法雖然形象直觀，但在算法設(shè)計(jì)過(guò)程中使用起來(lái)并不十分方便，特別是當(dāng)算法稍微復(fù)雜一點(diǎn)時(shí)，不易修改。w 在實(shí)際的算法設(shè)計(jì)中，常常使用自然語(yǔ)言或計(jì)算機(jī)語(yǔ)言或類計(jì)算機(jī)語(yǔ)言來(lái)描述。w 這里的類計(jì)算機(jī)語(yǔ)言是一種非計(jì)算機(jī)語(yǔ)言，借用了一些高

12、級(jí)語(yǔ)言的某些成分，沒(méi)有加入嚴(yán)格的規(guī)則，而且不能夠被計(jì)算機(jī)所接受，稱其為“偽代碼”。偽代碼偽代碼寫出求sum=1+2+3+4+5+（n-1）+n的 偽代碼的描述方法(1) 算法開(kāi)始；(2) 輸入 n 的值；(3) i 1； (4) sum 0；(5) do while i=n(6) sum sum + i；(7) i i + 1；(8) 輸出 sum 的值；(9) 算法結(jié)束；5.2.3 常用算法介紹常用算法介紹1.枚舉法2.遞推法3.求最大值、最小值問(wèn)題4.交換兩個(gè)變量的值5.排序算法6.查找算法枚舉法又稱為窮舉法w 基本思想：根據(jù)題目的部分條件確定答案的大致范圍，然后在此范圍內(nèi)對(duì)所有可能的情況

13、逐一驗(yàn)證，直到所有情況均通過(guò)驗(yàn)證。若某個(gè)情況符合題目條件，則為本題的一個(gè)答案；若全部情況驗(yàn)證完后均不符合題目的條件，則問(wèn)題無(wú)解。w 特點(diǎn)：算法簡(jiǎn)單，容易理解，運(yùn)算量大1.1.枚舉法枚舉法1.1.枚舉法枚舉法應(yīng)用：百錢買百雞問(wèn)題假定公雞每只5元，母雞每只3元，小雞3只1元?，F(xiàn)有100元錢要求買100只雞，問(wèn)共有幾種購(gòu)雞方案？w 問(wèn)題分析：根據(jù)題目，設(shè)公雞、母雞、小雞各為x，y，z只，列出方程為：x+y+z=1005x+3y+z/3=100w 巧妙和高效的算法很少來(lái)自于窮舉法，但基于以下因素，窮舉法仍是一種重要的算法設(shè)計(jì)策略：窮舉法幾乎可以通用于任何領(lǐng)域的問(wèn)題求解，可能是唯一一種解決所有問(wèn)題的一般

14、性方法即使效率低下，仍可用窮舉法求解一些小規(guī)模的問(wèn)題實(shí)例；如果解決的問(wèn)題實(shí)例不多，而窮舉法可用一種可接受的速度對(duì)問(wèn)題求解，那么花時(shí)間去設(shè)計(jì)一個(gè)更高效地算法是得不償失的。 1.1.枚舉法枚舉法 思考題思考題 舉例說(shuō)明生活中的窮舉法應(yīng)用。舉例說(shuō)明生活中的窮舉法應(yīng)用。遞推法又稱為迭代法w 基本思想：利用問(wèn)題本身所具有的某種遞推關(guān)系求解問(wèn)題。從初值出發(fā)，歸納出新值與舊值間存在的關(guān)系，從而把一個(gè)復(fù)雜的計(jì)算過(guò)程轉(zhuǎn)換為簡(jiǎn)單過(guò)程的多次重復(fù)，每次重復(fù)都從舊值的基礎(chǔ)上遞推出新值，并由新值代替舊值。2.2.遞推法遞推法2.2.遞推法遞推法w w 基本思想：采用如同打擂臺(tái)的方法。在n個(gè)數(shù)中，先假設(shè)第一個(gè)數(shù)為最大值，稱

15、為擂主，依次同第2，3，n個(gè)數(shù)據(jù)逐一比較，一旦某個(gè)數(shù)大，馬上替換擂主；所有值比較完，最大值也就獲得。求最小值問(wèn)題則先假設(shè)第一個(gè)數(shù)為最小值。3.3.求最大值、最小值問(wèn)題求最大值、最小值問(wèn)題3.3.求最大值、最小值問(wèn)題求最大值、最小值問(wèn)題應(yīng)用：對(duì)輸入的若干個(gè)學(xué)生成績(jī)，求出最高分和最低分。w max=min=a0；w 用max依次與后續(xù)的成績(jī)進(jìn)行對(duì)比，若比max大則將相應(yīng)值賦值給max；w 用min依次與后續(xù)的成績(jī)進(jìn)行對(duì)比，若比min小則將相應(yīng)值賦值給min；w 最后輸出max和min的值。w 基本思想：由于計(jì)算機(jī)內(nèi)存的特點(diǎn)，因此，計(jì)算機(jī)中交換兩個(gè)變量的值只能采取間接交換的方法。4.4.交換兩個(gè)變量

16、的值交換兩個(gè)變量的值4.4.交換兩個(gè)變量的值交換兩個(gè)變量的值有黑和藍(lán)兩個(gè)墨水瓶，但卻把黑墨水裝在了藍(lán)墨水的瓶子里，而把藍(lán)墨水錯(cuò)裝在了黑墨水瓶子里，要求將其互換。4.4.交換兩個(gè)變量的值交換兩個(gè)變量的值應(yīng)用：a=5, b=10，交換a，b的值并輸出w 引入一個(gè)新的變量c；w 將a的值賦值給c；w 將b的值賦值給a；w 將c的值賦值給b；w 選擇排序的基本思想：每一輪從待排序列中選取一個(gè)關(guān)鍵碼最小的記錄與第i個(gè)位置的記錄進(jìn)行交換，也即第一輪從n個(gè)記錄中選取關(guān)鍵碼最小的記錄與第1個(gè)位置的記錄交換，第二輪從剩下的n-1個(gè)記錄中選取關(guān)鍵碼最小的記錄與第2個(gè)位置的記錄進(jìn)行交換，直到整個(gè)序列的記錄選完5.5

17、.排序算法排序算法5.5.排序算法排序算法【例5.6】給出一組關(guān)鍵字(28，6，72，85，39，41，13，20)，排序后得到(6，13，20，28，39，41，72，85)，其選擇排序過(guò)程如下w 查找是指從給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)給定的值。w 常用的查找算法有順序查找、二分查找等等。w 順序查找是直接從頭到尾搜索集合中滿足條件的值。w 二分查找是必須首先將集合按照降序或升序排序，然后利用折半技術(shù)搜索集合中滿足條件的值。6.6.查找算法查找算法6.6.查找算法查找算法二分查找的方法如下：w 將x與線性表的中間項(xiàng)進(jìn)行比較；w 若中間項(xiàng)的值等于x，則說(shuō)明查找到，查找結(jié)束；w 若x小于中間項(xiàng)的值，

18、則在線性表的前半部分以相同的方法進(jìn)行查找。w 若x大于中間項(xiàng)的值，則在線性表的后半部分以相同的方法進(jìn)行查找。w 這個(gè)過(guò)程一直進(jìn)行到查找成功或子表長(zhǎng)度為0為止?！纠?.7】有序表中關(guān)鍵字序列為3，10，13，17，40，43，50，70，要查找關(guān)鍵字值為43的數(shù)據(jù)元素6.6.查找算法查找算法5.3.1 軟件危機(jī)軟件危機(jī)5.3.2 軟件工程軟件工程5.3.3 軟件生存周期軟件生存周期5.3 軟件工程概述軟件工程概述5.3.1 軟件危機(jī)軟件危機(jī)w 軟件危機(jī)是指在計(jì)算機(jī)軟件的開(kāi)發(fā)和維護(hù)過(guò)程中所遇到的一系列嚴(yán)重問(wèn)題，主要有以下一些表現(xiàn)形式。軟件開(kāi)發(fā)費(fèi)用和進(jìn)度失控。軟件的可靠性差。生產(chǎn)出來(lái)的軟件難以維護(hù)。

19、用戶對(duì)“已完成”的系統(tǒng)不滿意現(xiàn)象經(jīng)常發(fā)生。5.3.2 軟件工程軟件工程w IEEE給出的軟件工程的定義是：軟件工程是將系統(tǒng)化的、規(guī)范的、可度量的方法應(yīng)用于軟件的開(kāi)發(fā)、運(yùn)行、維護(hù)過(guò)程，即將工程化應(yīng)用于軟件中的方法的研究。w 人們給出的一般定義是：軟件工程是一門旨在生產(chǎn)無(wú)故障的、積極交付的、在預(yù)算之內(nèi)的和滿足用戶需求的軟件的學(xué)科。實(shí)質(zhì)上，軟件工程就是采用工程的概念、原理、技術(shù)和方法來(lái)開(kāi)發(fā)與維護(hù)軟件，把經(jīng)過(guò)實(shí)踐考驗(yàn)而證明正確的管理方法和最先進(jìn)的軟件開(kāi)發(fā)技術(shù)結(jié)合起來(lái)，應(yīng)用到軟件開(kāi)發(fā)和維護(hù)過(guò)程中，來(lái)解決軟件危機(jī)問(wèn)題。5.3.2 軟件工程軟件工程w 軟件工程包括三要素：方法、工具和過(guò)程。w 軟件工程的目標(biāo)是：在給定成本、進(jìn)度的前提下，開(kāi)發(fā)出具有可修改性、有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性并且滿足用戶需求的軟件產(chǎn)品。追求這些目標(biāo)有助于提高軟件產(chǎn)品的質(zhì)量和開(kāi)發(fā)效率，減少維護(hù)的困難w 軟件工程的原則：抽象、信息隱藏、模塊化、局部化、一致性、確定性、完備性和可驗(yàn)證性5.3.3 軟件生存周期軟件生存周期軟件過(guò)程模型軟件過(guò)程模型w 定義：從軟件項(xiàng)目需求定義直至軟件運(yùn)行定義：從軟件項(xiàng)目需求定義直至軟件運(yùn)行維護(hù)為止