使用環(huán)形復(fù)雜度度量程序的復(fù)雜程度課件

第6章詳細(xì)設(shè)計第6章詳細(xì)設(shè)計1主要內(nèi)容6.1結(jié)構(gòu)程序設(shè)計6.2人機(jī)界面設(shè)計6.3過程設(shè)計的工具6.4面向數(shù)據(jù)結(jié)構(gòu)的設(shè)計方法6.5程序復(fù)雜程度的定量度量主要內(nèi)容6.1結(jié)構(gòu)程序設(shè)計2目的與要求一般了解：Jackson程序設(shè)計方法；Warnier程序設(shè)計方法?；菊莆眨菏褂铆h(huán)形復(fù)雜度度量程序的復(fù)雜程度，結(jié)構(gòu)化程序設(shè)計方法的特點(diǎn)。重點(diǎn)掌握：詳細(xì)設(shè)計的任務(wù)；用流程框圖、NS圖、PAD圖、判定表和判定樹以及PDL語言描述算法。目的與要求一般了解：Jackson程序設(shè)計方法；Warn3重點(diǎn)與難點(diǎn)流程框圖、NS圖、PAD圖、判定表和判定樹以及PDL語言描述算法。環(huán)形復(fù)雜度的度量。重點(diǎn)與難點(diǎn)流程框圖、NS圖、PAD圖、判定表和判定樹以及PD4目標(biāo)：確定如何具體實現(xiàn)所要求的系統(tǒng)。不是具體編寫程序，而是設(shè)計程序的“藍(lán)圖”。詳細(xì)設(shè)計的結(jié)果決定最終程序代碼的質(zhì)量。目標(biāo)：確定如何具體實現(xiàn)所要求的系統(tǒng)。5E.W.Dijkstra最早提出結(jié)構(gòu)程序設(shè)計：程序質(zhì)量與程序中包含的Goto語句的數(shù)量成反比（1965）。1966，Bohm,Jacopini，證明了只用“順序”、“選擇”、“循環(huán)”控制結(jié)構(gòu)就能實現(xiàn)任何單入口單出口程序。6.1結(jié)構(gòu)程序設(shè)計E.W.Dijkstra最早提出結(jié)構(gòu)程序6理論上，最基本的控制結(jié)構(gòu)只有兩種：順序、循環(huán)結(jié)構(gòu)（選擇結(jié)構(gòu)可由其兩者構(gòu)造）。

學(xué)界認(rèn)識到，不是簡單去掉Goto語句的問題，而是要創(chuàng)立一種新的程序設(shè)計方法。

——結(jié)構(gòu)化程序設(shè)計（IBM率先成功運(yùn)用）。理論上，最基本的控制結(jié)構(gòu)只有兩種：順序、循環(huán)7結(jié)構(gòu)程序設(shè)計：一種設(shè)計程序的技術(shù)，它采用自頂向下逐步求精的設(shè)計方法和單入口單出口的控制結(jié)構(gòu)。

結(jié)構(gòu)程序設(shè)計：8使用結(jié)構(gòu)程序設(shè)計技術(shù)的好處：1）提高軟件開發(fā)工程的成功率和生產(chǎn)率；2）系統(tǒng)有清晰的層次結(jié)構(gòu)，容易閱讀理解；3）單入口單出口的控制結(jié)構(gòu)，容易診斷糾正；4）模塊化可以使得軟件可以重用；5）程序邏輯結(jié)構(gòu)清晰，有利于程序正確性證明。使用結(jié)構(gòu)程序設(shè)計技術(shù)的好處：9經(jīng)典的結(jié)構(gòu)程序設(shè)計：只允許使用順序、IF_THEN_ELSE選擇和DO_WHILE循環(huán)；擴(kuò)展的結(jié)構(gòu)程序設(shè)計：除了三種基本控制結(jié)構(gòu)，還使用DO_CASE和DO_UNTIL循環(huán)；修正的結(jié)構(gòu)程序設(shè)計：除了三種基本控制結(jié)構(gòu)和兩種擴(kuò)充結(jié)構(gòu)，還使用BREAK等結(jié)構(gòu)。經(jīng)典的結(jié)構(gòu)程序設(shè)計：只允許使用順序、IF_THEN_ELSE101）順序結(jié)構(gòu)：相當(dāng)于“A、B”2.三種基本控制結(jié)構(gòu)AB(a)順序結(jié)構(gòu)1）順序結(jié)構(gòu)：相當(dāng)于“A、B”2.三種基本控制結(jié)構(gòu)AB112）選擇結(jié)構(gòu)相當(dāng)于“IfexpthenAelseBendif”ABexp(b)選擇結(jié)構(gòu)2）選擇結(jié)構(gòu)ABexp(b)選擇結(jié)構(gòu)123）循環(huán)結(jié)構(gòu)：相當(dāng)于“WhileexpdoA”A(c)循環(huán)結(jié)構(gòu)exp3）循環(huán)結(jié)構(gòu)：相當(dāng)于“WhileexpdoA”131）多分支結(jié)構(gòu)相當(dāng)于“CaseIofI=1:C1;I=2:C2;I=3:C3;…;I=n:Cn”3.擴(kuò)充兩種控制結(jié)構(gòu)

