程序設(shè)計學(xué)PPT課件

1、第第2章章 結(jié)構(gòu)化程序結(jié)構(gòu)化程序n以前經(jīng)常采用的一種程序設(shè)計方法：要解決的問題流程圖編碼n使用流程圖的兩個主要缺陷：費時費力，沒有好的標準效率不高結(jié)構(gòu)不清晰影響正確性2.1 什么是結(jié)構(gòu)化程序n流程圖程序n正規(guī)程序n基本程序n結(jié)構(gòu)化程序面向過程與面向結(jié)構(gòu)n面向過程強調(diào)：問題處理的過程，即對軟件進行功能功能分解，寫成一個個函數(shù)調(diào)用。優(yōu)點：符合人們的思維習(xí)慣。缺點：強調(diào)過程，忽視結(jié)構(gòu)，所以易讀性較差。 n面向結(jié)構(gòu)（結(jié)構(gòu)化程序設(shè)計方法）是“面向過程”方法的改進 方法：優(yōu)點：強調(diào)程序的結(jié)構(gòu)性- 所以容易做到易讀- 易懂. 該方法思路清晰 劃分功能模塊連接各模塊組合構(gòu)成軟件系統(tǒng)2.1.1 流程圖程序n流程

2、圖流程圖是一個描述程序的控制流程和指令執(zhí)行情況的有向圖。 n一個程序的流程圖通常由下列3種結(jié)點組成: 函數(shù)節(jié)點 謂詞節(jié)點 匯點 函數(shù)節(jié)點 Process Box 如果一個結(jié)點有一個入口線一個入口線和一個出口一個出口線線，稱為函數(shù)結(jié)點。如下圖所示，其中f是函數(shù)結(jié)點的名字。f函數(shù)結(jié)點又叫處理單元處理單元，一般和賦值語賦值語句句相對應(yīng) 如果一個結(jié)點有一個入口線一個入口線和兩個出兩個出口線口線，而且它不改變程序的數(shù)據(jù)項值它不改變程序的數(shù)據(jù)項值，稱為謂詞結(jié)點。 謂詞節(jié)點 Decision BoxpTFpTF謂詞結(jié)點又叫判斷單元判斷單元，一般與條件語句條件語句相對應(yīng)匯點 Junction Box 如果一個

3、結(jié)點有兩個入口線兩個入口線和一一個出口線個出口線，而且它不執(zhí)行任何計算它不執(zhí)行任何計算，稱為匯點。 匯點又叫連接單元連接單元，在流程圖中，匯點只是起一個簡單的連接作用連接作用。例子phqg例子L1: if B1 then goto L2; S1; if B2 then goto L2; S2; goto L1;L2: S3;B1S1B2S2S3TTFF2.1.2 正規(guī)程序 一個流程圖程序如果滿足以下兩個條件，稱為正規(guī)程序：(1) 具有一個入口線一個入口線和一個出口線一個出口線(2) 對每一個結(jié)點，都有一條從入口線到一條從入口線到出口線的通路經(jīng)過該點出口線的通路經(jīng)過該點。正規(guī)程序phqg正規(guī)程序

4、（1）（2）（3）正規(guī)程序的抽象 一個正規(guī)程序可以抽象抽象為一個函數(shù)節(jié)函數(shù)節(jié)點點。這個函數(shù)結(jié)點概括了該正規(guī)程序?qū)?shù)據(jù)進行運算和測試的總的作用。a抽象成抽象成抽象成抽象成qpbpgbk正規(guī)子程序 一個正規(guī)程序的某些部分仍然是正規(guī)程序，把這些部分稱為正規(guī)子程序。正規(guī)子程序。g,b是k的正規(guī)子程序，a又是g的正規(guī)子程序bqapk抽象成抽象成gbP抽象成抽象成例子padqbstc2.1.3 基本程序 一個正規(guī)程序，如果不包含多于一個不包含多于一個結(jié)點的正規(guī)子程序結(jié)點的正規(guī)子程序，則稱為基本程序基本程序。l基本程序是正規(guī)程序l基本程序可以包含正規(guī)子程序l基本程序包含的正規(guī)子程序只有一個結(jié)點例子判斷：下面

5、的流程圖程序是不是基本程序?(1)(2)是是是是不是不是(3)七種基本程序ffgpfpfpfgpfpgf（1）（2）（3）（4）（5）（6）（7）FT函數(shù)序列do-untilif-then-elseif-thendo-while-dowhile-do基本程序 結(jié)構(gòu)化程序n構(gòu)造一個程序，并不需要使用所有7種基本結(jié)構(gòu)。pfwhile-dopfpIf-then和do-until2.1.4 結(jié)構(gòu)化程序 為了構(gòu)造一個流程圖程序，可以只使用七種基本程序中的一部分，把從這七種基本程序中挑出的這部分叫做基本程序的基集合基集合。例如：l序列，if-then-else，while-dol序列，if-then-el

