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

5.1程序設(shè)計(jì)概述5.2算法概述5.3軟件工程概述第5章程序設(shè)計(jì)基礎(chǔ)5.1程序設(shè)計(jì)概述第5章程序設(shè)計(jì)基礎(chǔ)5.1.1

程序設(shè)計(jì)的基本過程5.1.2

程序設(shè)計(jì)的方法5.1.3

程序設(shè)計(jì)語言5.1程序設(shè)計(jì)概述5.1.1程序設(shè)計(jì)的基本過程5.1程序設(shè)計(jì)概述5.1.1程序設(shè)計(jì)的基本過程程序設(shè)計(jì)：編寫程序的過程程序設(shè)計(jì)過程包括分析、設(shè)計(jì)、編碼、測(cè)試、編寫文檔等不同階段5.1.1程序設(shè)計(jì)的基本過程程序設(shè)計(jì)：編寫程序的過程5.1.2程序設(shè)計(jì)的方法結(jié)構(gòu)化程序設(shè)計(jì)方法面向?qū)ο蟪绦蛟O(shè)計(jì)方法5.1.2程序設(shè)計(jì)的方法結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的原則自頂向下逐步細(xì)化模塊化限制使用goto語句結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的原則結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)順序結(jié)構(gòu)按照程序語句的書寫順序一條一條的執(zhí)行最基本、最常用的結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)順序結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)選擇結(jié)構(gòu)（分支結(jié)構(gòu)）根據(jù)設(shè)定的條件，判斷應(yīng)該執(zhí)行哪一條語句包括單分支結(jié)構(gòu)、雙分支結(jié)構(gòu)和多分支結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)選擇結(jié)構(gòu)（分支結(jié)構(gòu)）結(jié)構(gòu)化程序設(shè)計(jì)循環(huán)結(jié)構(gòu)（重復(fù)結(jié)構(gòu)）根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行相同的程序段分為當(dāng)型循環(huán)結(jié)構(gòu)和直到型循環(huán)結(jié)構(gòu)

結(jié)構(gòu)化程序設(shè)計(jì)循環(huán)結(jié)構(gòu)（重復(fù)結(jié)構(gòu)）面向?qū)ο蟪绦蛟O(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)又稱為面向過程的程序設(shè)計(jì)面向?qū)ο蟪绦蛟O(shè)計(jì)方法模擬人們理解和處理客觀世界的方式來分析問題，把系統(tǒng)視為一系列對(duì)象的集合，分析者、設(shè)計(jì)者和編程者都可以使用相同的概念，從而使面向?qū)ο蟮某绦蛟O(shè)計(jì)方法能比較自然地模擬客觀世界的活動(dòng)，使問題描述空間與解空間在結(jié)構(gòu)上盡可能一致。面向?qū)ο蟪绦蛟O(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)又稱為面向過程的程序設(shè)計(jì)面向?qū)ο蟮幕靖拍顚?duì)象：客觀世界中的任何實(shí)體，既可以是具體的物理實(shí)體的抽象，也可以是人為的概念，或者是任何有明確邊界和意義的東西。對(duì)象的特點(diǎn)：標(biāo)識(shí)唯一性分類型多態(tài)性封裝性模塊獨(dú)立性面向?qū)ο蟮幕靖拍顚?duì)象：客觀世界中的任何實(shí)體，既可以是具體的面向?qū)ο蟪绦蛟O(shè)計(jì)類：類是對(duì)象的抽象，它描述了該對(duì)象類型的所有對(duì)象的性質(zhì)，而一個(gè)對(duì)象則是其對(duì)應(yīng)類的一個(gè)實(shí)例消息面向?qū)ο蟮氖澜缡峭ㄟ^對(duì)象與對(duì)象間彼此的相互合作來推動(dòng)的，對(duì)象間的這種相互合作需要一個(gè)機(jī)制來協(xié)助完成，這種機(jī)制稱為“消息”面向?qū)ο蟪绦蛟O(shè)計(jì)類：面向?qū)ο蟪绦蛟O(shè)計(jì)繼承使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)已有的類可當(dāng)做基類來引用，新類可當(dāng)做派生類來引用繼承具有傳遞性面向?qū)ο蟪绦蛟O(shè)計(jì)繼承面向?qū)ο蟪绦蛟O(shè)計(jì)封裝性所謂封裝，指的就是類中定義的數(shù)據(jù)只能被類中定義的方法所訪問，除此之外別無它法封裝的結(jié)果實(shí)際上隱蔽了復(fù)雜性，并提供了代碼重用性，從而降低了軟件開發(fā)的難度。多態(tài)性對(duì)象根據(jù)所接收的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象接收時(shí)，可導(dǎo)致完全不同的行動(dòng)，該現(xiàn)象稱為多態(tài)性面向?qū)ο蟪绦蛟O(shè)計(jì)封裝性面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)：與人類習(xí)慣的思維方法一致穩(wěn)定性好可重用性好易于開發(fā)大型軟件產(chǎn)品可維護(hù)性好面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)：5.1.3程序設(shè)計(jì)語言程序設(shè)計(jì)語言就是用于書寫計(jì)算機(jī)程序的一組記號(hào)和一組規(guī)則。分類：機(jī)器語言匯編語言高級(jí)語言5.1.3程序設(shè)計(jì)語言程序設(shè)計(jì)語言就是用于書寫計(jì)算機(jī)程序的(1)機(jī)器語言