CnC3C1C2(d)多分支結(jié)構(gòu)I=?…1）多分支結(jié)構(gòu)3.擴(kuò)充兩種控制結(jié)構(gòu)CnC3C1C2(d)142）UNTIL循環(huán)結(jié)構(gòu)相當(dāng)于“RepeatAUntilexp”A(e)UNTIL循環(huán)exp2）UNTIL循環(huán)結(jié)構(gòu)A(e)UNTIL循環(huán)exp156.2人機(jī)界面設(shè)計6.2.1設(shè)計問題1.系統(tǒng)響應(yīng)時間；2.用戶幫助；3.出錯信息處理；4.命令交互6.2人機(jī)界面設(shè)計6.2.1設(shè)計問題166.2.2設(shè)計過程6.2.3人機(jī)界面設(shè)計指南1.一般交互指南；2.信息顯示指南；3.數(shù)據(jù)輸入指南。6.2.2設(shè)計過程176.3過程設(shè)計的工具6.3.1程序流程圖

程序流程圖：是一種描述程序的控制結(jié)構(gòu)流程和指令執(zhí)行情況的有向圖。歷史悠久、使用廣泛、直觀描繪控制流程、便于初學(xué)者掌握。6.3過程設(shè)計的工具6.3.1程序流程圖程18

程序流程圖的標(biāo)準(zhǔn)符號

程序流程圖的標(biāo)準(zhǔn)符號19使用環(huán)形復(fù)雜度度量程序的復(fù)雜程度ppt課件20

示例示例21ASP檢索程序流程圖：開始加載Include文件定義記數(shù)變量、作物變量創(chuàng)建數(shù)據(jù)庫鏈接對象、記錄集對象打開數(shù)據(jù)庫用客戶提交的值對作物變量賦值SQL查詢語句賦值通過記錄集對象打開SQL語句設(shè)定的記錄記錄集末端？記數(shù)變量加1，輸出記錄字段值及圖像轉(zhuǎn)跳下一記錄關(guān)閉數(shù)據(jù)庫鏈接對象、記錄集對象，并釋放資源輸出記錄數(shù)和提示結(jié)束YNASP檢索程序流程圖：開始加載Include文件定義記數(shù)變222）程序流程圖中用箭頭代表控制流，因此程序員不受任何約束，可以完全不顧結(jié)構(gòu)程序設(shè)計的精神，隨意轉(zhuǎn)移控制。3）程序流程圖不易表示數(shù)據(jù)結(jié)構(gòu)。程序流程圖的缺點(diǎn)：1）程序流程圖本質(zhì)上不是逐步求精的好工具，它誘使程序員過早地考慮程序的控制流程，而不去考慮程序的全局結(jié)構(gòu)。2）程序流程圖中用箭頭代表控制流，因此程序員不受任何約束，可236.3.2盒圖（N-S圖）ABC條件FTElseBThenACase條件Case1ACase2B…CasenN循環(huán)條件循環(huán)條件Do-While部分Do-Until部分Aa.順序結(jié)構(gòu)b.選擇結(jié)構(gòu)c.多分支結(jié)構(gòu)d.當(dāng)型循環(huán)結(jié)構(gòu)e.直到型循環(huán)結(jié)構(gòu)f.調(diào)用子程序A圖6.4盒圖的基本符號6.3.2盒圖（N-S圖）ABC條件FTElseThe24盒圖的特點(diǎn)有：1）功能域明確，可以從盒圖上一眼就看出來；2）不可能任意轉(zhuǎn)移控制；3）很容易確定局部和全程數(shù)據(jù)的作用域；

