1、2022-3-8第六章第六章 程序編碼程序編碼 編碼的目的 是使用選定的程序設(shè)計(jì)語言，把模塊的過程性描述翻譯為用該語言書寫的源程序（源代碼）模塊的過程性描述 (不可執(zhí)行的) 源程序(可執(zhí)行的)編碼6.1 編碼的目的2022-3-8清晰性效率開發(fā)時(shí)間程序輸出內(nèi)存數(shù)語句數(shù)程序可讀性最佳輸出可讀性最佳占內(nèi)存最小語句數(shù)最少開發(fā)時(shí)間最短1-21-245321433351243521442-352-31編碼要求結(jié)果 名次評(píng)判 項(xiàng)目Winberg 的程序?qū)嶒?yàn)結(jié)果2022-3-8 結(jié)構(gòu)化程序設(shè)計(jì)是一種設(shè)計(jì)程序的技術(shù)，它采用自頂向下逐步細(xì)化的設(shè)計(jì)方法和單入口(Single entry)單出口（Single ex

2、it）的控制結(jié)構(gòu)。 這種控制結(jié)構(gòu)包括有： 順序、選擇和循環(huán)。 6.2 結(jié)構(gòu)化程序設(shè)計(jì) （Structured Programming）2022-3-8 for(a=1,b=1;a=20) break; if (b%3=1) b+=3; continue; b-=5; a=20b%3=1 b+=3 a+ b-=5TFFT a=0,b=1單入口 M1單出口2022-3-8ABA,B,CBCAC打印BFTFTTF打印C打印A If (A.LT.B) goto 120 If (B.LT.C) goto 110100 write(6,*) C goto 140 110 write(6,*) B goto

3、 140 120 If(A.LT.C) goto 130 goto 100 130 write(6,*) A 140 continue - 單入口多出口結(jié)構(gòu) M22022-3-8無節(jié)制地使用了GOTO語句所產(chǎn)生的程序流程 M 2022-3-8 一、結(jié)構(gòu)化程序設(shè)計(jì)的原則1 1、使用語言中的順序、選擇、重復(fù)等有限的基本控制結(jié)構(gòu)表示程序2、選用的控制結(jié)構(gòu)只準(zhǔn)許有一個(gè)入口和一個(gè)出口 3、程序語句組成容易識(shí)別的塊（Block）,每塊只有一個(gè)入口和一個(gè) 出口4、復(fù)雜結(jié)構(gòu)應(yīng)該用基本控制結(jié)構(gòu)進(jìn)行組合嵌套來實(shí)現(xiàn) 5、嚴(yán)格控制GOTO語句2022-3-8 F0=F(a); F1=F(b); if(F0*F1=0)

4、 X0=a; X1=b; for(i=1;i=n;i+) Xm=(X0+X1)/2; Fm=F(Xm); if(abs(Fm)eps|abs(X1-X0)0) X0=Xm; F0=Fm; else X1=Xm; finish: printf(“%dn”,Xm); 2022-3-8Begin(F0*F1)0 X0=Xm X1=Xm F0=Fm TTXmFTFF F0=F(a) F1=F(b)11End22 i=n Q=abs(Fm)eps|abs(X1-X0)eps)2022-3-8 F0=F(a); F1=F(b); if(F0*F1=0) X0=a; X1=b; for(i=1;i=n;i+

5、) Xm=(X0+X1)/2; Fm=F(Xm); if(abs(Fm)eps|abs(X1-X0)0) X0=Xm; F0=Fm; else X1=Xm; printf(“%dn”,Xm); 2022-3-8 F0=F(a); F1=F(b); if(F0*F1=0) X0=a; X1=b; i=1; finish=0; while(i=n & finish=0) Xm=(X0+X1)/2; Fm=F(Xm); if(abs(Fm)eps|abs(X1-X0)0) X0=Xm; F0=Fm; else X1=Xm; i+; printf(“%dn”,Xm); 2022-3-8二、程序