由0、1代碼組成，能被計(jì)算機(jī)硬件系統(tǒng)直接識(shí)別和執(zhí)行的計(jì)算機(jī)語言，不需要翻譯。特點(diǎn)：占用空間小、執(zhí)行速度快不易學(xué)習(xí)和修改不同類型機(jī)器的機(jī)器語言不同，通用性差程序設(shè)計(jì)語言(1)機(jī)器語言由0、1代碼組成，能被計(jì)算機(jī)硬件系統(tǒng)直機(jī)器語言程序注釋1011000000001000把8存放到累加器A中0010110000001010將10與累加器中的8相加，結(jié)果存在A中11110100程序結(jié)束機(jī)器語言實(shí)例機(jī)器語言程序注釋1011000000001000把8存放到(2)匯編語言（符號(hào)語言）程序設(shè)計(jì)語言

用助記符代替機(jī)器語言中的指令和數(shù)據(jù)特點(diǎn)：易修改，保持速度快，占用空間小不同類型機(jī)器的匯編語言不同，通用性差實(shí)例：8+10加法題MOVAX,8HMOVBX,0AHADDBX,AX(2)匯編語言（符號(hào)語言）程序設(shè)計(jì)語言用助記符代替機(jī)器語(3)高級(jí)語言程序設(shè)計(jì)語言

由貼近自然語言的“詞”和“數(shù)學(xué)公式”組成

特點(diǎn)：

易學(xué)、易讀，易修改通用性好，不依賴于機(jī)器具有很強(qiáng)的通用性和可移植性

實(shí)例：c=8+10(3)高級(jí)語言程序設(shè)計(jì)語言由貼近自然語言的“詞”和“常用的程序設(shè)計(jì)語言面向過程語言Fortran、Pascal、C等面向?qū)ο笳Z言C++、java常用的程序設(shè)計(jì)語言面向過程語言語言處理系統(tǒng)的作用就是把程序語言編寫的程序變換成計(jì)算機(jī)上執(zhí)行的程序分類匯編程序編譯程序解釋程序程序設(shè)計(jì)語言處理系統(tǒng)語言處理系統(tǒng)的作用就是把程序語言編寫的程序變換成計(jì)算機(jī)上執(zhí)行匯編語言源程序機(jī)器語言程序匯編程序

匯編程序程序設(shè)計(jì)語言處理系統(tǒng)匯編程序匯編程序程序設(shè)計(jì)語言處理系統(tǒng)高級(jí)語言源程序高級(jí)語言目標(biāo)源程序程序編譯程序連接程序可執(zhí)行程序計(jì)算結(jié)果數(shù)據(jù)解釋程序計(jì)算結(jié)果數(shù)據(jù)編譯程序：執(zhí)行速度快，但占用內(nèi)存多，可脫離編譯程序和源程序獨(dú)立存在并反復(fù)使用.如：C/C++、Pascal、FORTRAN等解釋程序：邊解釋邊執(zhí)行，便于查錯(cuò)，占用內(nèi)存少，執(zhí)行效率低、速度慢。如：BASIC語言程序設(shè)計(jì)語言處理系統(tǒng)編譯程序連接程序可執(zhí)行計(jì)算數(shù)據(jù)解釋程序計(jì)算數(shù)據(jù)編譯程序：執(zhí)行編譯程序與解釋程序的區(qū)別編譯程序與解釋程序的區(qū)別5.2.1

算法的概念5.2.2

算法的表示5.2.3