6、se，do-until復(fù)合程序復(fù)合程序 反復(fù)應(yīng)用基集合構(gòu)造出來的程序稱為基集合的復(fù)合程序復(fù)合程序。 構(gòu)造方法構(gòu)造方法：一個基本程序的函數(shù)結(jié)點用另外一個基本程序替換。bqapkgbP結(jié)構(gòu)化程序n結(jié)構(gòu)化程序 由基本程序的一個固定的基集合，構(gòu)造出來的復(fù)合程序稱為結(jié)構(gòu)化程序結(jié)構(gòu)化程序。流程圖程序正規(guī)程序基本程序復(fù)合程序基集合序列,if-then-else,while-do判斷：下述程序是否是結(jié)構(gòu)化程序?(基集合為序列，if-then-else，while-do)phqgWhile-do序列If-then-else判斷：下述程序是否是結(jié)構(gòu)化程序?(基集合為序列，if-then-else，while-do

7、)2.2 結(jié)構(gòu)化定理n結(jié)構(gòu)化定理: 任意一個正規(guī)程序，都可以函數(shù)等價函數(shù)等價于一個由基集合序列,if-then-else,while-do 產(chǎn)生的結(jié)構(gòu)化程序。2.2.1 程序函數(shù)n任何一個正規(guī)程序可以定義程序初始狀態(tài)與程序最終狀態(tài)之間的函數(shù)，這個函數(shù)稱為程序函數(shù)程序函數(shù)，記為P。X：程序初始狀態(tài)； Y：程序最終狀態(tài)。且：對于每一個初始的數(shù)據(jù)狀態(tài)X，程序是終止的對于每一個給定的X，值Y是唯一的PXY(X,Y)程序函數(shù)表示形式有序?qū)τ行驅(qū)?、條件規(guī)則條件規(guī)則、數(shù)據(jù)賦值數(shù)據(jù)賦值等形式例如：if x y then z:=x else z:=y fi有序?qū)Γ河行驅(qū)Γ?x,y,z),(x,y,min(x,y

8、)條件規(guī)則：條件規(guī)則：(x,y,z)|x yz:=x xyz:=y數(shù)據(jù)賦值：數(shù)據(jù)賦值：(z:=min(x,y)例子n寫出下列程序的程序函數(shù)(x,y為整數(shù))1、while x0 do x:=x-1 od=(x,min(0,x)=(x:=min(0,x)2、x:=x+y;y:=x-y=(x,y),(x+y,x)=(x, y:=x+y,x)3、do x:=x+1 until xy od=(x,y),(max(x+1,y+1),y)=(x:=max(x+1,y+1)基本程序所對應(yīng)的程序函數(shù)n函數(shù)： f=(x,y)|y=f(x) n序列： f; g=(x,y)|y=g f(x) nIF-THEN: if

9、-then=(x,y)|p(x) y=f(x) p(x) y=x nIF-THEN-ELSE : if-then-else=(x,y)|p(x) y=f(x) p(x) y=g(x) 基本程序所對應(yīng)的程序函數(shù)nWHILE-DO: while-do=(x,y)| k 0(j,0j 0( j,1 jk)( p fj(x) p fk(x)y= fk(x)n說明k=1時，j不存在，則p f(x)為真，y=f(x)；k=2時，j只能為1，此時p f1(x)為假， p f 2(x)為真，y= f 2(x)；基本程序所對應(yīng)的程序函數(shù)nDO-WHILE-DO: do-while-do=(x,y)| k 0(

10、j, 0 jk)(p f(g f)j(x) p f(g f) k(x)y= f(g f)k(x) n分析k=0時，j不存在，則p f(x)為假，y=f(x)；k=1時，j0，則p f(x)為真， p f(g f(x) 為假，y= f(g f(x)；k=2時，j0、1時， p f(g f)j(x)為真，p f(g f)2(x) )為假，y= f(g f)2(x)；程序函數(shù)與函數(shù)等價n程序函數(shù)是對程序功能的一個精確的描述。n定義定義 如果程序P1和P2有相同的程序函數(shù)，稱它們是函數(shù)等價函數(shù)等價的，簡稱是等價等價的。2.2.2 結(jié)構(gòu)化定理n結(jié)構(gòu)化定理任一正規(guī)程序正規(guī)程序都可以函數(shù)等價函數(shù)等價于一個由

11、基集合序列，IF-THEN-ELSE，WHILE-DO 產(chǎn)生的結(jié)結(jié)構(gòu)化程序構(gòu)化程序。n定理的作用結(jié)構(gòu)化程序是一種好結(jié)構(gòu)的程序結(jié)構(gòu)清晰、易于讀寫、易于驗證、可靠性好、可維護性高。表明任何一個正規(guī)程序都可以轉(zhuǎn)化為一個結(jié)構(gòu)化程序。結(jié)構(gòu)化定理的證明過程提供了一種將正規(guī)程序轉(zhuǎn)化為結(jié)構(gòu)化程序的方法。結(jié)構(gòu)化定理證明思路n證明思路保留原程序中的函數(shù)結(jié)點、謂詞結(jié)點。增加一個附加計數(shù)器附加計數(shù)器，通過對這個計數(shù)器的賦值，以循環(huán)測試的方式實現(xiàn)程序流程再造。選擇 循環(huán) 序列結(jié)構(gòu)化定理證明考察任何任何一個正規(guī)程序：n首先，給結(jié)點結(jié)點及出口線出口線編號從程序的入口處開始給程序的函數(shù)結(jié)點函數(shù)結(jié)點和謂詞謂詞結(jié)點結(jié)點編號，編號

12、為1，2，n。如果是匯點匯點，那么沿匯點的出口線繼續(xù)考察，直到找到第一個函數(shù)結(jié)點或謂詞結(jié)點。將每一個函數(shù)及謂詞結(jié)點的出口線出口線用它后面的節(jié)點的號碼進行編號。如果出口線后面沒有函數(shù)或謂詞結(jié)點，即該結(jié)點的出口線直接或通過匯點和程序的出口相連時，出口線編號為0。qep h 1 4 3 22304101. 對函數(shù)結(jié)點函數(shù)結(jié)點和謂詞結(jié)點謂詞結(jié)點編號2. 對函數(shù)結(jié)點函數(shù)結(jié)點及謂詞結(jié)點謂詞結(jié)點的出口線出口線編號結(jié)構(gòu)化定理證明n其次，構(gòu)造函數(shù)結(jié)點函數(shù)結(jié)點和謂詞結(jié)點謂詞結(jié)點的新程序?qū)υ绦蛑械拿恳粋€編號為i, 出口線編號為j的函數(shù)結(jié)點h，構(gòu)造一個新的序列程序gi（其中，L作為計數(shù)器）。對每一個編號為i, 出口

13、線編號為j、k的謂詞結(jié)點，構(gòu)造一個新的if-then-else程序gi.n最后，最后，利用已經(jīng)得到的一些gi（i=1,2,n）按下圖的形式構(gòu)造一個while-do循環(huán)，這個循環(huán)的循環(huán)體是一個對L從1到n進行測試的嵌套的if-then-else程序。其中， I:X X為恒等函數(shù)，I=|xX。作用：使最后一次測試仍然為IF-THEN-ELSE。L=n gn I L=n-1 gn-1 L=2 g2 L=1 g1 L0 L:=1 f =例子編碼規(guī)則1：給程序的函數(shù)結(jié)點函數(shù)結(jié)點、謂詞結(jié)點謂詞結(jié)點編號，匯點匯點略過規(guī)則2：出口線出口線用它后面的結(jié)點的號碼進行編號規(guī)則3：出口線后無結(jié)點（函數(shù)結(jié)點、謂詞結(jié)點）

14、，編號=0q e p h 1 4 3 2230410編碼后，對每一個編號構(gòu)造一個新的序列程序方法1：函數(shù)程序方法2：謂詞程序 P L:=2 L:=3 g1=q L:=0 L:=4 g3=e L:=0 g2=h L:=1 g4=q e p h 14 3 2230410gi由所有g(shù)i組合成新結(jié)構(gòu)程序結(jié)構(gòu)化程序L=4IL=3L =2eL =1L 0L:=1hL:=1L:=0L:=4qL:=0PL:=2L:=3q e ph 14 3 2230410結(jié)構(gòu)化定理意義1、任意一個正規(guī)程序都可以用一個等價的 結(jié)構(gòu)化程序表示。2、提供了一種將正規(guī)程序轉(zhuǎn)化為結(jié)構(gòu)化程 序的方法。問題：比較龐大，而且效率不高。問題：

15、比較龐大，而且效率不高。解決辦法：需要簡化，特別是消除一些多余的對解決辦法：需要簡化，特別是消除一些多余的對L的測試與賦值。的測試與賦值。2.2.3 遞歸結(jié)構(gòu)程序基本思想：對于某些j0，如果在gj中不包含有賦值L:=j，那么可以用程序gj代替所有的賦值L:=j。原因：這樣代替以后，由于j不再賦值給L，因而測試L=j可以從if-then-else結(jié)構(gòu)中去掉。這個替換過程可以一直繼續(xù)到下面兩種情況出現(xiàn)為止：1) 除了 L:=0以外，所有的給L賦值均被消除；2) 若L賦值未被消除，則一定出現(xiàn)下述情況：每一個余下的gi中都包含有相應(yīng)的賦值L:=i。（gi是gi經(jīng)過替換以后得到的復(fù)合程序）采用以上步驟得

16、到的程序通常稱為遞歸結(jié)構(gòu)程序遞歸結(jié)構(gòu)程序。n第一步，用g4代替賦值L:=4，并且消除測試, 得到： 結(jié)構(gòu)化程序結(jié)構(gòu)化程序遞歸遞歸結(jié)構(gòu)程序結(jié)構(gòu)程序L=4IL=3L =2eL =1L 0L:=1hL:=1L:=0L:=4qL:=0PL:=2L:=3g4IL=3L=2eL=1L0L:=1L:=0L:=1qL:=0PL:=2L:=3hg3n第二步，用代換后的g3，即L=3通路上的if-then-else程序代替賦值L:=3，并且消除測試L=3，得到 IL 0L:=1L:=0L:=1qPL:=2hL =1L =2eL:=0n第三步，用g2代替賦值L:=2，得到 I L0 L:=1 L:=0 L:=1 q

17、 P h L=1 e L:=0 第四步，L的初值為1，而且只有在程序的出口處才變?yōu)?，所以在循環(huán)中的賦值L:=1和測試L=1是不需要的，可以消除它們。 L0 L:=1 L:=0 q P h e L:=0 對應(yīng)的程序L:=1;while L0 do Begin if p then begin e; L:=0; end; else begin if q then L:=0; else h; end;End. L0 L:=1 L:=0 q P h e L:=0 結(jié)構(gòu)化定理小結(jié)n采用序列、條件和循環(huán)表示任意復(fù)雜控制結(jié)構(gòu)，表示方法不唯一，采用序列,if-then-else,do-until同樣可以表示所

18、有的正規(guī)程序。 n采用上述方法得到的結(jié)構(gòu)化程序比較龐大，效率不高，可以通過消除多余的對計數(shù)器L的測試和賦值，形成較為簡化的遞歸結(jié)構(gòu)程序遞歸結(jié)構(gòu)程序。 改造結(jié)果不唯一改造形式不是最簡的2.3 一些新的控制結(jié)構(gòu)n結(jié)構(gòu)FORTRAN語言、結(jié)構(gòu)COBOL語言都是在原有的高級語言的基礎(chǔ)上增加了若干個新的控制結(jié)構(gòu)而建立的。n1954到1957年間，世界上第一種高級程序設(shè)計語言Fortran誕生于IBM公司。以后又經(jīng)歷了Fortran 77、Fortran 90 、Fortran 95 等版本，直到當前的Fortran 2003 。nFortran語言的設(shè)計目的在于為科研人員提供一種符合數(shù)學(xué)思維習(xí)慣的高級語

19、言，以滿足科學(xué)計算的需要。 曾經(jīng)被譽為“高級語言之王”。2.3 一些新的控制結(jié)構(gòu)until EV1 or EV2 or or EVn do S0then case EV1: S1 EV2: S2 EVn: Snn 事件驅(qū)動語句 C.T.Zahn在1974年提出 含義：重復(fù)執(zhí)行S0,直到出現(xiàn)事件EV1，EV2，EVn之一為止。L1: if B1 then goto L2; S1; if B2 then goto L2; S2; goto L1;L2: S3;Until L2 do if B1 then L2 fi; S1; if B2 then L2 fi; S2;Then caseL2 : S3變換為事件驅(qū)動語句多重出口循環(huán)語句G.V.Bochmann在1973年提出含義：如果簡單循環(huán)以正常方式結(jié)束，則執(zhí)行中未遇到出口語句，則執(zhí)行ended后面的語句S0 ；若執(zhí)行中遇到某一出口語句exit，則跳去執(zhí)行Si 。:=exit :=|:= ： S1; ： Sn; ended: S0;for i:=1 to m do if Ai=x then go