PM-第二章 結構化程序設計

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

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

解：假設變量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)}程序函數的計算練習：計算下列語句序列的程序函數：

y:=a;y:=x*y+b;y:=x*y+c;y:=x*y+d程序函數的計算2)無循環(huán)程序的程序函數首先：構造有窮的執(zhí)行樹然后：對每條路徑寫出相應的表達式例：pfhrgq程序函數的計算執(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)…|…程序函數的計算3)循環(huán)程序的程序函數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)}程序的函數等價1.程序的函數等價如果程序P1和程序P2有相同的程序函數，稱它們是函數等價的，或簡稱是等價的。結構化定理2.結構化定理定理：任一正規(guī)程序都可以函數等價與一個由基集合{序列，if-then-else，while-do}產生的結構化程序。結構化定理-證明證明：考察任一正規(guī)程序:

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