常用算法介紹5.2算法概述5.2.1算法的概念5.2算法概述算法算法(Algorithm)：算法就是一個(gè)有窮規(guī)則的集合，其中的規(guī)則確定了一個(gè)解決某一特定類型問題的運(yùn)算序列。5.2.1算法的概念算法5.2.1算法的概念算法的特性①有限性②確定性③可行性④輸入⑤輸出算法的特性①有限性算法的表示方法算法的表示方法：自然語言；程序流程圖；N-S流程圖；偽代碼；算法的表示方法算法的表示方法：自然語言使用自然語言描述求解sum=1+2+3+4+5……+（n-1）+n的方法。①確定一個(gè)n的值；②設(shè)等號(hào)右邊的算式項(xiàng)中的初始值i為1；③設(shè)sum的初始值為0；④如果i≤n時(shí)，執(zhí)行⑤，否則轉(zhuǎn)出執(zhí)行⑧；⑤計(jì)算sum加上i的值后，重新賦值給sum；⑥計(jì)算i加1，然后將值重新賦值給i；⑦轉(zhuǎn)去執(zhí)行④；⑧輸出sum的值，算法結(jié)束。自然語言使用自然語言描述求解sum=1+2+3+4+5……+自然語言自然語言描述方法的缺點(diǎn)：自言語言的歧異性容易導(dǎo)致算法執(zhí)行的不確定性。自然語言的語句一般太長(zhǎng)，從而導(dǎo)致了用自然語言描述的算法太長(zhǎng)。由于自然語言表示的串行性，因此，當(dāng)一個(gè)算法中循環(huán)和分支較多時(shí)就很難清晰地表示出來。自然語言表示的算法不便翻譯成計(jì)算機(jī)程序設(shè)計(jì)語言理解的語言。自然語言自然語言描述方法的缺點(diǎn)：程序流程圖程序流程圖符號(hào)程序流程圖程序流程圖符號(hào)程序流程圖以求解sum=1+2+3+4+5……+（n-1）+n為例來介紹算法的流程圖描述方法程序流程圖以求解sum=1+2+3+4+5……+（n-1）+N-S流程圖N-S流程圖簡(jiǎn)稱N-S圖，也被稱為盒圖。N-S圖是在1973年，由美國(guó)學(xué)者I.Nassi和B.Shneiderman提出來的，并分別取兩人名字的首字母來進(jìn)行命名。N-S圖是在程序流程圖的基礎(chǔ)上去掉流程線，將全部算法寫在一個(gè)矩形框內(nèi)，在該框內(nèi)還可以包含其他的從屬于它的框的一種算法表示方法。即由一些基本的框組成的一個(gè)大框。N-S流程圖N-S流程圖簡(jiǎn)稱N-S圖，也被稱為盒圖。N-S圖N-S流程圖N-S流程圖的三大結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)N-S流程圖N-S流程圖的三大結(jié)構(gòu)N-S流程圖寫出求sum=1+2+3+4+5……+（n-1）+n的N-S圖的描述方法N-S流程圖寫出求sum=1+2+3+4+5……+（n-1）偽代碼用流程圖或N-S圖來描述算法雖然形象直觀，但在算法設(shè)計(jì)過程中使用起來并不十分方便，特別是當(dāng)算法稍微復(fù)雜一點(diǎn)時(shí)，不易修改。在實(shí)際的算法設(shè)計(jì)中，常常使用自然語言或計(jì)算機(jī)語言或類計(jì)算機(jī)語言來描述。這里的類計(jì)算機(jī)語言是一種非計(jì)算機(jī)語言，借用了一些高級(jí)語言的某些成分，沒有加入嚴(yán)格的規(guī)則，而且不能夠被計(jì)算機(jī)所接受，稱其為“偽代碼”。偽代碼用流程圖或N-S圖來描述算法雖然形象直觀，但在算法設(shè)計(jì)偽代碼寫出求sum=1+2+3+4+5……+（n-1）+n的偽代碼的描述方法(1)算法開始；(2)輸入n的值；(3)i←1；(4)sum←0；(5)dowhilei<=n(6){sum←sum+i；(7)

i←i+1；}(8)輸出sum的值；(9)算法結(jié)束；偽代碼寫出求sum=1+2+3+4+5……+（n-1）+n的5.2.3常用算法介紹1.枚舉法2.遞推法3.求最大值、最小值問題4.交換兩個(gè)變量的值5.排序算法6.查找算法5.2.3常用算法介紹1.枚舉法枚舉法又稱為窮舉法基本思想：根據(jù)題目的部分條件確定答案的大致范圍，然后在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，直到所有情況均通過驗(yàn)證。若某個(gè)情況符合題目條件，則為本題的一個(gè)答案；若全部情況驗(yàn)證完后均不符合題目的條件，則問題無解。特點(diǎn)：算法簡(jiǎn)單，容易理解，運(yùn)算量大1.枚舉法枚舉法又稱為窮舉法1.枚舉法1.枚舉法應(yīng)用：百錢買百雞問題假定公雞每只5元，母雞每只3元，小雞3只1元?，F(xiàn)有100元錢要求買100只雞，問共有幾種購(gòu)雞方案？問題分析：根據(jù)題目，設(shè)公雞、母雞、小雞各為x，y，z只，列出方程為： x+y+z=100 5x+3y+z/3=1001.枚舉法應(yīng)用：百錢買百雞問題巧妙和高效的算法很少來自于窮舉法，但基于以下因素，窮舉法仍是一種重要的算法設(shè)計(jì)策略：①窮舉法幾乎可以通用于任何領(lǐng)域的問題求解，可能是唯一一種解決所有問題的一般性方法②即使效率低下，仍可用窮舉法求解一些小規(guī)模的問題實(shí)例；③如果解決的問題實(shí)例不多，而窮舉法可用一種可接受的速度對(duì)問題求解，那么花時(shí)間去設(shè)計(jì)一個(gè)更高效地算法是得不償失的。

1.枚舉法[思考題]舉例說明生活中的窮舉法應(yīng)用。巧妙和高效的算法很少來自于窮舉法，但基于以下因素，窮舉法仍是遞推法又稱為迭代法基本思想：利用問題本身所具有的某種遞推關(guān)系求解問題。從初值出發(fā)，歸納出新值與舊值間存在的關(guān)系，從而把一個(gè)復(fù)雜的計(jì)算過程轉(zhuǎn)換為簡(jiǎn)單過程的多次重復(fù)，每次重復(fù)都從舊值的基礎(chǔ)上遞推出新值，并由新值代替舊值。2.遞推法遞推法又稱為迭代法2.遞推法2.遞推法

2.遞推法