4）很容易表現(xiàn)嵌套關(guān)系，也可以表示模塊的層次結(jié)構(gòu)。

盒圖的特點(diǎn)有：25FTBCDACase1E2F3G4HA：盒圖例子FTBCDACase1234A：盒圖例子26示例示例27N-S圖的嵌套定義形式N-S圖的嵌套定義形式28

PAD（ProblemAnalysisDiagram）是問題分析圖。日立公司發(fā)明和推廣（1973）。6.3.3PAD圖PAD（ProblemAnalysisD29P1P2WHILECUNTILCPPP2P1CP1P2Pn…X=L1L2Lndefa.順序結(jié)構(gòu)b.當(dāng)型循環(huán)結(jié)構(gòu)c.直到型循環(huán)結(jié)構(gòu)d.選擇結(jié)構(gòu)e.多分支結(jié)構(gòu)f.語句標(biāo)號g.定義圖6.5PAD圖的基本符號P1P2WHILECUNTILCPPP2P1CP1P30例子：

P1P2UNTILC2P7P4P3Cdefa.初始的PAD圖圖6.6PAD圖例子b.使用def符號細(xì)化處理框P2P5P2P8C1UNTILC2P9P10P6例子：P1P2UNTILC2P7P4P3Cdefa.初31PAD圖的優(yōu)點(diǎn)：1）使用表示結(jié)構(gòu)化控制結(jié)構(gòu)的PAD符號所設(shè)計出來的程序必然是結(jié)構(gòu)化程序；2）PAD圖所描繪的程序結(jié)構(gòu)十分清晰。圖中最左面的豎線是程序的主線，即第一層結(jié)構(gòu)。隨著程序?qū)哟蔚脑黾樱琍AD圖逐漸向右延伸，每增加一個層次，圖形向右擴(kuò)展一條豎線。PAD圖中豎線的總條數(shù)就是程序的層次數(shù)；PAD圖的優(yōu)點(diǎn)：323）用PAD圖表現(xiàn)程序，通俗易懂，程序從圖中最左豎線上端的結(jié)點(diǎn)開始執(zhí)行，自上而下，從左向右順序執(zhí)行，遍歷所有結(jié)點(diǎn)；3）用PAD圖表現(xiàn)程序，通俗易懂，程序從圖中最左豎線上端的結(jié)334）容易將PAD圖轉(zhuǎn)換成高級語言源程序，這種轉(zhuǎn)換可以用軟件工具自動完成；5）可用于表示程序邏輯，也可用于描繪數(shù)據(jù)結(jié)構(gòu)；6）PAD圖的符號支持自頂向下、逐步求精的方法。4）容易將PAD圖轉(zhuǎn)換成高級語言源程序，這種轉(zhuǎn)換可以用軟件工34判定表由四部分組成：左上部列出所有條件左下部是所有可能做的動作右上部表示各種條件組合右下部是和每種條件組合相對應(yīng)的動作

6.3.4判定表判定表由四部分組成：6.3.4判定表35

123456789國內(nèi)乘客

TTTTFFFF頭等艙

TFTFTFTF殘疾乘客

FFTTFFTT行李重量W≤30

TFFFFFFFF

免費(fèi)

×

(W-30)×2

×

(W-30)×3

×

(W-30)×4

×

×

(W-30)×6

×

×(W-30)×8

×

(W-30)×12

×

123456789國內(nèi)乘客

TTTTFFFF頭等艙

