PM-第二章 結(jié)構(gòu)化程序設(shè)計

第二章結(jié)構(gòu)化程序設(shè)計一節(jié)關(guān)于結(jié)構(gòu)程序設(shè)計1.定義結(jié)構(gòu)程序設(shè)計是避免使用GOTO語句的一種程序設(shè)計結(jié)構(gòu)程序設(shè)計是自頂向下的程序設(shè)計是一種組織和編制程序的方法,利用它編制的乘隙易于理解和修改程序結(jié)構(gòu)化的一個主要功能是似的正確性證明容易實現(xiàn)允許在設(shè)計過程中的每一步驗證其正確性,即自動導致自我說明與自我捍衛(wèi)的程序風格事態(tài)論如何將任何大規(guī)模的復雜的流程途程許轉(zhuǎn)換成一種標準形式,使得它們用幾種標準的控制結(jié)構(gòu),通過重復和嵌套來表示.結(jié)構(gòu)程序設(shè)計的綜合描述結(jié)構(gòu)程序設(shè)計的綜合描述:結(jié)構(gòu)程序設(shè)計是一種進行程序設(shè)計的原則和方法，按照這種原則和方法設(shè)計出的程序的特點是：結(jié)構(gòu)清晰、易閱讀、易修改、易驗證。結(jié)構(gòu)程序設(shè)計語言：按照結(jié)構(gòu)程序設(shè)計的要求設(shè)計出的程序設(shè)計語言稱為結(jié)構(gòu)程序設(shè)計語言。結(jié)構(gòu)化程序：利用結(jié)構(gòu)程序設(shè)計語言，或按照結(jié)構(gòu)程序設(shè)計的思想編制的程序稱為“結(jié)構(gòu)化程序”。關(guān)于GOTO語句的問題2.關(guān)于GOTO語句的問題取消GOTO語句，即GOTO有害。理由：GOTO語句使程序的靜態(tài)結(jié)構(gòu)與它的動態(tài)執(zhí)行之間有很大的差別。這樣使程序難閱讀、難查錯。去掉GOTO語句可以直接從程序結(jié)構(gòu)上反映出程序運行的過程，結(jié)構(gòu)清晰、便于查錯、易驗證。保留GOTO語句GOTO語句使用起來比較靈活，而且有些情況下能夠提高程序的效率，若一味地強調(diào)刪除GOTO語句，有些情形會使程序過于復雜，增加不必要的計算量。折中派（Knuth）不加限制地使用GOTO語句，特別往回跳的GOTO語句，會使程序結(jié)構(gòu)難以理解，這種情形應(yīng)盡量避免使用GOTO語句。為提高效率，同時又不破壞程序的良好結(jié)構(gòu)，有控制地使用GOTO語句是有必要的。結(jié)構(gòu)程序設(shè)計結(jié)論結(jié)論：結(jié)構(gòu)程序設(shè)計討論的是一種程序設(shè)計的方法和風格。關(guān)注的焦點是得到的程序的結(jié)構(gòu)的好壞，而有無GOTO語句并不是一個程序結(jié)構(gòu)好壞的標志。避免和限制使用GOTO語句是得到結(jié)構(gòu)化程序的一種手段，而不是我們的目的。2.2節(jié)結(jié)構(gòu)化程序和結(jié)構(gòu)定理一、結(jié)構(gòu)化程序下面給結(jié)構(gòu)化程序下一個精確的定義.流程圖程序流程圖程序的組成：函數(shù)節(jié)點、謂詞節(jié)點和匯點。函數(shù)節(jié)點：只有一條入口線和一條出口線，一般與賦值語句相對應(yīng)。謂詞節(jié)點：有一條入口線和兩條出口線，它不改變程序的數(shù)據(jù)項的值。匯點：有兩條入口線和一條出口線，它不執(zhí)行任何運算，只起到收集出口線的作用。fp1.流程圖程序定義：一個用流程圖的形式表示出來的程序，稱為流程圖程序。流程圖程序舉例流程圖程序舉例:pqgf正規(guī)程序2.正規(guī)程序定義：滿足以下兩個條件的流程圖程序稱為正規(guī)程序。條件：具有一條入口線和一條出口線，且對每個節(jié)點，都有一條從入口線到出口線的通路通過該節(jié)點。例：下面兩個流程圖程序不是正規(guī)程序pfgpf正規(guī)子程序3.正規(guī)子程序一個正規(guī)程序的某些部分仍然可以是正規(guī)程序,這些部分稱為正規(guī)子程序.基本程序4.基本程序定義：一個正規(guī)程序，如果不包含多余一個節(jié)點的正規(guī)子程序，稱為基本程序。即基本程序是一種不可再分解的正規(guī)程序。例：fgfghfgf七種重要的基本程序函數(shù):序列:If-thenIf-then-elsefgfpfgpf七種重要的基本程序while-do:Do-until:Do-while-do:pfpgfpg復合程序和結(jié)構(gòu)化程序5.復合程序若一個基本程序的函數(shù)節(jié)點用另外一個基本程序替換,所產(chǎn)生的正規(guī)程序稱為復合程序。6.結(jié)構(gòu)化程序由基本程序的一個固定的基集合構(gòu)造出的復合程序稱為結(jié)構(gòu)化程序。二、結(jié)構(gòu)化定理1.程序函數(shù)已知一正規(guī)程序P，對于每個初始的數(shù)據(jù)狀態(tài)X，若程序是終止的，那么有確定的最終數(shù)據(jù)狀態(tài)Y。如果對于每一個給定的X，值Y是唯一的，那么所有的有序?qū)Φ募蟵（X，Y）}定義了一個函數(shù)，稱這個函數(shù)為程序P的程序函數(shù)，記為[P]。例：設(shè)程序P由三條語句組成：T:=x;x:=y;y:=t;對任意的x(x,y,t),程序P的執(zhí)行結(jié)果Y：（y,x,x）因此，程序函數(shù)是{（x,y,t）,(y,x,x)}七種基本程序的程序函數(shù)2.七種基本程序的程序函數(shù)[f]={(x,y)|y=f(x)}[f;g]={(x,y)|y=g·f(x)}[if-then]={(x,y)|p(x)y=f(x)|?p(x)y=x}[if-then-else]={(x,y)|p(x)y=f(x)|?p(x)y=g(x)}七種基本程序的程序函數(shù)(續(xù))[while-do]={(x,y)|k0((j:0<=j<k:p·fj(x))|?p·fk(x)y=fk(x))}[do-until]={(x,y)|k>0(j:1<=j<k)(

?p·fj(x)|p·fk(x)y=fk(x))}[dofwhilepdogod]={(x,y)|k0(

j:0<=j<k:p·f·(g·f)j(x))|?p·f·(g·f)k(x)y=f·(g·f)k(x))}程序函數(shù)的計算1）對于序列程序可使用跟蹤表的方法計算[p]