基本思想：采用如同打擂臺(tái)的方法。在n個(gè)數(shù)中，先假設(shè)第一個(gè)數(shù)為最大值，稱為擂主，依次同第2，3，……，n個(gè)數(shù)據(jù)逐一比較，一旦某個(gè)數(shù)大，馬上替換擂主；所有值比較完，最大值也就獲得。求最小值問題則先假設(shè)第一個(gè)數(shù)為最小值。3.求最大值、最小值問題基本思想：采用如同打擂臺(tái)的方法。在n個(gè)數(shù)中，先假設(shè)第一個(gè)數(shù)為3.求最大值、最小值問題應(yīng)用：對(duì)輸入的若干個(gè)學(xué)生成績(jī)，求出最高分和最低分。max=min=a[0]；用max依次與后續(xù)的成績(jī)進(jìn)行對(duì)比，若比max大則將相應(yīng)值賦值給max；用min依次與后續(xù)的成績(jī)進(jìn)行對(duì)比，若比min小則將相應(yīng)值賦值給min；最后輸出max和min的值。3.求最大值、最小值問題應(yīng)用：對(duì)輸入的若干個(gè)學(xué)生成績(jī)，求出最基本思想：由于計(jì)算機(jī)內(nèi)存的特點(diǎn)，因此，計(jì)算機(jī)中交換兩個(gè)變量的值只能采取間接交換的方法。4.交換兩個(gè)變量的值基本思想：由于計(jì)算機(jī)內(nèi)存的特點(diǎn)，因此，計(jì)算機(jī)中交換兩個(gè)變量的4.交換兩個(gè)變量的值有黑和藍(lán)兩個(gè)墨水瓶，但卻把黑墨水裝在了藍(lán)墨水的瓶子里，而把藍(lán)墨水錯(cuò)裝在了黑墨水瓶子里，要求將其互換。4.交換兩個(gè)變量的值有黑和藍(lán)兩個(gè)墨水瓶，但卻把黑墨水裝在了藍(lán)4.交換兩個(gè)變量的值應(yīng)用：a=5,b=10，交換a，b的值并輸出引入一個(gè)新的變量c；將a的值賦值給c；將b的值賦值給a；將c的值賦值給b；4.交換兩個(gè)變量的值應(yīng)用：a=5,b=10，交換a，b的值選擇排序的基本思想：每一輪從待排序列中選取一個(gè)關(guān)鍵碼最小的記錄與第i個(gè)位置的記錄進(jìn)行交換，也即第一輪從n個(gè)記錄中選取關(guān)鍵碼最小的記錄與第1個(gè)位置的記錄交換，第二輪從剩下的n-1個(gè)記錄中選取關(guān)鍵碼最小的記錄與第2個(gè)位置的記錄進(jìn)行交換，直到整個(gè)序列的記錄選完5.排序算法選擇排序的基本思想：每一輪從待排序列中選取一個(gè)關(guān)鍵碼最小的記5.排序算法【例5.6】給出一組關(guān)鍵字(28，6，72，85，39，41，13，20)，排序后得到(6，13，20，28，39，41，72，85)，其選擇排序過程如下5.排序算法【例5.6】給出一組關(guān)鍵字(28，6，72，85查找是指從給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)給定的值。常用的查找算法有順序查找、二分查找等等。順序查找是直接從頭到尾搜索集合中滿足條件的值。二分查找是必須首先將集合按照降序或升序排序，然后利用折半技術(shù)搜索集合中滿足條件的值。6.查找算法查找是指從給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)給定的值。6.查找算法6.查找算法二分查找的方法如下：將x與線性表的中間項(xiàng)進(jìn)行比較；若中間項(xiàng)的值等于x，則說明查找到，查找結(jié)束；若x小于中間項(xiàng)的值，則在線性表的前半部分以相同的方法進(jìn)行查找。若x大于中間項(xiàng)的值，則在線性表的后半部分以相同的方法進(jìn)行查找。這個(gè)過程一直進(jìn)行到查找成功或子表長(zhǎng)度為0為止。6.查找算法二分查找的方法如下：【例5.7】有序表中關(guān)鍵字序列為3，10，13，17，40，43，50，70，要查找關(guān)鍵字值為43的數(shù)據(jù)元素6.查找算法【例5.7】有序表中關(guān)鍵字序列為3，10，13，17，40，5.3.1

軟件危機(jī)5.3.2

軟件工程5.3.3

軟件生存周期5.3軟件工程概述5.3.1軟件危機(jī)5.3軟件工程概述5.3.1軟件危機(jī)軟件危機(jī)是指在計(jì)算機(jī)軟件的開發(fā)和維護(hù)過程中所遇到的一系列嚴(yán)重問題，主要有以下一些表現(xiàn)形式。①軟件開發(fā)費(fèi)用和進(jìn)度失控。②軟件的可靠性差。③生產(chǎn)出來的軟件難以維護(hù)。④用戶對(duì)“已完成”的系統(tǒng)不滿意現(xiàn)象經(jīng)常發(fā)生。5.3.1軟件危機(jī)軟件危機(jī)是指在計(jì)算機(jī)軟件的開發(fā)和維護(hù)過程5.3.2軟件工程IEEE給出的軟件工程的定義是：軟件工程是將系統(tǒng)化的、規(guī)范的、可度量的方法應(yīng)用于軟件的開發(fā)、運(yùn)行、維護(hù)過程，即將工程化應(yīng)用于軟件中的方法的研究。人們給出的一般定義是：軟件工程是一門旨在生產(chǎn)無故障的、積極交付的、在預(yù)算之內(nèi)的和滿足用戶需求的軟件的學(xué)科。實(shí)質(zhì)上，軟件工程就是采用工程的概念、原理、技術(shù)和方法來開發(fā)與維護(hù)軟件，把經(jīng)過實(shí)踐考驗(yàn)而證明正確的管理方法和最先進(jìn)的軟件開發(fā)技術(shù)結(jié)合起來，應(yīng)用到軟件開發(fā)和維護(hù)過程中，來解決軟件危機(jī)問題。5.3.2軟件工程IEEE給出的軟件工程的定義是：軟件工程5.3.2軟件工程軟件工程包括三要素：方法、工具和過程。軟件工程的目標(biāo)是：在給定成本、進(jìn)度的前提下，開發(fā)出具有可修改性、有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性并且滿足用戶需求的軟件產(chǎn)品。追求這些目標(biāo)有助于提高軟件產(chǎn)品的質(zhì)量和開發(fā)效率，減少維護(hù)的困難軟件工程的原則：抽象、信息隱藏、模塊化、局部化、一致性、確定性、完備性和可驗(yàn)證性5.3.2軟件工程軟件工程包括三要素：方法、工具和過程。5.3.3軟件生存周期軟件定義期——“做什么”，確定工程的總目標(biāo)和可行性，導(dǎo)出實(shí)現(xiàn)工程目標(biāo)應(yīng)使用的策略及系統(tǒng)必須完成的功能，估計(jì)完成工程需要的資源和成本，制定進(jìn)度表。軟件開發(fā)期——“如何做”，具體設(shè)計(jì)和實(shí)現(xiàn)在前一個(gè)使其定義的軟件軟件維護(hù)期——“如何長(zhǎng)久的做”，使軟件持久地滿足用戶的需求。5.3.3軟件生存周期軟件定義期——“做什么”，確定工程的軟件過程模型定義：從軟件項(xiàng)目需求定義直至軟件運(yùn)行維護(hù)為止，跨越整個(gè)生存期的系統(tǒng)開發(fā)、運(yùn)作和維護(hù)所實(shí)施的全部過程、活動(dòng)和任務(wù)的結(jié)構(gòu)框架。常見的軟件過程模型：瀑布模型原型模型增量模型螺旋模型軟件過程模型定義：從軟件項(xiàng)目需求定義直至軟件運(yùn)行維護(hù)為止，跨瀑布模型（WaterfallModel）1970年提出，又稱線性模型，是歷史上第一個(gè)正式使用并得到業(yè)界廣泛認(rèn)可的軟件開發(fā)模型具體劃分：制定計(jì)劃、需求分析、軟件設(shè)計(jì)、程序編寫、軟件測(cè)試、運(yùn)行維護(hù)規(guī)定了自上而下、相互銜接的固定次序瀑布模型（WaterfallModel）1970年提出，又原型模型原型模型的基本思想是：原型模型從需求采集開始，如圖所示，然后是“快速設(shè)計(jì)”，集中于軟件中那些對(duì)用戶可見的部分的表示，并最終導(dǎo)致原型的創(chuàng)建。

