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

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

2、oto語句結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計w 結(jié)構(gòu)化程序設(shè)計的基本結(jié)構(gòu)n順序結(jié)構(gòu)n選擇結(jié)構(gòu)n循環(huán)結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計w順序結(jié)構(gòu)n按照程序語句的書寫順序一條一條的執(zhí)行n最基本、最常用的結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計w選擇結(jié)構(gòu)（分支結(jié)構(gòu)）n根據(jù)設(shè)定的條件，判斷應(yīng)該執(zhí)行哪一條語句n包括單分支結(jié)構(gòu)、雙分支結(jié)構(gòu)和多分支結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計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è)計面向?qū)ο蟪绦蛟O(shè)計w 結(jié)構(gòu)化程序設(shè)計又稱為面向過程的程序設(shè)計w 面向?qū)ο蟪绦蛟O(shè)計方法模擬人們理解和處理客觀世界的方式來分析問題

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

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

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

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

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

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

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

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

11、進(jìn)行命名。N-S圖是在程序流程圖的基礎(chǔ)上去掉流程線，將全部算法寫在一個矩形框內(nèi)，在該框內(nèi)還可以包含其他的從屬于它的框的一種算法表示方法。即由一些基本的框組成的一個大框。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圖來描述算法雖然形象直觀，但在算法設(shè)計過程中使用起來并不十分方便，特別是當(dāng)算法稍微復(fù)雜一點時，不易修改。w 在實際的算法設(shè)計中，常常使用自然語言或計算機語言或類計算機語言來描述。w 這里的類計算機語言是一種非計算機語言，借用了一些高

12、級語言的某些成分，沒有加入嚴(yán)格的規(guī)則，而且不能夠被計算機所接受，稱其為“偽代碼”。偽代碼偽代碼寫出求sum=1+2+3+4+5+（n-1）+n的 偽代碼的描述方法(1) 算法開始；(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.求最大值、最小值問題4.交換兩個變量的值5.排序算法6.查找算法枚舉法又稱為窮舉法w 基本思想：根據(jù)題目的部分條件確定答案的大致范圍，然后在此范圍內(nèi)對所有可能的情況

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

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

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

16、的值交換兩個變量的值4.4.交換兩個變量的值交換兩個變量的值有黑和藍(lán)兩個墨水瓶，但卻把黑墨水裝在了藍(lán)墨水的瓶子里，而把藍(lán)墨水錯裝在了黑墨水瓶子里，要求將其互換。4.4.交換兩個變量的值交換兩個變量的值應(yīng)用：a=5, b=10，交換a，b的值并輸出w 引入一個新的變量c；w 將a的值賦值給c；w 將b的值賦值給a；w 將c的值賦值給b；w 選擇排序的基本思想：每一輪從待排序列中選取一個關(guān)鍵碼最小的記錄與第i個位置的記錄進(jìn)行交換，也即第一輪從n個記錄中選取關(guān)鍵碼最小的記錄與第1個位置的記錄交換，第二輪從剩下的n-1個記錄中選取關(guān)鍵碼最小的記錄與第2個位置的記錄進(jìn)行交換，直到整個序列的記錄選完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)，其選擇排序過程如下w 查找是指從給定的數(shù)據(jù)結(jié)構(gòu)中查找某個給定的值。w 常用的查找算法有順序查找、二分查找等等。w 順序查找是直接從頭到尾搜索集合中滿足條件的值。w 二分查找是必須首先將集合按照降序或升序排序，然后利用折半技術(shù)搜索集合中滿足條件的值。6.6.查找算法查找算法6.6.查找算法查找算法二分查找的方法如下：w 將x與線性表的中間項進(jìn)行比較；w 若中間項的值等于x，則說明查找到，查找結(jié)束；w 若x小于中間項的值，

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

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