第 2章
结构化程序
? 结构化程序的概念
? 程序标记法与流程图
? 程序函数与结构化定理
? 结构化程序设计方法
本章的主要内容
? 程序流程图也称程序框图，是用一种标准的图形
助记符表示编程思路的辅助手段，是一个描述程序
的控制流程和指令执行情况的有向图
? 将一个程序用流程图的形式表示，即为流程图程
序
? 一个流程图通常有 7种图形符号组成
流程图程序
流程图的符号组成
1,处理单元（ Process Box），也称 函
数结点,只有一个入口和一个出口线，
F是函数结点的名称，函数结点一般
和赋值语句对应。
F
流程图的符号组成
? 2,判 断单元（ Decision Box），也称 谓词
结点,有一个入口和两个出口线，且谓
词结点不改变变量的值（只作判断，不
做计算），一般对应条件语句。
P P
T
F
T
F
流程图的符号组成
3,连接单元 (Junction Box),也称 汇点 。 有两个入口和
一个出口线, 或者又一个入口和多个出口, 控制路径
在此聚会或者在此发散, 汇点不执行任何运算, 只是
一个简单的的结点 。
流程图的符号组成
4,流线（ Flow Lines），也称连接线，从一个处理单
元到另外一个处理单元，表示程序的运行方向。
5.开始单元（ Start Box）
表示为长圆形的符号及
其引出线，表示一个算
法流程图的逻辑起始点
流程图的符号组成
一般而言，一个程序的流程图主要由函数结点、
谓词结点、汇点组成，如下图：
p
q
h
g
正规程序
? 若一个流程图满足以下两个条件，称之
为正规程序：
（ 1）具有一个入口线和一个出口线
（ 2）对每一个结点，都有一条从入口线到
出口线的通路（流线）
正规程序
正规程序 非正规程序
正规程序与正规子程序
? 由于正规程序具有一个入口线和一个出
口线，因此，正规程序可以抽象为一个
函数结点。
? 若一个正规程序的某些部分仍然为正规
程序，则称为正规子程序
正规程序与正规子程序
? 由于正规程序具有一个入口线和一个出
口线，因此，正规程序可以抽象为一个
函数结点。
? 若一个正规程序的某些部分仍然为正规
程序，则称为正规子程序
正规程序与正规子程序实例
p
q
b
a
s
c
t
d
正规程序与正规子程序实例
k p
h
g
基本程序
? 对一个正规程序，如果不包含多于一个
节点的正规子程序，称为基本程序
? 基本程序是正规程序的一种，要求其包
含的正规子程序中不得多于一个结点，
实际上基本程序就是指一种不可再分解
的正规程序。
ba c
ba
q
a
q
b
a
基本程序实例
基本程序实例
p
h
g
p
q
h
g
r
基本程序与基集合
? 1,对程序结构的统计、分析表明：基本程序有
7种形式，进一步的理论可以证明：任何一个
结构化程序度可以用这 7种基本程序组成
? 2,实际构造一个程序时，可能只使用 7个基本
程序中的一部分，将用以构造程序的基本程序
的集合称为基集合
? 3,基集合的实例：
{序列,if-then-else,while-do}，或：
{序列,if-then-else,do-until}
基集合
返回
F函数
序列 F G
If-then
F
P
基集合
WHILE-DO P
F
DO-UNTIL PF
IF-THEN-ELSE
F
G
P
基集合
DO-WHILE-DO PF
G
结构化程序
? 如果一个基本程序的函数结点用另一个基
本程序替换，就产生了一个新的正规程序，这
样的程序称为复合程序。
? 复合程序的规模及复杂程度取决于所使用
的基集合，例如,{序列,IF-THEN-ELSE }产
生一个无循环的程序类。
? 抽象地说, 由基本程序的一个固定的基集合构
造出的复合程序称为结构化程序 。
程序函数
? 1） 程序函数
? 对于一正规程序 P,设每一个初始的数据状态
为 X,若程序是终止的, 则确定的最终数据状
态为 Y。 如果对于每一个给定的 X,值 Y是唯一
的, 那么所有的有序对的集合 {（ X,Y） }定义
了一个函数 。 称这个函数为程序 P的程序函数,
记为 [P]。
? 2） 程序函数实例 1
? 程序 P:
? t:=x;
? x:=y;
? y:=t;
程序函数
则对于任意的 X,(x,y,t),执行结果 Y为：
(y,x,x),程序函数为,{（ (x,y,t),(y,x,x)） }
? 程序函数实例 2
? If x<y then z:=x
? Else z:=y
程序函数为,{（ (x,y,z),(x,y,min(x,y)） }
程序函数
也可以直接写为数据赋值的形式：
(z:=min(x,y))
? 程序函数一般用有序对和数据赋值两种
形式表示
? 程序函数是对程序功能的一个精确的描
述，如果两个程序有相同的程序函数，
则可以认为这两个程序所完成的功能是
相同的
程序函数与结构化定理
如果程序 P1和 P2有相同的程序函数，则认
为 P1,P2是函数等价的，或者说 P1,P2
是等价的。
结构化定理：任一正规程序度可以函数等
价于一个由基集合｛序列,if-then-
else,while-do}产生的结构化程序，也即
任一正规程序都可以转换为一个等价的
结构化程序。
结构化定理的证明
（ 1） 从程序的入口处开始给程序的函数结点和谓词结
点编号，编号为 1,2,……, n(如果是汇点，那么沿
汇点的出口线继续考察，直到找到第一个函数结点或
谓词结点 )。
（ 2）将每一个函数及谓词结点的出口线用它后面的节
点的号码进行编号。如果他后面没有函数或谓词结点，
即该结点的出口线直接或通过汇点和程序的出口相连
时，出口线编号记为 0
结构化定理的证明
h
i
j
h L:=j
i
gi
(3) 对原程序中的每一个编号为 i，出口线
编号为 j的函数节点 h，构造一个新的序列
程序 gi
结构化定理的证明
(4) 对原程序中的每一个编号为 i，出口线
编号分别为 j,k的谓词结点 p，构造一个
新的 if-then-else程序 gi
P
P
L:=j
L:=k
i
k
j
i
gi
结构化定理的证明
(5) 利用新产生的 gi(i＝ 1,2,3,…,n为函数
结点与谓词结点的个数 )构造一个 while-
do循环，其循环体为一个对 L从 1到 n进行
测试的嵌套 if-then-else程序。
结构化定理的证明
L=n
gn
I
L=n-
1
gn-1
L=
2
g2L=1
g1
L>
0
L:=1
…… ……
结构化定理的证明
显然，转化后的程序与原程序的功能是相同
的，是函数等价的，而且是由基集合｛序列,if-
then-else,while-do}产生的结构程序。
结构化定理的证明过程实际上提供了一种将
正规程序转化为结构化程序的方法。
可以证明：基集合｛序列,if-then-
else,while-do}不是唯一的，如也可以用序列,if-
then-else,do-until}来表示一个正规程序。
正规程序到结构化程序的转换
q
e
p
h
1 3
4
2
正规程序到结构化程序的转换
P
L:=2
L:=3
Q
L:=0
L:=4
e L:=0 h L:=1
g1=
g4=
g3=
g2=
正规程序到结构化程序的转换
L=4
I
L=3
L=
2
e
L=
1
L>
0
L:=1
h L:=1
q
L:=0
L:=4
L:=0
P
L:=2
L:=3
对转换方法的改进－－递归结构程序
? 显然，利用上述方法的结构程序很庞大，效率
也不高，可以采用递归结构程序予以改进。基
本思想：尽可能消除多余的对 L赋值和测试。
? 改进过程：对于某些 j〉 0，如果在 gj中不包含
有赋值 L:=j，则可以用程序 gj代替所有的赋值
L:=j。代替以后，由于 j不再赋值给 L，因而测
试 L=j可以从 if-then-else结构中去掉。
对转换方法的改进－－递归结构程序
? 替换过程可以一直继续到下面两种情况出现为止：
? a)除了 L:=0以外, 所有的给 L的赋值均被消除；
? b) 每一个余下的 gi’中都包含有相应的赋值 L:=i。
? 采用以上步骤得到的程序通常称为递归结构程序 。
对转换方法的改进－－递归结构程序
? 第一步，用 g4代替赋值 L:=4，并且消除对 L=4的 测试,得到,
I
L=3
L=
2
e
L=
1
L>
0
L:=1 q
L:=0
L:=1
L:=0
P
L:=2
L:=3
h
对转换方法的改进－－递归结构程序
? 第二步, 用代换后的 g3’,即 L=3通路上的 if-then-else程序代替
赋值 L:=3,并且消除测试 L=3,得到：
I
L>
0
L:=1
q
L:=0
L:=1
P
L:=2
h
L=
1
L=
2
e L:=0
对转换方法的改进－－递归结构程序
? 第三步, 用 g2代替赋值 L:=2,得到,
I
L >0
L, =1
L, =0
L, =1
q
P
h
L =1
e L, =0
对转换方法的改进－－递归结构程序
? 由于转换以后的 g1’ 包含赋值 L:=1,故不能再进一步替换, 考
虑到 L只是在程序的出口处才变为 0,因而可消去赋值 L:=1及对
? L=1的测试。进一步可简化为：
L > 0 L, = 1
L, = 0
q
P
h
e L, = 0
对转换方法的改进－－递归结构程序
? 实际对应的程序是：
? L:=1;
? while L>0 do
? Begin
? if p then
? begin
? e;
? L:=0;
? end;
? else
? begin
? if q then
? L:=0;
? else
? h;
? end;
? End.
对转换方法的改进－－递归结构程序
另一个例子：
r
hq
42
p
g
f
k
1
6
3 5 7
对转换方法的改进－－递归结构程序
h
L>0L:=1
q
L:=6
L:=5
L:=5
L:=4f
g
P
L:=2
L:=3
r
L:=6
L:=7
L:=0
L:=0
k
L
1
2
3
4
5
6
7
对转换方法的改进－－递归结构程序
k
L>0L:=1
q
q
L:=0h
L=
1
h
rg
L:=0
L:=0k
h
r
L:=0
L:=0
I
f
对转换方法的改进－－递归结构程序
g
p
h
f q
k
r
h
r
k
h
结构化程序设计 — 概述
? 结构化程序设计是一种进行程序设计的原则和
方法，按该原则和方法设计的程序具有结构清
晰、容易阅读、容易修改、容易验证的特点。
? 支持结构化设计的程序设计语言称为结构程序
设计语言，如 PASCAL,C,Ada
? 按照结构程序设计的思想编制的程序称为结构
化程序，或称之为结构, 好, 的程序
? 结构化程序设计方法的基本特征：
结构化程序设计 — 基本特征
? 结构化程序设计的内涵和外延一直有争议的，
还没有一个严格的、并能为大家普遍接受的定
义，主要特征有：
? 结构化程序设计是指导我们编写程序的一般方
法，利用他编制的程序是容易理解和维护的
? 结构化程序设计避免使用 GOTO语句
? 结构化程序设计采用自顶向下逐步求精的程序
设计方式
? 结构化程序设计把任意大且复杂的流程图转变
为标准形式，以便用循环表示，并嵌套为少数
基本且标准的控制逻辑结构（基集合，如序列、
选择、循环）
结构化程序设计 — 基本特征
? 结构化程序设计的一个主要功能实施的
正确性的证明容易实现
? 从另一个角度说，结构化程序设计有：
? 1.模块化
? （ 1） 把一个大的程序划分为若干个子程序，
每个子程序独立成为一个模块
? （ 2）每个模块又可以继续划分为更小的模块
? （ 3）程序呈现层次结构
结构化程序设计 — 基本特征
? 2.自顶向下
? （ 1） 先设计第一层（顶层），再逐层细分，逐步求
精，直到整个程序可用程序设计语言明确地表示为止
? （ 2）程序设计过程：
? A,分析问题
? 先对问题进行仔细分析，明确题目的要求，列出所有
已知量，找出题目的求解范围、解的精度等
? B.建立数学模型
? 在对实际问题分析后，找出其内在规律，建立数学模
型，只有建立的模型的问题，才便于利用计算机编程
来求解
结构化程序设计 — 基本特征
? C,选择算法
? 建立数学模型后，先不忙着手写代码，而应该根据数
据结构，选择解决问题的算法，选择算法的主要原则：
? a,算法的逻辑结构尽可能简单
? b,算法所要求的存储量应尽可能少
? c,避免不必要的循环，减少算法的执行时间
? D,编写程序
? 自顶向下，先全局后局部，先抽象后具体，逐层逐个
模块编写，如果某些子问题的算法相同而仅参数不同，
可考虑用子程序来表示
结构化程序设计 — 基本特征
? E,调试运行
? F,分析结果
? G,编写文档
结构化程序设计 — 基本特征
? 2.自底向上
? 先设计底层，最后设计顶层
? 自底向上是面向对象程序设计的基本方
法，结构化程序设计一般不用，而且不
好用！
结构化程序设计 — 逐步求精法
? 逐步求精法是自顶向下设计方法的具体
实现。在编写一个程序时，首先考虑程
序的整体结构而忽视一些细节，然后逐
步地、一层一层地细化、完善程序直到
可用所选用的语言完全描述每一个细节，
即得到所期望的代码为止，在编写过程
中，一些算法可以采用编程者所能共同
接受的语言来描述（如类 PASCAL,UML、
甚至自然语言）。
结构化程序设计 — 逐步求精法
? 通常，第一步编出的程序最为抽象
? 第二步编出的程序是把第一步所编的程
序 (如子模块、函数、子程序 )细化，较为
抽象
? ……
? 第 I步编出的程序比第 I－ 1步抽象级要低
? ……
? 最后，第 N步编出的程序即为标准的可编
译（可执行）的源程序代码
结构化程序设计 — 逐步求精法
?,抽象”是指程序所描述的解决问题的处
理规则，是由哪些“作什么”操作组成，
而不涉及这些操作“怎么做”以及解决
问题的对象具有什么结构，不涉及构造
的每个局部细节
?,抽象”与“细化”是个相对的概念，
其粒度，逐步求精的步长等因人而异，
并无绝对的标准
结构化程序设计 — 逐步求精法实例 1
? 例 1：求两个自然数，其和是 667，最小公倍数
与最大公约数之比是 120,1。
? 逐步求精法的编程过程：
? 设两个自然数分别为 m和 667-m(2≤ m≤ 333)
? 处理对象,m(自然数 ),l(两数的最小公倍数 )、
g(两数的最大公约数 )
处理步骤：对 m从 2到 333检查 l与 g的商为 120，且
余数为 0时，打印 m与 667-m。
结构化程序设计 — 逐步求精法实例 1
? 第一层抽象程序：
? Program TwoNum;
? Var m,l,g:integer;
? Begin
? For m:=2 to 333 do
? begin
? l:=lcm(m,667-m);/求最小公倍数
? g:=gcd(m,667-m);/求最大公约数
? if(l=g*120)and(l mod g=0) then
? writenln(m:5,667-m:5);
? end
? End
结构化程序设计 — 逐步求精法实例 1
? 第二层抽象程序：
? 1,考虑函数 lcm（最小公倍数）与
? 2,考虑函数 gcd（最大公约数）的细化
? A.最小公倍数的算法：
? 对于两个自然数 a,b，对 a(或 b)累加，一
直到累加的和刚好被 b(或 a)整除为止，则
累加的和就是 a和 b的最小公倍数
结构化程序设计 — 逐步求精法实例 1
? B,函数 lcm（最小公倍数）的细化
?Function lcm(a,b:integer),integer;
?Var i:integer;
?Begin
? i:=b;
? while i mod a <> 0 do
? i:=i+b;
? lcm:=i;
?End
结构化程序设计 — 逐步求精法实例 1
? A,gcd（最大公约数）的细化 (算法 )
? 用辗转相除法求两个数的最大公约数的步骤如
下：
先用大的一个数除小的一个数，得第一个余数；
再用小的一个数除以第一个余数，得第二个余
数；
又用第一个余数除以第二个余数，得第三个余
数；
这样逐次用前一个余数除以后一个数，直到余
数是 0为止。那么，最后一个除数就是所求的
最大公约数（如果最后的除数是 1，那么原来
的两个数是互质数）。
结构化程序设计 — 逐步求精法实例 1
? B,函数 gcd（最大公约数）的细化
? Function gcd(a,b:integer),integer;
? Var i:integer;
? Begin
? while a mod b <> 0 do
? begin
? i:=b;
? b:= a mod b;
? a:=i;
? end
? gcd:=b;
? End
结构化程序设计 — 逐步求精法实例 2
? 例 2：确定并打印前 n个素数
? 第一步抽象：程序的整体
? Begin
? Read(n);
? number:=2;
? while number <n do
? begin
? if number 是一个素数 then write(number);
? number取下一个值；
? end
? End
结构化程序设计 — 逐步求精法实例 2
? 第二步抽象：细化,number 是一个素数,及
,number取下一个值”
? (1)细化,number 是一个素数,
? k:=2;/素数从 2开始
? lim:=number-1;／素数是只能被 1及其自身整除的自然数
? repeat /lim为参与除法的最大数
? if number 能被 k整除 then prim:=false／ prim是逻辑变量
? else begin
? k:=k+1;
? prim:=true;
? end
? until not(prim) or (k达到 lim);
结构化程序设计 — 逐步求精法实例 2
? (2)细化,number取下一个值”
? number:= number +1;
? 第三步抽象：细化,number能 k被整除”及,k达
到 lim”
? (1)细化,number能 k被整除”
? number mod k=0;
? (2)细化,k达到 lim”
? k=m;
? 第四步：补充完成整个程序
? 第五步：利用被求解问题的领域知识－数论知识
? 优化程序，如出了 2之外的素数都应该是奇数，用
number:= number +2，则可以减少一半计算量。
结构化程序设计 — 逐步求精法实例 2
? 完整的程序 ( pascal )
? Program A
? Var n,x,k,lim:Integer;
? prim:Boolean;
? Begin
? read(n);
? x:=1;
? write(2,’,’);
? while x+1<n do
? begin
? x:=x+1;
? k:=2;
? lim:=x-1;
? repeat
? If (x mod k)=0 then prim:=false;
? else begin
? k:=k+1;
? prim:=true;
? end
? until (not prim) or (k>=lim)
? if prim then write(x,’,’);
? end
? End
结构化程序设计 — 逐步求精法实例 2
? 完整的程序 (标准 C )
? #include <stdio.h>
#include <MATH.H> void Output();
int main(int argc,char* argv[])
{
printf("素数输出程序,\n");
Output();
return 0;
}
结构化程序设计 — 逐步求精法实例 2
? 完整的程序 (标准 C )
? #define N 10 //需要输出的素数个数
? void Output()
{
int i,k,lim,x;
bool prim;
int p[N]; //单独打印素数 2
p[0] = 2;
printf("第 %2d个素数 \t%2d\n",1,2); x = 1;
lim = 1;
for(i=1; i<N; i++)
{
prim = false;
while (!prim)
{
//自增 2以避免偶数被计算
x += 2;
//确定最佳上限
if (sqrt(p[lim - 1]) < x)
{
lim ++;
} k = 2;
prim = true; //循环直至有素数被发现
while (prim && k < lim)
{
prim = ((x % p[k - 1]) != 0);
k++;
}
} //打印素数
p[i] = x;
printf("第 %2d个素数 \t%2d\n",i+1,x);
结构化程序设计 — 逐步求精法实例 3
? 例 3 梵塔问题
1 32
c b
a
要求：将 a,b,c三个盘子从柱子 1移到柱
子 3，柱子 2为过渡，一次只能移动一个盘
子，而且在小盘子移动之前，不能移动大
盘子。（本问题可以将 3个盘子推广到任意
n个盘子）
结构化程序设计 — 逐步求精法实例 3
? 例 3 梵塔问题－－问题逐层分解过程
? 定义三元组（ i,j,k）分别对应 a,b,c三个盘子
的实际位置，初始位置为（ 1,1,1）,目的位置为
(3,3,3),逐层分解过程：
结构化程序设计 — 逐步求精法实例 3
(1,1,1) →(3,3,3)
逐层分解过程：
(1,1,1) →(1,2,2) (1,2,2) →(3,2,2) (3,2,2) →(3,3,3)
(1,1,1) →(1,1,3) (1,1,3) →(1,2,3) (1,2,3) →(1,2,2)
(3,2,2) →(3,2,1) (3,2,1) →(3,3,1) (3,3,1) →(3,3,3)
结构化程序设计 — 逐步求精法实例 3
? 试验 1：
? 1.用逐步求精法写出求解梵塔问题的过
程 (要求通用，即不限盘子的个数 )
? 2.编程实现（不限语言），打印出 n=3的
运行结果
? 作完后发到我的信箱
结构化程序设计 — 逐步求精法实例 3
? 逐步求精法的优点：
? （ 1）便于构造程序，由这种方法产生的程序，
其结构清晰、易读、易写、易理解、易调式和
维护；
? （ 2）适用于大任务、多人员、产业化设计，
也便于软件管理。是软件产业常用的生产方法
? 逐步求精法的缺点：
? （ 1）对系统层（顶层）分解的要求及依赖太
高，软件高层主管（金领、白领）对项目全局
的理解和把握很重要，容易返工；
? （ 2）有些软件的层次及模块化不明显，难于
逐层分解。
结构化程序设计 — 如何消除 GOTO语句
? GOTO语句对程序结构的危害性很大，使程序难以阅读，
难以查错，也不便于程序的正确性证明。
? 在程序设计中，要少用 GOTO语句，尤其不要使用往回
跳的 GOTO语句。
? 按照结构化程序设计的思想,GOTO是可以不存在的
（因为任何程序都可以用序列、条件、循环表示）。
? 少量的 GOTO语句降低程序的代码量及计算量，使程序
简单，消除 GOTO语句是保证程序结构优秀的手段，但
结构化不是以消去 GOTO语句为目的。主要的算法语言
均设有 GOTO语句。
? 在实际工作中，可采用增加辅助变量，或者改变程序
执行顺序的方法来消除 GOTO语句。
结构化程序设计 — 如何消除 GOTO语句
? 例 1
L1,if B1 then goto L2
? s1;
? if B2 then goto L2
? s2;
? goto L1;
? L2,s3;
? 问题：如何消去 GOTO语句？
结构化程序设计 — 如何消除 GOTO语句
? 引入逻辑变量 p，可建立等价的程序
? p:=true;
? while p do
? begin
? if B1 then p:=false;
? else
? begin
? s1;
? if B2 then p:=false;
? else s2;
? end
? end
? s3;/ 显然，为了消去 GOTO代码变长了，但结构变好了
结构化程序设计 — 如何消除 GOTO语句
? 例 2 数据结构中的查表程序：在一个表中有 m
个不同的数 A[1],A[2]… A[m]。要求在该表中
查找数 x，若找到，打印该数以及它在表中的
位置，否则将该数添加到表中去。
? （ 1）含有 GOTO语句的程序
for i:=1 to m do
? begin
? if A[i]=x then goto L1;
? end
? m:=m+1;
? A[m]:=x;
? Goto L2;
? L1,write(i,x);
? L2,stop;
结构化程序设计 — 如何消除 GOTO语句
? （ 2）采用逻辑变量消除 GOTO语句
? p:=false;
? for i:=1 to m do
? begin
? if A[i]=x then
? begin
? p:=true;
? y:=i;
? end
? end
? If p then write(y,x);
? else
? begin
? m:=m+1;
? A[m]:=x;
? end
?
结构化程序设计 — 如何消除 GOTO语句
? （ 3）采用改变程序执行的顺序来消除
GOTO语句
? ……
? i:=1;
? While(A[i] ≠x) ∧ (i<=m) do
? i:=i+1;
? If i>m then
? begin
? m:=m+1;
? A[m]:=x;
? end
? else write(i,x);
结构化程序设计 — 如何消除 GOTO语句
? 思考题：选用合适的方法消除 GOTO语句
PROC:
?switch(state){
Case STATE_ZOOMIN:
……;goto ERROR;
Case STATE_DRAWRECT:
……;goto ERROR;
……
}
ERROR,
……;
goto PROC;
结化程序设计 — 本章小结
? （ 1）结构化程序的概念
? 理解正规程序、正规子程序、基本程序、基集合、
复合程序、结构化程序等概念及其之间的关系
? （ 2）程序标记法与流程图
? 流程图的概念及 7种基本图元
? （ 3）程序函数与结构化定理
? 重点掌握利用结构化定理进行结构化程序的转换，
递归结构程序的转换方法（可选作教材 P38习题）
? （ 4）结构化程序设计方法
? 结构化程序的基本特征、优缺点、基本的设计方法，
重点掌握逐步求精法和消除 GOTO语句的基本方法。
结构化程序
? 结构化程序的概念
? 程序标记法与流程图
? 程序函数与结构化定理
? 结构化程序设计方法
本章的主要内容
? 程序流程图也称程序框图，是用一种标准的图形
助记符表示编程思路的辅助手段，是一个描述程序
的控制流程和指令执行情况的有向图
? 将一个程序用流程图的形式表示，即为流程图程
序
? 一个流程图通常有 7种图形符号组成
流程图程序
流程图的符号组成
1,处理单元（ Process Box），也称 函
数结点,只有一个入口和一个出口线，
F是函数结点的名称，函数结点一般
和赋值语句对应。
F
流程图的符号组成
? 2,判 断单元（ Decision Box），也称 谓词
结点,有一个入口和两个出口线，且谓
词结点不改变变量的值（只作判断，不
做计算），一般对应条件语句。
P P
T
F
T
F
流程图的符号组成
3,连接单元 (Junction Box),也称 汇点 。 有两个入口和
一个出口线, 或者又一个入口和多个出口, 控制路径
在此聚会或者在此发散, 汇点不执行任何运算, 只是
一个简单的的结点 。
流程图的符号组成
4,流线（ Flow Lines），也称连接线，从一个处理单
元到另外一个处理单元，表示程序的运行方向。
5.开始单元（ Start Box）
表示为长圆形的符号及
其引出线，表示一个算
法流程图的逻辑起始点
流程图的符号组成
一般而言，一个程序的流程图主要由函数结点、
谓词结点、汇点组成，如下图：
p
q
h
g
正规程序
? 若一个流程图满足以下两个条件，称之
为正规程序：
（ 1）具有一个入口线和一个出口线
（ 2）对每一个结点，都有一条从入口线到
出口线的通路（流线）
正规程序
正规程序 非正规程序
正规程序与正规子程序
? 由于正规程序具有一个入口线和一个出
口线，因此，正规程序可以抽象为一个
函数结点。
? 若一个正规程序的某些部分仍然为正规
程序，则称为正规子程序
正规程序与正规子程序
? 由于正规程序具有一个入口线和一个出
口线，因此，正规程序可以抽象为一个
函数结点。
? 若一个正规程序的某些部分仍然为正规
程序，则称为正规子程序
正规程序与正规子程序实例
p
q
b
a
s
c
t
d
正规程序与正规子程序实例
k p
h
g
基本程序
? 对一个正规程序，如果不包含多于一个
节点的正规子程序，称为基本程序
? 基本程序是正规程序的一种，要求其包
含的正规子程序中不得多于一个结点，
实际上基本程序就是指一种不可再分解
的正规程序。
ba c
ba
q
a
q
b
a
基本程序实例
基本程序实例
p
h
g
p
q
h
g
r
基本程序与基集合
? 1,对程序结构的统计、分析表明：基本程序有
7种形式，进一步的理论可以证明：任何一个
结构化程序度可以用这 7种基本程序组成
? 2,实际构造一个程序时，可能只使用 7个基本
程序中的一部分，将用以构造程序的基本程序
的集合称为基集合
? 3,基集合的实例：
{序列,if-then-else,while-do}，或：
{序列,if-then-else,do-until}
基集合
返回
F函数
序列 F G
If-then
F
P
基集合
WHILE-DO P
F
DO-UNTIL PF
IF-THEN-ELSE
F
G
P
基集合
DO-WHILE-DO PF
G
结构化程序
? 如果一个基本程序的函数结点用另一个基
本程序替换，就产生了一个新的正规程序，这
样的程序称为复合程序。
? 复合程序的规模及复杂程度取决于所使用
的基集合，例如,{序列,IF-THEN-ELSE }产
生一个无循环的程序类。
? 抽象地说, 由基本程序的一个固定的基集合构
造出的复合程序称为结构化程序 。
程序函数
? 1） 程序函数
? 对于一正规程序 P,设每一个初始的数据状态
为 X,若程序是终止的, 则确定的最终数据状
态为 Y。 如果对于每一个给定的 X,值 Y是唯一
的, 那么所有的有序对的集合 {（ X,Y） }定义
了一个函数 。 称这个函数为程序 P的程序函数,
记为 [P]。
? 2） 程序函数实例 1
? 程序 P:
? t:=x;
? x:=y;
? y:=t;
程序函数
则对于任意的 X,(x,y,t),执行结果 Y为：
(y,x,x),程序函数为,{（ (x,y,t),(y,x,x)） }
? 程序函数实例 2
? If x<y then z:=x
? Else z:=y
程序函数为,{（ (x,y,z),(x,y,min(x,y)） }
程序函数
也可以直接写为数据赋值的形式：
(z:=min(x,y))
? 程序函数一般用有序对和数据赋值两种
形式表示
? 程序函数是对程序功能的一个精确的描
述，如果两个程序有相同的程序函数，
则可以认为这两个程序所完成的功能是
相同的
程序函数与结构化定理
如果程序 P1和 P2有相同的程序函数，则认
为 P1,P2是函数等价的，或者说 P1,P2
是等价的。
结构化定理：任一正规程序度可以函数等
价于一个由基集合｛序列,if-then-
else,while-do}产生的结构化程序，也即
任一正规程序都可以转换为一个等价的
结构化程序。
结构化定理的证明
（ 1） 从程序的入口处开始给程序的函数结点和谓词结
点编号，编号为 1,2,……, n(如果是汇点，那么沿
汇点的出口线继续考察，直到找到第一个函数结点或
谓词结点 )。
（ 2）将每一个函数及谓词结点的出口线用它后面的节
点的号码进行编号。如果他后面没有函数或谓词结点，
即该结点的出口线直接或通过汇点和程序的出口相连
时，出口线编号记为 0
结构化定理的证明
h
i
j
h L:=j
i
gi
(3) 对原程序中的每一个编号为 i，出口线
编号为 j的函数节点 h，构造一个新的序列
程序 gi
结构化定理的证明
(4) 对原程序中的每一个编号为 i，出口线
编号分别为 j,k的谓词结点 p，构造一个
新的 if-then-else程序 gi
P
P
L:=j
L:=k
i
k
j
i
gi
结构化定理的证明
(5) 利用新产生的 gi(i＝ 1,2,3,…,n为函数
结点与谓词结点的个数 )构造一个 while-
do循环，其循环体为一个对 L从 1到 n进行
测试的嵌套 if-then-else程序。
结构化定理的证明
L=n
gn
I
L=n-
1
gn-1
L=
2
g2L=1
g1
L>
0
L:=1
…… ……
结构化定理的证明
显然，转化后的程序与原程序的功能是相同
的，是函数等价的，而且是由基集合｛序列,if-
then-else,while-do}产生的结构程序。
结构化定理的证明过程实际上提供了一种将
正规程序转化为结构化程序的方法。
可以证明：基集合｛序列,if-then-
else,while-do}不是唯一的，如也可以用序列,if-
then-else,do-until}来表示一个正规程序。
正规程序到结构化程序的转换
q
e
p
h
1 3
4
2
正规程序到结构化程序的转换
P
L:=2
L:=3
Q
L:=0
L:=4
e L:=0 h L:=1
g1=
g4=
g3=
g2=
正规程序到结构化程序的转换
L=4
I
L=3
L=
2
e
L=
1
L>
0
L:=1
h L:=1
q
L:=0
L:=4
L:=0
P
L:=2
L:=3
对转换方法的改进－－递归结构程序
? 显然，利用上述方法的结构程序很庞大，效率
也不高，可以采用递归结构程序予以改进。基
本思想：尽可能消除多余的对 L赋值和测试。
? 改进过程：对于某些 j〉 0，如果在 gj中不包含
有赋值 L:=j，则可以用程序 gj代替所有的赋值
L:=j。代替以后，由于 j不再赋值给 L，因而测
试 L=j可以从 if-then-else结构中去掉。
对转换方法的改进－－递归结构程序
? 替换过程可以一直继续到下面两种情况出现为止：
? a)除了 L:=0以外, 所有的给 L的赋值均被消除；
? b) 每一个余下的 gi’中都包含有相应的赋值 L:=i。
? 采用以上步骤得到的程序通常称为递归结构程序 。
对转换方法的改进－－递归结构程序
? 第一步，用 g4代替赋值 L:=4，并且消除对 L=4的 测试,得到,
I
L=3
L=
2
e
L=
1
L>
0
L:=1 q
L:=0
L:=1
L:=0
P
L:=2
L:=3
h
对转换方法的改进－－递归结构程序
? 第二步, 用代换后的 g3’,即 L=3通路上的 if-then-else程序代替
赋值 L:=3,并且消除测试 L=3,得到：
I
L>
0
L:=1
q
L:=0
L:=1
P
L:=2
h
L=
1
L=
2
e L:=0
对转换方法的改进－－递归结构程序
? 第三步, 用 g2代替赋值 L:=2,得到,
I
L >0
L, =1
L, =0
L, =1
q
P
h
L =1
e L, =0
对转换方法的改进－－递归结构程序
? 由于转换以后的 g1’ 包含赋值 L:=1,故不能再进一步替换, 考
虑到 L只是在程序的出口处才变为 0,因而可消去赋值 L:=1及对
? L=1的测试。进一步可简化为：
L > 0 L, = 1
L, = 0
q
P
h
e L, = 0
对转换方法的改进－－递归结构程序
? 实际对应的程序是：
? L:=1;
? while L>0 do
? Begin
? if p then
? begin
? e;
? L:=0;
? end;
? else
? begin
? if q then
? L:=0;
? else
? h;
? end;
? End.
对转换方法的改进－－递归结构程序
另一个例子：
r
hq
42
p
g
f
k
1
6
3 5 7
对转换方法的改进－－递归结构程序
h
L>0L:=1
q
L:=6
L:=5
L:=5
L:=4f
g
P
L:=2
L:=3
r
L:=6
L:=7
L:=0
L:=0
k
L
1
2
3
4
5
6
7
对转换方法的改进－－递归结构程序
k
L>0L:=1
q
q
L:=0h
L=
1
h
rg
L:=0
L:=0k
h
r
L:=0
L:=0
I
f
对转换方法的改进－－递归结构程序
g
p
h
f q
k
r
h
r
k
h
结构化程序设计 — 概述
? 结构化程序设计是一种进行程序设计的原则和
方法，按该原则和方法设计的程序具有结构清
晰、容易阅读、容易修改、容易验证的特点。
? 支持结构化设计的程序设计语言称为结构程序
设计语言，如 PASCAL,C,Ada
? 按照结构程序设计的思想编制的程序称为结构
化程序，或称之为结构, 好, 的程序
? 结构化程序设计方法的基本特征：
结构化程序设计 — 基本特征
? 结构化程序设计的内涵和外延一直有争议的，
还没有一个严格的、并能为大家普遍接受的定
义，主要特征有：
? 结构化程序设计是指导我们编写程序的一般方
法，利用他编制的程序是容易理解和维护的
? 结构化程序设计避免使用 GOTO语句
? 结构化程序设计采用自顶向下逐步求精的程序
设计方式
? 结构化程序设计把任意大且复杂的流程图转变
为标准形式，以便用循环表示，并嵌套为少数
基本且标准的控制逻辑结构（基集合，如序列、
选择、循环）
结构化程序设计 — 基本特征
? 结构化程序设计的一个主要功能实施的
正确性的证明容易实现
? 从另一个角度说，结构化程序设计有：
? 1.模块化
? （ 1） 把一个大的程序划分为若干个子程序，
每个子程序独立成为一个模块
? （ 2）每个模块又可以继续划分为更小的模块
? （ 3）程序呈现层次结构
结构化程序设计 — 基本特征
? 2.自顶向下
? （ 1） 先设计第一层（顶层），再逐层细分，逐步求
精，直到整个程序可用程序设计语言明确地表示为止
? （ 2）程序设计过程：
? A,分析问题
? 先对问题进行仔细分析，明确题目的要求，列出所有
已知量，找出题目的求解范围、解的精度等
? B.建立数学模型
? 在对实际问题分析后，找出其内在规律，建立数学模
型，只有建立的模型的问题，才便于利用计算机编程
来求解
结构化程序设计 — 基本特征
? C,选择算法
? 建立数学模型后，先不忙着手写代码，而应该根据数
据结构，选择解决问题的算法，选择算法的主要原则：
? a,算法的逻辑结构尽可能简单
? b,算法所要求的存储量应尽可能少
? c,避免不必要的循环，减少算法的执行时间
? D,编写程序
? 自顶向下，先全局后局部，先抽象后具体，逐层逐个
模块编写，如果某些子问题的算法相同而仅参数不同，
可考虑用子程序来表示
结构化程序设计 — 基本特征
? E,调试运行
? F,分析结果
? G,编写文档
结构化程序设计 — 基本特征
? 2.自底向上
? 先设计底层，最后设计顶层
? 自底向上是面向对象程序设计的基本方
法，结构化程序设计一般不用，而且不
好用！
结构化程序设计 — 逐步求精法
? 逐步求精法是自顶向下设计方法的具体
实现。在编写一个程序时，首先考虑程
序的整体结构而忽视一些细节，然后逐
步地、一层一层地细化、完善程序直到
可用所选用的语言完全描述每一个细节，
即得到所期望的代码为止，在编写过程
中，一些算法可以采用编程者所能共同
接受的语言来描述（如类 PASCAL,UML、
甚至自然语言）。
结构化程序设计 — 逐步求精法
? 通常，第一步编出的程序最为抽象
? 第二步编出的程序是把第一步所编的程
序 (如子模块、函数、子程序 )细化，较为
抽象
? ……
? 第 I步编出的程序比第 I－ 1步抽象级要低
? ……
? 最后，第 N步编出的程序即为标准的可编
译（可执行）的源程序代码
结构化程序设计 — 逐步求精法
?,抽象”是指程序所描述的解决问题的处
理规则，是由哪些“作什么”操作组成，
而不涉及这些操作“怎么做”以及解决
问题的对象具有什么结构，不涉及构造
的每个局部细节
?,抽象”与“细化”是个相对的概念，
其粒度，逐步求精的步长等因人而异，
并无绝对的标准
结构化程序设计 — 逐步求精法实例 1
? 例 1：求两个自然数，其和是 667，最小公倍数
与最大公约数之比是 120,1。
? 逐步求精法的编程过程：
? 设两个自然数分别为 m和 667-m(2≤ m≤ 333)
? 处理对象,m(自然数 ),l(两数的最小公倍数 )、
g(两数的最大公约数 )
处理步骤：对 m从 2到 333检查 l与 g的商为 120，且
余数为 0时，打印 m与 667-m。
结构化程序设计 — 逐步求精法实例 1
? 第一层抽象程序：
? Program TwoNum;
? Var m,l,g:integer;
? Begin
? For m:=2 to 333 do
? begin
? l:=lcm(m,667-m);/求最小公倍数
? g:=gcd(m,667-m);/求最大公约数
? if(l=g*120)and(l mod g=0) then
? writenln(m:5,667-m:5);
? end
? End
结构化程序设计 — 逐步求精法实例 1
? 第二层抽象程序：
? 1,考虑函数 lcm（最小公倍数）与
? 2,考虑函数 gcd（最大公约数）的细化
? A.最小公倍数的算法：
? 对于两个自然数 a,b，对 a(或 b)累加，一
直到累加的和刚好被 b(或 a)整除为止，则
累加的和就是 a和 b的最小公倍数
结构化程序设计 — 逐步求精法实例 1
? B,函数 lcm（最小公倍数）的细化
?Function lcm(a,b:integer),integer;
?Var i:integer;
?Begin
? i:=b;
? while i mod a <> 0 do
? i:=i+b;
? lcm:=i;
?End
结构化程序设计 — 逐步求精法实例 1
? A,gcd（最大公约数）的细化 (算法 )
? 用辗转相除法求两个数的最大公约数的步骤如
下：
先用大的一个数除小的一个数，得第一个余数；
再用小的一个数除以第一个余数，得第二个余
数；
又用第一个余数除以第二个余数，得第三个余
数；
这样逐次用前一个余数除以后一个数，直到余
数是 0为止。那么，最后一个除数就是所求的
最大公约数（如果最后的除数是 1，那么原来
的两个数是互质数）。
结构化程序设计 — 逐步求精法实例 1
? B,函数 gcd（最大公约数）的细化
? Function gcd(a,b:integer),integer;
? Var i:integer;
? Begin
? while a mod b <> 0 do
? begin
? i:=b;
? b:= a mod b;
? a:=i;
? end
? gcd:=b;
? End
结构化程序设计 — 逐步求精法实例 2
? 例 2：确定并打印前 n个素数
? 第一步抽象：程序的整体
? Begin
? Read(n);
? number:=2;
? while number <n do
? begin
? if number 是一个素数 then write(number);
? number取下一个值；
? end
? End
结构化程序设计 — 逐步求精法实例 2
? 第二步抽象：细化,number 是一个素数,及
,number取下一个值”
? (1)细化,number 是一个素数,
? k:=2;/素数从 2开始
? lim:=number-1;／素数是只能被 1及其自身整除的自然数
? repeat /lim为参与除法的最大数
? if number 能被 k整除 then prim:=false／ prim是逻辑变量
? else begin
? k:=k+1;
? prim:=true;
? end
? until not(prim) or (k达到 lim);
结构化程序设计 — 逐步求精法实例 2
? (2)细化,number取下一个值”
? number:= number +1;
? 第三步抽象：细化,number能 k被整除”及,k达
到 lim”
? (1)细化,number能 k被整除”
? number mod k=0;
? (2)细化,k达到 lim”
? k=m;
? 第四步：补充完成整个程序
? 第五步：利用被求解问题的领域知识－数论知识
? 优化程序，如出了 2之外的素数都应该是奇数，用
number:= number +2，则可以减少一半计算量。
结构化程序设计 — 逐步求精法实例 2
? 完整的程序 ( pascal )
? Program A
? Var n,x,k,lim:Integer;
? prim:Boolean;
? Begin
? read(n);
? x:=1;
? write(2,’,’);
? while x+1<n do
? begin
? x:=x+1;
? k:=2;
? lim:=x-1;
? repeat
? If (x mod k)=0 then prim:=false;
? else begin
? k:=k+1;
? prim:=true;
? end
? until (not prim) or (k>=lim)
? if prim then write(x,’,’);
? end
? End
结构化程序设计 — 逐步求精法实例 2
? 完整的程序 (标准 C )
? #include <stdio.h>
#include <MATH.H> void Output();
int main(int argc,char* argv[])
{
printf("素数输出程序,\n");
Output();
return 0;
}
结构化程序设计 — 逐步求精法实例 2
? 完整的程序 (标准 C )
? #define N 10 //需要输出的素数个数
? void Output()
{
int i,k,lim,x;
bool prim;
int p[N]; //单独打印素数 2
p[0] = 2;
printf("第 %2d个素数 \t%2d\n",1,2); x = 1;
lim = 1;
for(i=1; i<N; i++)
{
prim = false;
while (!prim)
{
//自增 2以避免偶数被计算
x += 2;
//确定最佳上限
if (sqrt(p[lim - 1]) < x)
{
lim ++;
} k = 2;
prim = true; //循环直至有素数被发现
while (prim && k < lim)
{
prim = ((x % p[k - 1]) != 0);
k++;
}
} //打印素数
p[i] = x;
printf("第 %2d个素数 \t%2d\n",i+1,x);
结构化程序设计 — 逐步求精法实例 3
? 例 3 梵塔问题
1 32
c b
a
要求：将 a,b,c三个盘子从柱子 1移到柱
子 3，柱子 2为过渡，一次只能移动一个盘
子，而且在小盘子移动之前，不能移动大
盘子。（本问题可以将 3个盘子推广到任意
n个盘子）
结构化程序设计 — 逐步求精法实例 3
? 例 3 梵塔问题－－问题逐层分解过程
? 定义三元组（ i,j,k）分别对应 a,b,c三个盘子
的实际位置，初始位置为（ 1,1,1）,目的位置为
(3,3,3),逐层分解过程：
结构化程序设计 — 逐步求精法实例 3
(1,1,1) →(3,3,3)
逐层分解过程：
(1,1,1) →(1,2,2) (1,2,2) →(3,2,2) (3,2,2) →(3,3,3)
(1,1,1) →(1,1,3) (1,1,3) →(1,2,3) (1,2,3) →(1,2,2)
(3,2,2) →(3,2,1) (3,2,1) →(3,3,1) (3,3,1) →(3,3,3)
结构化程序设计 — 逐步求精法实例 3
? 试验 1：
? 1.用逐步求精法写出求解梵塔问题的过
程 (要求通用，即不限盘子的个数 )
? 2.编程实现（不限语言），打印出 n=3的
运行结果
? 作完后发到我的信箱
结构化程序设计 — 逐步求精法实例 3
? 逐步求精法的优点：
? （ 1）便于构造程序，由这种方法产生的程序，
其结构清晰、易读、易写、易理解、易调式和
维护；
? （ 2）适用于大任务、多人员、产业化设计，
也便于软件管理。是软件产业常用的生产方法
? 逐步求精法的缺点：
? （ 1）对系统层（顶层）分解的要求及依赖太
高，软件高层主管（金领、白领）对项目全局
的理解和把握很重要，容易返工；
? （ 2）有些软件的层次及模块化不明显，难于
逐层分解。
结构化程序设计 — 如何消除 GOTO语句
? GOTO语句对程序结构的危害性很大，使程序难以阅读，
难以查错，也不便于程序的正确性证明。
? 在程序设计中，要少用 GOTO语句，尤其不要使用往回
跳的 GOTO语句。
? 按照结构化程序设计的思想,GOTO是可以不存在的
（因为任何程序都可以用序列、条件、循环表示）。
? 少量的 GOTO语句降低程序的代码量及计算量，使程序
简单，消除 GOTO语句是保证程序结构优秀的手段，但
结构化不是以消去 GOTO语句为目的。主要的算法语言
均设有 GOTO语句。
? 在实际工作中，可采用增加辅助变量，或者改变程序
执行顺序的方法来消除 GOTO语句。
结构化程序设计 — 如何消除 GOTO语句
? 例 1
L1,if B1 then goto L2
? s1;
? if B2 then goto L2
? s2;
? goto L1;
? L2,s3;
? 问题：如何消去 GOTO语句？
结构化程序设计 — 如何消除 GOTO语句
? 引入逻辑变量 p，可建立等价的程序
? p:=true;
? while p do
? begin
? if B1 then p:=false;
? else
? begin
? s1;
? if B2 then p:=false;
? else s2;
? end
? end
? s3;/ 显然，为了消去 GOTO代码变长了，但结构变好了
结构化程序设计 — 如何消除 GOTO语句
? 例 2 数据结构中的查表程序：在一个表中有 m
个不同的数 A[1],A[2]… A[m]。要求在该表中
查找数 x，若找到，打印该数以及它在表中的
位置，否则将该数添加到表中去。
? （ 1）含有 GOTO语句的程序
for i:=1 to m do
? begin
? if A[i]=x then goto L1;
? end
? m:=m+1;
? A[m]:=x;
? Goto L2;
? L1,write(i,x);
? L2,stop;
结构化程序设计 — 如何消除 GOTO语句
? （ 2）采用逻辑变量消除 GOTO语句
? p:=false;
? for i:=1 to m do
? begin
? if A[i]=x then
? begin
? p:=true;
? y:=i;
? end
? end
? If p then write(y,x);
? else
? begin
? m:=m+1;
? A[m]:=x;
? end
?
结构化程序设计 — 如何消除 GOTO语句
? （ 3）采用改变程序执行的顺序来消除
GOTO语句
? ……
? i:=1;
? While(A[i] ≠x) ∧ (i<=m) do
? i:=i+1;
? If i>m then
? begin
? m:=m+1;
? A[m]:=x;
? end
? else write(i,x);
结构化程序设计 — 如何消除 GOTO语句
? 思考题：选用合适的方法消除 GOTO语句
PROC:
?switch(state){
Case STATE_ZOOMIN:
……;goto ERROR;
Case STATE_DRAWRECT:
……;goto ERROR;
……
}
ERROR,
……;
goto PROC;
结化程序设计 — 本章小结
? （ 1）结构化程序的概念
? 理解正规程序、正规子程序、基本程序、基集合、
复合程序、结构化程序等概念及其之间的关系
? （ 2）程序标记法与流程图
? 流程图的概念及 7种基本图元
? （ 3）程序函数与结构化定理
? 重点掌握利用结构化定理进行结构化程序的转换，
递归结构程序的转换方法（可选作教材 P38习题）
? （ 4）结构化程序设计方法
? 结构化程序的基本特征、优缺点、基本的设计方法，
重点掌握逐步求精法和消除 GOTO语句的基本方法。