原型模型原型模型的基本思想是：原型模型從需求采集開始，如圖所螺旋模型1988年由TRW公司的B.Boehm提出，將瀑布模型和演化模型結(jié)合，并強(qiáng)調(diào)了其他模型都忽略了的風(fēng)險(xiǎn)分析。螺旋模型1988年由TRW公司的B.Boehm提出，將瀑布模并發(fā)模型并發(fā)模型也稱并發(fā)工程，它表達(dá)了在軟件項(xiàng)目任一階段的活動(dòng)之間存在的并發(fā)性。并發(fā)模型并發(fā)模型也稱并發(fā)工程，它表達(dá)了在軟件項(xiàng)目任一階段的活基于構(gòu)件的開發(fā)模型基于構(gòu)件的開發(fā)（CBD）模型（如圖5.18所示）融合了螺旋模型的許多特征，本質(zhì)上是演化型的，要求軟件創(chuàng)建迭代過程，但是基于構(gòu)件的開發(fā)模型是利用預(yù)先封裝好的軟件構(gòu)件來構(gòu)造應(yīng)用的?；跇?gòu)件的開發(fā)模型基于構(gòu)件的開發(fā)（CBD）模型（如圖5.18小結(jié)程序設(shè)計(jì)的基本方法程序設(shè)計(jì)語言算法的表示方法常用的算法軟件工程軟件生存周期小結(jié)程序設(shè)計(jì)的基本方法5.1程序設(shè)計(jì)概述5.2算法概述5.3軟件工程概述第5章程序設(shè)計(jì)基礎(chǔ)5.1程序設(shè)計(jì)概述第5章程序設(shè)計(jì)基礎(chǔ)5.1.1

程序設(shè)計(jì)的基本過程5.1.2

程序設(shè)計(jì)的方法5.1.3

程序設(shè)計(jì)語言5.1程序設(shè)計(jì)概述5.1.1程序設(shè)計(jì)的基本過程5.1程序設(shè)計(jì)概述5.1.1程序設(shè)計(jì)的基本過程程序設(shè)計(jì)：編寫程序的過程程序設(shè)計(jì)過程包括分析、設(shè)計(jì)、編碼、測(cè)試、編寫文檔等不同階段5.1.1程序設(shè)計(jì)的基本過程程序設(shè)計(jì)：編寫程序的過程5.1.2程序設(shè)計(jì)的方法結(jié)構(gòu)化程序設(shè)計(jì)方法面向?qū)ο蟪绦蛟O(shè)計(jì)方法5.1.2程序設(shè)計(jì)的方法結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的原則自頂向下逐步細(xì)化模塊化限制使用goto語句結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的原則結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)順序結(jié)構(gòu)按照程序語句的書寫順序一條一條的執(zhí)行最基本、最常用的結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)順序結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)選擇結(jié)構(gòu)（分支結(jié)構(gòu)）根據(jù)設(shè)定的條件，判斷應(yīng)該執(zhí)行哪一條語句包括單分支結(jié)構(gòu)、雙分支結(jié)構(gòu)和多分支結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)選擇結(jié)構(gòu)（分支結(jié)構(gòu)）結(jié)構(gòu)化程序設(shè)計(jì)循環(huán)結(jié)構(gòu)（重復(fù)結(jié)構(gòu)）根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行相同的程序段分為當(dāng)型循環(huán)結(jié)構(gòu)和直到型循環(huán)結(jié)構(gòu)