例：語句段：x:=x+y;y:=x-y;x:=x-y;

解：假設(shè)變量x,y的初值為x0,y0,…

有跟蹤表：語句xyx:=x+yx1=x0+y0y1=y0y:=x-yy2=x1–y1x2=x1x:=x-yX3=x2-y2y3=y2X3=x2-y2=x1-(x1-y1)=y1=y0Y3=y2=x1-y1=x0+y0–y0=x0[P]={((x,y),(y,x)}程序函數(shù)的計算練習：計算下列語句序列的程序函數(shù)：

y:=a;y:=x*y+b;y:=x*y+c;y:=x*y+d程序函數(shù)的計算2)無循環(huán)程序的程序函數(shù)首先：構(gòu)造有窮的執(zhí)行樹然后：對每條路徑寫出相應(yīng)的表達式例：pfhrgq程序函數(shù)的計算執(zhí)行樹：pfhrqghrgg[p]={(x,y)|p(x)qf(x)y=gf(x)|p(x)

qf(x)rhf(x)y=ghf(x)|p(x)

qf(x)

rhf(x)y=hf(x)|p(x)…|…程序函數(shù)的計算3)循環(huán)程序的程序函數(shù)g1g3p1p2p3g2g4g51g12g3p1g213p2p3g23g42執(zhí)行樹：代換后的執(zhí)行樹：g1g3p1g2p2p3g5g4f1f3f1f2f2f3f1={(x,y)|y=f2g1(x)}F2={(x,y)|p1g3(x)y=f1g2g3(x)|p1g3(x)y=f3g3(x)}F3={(x,y)|p2(x)p3(x)y=f3g5(x)|p2(x)p3(x)y=x|

p2(x)y=f2g4(x)}程序的函數(shù)等價1.程序的函數(shù)等價如果程序P1和程序P2有相同的程序函數(shù)，稱它們是函數(shù)等價的，或簡稱是等價的。結(jié)構(gòu)化定理2.結(jié)構(gòu)化定理定理：任一正規(guī)程序都可以函數(shù)等價與一個由基集合{序列，if-then-else，while-do}產(chǎn)生的結(jié)構(gòu)化程序。結(jié)構(gòu)化定理-證明證明：考察任一正規(guī)程序:

