程序设计方法学-第二章结构化程序.pptx

第2章结构化程序

回顾学科地位程序设计语言和程序设计方法程序设计方法产生与发展程序设计方法学的定义与意义结构化程序设计及其讨论的主要问题

01?有哪些控制结构02?如何得到良结构的程序本章目标

010302什么是结构化程序结构化定理一些新的控制结构主要内容

什么是结构化程序流程图程序正规程序基本程序结构化程序结构化定理一些新的控制结构内容线索

流程图程序01流程图是一个描述程序的控制流程和指令执行情况的有向图。02函数结点：有一个入口和一个出口线的结点；03谓词结点：有一个入口和两个出口线，且它不改变程序的数据项的值的结点；（只作判断，不做计算）04汇点：两个入口和一个出口线，且它不执行任何运算的结点。

例子B1S1B2S2S3TTFFL1:ifB1thengotoL2;S1;ifB2thengotoL2;S2;gotoL1;L2:S3;

只有一个入口和一个出口对于每一个结点，都有一个从入口到出口的通路（即每个结点都可达）01则这个流程图程序称为正规程序。02一个流程图程序如果满足：正规程序

正规程序图例paqbstcdkpgh

正规子程序paqbstcd一个正规程序的某些部分仍然是正规程序，把这些部分称为正规子程序。

正规程序一个正规程序可以抽象为一个函数结点组成：正规子程序。bqapk抽象成=gbPqagg,b是k的正规子程序，函数结点a又是g的正规子程序

同步练习判断一个程序是否为正规程序的标准具有一个入口线和一个出口线；对每一个结点，都有一条入口线到出口线的通路通过该结点。（a）（b）（c）

基本程序…一个正规程序，如果不包含多于一个结点的正规子程序，称为基本程序。一个不可再分解的正规程序仅含一个正规子程序FFGFPPF

同步练习判断下列程序是正规程序，还是基本程序？010203040506

7种基本程序If-then-elseWhile-doDo-untilIf-thenDo-while-do函数序列

基集合为了构造一个程序，可以只使用七种基本程序中的一部分。基集合：用以构造程序的基本程序的集合。例如：{序列，if-then-else，while-do}或{序列，if-then-else，do-until}…

结构化程序定义:由基本程序的一个固定的基集合构造出的复合程序称为结构化程序。结构化程序就是我们通常说得好结构的程序。一个复合程序的规模可大可小。它的复杂程度依赖于所使用的基集合。如果一个基本程序的函数结点用另一个基本程序替换，就产生了一个新的正规程序，这样的程序称为复合程序。01基集合{序列，if-then-else}产生一个无循环的程序类基集合{序列，do-until}产生的程序类是由基集合{序列，if-then，while-do}产生的程序类的子集例如：02

什么是结构化程序01结构化定理程序函数结构化定理递归结构程序02一些新的控制结构03主要内容

程序函数1）程序函数已知一正归程序P，对于每一个初始的数据状态X，若程序是终止的，那么有确定的最终数据状态Y。如果对于每一个给定的X，值Y是唯一的，那么所有的有序对的集合{（X,Y）}定义了一个函数。我们称这个函数为程序P的程序函数，记为[P]。

PXY例：Ifxythenz=x;Elsez=y;程序函数1：{(x，y，z)，(x，y，min(x，y))}程序函数2：{z=min(x，y)}例：t:=x;x:=y;y:=t;程序函数为：{(x，y，t)，(y，x，x)}

程序函数表示形式：有序对、数据赋值以及条件规则等形式例如：[ifx?ythenz:=xelsez:=yfi]={((x,y,z),(x,y,min(x,y)))}//有序对的形式{(x,y,z)|x?y?z:=x?xy?z:=y}//条件规则的形式(z:=min(x,y))//数据赋值的形式

基本程序所对应的程序函数…函数：[f]={(x,y)|y=f(x)}序列：[f;g]={(x,y)|y=g?f(x)}IF-THEN:[if-then]={(x,y)|p(x)→y=f(x)|?p(x)→y=x}WHILE-DO:[while-do]={(x,y)|?k?0((?j,1?jk)(p?fj(x))??p?fk(x)→y=fk(x)}FFGPFg?f(x)表示函数的复合，即g(f(x))Fj(x)表示同一函数的多重复合，即f0(x)=x，fk(x)=f?fk-1(x),k=1,2,…FP

…基本程序