結(jié)構(gòu)化程序設(shè)計(jì)循環(huán)結(jié)構(gòu)（重復(fù)結(jié)構(gòu)）面向?qū)ο蟪绦蛟O(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)又稱為面向過程的程序設(shè)計(jì)面向?qū)ο蟪绦蛟O(shè)計(jì)方法模擬人們理解和處理客觀世界的方式來分析問題，把系統(tǒng)視為一系列對(duì)象的集合，分析者、設(shè)計(jì)者和編程者都可以使用相同的概念，從而使面向?qū)ο蟮某绦蛟O(shè)計(jì)方法能比較自然地模擬客觀世界的活動(dòng)，使問題描述空間與解空間在結(jié)構(gòu)上盡可能一致。面向?qū)ο蟪绦蛟O(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)又稱為面向過程的程序設(shè)計(jì)面向?qū)ο蟮幕靖拍顚?duì)象：客觀世界中的任何實(shí)體，既可以是具體的物理實(shí)體的抽象，也可以是人為的概念，或者是任何有明確邊界和意義的東西。對(duì)象的特點(diǎn)：標(biāo)識(shí)唯一性分類型多態(tài)性封裝性模塊獨(dú)立性面向?qū)ο蟮幕靖拍顚?duì)象：客觀世界中的任何實(shí)體，既可以是具體的面向?qū)ο蟪绦蛟O(shè)計(jì)類：類是對(duì)象的抽象，它描述了該對(duì)象類型的所有對(duì)象的性質(zhì)，而一個(gè)對(duì)象則是其對(duì)應(yīng)類的一個(gè)實(shí)例消息面向?qū)ο蟮氖澜缡峭ㄟ^對(duì)象與對(duì)象間彼此的相互合作來推動(dòng)的，對(duì)象間的這種相互合作需要一個(gè)機(jī)制來協(xié)助完成，這種機(jī)制稱為“消息”面向?qū)ο蟪绦蛟O(shè)計(jì)類：面向?qū)ο蟪绦蛟O(shè)計(jì)繼承使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)已有的類可當(dāng)做基類來引用，新類可當(dāng)做派生類來引用繼承具有傳遞性面向?qū)ο蟪绦蛟O(shè)計(jì)繼承面向?qū)ο蟪绦蛟O(shè)計(jì)封裝性所謂封裝，指的就是類中定義的數(shù)據(jù)只能被類中定義的方法所訪問，除此之外別無它法封裝的結(jié)果實(shí)際上隱蔽了復(fù)雜性，并提供了代碼重用性，從而降低了軟件開發(fā)的難度。多態(tài)性對(duì)象根據(jù)所接收的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象接收時(shí)，可導(dǎo)致完全不同的行動(dòng)，該現(xiàn)象稱為多態(tài)性面向?qū)ο蟪绦蛟O(shè)計(jì)封裝性面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)：與人類習(xí)慣的思維方法一致穩(wěn)定性好可重用性好易于開發(fā)大型軟件產(chǎn)品可維護(hù)性好面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)：5.1.3程序設(shè)計(jì)語言程序設(shè)計(jì)語言就是用于書寫計(jì)算機(jī)程序的一組記號(hào)和一組規(guī)則。分類：機(jī)器語言匯編語言高級(jí)語言5.1.3程序設(shè)計(jì)語言程序設(shè)計(jì)語言就是用于書寫計(jì)算機(jī)程序的(1)機(jī)器語言

由0、1代碼組成，能被計(jì)算機(jī)硬件系統(tǒng)直接識(shí)別和執(zhí)行的計(jì)算機(jī)語言，不需要翻譯。特點(diǎn)：占用空間小、執(zhí)行速度快不易學(xué)習(xí)和修改不同類型機(jī)器的機(jī)器語言不同，通用性差程序設(shè)計(jì)語言(1)機(jī)器語言由0、1代碼組成，能被計(jì)算機(jī)硬件系統(tǒng)直機(jī)器語言程序注釋1011000000001000把8存放到累加器A中0010110000001010將10與累加器中的8相加，結(jié)果存在A中11110100程序結(jié)束機(jī)器語言實(shí)例機(jī)器語言程序注釋1011000000001000把8存放到(2)匯編語言（符號(hào)語言）程序設(shè)計(jì)語言

用助記符代替機(jī)器語言中的指令和數(shù)據(jù)特點(diǎn)：易修改，保持速度快，占用空間小不同類型機(jī)器的匯編語言不同，通用性差實(shí)例：8+10加法題MOVAX,8HMOVBX,0AHADDBX,AX(2)匯編語言（符號(hào)語言）程序設(shè)計(jì)語言用助記符代替機(jī)器語(3)高級(jí)語言程序設(shè)計(jì)語言

由貼近自然語言的“詞”和“數(shù)學(xué)公式”組成

特點(diǎn)：

易學(xué)、易讀，易修改通用性好，不依賴于機(jī)器具有很強(qiáng)的通用性和可移植性

實(shí)例：c=8+10(3)高級(jí)語言程序設(shè)計(jì)語言由貼近自然語言的“詞”和“常用的程序設(shè)計(jì)語言面向過程語言Fortran、Pascal、C等面向?qū)ο笳Z言C++、java常用的程序設(shè)計(jì)語言面向過程語言語言處理系統(tǒng)的作用就是把程序語言編寫的程序變換成計(jì)算機(jī)上執(zhí)行的程序分類匯編程序編譯程序解釋程序程序設(shè)計(jì)語言處理系統(tǒng)語言處理系統(tǒng)的作用就是把程序語言編寫的程序變換成計(jì)算機(jī)上執(zhí)行匯編語言源程序機(jī)器語言程序匯編程序

匯編程序程序設(shè)計(jì)語言處理系統(tǒng)匯編程序匯編程序程序設(shè)計(jì)語言處理系統(tǒng)高級(jí)語言源程序高級(jí)語言目標(biāo)源程序程序編譯程序連接程序可執(zhí)行程序計(jì)算結(jié)果數(shù)據(jù)解釋程序計(jì)算結(jié)果數(shù)據(jù)編譯程序：執(zhí)行速度快，但占用內(nèi)存多，可脫離編譯程序和源程序獨(dú)立存在并反復(fù)使用.如：C/C++、Pascal、FORTRAN等解釋程序：邊解釋邊執(zhí)行，便于查錯(cuò)，占用內(nèi)存少，執(zhí)行效率低、速度慢。如：BASIC語言程序設(shè)計(jì)語言處理系統(tǒng)編譯程序連接程序可執(zhí)行計(jì)算數(shù)據(jù)解釋程序計(jì)算數(shù)據(jù)編譯程序：執(zhí)行編譯程序與解釋程序的區(qū)別編譯程序與解釋程序的區(qū)別5.2.1