36某單位招聘考試，共考核三門課，錄取方式是：總分250分（含）以上，且每門課都70分（含）以上錄?。蝗绻偡?50分（含）以上，其中至少1門在60分（含）以上70分（不含）以下需復(fù)試該課程，復(fù)試后達(dá)到70分（含）以上錄?。黄渌闆r都不錄取。作出錄取過程的決策表。某單位招聘考試，共考核三門課，錄取方式是：376.3.5判定樹判定樹是判定表的變種。行李重量W>30行李重量W≤30國內(nèi)乘客外國乘客頭等艙其他艙頭等艙其他艙殘疾乘客正常乘客殘疾乘客正常乘客殘疾乘客正常乘客殘疾乘客正常乘客（W-30）×2（W-30）×4（W-30）×3（W-30）×6（W-30）×4（W-30）×8（W-30）×6（W-30）×12免費(fèi)圖6.7用判定樹表示計算行李費(fèi)的算法行李費(fèi)算法6.3.5判定樹行李重量W>30行李重量W≤30國內(nèi)乘客38PDL也稱為偽碼。如：ifI>0then執(zhí)行訂單數(shù)據(jù)輸入模塊else報告出錯信息endif6.3.6過程設(shè)計語言（PDL）PDL也稱為偽碼。6.3.6過程設(shè)計語言（PDL）39PDL的優(yōu)點(diǎn)：1）可以作為注釋直接插在源程序中間；2）可以使用普通的正文編輯程序或文字處理系統(tǒng)來完成PDL的書寫和編輯工作；3）現(xiàn)在已經(jīng)有一些自動處理程序可以自動地把PDL生成程序代碼。PDL的缺點(diǎn)：不如圖形工具形象直觀。PDL的優(yōu)點(diǎn)：PDL的缺點(diǎn)：不如圖形工具形象直觀。406.1結(jié)構(gòu)程序設(shè)計6.2人機(jī)界面設(shè)計6.3過程設(shè)計的工具6.4面向數(shù)據(jù)結(jié)構(gòu)的設(shè)計方法6.5程序復(fù)雜程度的定量度量6.1結(jié)構(gòu)程序設(shè)計416.4面向數(shù)據(jù)結(jié)構(gòu)的設(shè)計方法1）順序結(jié)構(gòu)

ABCD圖6.8A由B、C、D三個元素順序組成6.4.1Jackson圖6.4面向數(shù)據(jù)結(jié)構(gòu)的設(shè)計方法1）順序結(jié)構(gòu)ABCD圖6422）選擇結(jié)構(gòu)

AB°C°D°圖6.9根據(jù)條件A選擇B、C、D中的某一個2）選擇結(jié)構(gòu)AB°C°D°圖6.9根據(jù)條件A選擇B、C433）重復(fù)結(jié)構(gòu)AB*圖6.10A由B出現(xiàn)N次組成3）重復(fù)結(jié)構(gòu)AB*圖6.10A由B出現(xiàn)N次組成446.4.2改進(jìn)的Jackson圖

ABCD圖6.11改進(jìn)的Jackson圖ABoCoDoABo-oAB*S(i)S(i)I(i)(a)(b)(c)(d)6.4.2改進(jìn)的Jackson圖ABCD圖6.11改45Jackson方法的目標(biāo)是：得出對程序處理過程的詳細(xì)描述。