6、設(shè)計(jì)自頂向下，逐步求精1、程序設(shè)計(jì)是一個(gè)由粗到細(xì)的 “漸進(jìn)” 的過程 2、程序設(shè)計(jì)不僅包括對(duì)控制結(jié)構(gòu)的設(shè)計(jì)，也包括對(duì)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。 二者都要一步一步地細(xì)化。 采用逐步細(xì)化方法設(shè)計(jì)程序的步驟列出問題的初步解分解主要問題繼續(xù)細(xì)化利用圖形工具或偽代碼描述程序的詳細(xì)邏輯2022-3-8用逐步細(xì)化方法設(shè)計(jì)一個(gè)程序，其功能為“從一組數(shù)中找出最大的數(shù) ” 第一步：列出問題的初步解1：輸入一組數(shù)2：找出其中最大的數(shù)3：輸出最大的數(shù)2022-3-8第二步：分解主要問題2.1：首先讀入一個(gè)數(shù)并設(shè)其為最大的數(shù)2.2：將該數(shù)逐次與其它數(shù)進(jìn)行比較2.3：若有大于該數(shù)的則將其保存2022-3-8第三步：確定數(shù)據(jù)結(jié)構(gòu)3.

7、1：定義一數(shù)組 A3.2：max=A(1)3.3：從A(2)至A(n)開始比較3.4：若當(dāng)前數(shù)大于max, 則令：max=A(i)2022-3-8第四步：用PDL描述Input array ASet Max=A(1)DO for i=2 to N IF MaxA(i) Set Max=A(i) ENDIFENDDOPrint Max2022-3-8 請(qǐng)用逐步細(xì)化方法設(shè)計(jì)一由下列描述的程序結(jié)構(gòu) 讀入一段任意長(zhǎng)度的英語課文，將其分解為單字，然后輸出一張單詞表(list of words),并指出每種單詞在課文中的出現(xiàn)次數(shù)。2022-3-8三、程序復(fù)雜性的度量 程序復(fù)雜性主要是指模塊內(nèi)部程序的復(fù)雜性

8、。它 直接關(guān)系到軟件開發(fā)費(fèi)用的多少，開發(fā)周期的長(zhǎng)短和 軟件和軟件內(nèi)部潛伏錯(cuò)誤的多少。同時(shí)它也是軟件可 理解性的另一種度量。2022-3-8 它可以用來計(jì)算任何一個(gè)程序的復(fù)雜性； 對(duì)于不合理的程序，例如對(duì)于長(zhǎng)度動(dòng)態(tài)增長(zhǎng)的程序， 或者對(duì)于原則上無法排錯(cuò)的程序，不應(yīng)當(dāng)使用它進(jìn)行 復(fù)雜性計(jì)算；為了度量程序復(fù)雜性，要求復(fù)雜性度量應(yīng)滿足以下假設(shè)：2022-3-8 如果設(shè)每行代碼的出錯(cuò)率為每100行源程序中可能的錯(cuò)誤數(shù)目。例如，每行代碼的出錯(cuò)率為 1%，也就是說，每 100 行源程序中就可能有一個(gè)錯(cuò)誤。 1、代碼行度量法 ：統(tǒng)計(jì)程序中的源代碼的行數(shù)較小的程序 -1.3%1.8%/行較大的程序 -2.7%3.

9、2%/行2022-3-8 該方法是利用程序模塊的程序圖中環(huán)路的個(gè)數(shù)，來計(jì)算程序的復(fù)雜性的。為此，該方法也稱為環(huán)路復(fù)雜度計(jì)算法。 2、McCabe 度量法利用程序的控制流來度量程序的復(fù)雜性 它是一種退化了的程序流程圖。即:把程序流程圖中每個(gè)處理符號(hào)都退化成一個(gè)結(jié)點(diǎn)，而原來流程圖中的流程線，則變成連接不同結(jié)點(diǎn)的有向弧。2022-3-8(1)程序圖符號(hào)2022-3-82022-3-8TC1C2CABED(2)從流程圖導(dǎo)出程序圖 A開始C1BCED結(jié)束C2TF2022-3-8(3)環(huán)路復(fù)雜性的計(jì)算方法 V(G)=m-n+2p 說明： V(G) 是有向圖G中環(huán)路數(shù)； m: 為圖G中弧數(shù)； n: 為圖G中