算法的概念5.2.2

算法的表示5.2.3

常用算法介紹5.2算法概述5.2.1算法的概念5.2算法概述算法算法(Algorithm)：算法就是一個(gè)有窮規(guī)則的集合，其中的規(guī)則確定了一個(gè)解決某一特定類型問題的運(yùn)算序列。5.2.1算法的概念算法5.2.1算法的概念算法的特性①有限性②確定性③可行性④輸入⑤輸出算法的特性①有限性算法的表示方法算法的表示方法：自然語言；程序流程圖；N-S流程圖；偽代碼；算法的表示方法算法的表示方法：自然語言使用自然語言描述求解sum=1+2+3+4+5……+（n-1）+n的方法。①確定一個(gè)n的值；②設(shè)等號(hào)右邊的算式項(xiàng)中的初始值i為1；③設(shè)sum的初始值為0；④如果i≤n時(shí)，執(zhí)行⑤，否則轉(zhuǎn)出執(zhí)行⑧；⑤計(jì)算sum加上i的值后，重新賦值給sum；⑥計(jì)算i加1，然后將值重新賦值給i；⑦轉(zhuǎn)去執(zhí)行④；⑧輸出sum的值，算法結(jié)束。自然語言使用自然語言描述求解sum=1+2+3+4+5……+自然語言自然語言描述方法的缺點(diǎn)：自言語言的歧異性容易導(dǎo)致算法執(zhí)行的不確定性。自然語言的語句一般太長(zhǎng)，從而導(dǎo)致了用自然語言描述的算法太長(zhǎng)。由于自然語言表示的串行性，因此，當(dāng)一個(gè)算法中循環(huán)和分支較多時(shí)就很難清晰地表示出來。自然語言表示的算法不便翻譯成計(jì)算機(jī)程序設(shè)計(jì)語言理解的語言。自然語言自然語言描述方法的缺點(diǎn)：程序流程圖程序流程圖符號(hào)程序流程圖程序流程圖符號(hào)程序流程圖以求解sum=1+2+3+4+5……+（n-1）+n為例來介紹算法的流程圖描述方法程序流程圖以求解sum=1+2+3+4+5……+（n-1）+N-S流程圖N-S流程圖簡(jiǎn)稱N-S圖，也被稱為盒圖。N-S圖是在1973年，由美國(guó)學(xué)者I.Nassi和B.Shneiderman提出來的，并分別取兩人名字的首字母來進(jìn)行命名。N-S圖是在程序流程圖的基礎(chǔ)上去掉流程線，將全部算法寫在一個(gè)矩形框內(nèi)，在該框內(nèi)還可以包含其他的從屬于它的框的一種算法表示方法。即由一些基本的框組成的一個(gè)大框。N-S流程圖N-S流程圖簡(jiǎn)稱N-S圖，也被稱為盒圖。N-S圖N-S流程圖N-S流程圖的三大結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)N-S流程圖N-S流程圖的三大結(jié)構(gòu)N-S流程圖寫出求sum=1+2+3+4+5……+（n-1）+n的N-S圖的描述方法N-S流程圖寫出求sum=1+2+3+4+5……+（n-1）偽代碼用流程圖或N-S圖來描述算法雖然形象直觀，但在算法設(shè)計(jì)過程中使用起來并不十分方便，特別是當(dāng)算法稍微復(fù)雜一點(diǎn)時(shí)，不易修改。在實(shí)際的算法設(shè)計(jì)中，常常使用自然語言或計(jì)算機(jī)語言或類計(jì)算機(jī)語言來描述。這里的類計(jì)算機(jī)語言是一種非計(jì)算機(jī)語言，借用了一些高級(jí)語言的某些成分，沒有加入嚴(yán)格的規(guī)則，而且不能夠被計(jì)算機(jī)所接受，稱其為“偽代碼”。偽代碼用流程圖或N-S圖來描述算法雖然形象直觀，但在算法設(shè)計(jì)偽代碼寫出求sum=1+2+3+4+5……+（n-1）+n的偽代碼的描述方法(1)算法開始；(2)輸入n的值；(3)i←1；(4)sum←0；(5)dowhilei<=n(6){sum←sum+i；(7)

i←i+1；}(8)輸出sum的值；(9)算法結(jié)束；偽代碼寫出求sum=1+2+3+4+5……+（n-1）+n的5.2.3常用算法介紹1.枚舉法2.遞推法3.求最大值、最小值問題4.交換兩個(gè)變量的值5.排序算法6.查找算法5.2.3常用算法介紹1.枚舉法枚舉法又稱為窮舉法基本思想：根據(jù)題目的部分條件確定答案的大致范圍，然后在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，直到所有情況均通過驗(yàn)證。若某個(gè)情況符合題目條件，則為本題的一個(gè)答案；若全部情況驗(yàn)證完后均不符合題目的條件，則問題無解。特點(diǎn)：算法簡(jiǎn)單，容易理解，運(yùn)算量大1.枚舉法枚舉法又稱為窮舉法1.枚舉法1.枚舉法應(yīng)用：百錢買百雞問題假定公雞每只5元，母雞每只3元，小雞3只1元?，F(xiàn)有100元錢要求買100只雞，問共有幾種購(gòu)雞方案？問題分析：根據(jù)題目，設(shè)公雞、母雞、小雞各為x，y，z只，列出方程為： x+y+z=100 5x+3y+z/3=1001.枚舉法應(yīng)用：百錢買百雞問題巧妙和高效的算法很少來自于窮舉法，但基于以下因素，窮舉法仍是一種重要的算法設(shè)計(jì)策略：①窮舉法幾乎可以通用于任何領(lǐng)域的問題求解，可能是唯一一種解決所有問題的一般性方法②即使效率低下，仍可用窮舉法求解一些小規(guī)模的問題實(shí)例；③如果解決的問題實(shí)例不多，而窮舉法可用一種可接受的速度對(duì)問題求解，那么花時(shí)間去設(shè)計(jì)一個(gè)更高效地算法是得不償失的。