6.4.3Jackson方法Jackson方法的目標(biāo)是：6.4.3Jackson方法46Jackson結(jié)構(gòu)程序設(shè)計方法由五個步驟組成：1）分析并確定輸入數(shù)據(jù)和輸出數(shù)據(jù)的邏輯結(jié)構(gòu)，并用Jackson圖描繪這些數(shù)據(jù)結(jié)構(gòu)；2）找出輸入數(shù)據(jù)結(jié)構(gòu)和輸出數(shù)據(jù)結(jié)構(gòu)中有對應(yīng)關(guān)系的數(shù)據(jù)單元；Jackson結(jié)構(gòu)程序設(shè)計方法由五個步驟組成：473）用三條規(guī)則從描繪數(shù)據(jù)結(jié)構(gòu)的Jackson圖導(dǎo)出描繪程序結(jié)構(gòu)的Jackson圖：A．為每對有對應(yīng)關(guān)系的數(shù)據(jù)單元，按照它們在數(shù)據(jù)結(jié)構(gòu)圖中的層次在程序結(jié)構(gòu)圖的相應(yīng)層次畫一個處理框；3）用三條規(guī)則從描繪數(shù)據(jù)結(jié)構(gòu)的Jackson圖導(dǎo)出描繪程序結(jié)48B．根據(jù)輸入數(shù)據(jù)結(jié)構(gòu)中剩余的每個數(shù)據(jù)單元所處的層次，在程序結(jié)構(gòu)圖的相應(yīng)層次分別為它們畫上對應(yīng)的處理框；C．根據(jù)輸出數(shù)據(jù)結(jié)構(gòu)中剩余的每個數(shù)據(jù)單元所處的層次，在程序結(jié)構(gòu)圖的相應(yīng)層次分別為它們畫上對應(yīng)的處理框；B．根據(jù)輸入數(shù)據(jù)結(jié)構(gòu)中剩余的每個數(shù)據(jù)單元所處的層次，在程序結(jié)494）列出所有操作和條件（包括分支條件和循環(huán)結(jié)束條件），并且把它們分配到程序結(jié)構(gòu)圖的適當(dāng)位置；5）用偽碼表示程序。4）列出所有操作和條件（包括分支條件和循環(huán)結(jié)束條件），并且把50順序結(jié)構(gòu)：AseqBCDAend與三種基本結(jié)構(gòu)對應(yīng)的偽碼是：順序結(jié)構(gòu)：與三種基本結(jié)構(gòu)對應(yīng)的偽碼是：51選擇結(jié)構(gòu)Aselectcond1BAorcond2CAorcond3DAend選擇結(jié)構(gòu)52重復(fù)結(jié)構(gòu)Aiteruntil(或while)condBAend重復(fù)結(jié)構(gòu)53例：一個正文文件由若干記錄組成，每個記錄是一個字符串。如：Record1：Howmanystagesarethereinthetraditionalsoftwaredevelopmentmodel?Record2：Afterenteringtheroom,walktothepersonsittingnearesttoyouandgreethim/herwitha“highfive”.Record3：Whatareencapsulatedintoanobject?Record4：Whatdiagramisthefollowingdiagram?Simplydescribethemeaningofit.

例：一個正文文件由若干記錄組成，每個記錄是一個字符串。54要求：1）設(shè)計程序統(tǒng)計每個記錄中空格字符的個數(shù)，輸出數(shù)據(jù)的格式是，每讀入一個記錄（字符串）之后，另起一行打印出這個字符串及其空格數(shù)；2）最后打印出文件中空格的總個數(shù)。

要求：55正文文件字符串*字符*空格o非空格oIIS(a)輸入數(shù)據(jù)結(jié)構(gòu)正文文件字符串*字符*空格o非空格oIIS(a)輸入數(shù)據(jù)結(jié)構(gòu)56輸出表格表格體空格總數(shù)串信息*字符串空格數(shù)I輸出表格表格體空格總數(shù)串信息*字符串空格數(shù)I57輸出表格表格體空格總數(shù)串信息*字符串空格數(shù)I正文文件字符串*字符*空格o非空格oIIS圖6.12表示輸入/輸出數(shù)據(jù)結(jié)構(gòu)的Jackson圖分析輸入、輸出數(shù)據(jù)結(jié)構(gòu)，用Jackson圖描繪，并找出兩者對應(yīng)的數(shù)據(jù)單元：輸出表格表格體空格總數(shù)串信息*字符串空格數(shù)I正文文件字符串*58統(tǒng)計空格程序體印總數(shù)處理字符串*分析字符串印空格數(shù)印字符串分析字符*處理空格o處理非空格oIIS圖6.13描繪統(tǒng)計空格程序結(jié)構(gòu)的Jackson圖導(dǎo)出描繪程序結(jié)構(gòu)的Jackson圖：注意：改進(jìn)的Jackson圖規(guī)定在順序結(jié)構(gòu)的元素中不能有重復(fù)出現(xiàn)或選擇出現(xiàn)的元素，因此需要增加中間層次的處理框。統(tǒng)計空格程序體印總數(shù)處理字符串*分析字符串印空格數(shù)印字符串分59（1）停止（2）打開文件（3）關(guān)閉文件（4）印出字符串（5）印出空格數(shù)目（6）印出空格總數(shù)（7）sum:=sum+1（8）totalsum:=totalsum+sum（9）讀入字符串（10）sum:=0（11）totalsum:=0（12）pointer:=1（13）pointer:=pointer+1I(1)文件結(jié)束I(2)字符串結(jié)束S(3)字符是空格列出所有操作和條件：