10、節(jié)點(diǎn)數(shù)； p: 為圖G中強(qiáng)連通分量個(gè)數(shù)； A B C D E F G H K L I McCabe 的環(huán)路復(fù)雜性度量值為 42022-3-8請(qǐng)將右側(cè)給出的程序流程圖轉(zhuǎn)換為程序圖并計(jì)算其環(huán)路值。a=20b%3=1 b+=3 a+ b-=5TFFT a=0,b=12022-3-8 程序的環(huán)路復(fù)雜度則取決于程序控制流的復(fù)雜度，也就 是取決于程序結(jié)構(gòu)的復(fù)雜程度。當(dāng)程序內(nèi)分支或循環(huán)個(gè)數(shù)增 加時(shí)，則相應(yīng)地環(huán)域復(fù)雜度也隨之增加。因此，它是對(duì)測(cè)試 難度的一種定量度量，也能對(duì)軟件最終的可靠性給出某種預(yù) 測(cè)。(4)、環(huán)路復(fù)雜度的用途2022-3-8 請(qǐng)用程序流程圖描述下列問題的算法，再將其轉(zhuǎn)換為程序圖并計(jì)算其環(huán)路

11、值。 請(qǐng)定義一個(gè)數(shù)組 ，要求找出數(shù)組中最大數(shù)和最小 數(shù)，并把最大數(shù)和 中的數(shù)對(duì)調(diào)、最小數(shù)和 中的數(shù)對(duì)調(diào)。 2022-3-8 請(qǐng)畫出下列偽代碼程序的流程圖、程序圖并計(jì)算它的環(huán)路復(fù)雜度。 LOOP : Do While Z0 A=A+1 IF A10 THEN X=A ELSE Y=Z END IF IF Y0 THEN PRINT G E LSE PRINT K END IF STOP 2022-3-8四、程序效率 程序效率是指程序的執(zhí)行速度及程序占用的存儲(chǔ)空間。程序編碼是最后提高運(yùn)行速度和節(jié)省存儲(chǔ)機(jī)會(huì)，因此在此階段不能不考慮程序的效率。2022-3-81、算法對(duì)效率的影響源程序的效率與詳細(xì)設(shè)計(jì)

12、階段確定的算法的效率有著直接的關(guān)系。當(dāng)我們把詳細(xì)設(shè)計(jì)翻譯并轉(zhuǎn)換成源代碼之后，那么算法效率就會(huì)反映為程序的執(zhí)行速度和存儲(chǔ)容量的要求2022-3-8（1）在編程序前，盡可能化簡(jiǎn)有關(guān)的算術(shù)表達(dá)式和邏輯表達(dá)式（2）仔細(xì)檢查算法中的嵌套的循環(huán)，盡可能將某些語句或表達(dá) 式移到循環(huán)外面（3）盡量避免使用多維數(shù)組（4）盡量避免使用指針和復(fù)雜的表（5）不要混淆數(shù)據(jù)類型，避免在表達(dá)式中出現(xiàn)類型混雜（6）盡量采用整數(shù)算術(shù)表達(dá)式和布爾表達(dá)式（7）選用等效的高效率算法轉(zhuǎn)換過程中的指導(dǎo)原則是：2022-3-8請(qǐng)?jiān)O(shè)計(jì)求解下列問題的算法2022-3-8 (i+1) (j+2) 20 3 i=1 j=1 內(nèi)循環(huán)次數(shù) 20*4=

13、80 外循環(huán)次數(shù) 21 總循環(huán)次數(shù) 101 2022-3-8應(yīng)把變化范圍大的循環(huán)變量放在內(nèi)層。 內(nèi)循環(huán)次數(shù) 3*21=63 外循環(huán)次數(shù) 4 總循環(huán)次數(shù) 672022-3-8 j+2 共計(jì)執(zhí)行了 3*20=60次 重復(fù)執(zhí)行57次2022-3-8 j+2 共計(jì)執(zhí)行了 3次 減少了57次應(yīng)盡量把與循環(huán)變量無關(guān)的運(yùn)算移到循環(huán)外去。2022-3-8 i+1 共計(jì)執(zhí)行了 60+60=120次 2022-3-8 i+1 共計(jì)執(zhí)行了 60次 2022-3-8 從鍵盤輸入 10個(gè)整數(shù)，要求按有小到大的順序?qū)⑺鼈冚敵觥?請(qǐng)采用比較交換法和選擇法對(duì)上述10條數(shù)據(jù)進(jìn)行排序，然后分別對(duì)這兩種方法進(jìn)行比較，并從程序的運(yùn)行