1.枚舉法[思考題]舉例說明生活中的窮舉法應(yīng)用。巧妙和高效的算法很少來自于窮舉法，但基于以下因素，窮舉法仍是遞推法又稱為迭代法基本思想：利用問題本身所具有的某種遞推關(guān)系求解問題。從初值出發(fā)，歸納出新值與舊值間存在的關(guān)系，從而把一個(gè)復(fù)雜的計(jì)算過程轉(zhuǎn)換為簡(jiǎn)單過程的多次重復(fù)，每次重復(fù)都從舊值的基礎(chǔ)上遞推出新值，并由新值代替舊值。2.遞推法遞推法又稱為迭代法2.遞推法2.遞推法

2.遞推法

基本思想：采用如同打擂臺(tái)的方法。在n個(gè)數(shù)中，先假設(shè)第一個(gè)數(shù)為最大值，稱為擂主，依次同第2，3，……，n個(gè)數(shù)據(jù)逐一比較，一旦某個(gè)數(shù)大，馬上替換擂主；所有值比較完，最大值也就獲得。求最小值問題則先假設(shè)第一個(gè)數(shù)為最小值。3.求最大值、最小值問題基本思想：采用如同打擂臺(tái)的方法。在n個(gè)數(shù)中，先假設(shè)第一個(gè)數(shù)為3.求最大值、最小值問題應(yīng)用：對(duì)輸入的若干個(gè)學(xué)生成績(jī)，求出最高分和最低分。max=min=a[0]；用max依次與后續(xù)的成績(jī)進(jìn)行對(duì)比，若比max大則將相應(yīng)值賦值給max；用min依次與后續(xù)的成績(jī)進(jìn)行對(duì)比，若比min小則將相應(yīng)值賦值給min；最后輸出max和min的值。3.求最大值、最小值問題應(yīng)用：對(duì)輸入的若干個(gè)學(xué)生成績(jī)，求出最基本思想：由于計(jì)算機(jī)內(nèi)存的特點(diǎn)，因此，計(jì)算機(jī)中交換兩個(gè)變量的值只能采取間接交換的方法。4.交換兩個(gè)變量的值基本思想：由于計(jì)算機(jī)內(nèi)存的特點(diǎn)，因此，計(jì)算機(jī)中交換兩個(gè)變量的4.交換兩個(gè)變量的值有黑和藍(lán)兩個(gè)墨水瓶，但卻把黑墨水裝在了藍(lán)墨水的瓶子里，而把藍(lán)墨水錯(cuò)裝在了黑墨水瓶子里，要求將其互換。4.交換兩個(gè)變量的值有黑和藍(lán)兩個(gè)墨水瓶，但卻把黑墨水裝在了藍(lán)4.交換兩個(gè)變量的值應(yīng)用：a=5,b=10，交換a，b的值并輸出引入一個(gè)新的變量c；將a的值賦值給c；將b的值賦值給a；將c的值賦值給b；4.交換兩個(gè)變量的值應(yīng)用：a=5,b=10，交換a，b的值選擇排序的基本思想：每一輪從待排序列中選取一個(gè)關(guān)鍵碼最小的記錄與第i個(gè)位置的記錄進(jìn)行交換，也即第一輪從n個(gè)記錄中選取關(guān)鍵碼最小的記錄與第1個(gè)位置的記錄交換，第二輪從剩下的n-1個(gè)記錄中選取關(guān)鍵碼最小的記錄與第2個(gè)位置的記錄進(jìn)行交換，直到整個(gè)序列的記錄選完5.排序算法選擇排序的基本思想：每一輪從待排序列中選取一個(gè)關(guān)鍵碼最小的記5.排序算法【例5.6】給出一組關(guān)鍵字(28，6，72，85，39，41，13，20)，排序后得到(6，13，20，28，39，41，72，85)，其選擇排序過程如下5.排序算法【例5.6】給出一組關(guān)鍵字(28，6，72，85查找是指從給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)給定的值。常用的查找算法有順序查找、二分查找等等。順序查找是直接從頭到尾搜索集合中滿足條件的值。二分查找是必須首先將集合按照降序或升序排序，然后利用折半技術(shù)搜索集合中滿足條件的值。6.查找算法查找是指從給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)給定的值。6.查找算法6.查找算法二分查找的方法如下：將x與線性表的中間項(xiàng)進(jìn)行比較；若中間項(xiàng)的值等于x，則說明查找到，查找結(jié)束；若x小于中間項(xiàng)的值，則在線性表的前半部分以相同的方法進(jìn)行查找。若x大于中間項(xiàng)的值，則在線性表的后半部分以相同的方法進(jìn)行查找。這個(gè)過程一直進(jìn)行到查找成功或子表長(zhǎng)度為0為止。6.查找算法二分查找的方法如下：【例5.7】有序表中關(guān)鍵字序列為3，10，13，17，40，43，50，70，要查找關(guān)鍵字值為43的數(shù)據(jù)元素6.查找算法【例5.7】有序表中關(guān)鍵字序列為3，10，13，17，40，5.3.1

軟件危機(jī)5.3.2

軟件工程5.3.3

軟件生存周