首先，從程序的入口處開始給程序的函數(shù)節(jié)點和謂詞節(jié)點編號。編號為1，2，3，…，n（若入口處是匯點，那么宴會點的出口線繼續(xù)考察，直到找到第一個函數(shù)節(jié)點或謂詞節(jié)點）。同時將每一個函數(shù)節(jié)點及謂詞節(jié)點的出口線用它后面的節(jié)點的編號進行編號。如果它后面沒有函數(shù)節(jié)點或謂詞節(jié)點，即該節(jié)點的出口線直接或通過匯點與程序的出口相連時，出口線的編號為0。peqh123400結(jié)構(gòu)化定理--證明對每一個編號為i，出口線編號為j、k的謂詞節(jié)點p，構(gòu)造一個新的IF-THEN-ELSE程序gi，如圖：h其次，對原程序種的每一個編號為i，出口線編號為J的函數(shù)節(jié)點h，構(gòu)造一個新的序列程序gi，如圖：ijhL:=jgi=pgi=pL:=jL:=kjik結(jié)構(gòu)化定理--證明最后，利用已經(jīng)得到的一些gi（I=1,2,3,…,n），按下圖形式構(gòu)造一個while-do循環(huán)。這個循環(huán)體是一個對L從1到n進行測試的嵌套的IF-THEN-ELSE程序（最內(nèi)層的I表示恒等函數(shù)）：L:=1L>0L=1?g1L=2?g2L=n-1?gn-1L=n?gn???I???F=結(jié)構(gòu)化定理--證明結(jié)論:顯然,上面程序的功能和原程序的功能是相同的,因而它和原程序是函數(shù)等價的。而且，該程序是由一個固定的基集合{序列，IF-THEN-ELSE，WHILE-DO}產(chǎn)生的結(jié)構(gòu)化程序，從而定理得證。結(jié)構(gòu)化定理舉例例：考察如下的流程圖程序：peqh123400第一步：編號，結(jié)果如上圖。結(jié)構(gòu)化定理舉例第二步：重新構(gòu)造函數(shù)節(jié)點和謂詞節(jié)點eL:=0g2=g1=pL:=2L:=3g3=qL:=0L:=4hL:=1g4=結(jié)構(gòu)化定理舉例第三步：用IF-THEN-ELSE和WHILE-DO重新構(gòu)造程序：L:=1L>0L=1?L=2?pL:=2L:=3eL:=0L=3?qL:=0L:=4L=4?hL:=1I結(jié)構(gòu)化定理舉例第四步：化簡：上面得到的結(jié)構(gòu)化程序比較龐大，且效率不高，還可以進一步改進，消除一些多余的對L的測試和賦值?；喌幕舅枷耄簩τ谀承﹋>0，如果gj中不包含賦值語句L:=j，則可以用gj代替所有的賦值L:=j。這樣代替后，由于j不再賦值給L，因而測試L=j可以從IF-THEN-ELSE結(jié)構(gòu)中去掉。這種替換直到以下情況出現(xiàn)為止：除了L:=0以外，所有給L賦值的語句均被消除；每個余下的gi’中都包含由相應(yīng)賦值L:=I（gi’是gi經(jīng)過一些替換以后得到的復合程序）例：結(jié)構(gòu)化定理轉(zhuǎn)換的化簡用g4代替所有的L:=4的賦值語句，并刪除L=4的測試L:=1L>0L=1?L=2?pL:=2L:=3eL:=0L=3?qL:=0hL:=1I結(jié)構(gòu)化定理轉(zhuǎn)換的化簡（續(xù)）用當前的g3’替換L:=3的賦值語句，并刪除L=3的測試L:=1L>0L=1?L=2?pL:=2eL:=0qL:=0hL:=1I結(jié)構(gòu)化定理轉(zhuǎn)換的化簡（續(xù)）用g2’替換L:=2的賦值。L:=1L>0L=1?