14、了效率的角度對(duì)兩個(gè)程序進(jìn)行比較。2022-3-82022-3-82022-3-8五、程序設(shè)計(jì)風(fēng)格 Coding style 1、保持控制流的直線性 (1)、對(duì)多入口和多出口的控制結(jié)構(gòu) 要作適當(dāng)?shù)奶幚硪鬟m當(dāng)?shù)奶幚?C1S1S2C2SnTT多入口循環(huán)結(jié)構(gòu)多入口循環(huán)結(jié)構(gòu)2022-3-8C1S1C2SnTTS2S2改進(jìn)后的循環(huán)結(jié)構(gòu)改進(jìn)后的循環(huán)結(jié)構(gòu)重復(fù)環(huán)節(jié)法2022-3-8多出口循環(huán)結(jié)構(gòu)多出口循環(huán)結(jié)構(gòu)C1S2TTC2S12022-3-8經(jīng)過處理后的單出口循環(huán)結(jié)構(gòu)C1 and C2S2TC1S1SnT邏輯分析法2022-3-8 while (C1) do Begin S1 If C2 then goto

15、 10 else S2End 10 Sn EXIT:=false while (C1 and (not EXIT) do Begin S1 If then EXIT:=true else S2 End 10 Sn 標(biāo)志變量法標(biāo)志變量2022-3-8使用 Ture Basic 語言中的專用語句退出循環(huán)上面程序的功能是：從鍵盤輸入一個(gè)數(shù)，并累加到總和中。當(dāng)總和超過1000或輸入為 0時(shí)則停止輸入，并打印出總和。2022-3-8if (N=0) then if (N能被能被2整除）整除）then print “正偶數(shù)正偶數(shù)” else print “負(fù)數(shù)負(fù)數(shù)” 導(dǎo)致二義性的 then-if 結(jié)構(gòu)(2

16、)、避免使用模糊或費(fèi)解的結(jié)構(gòu) if (N0) then print “負(fù)數(shù)負(fù)數(shù)” else if (N能被能被2整除）整除） then print “正偶數(shù)正偶數(shù)” 2022-3-8 While C1 If C2 then While C3 If C4 then Repeat S Until C5 Loop Loop . 費(fèi)解的 深層嵌套 結(jié)構(gòu)嵌套層最好不要超過 層2022-3-8 二、保持控制流的局部性 局部性是程序設(shè)計(jì)的一條準(zhǔn)則。像應(yīng)用甚廣的 模塊化設(shè)計(jì)，可看成是局部化原理在總體設(shè)計(jì)中的 具體體現(xiàn)。其實(shí)，在編碼時(shí)也要遵守局部化的原則 ，這就是保持控制流的局部性，其目的不僅是為了 提高程序的

17、清晰度，也有利于防止錯(cuò)誤的擴(kuò)散，提 高程序的可修改性。 2022-3-8 1、GOTO 語句的使用準(zhǔn)則 向前不向后的規(guī)則 2022-3-8 goto的目的地最好在同一控制結(jié)構(gòu)內(nèi)部，或者離本結(jié)構(gòu)出口相近的地方。2022-3-8TTTF 2、GOTO 語句的常見用法 請(qǐng)將右側(cè)的具有多個(gè)循環(huán)出口的結(jié)構(gòu)改寫為單出口結(jié)構(gòu)2022-3-8TTTF(用GOTO語句提前退出循環(huán)) 方法一:EXIT2=false; EXIT3=false; while(C1) and (not (EXIT2) and (not( EXIT3) do begin if C2 then EXIT2:=true; if C3 the

18、n EXIT3:=true; end if(EXIT2) then goto 20; if(EXIT3) then goto 30; goto 40; 20: C2為真時(shí)執(zhí)行的語句 gotot 40; 30: C3為真時(shí)的語句 40: Sn 后續(xù)語句標(biāo)志變量2022-3-8 while C1 do begin if C2 then goto 20; if C3 then goto 30; end goto 40; 20: 從e2退出前執(zhí)行的語句 gotot 40; 30: e3 退出前執(zhí)行的語句 40: Sn 后續(xù)語句 (用GOTO語句提前退出循環(huán)) 方法二:2022-3-8IF (X .LT. Y) GOTO 30IF (Y .LT. Z) GOTO 50SMALL=Z GOTO 70 30 IF (X .LT. Z ) GOTO 60 SMALL=Z GOTO 70 50 SMALL=Y GOTO 70 60 SMALL=X 70 CONTINUE 請(qǐng)將右側(cè)用FORTRAN語言編寫的源程序改用C語言編寫,要求程序的清晰度要好small=x; if (ysmall) sma