（1）停止（260統(tǒng)計空格程序體印總數(shù)處理字符串*分析字符串印空格數(shù)印字符串分析字符*處理空格o處理非空格oI(1)I(2)S(3)圖6.14最終分配好操作和條件的Jackson圖31119261012458971313統(tǒng)計空格程序體印總數(shù)處理字符串*分析字符串印空格數(shù)印字符串分61偽代碼表示練習(xí)偽代碼表示626.1結(jié)構(gòu)程序設(shè)計6.2人機(jī)界面設(shè)計6.3過程設(shè)計的工具6.4面向數(shù)據(jù)結(jié)構(gòu)的設(shè)計方法6.5程序復(fù)雜程度的定量度量6.1結(jié)構(gòu)程序設(shè)計636.5程序復(fù)雜度的定量度量定量度量程序復(fù)雜度的作用：（1）可估算軟件中錯誤的數(shù)量及軟件開發(fā)工作量；（2）度量的結(jié)果可用來比較不同設(shè)計或不同算法的優(yōu)劣；（3）程序的復(fù)雜度可作為模塊規(guī)模的限度。6.5程序復(fù)雜度的定量度量定量度量程序復(fù)雜度的作用：641.流圖“退化”的程序流程圖，僅描繪程序的控制流程，不表現(xiàn)對數(shù)據(jù)的具體操作及循環(huán)、選擇的條件。

6.5.1McCabe方法1.流圖6.5.1McCabe方法65一個圓代表一條或多條語句；一個順序結(jié)構(gòu)可以合并成一個結(jié)點(diǎn)；匯點(diǎn)也是結(jié)點(diǎn)；一個順序處理框序列和一個判斷框可映射成一個結(jié)點(diǎn)。一個圓代表一條或多條語句；匯點(diǎn)也是結(jié)點(diǎn)；66使用環(huán)形復(fù)雜度度量程序的復(fù)雜程度ppt課件67復(fù)合條件：包含了一個或多個布爾運(yùn)算符（OR、AND、NOR等）。應(yīng)把復(fù)合條件分解為簡單條件，每個條件對應(yīng)一個結(jié)點(diǎn)。復(fù)合條件：682.計算環(huán)形復(fù)雜度的方法1）環(huán)形復(fù)雜度V（G）等于流圖中的區(qū)域數(shù)；2）環(huán)形復(fù)雜度V（G）＝E－N+2，其中E是流圖中邊的條數(shù)，N是結(jié)點(diǎn)數(shù)；3）環(huán)形復(fù)雜度V（G）＝P＋1，其中P為流圖中判定結(jié)點(diǎn)的數(shù)目。2.計算環(huán)形復(fù)雜度的方法69例：計算下列程序圖的程序復(fù)雜度例：計算下列程序圖的程序復(fù)雜度70解：方法一：程序圖把平面分為4個區(qū)域，程序復(fù)雜度V（G）＝4；方法二：邊的條數(shù)E＝11，結(jié)點(diǎn)數(shù)N＝9，程序復(fù)雜度V（G）＝E－N＋2＝4；方法三：判定結(jié)點(diǎn)為1、2、4點(diǎn)，數(shù)目為P＝3個，所以V（G）＝P＋1＝4。解：713.環(huán)形復(fù)雜度的用途對測試難度的一種定量度量，也能對軟件最終的可靠性給出某種預(yù)測。實踐表明，模塊規(guī)模以V（G）≤10為宜。3.環(huán)形復(fù)雜度的用途72根據(jù)程序中運(yùn)算符和操作數(shù)的總數(shù)來度量程序復(fù)雜度。N=N1+N2其中：N定義為程序長度；N1為程序中運(yùn)算符出現(xiàn)的總次數(shù)；N2為操作數(shù)出現(xiàn)的總次數(shù)。6.5.2Halstead方法根據(jù)程序中運(yùn)算符和操作數(shù)的總