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

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

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

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