《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 1 页
手记1 程序规划方法漫谈
一、前言
“程序MATCH_
word
word文档格式规范word作业纸小票打印word模板word简历模板免费word简历
_1715976917615_3”的真谛是什么?许多初学者的理解是“写代码”。但是,在匠人看来,把
“程序设计”理解为“写代码”,就像把“电路设计”理解为“画 PCB”一样。
新手们苦恼的问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
是,他们只会“写代码”。他们一接到新的项目,总是在第一时间就
爬到键盘上去敲代码。新手们的精力总是比较旺盛,他们加班加点,两天就把所有代码敲完。
然后他们会用十倍或几十倍以上的时间去调试,中间伴随着几次三番的推倒重来。最后,他
们交出一个勉强能跑的程序。这种程序,外行乍一看,觉得还行;内行乍一看,却是吓出一
身冷汗!
这也许不能怪新手们,因为他们的老师还没有来得及教会他们“程序设计”的一些方法。
他们甚至还没有学会写注释,就已经毕业了。于是他们只能在毕业后的工作中,去完成这段
本该在学校里完成的修炼。
要说到程序设计,最重要的一种方法,就是“多思考”。偏偏这又是最难手把手地教的。
在此,匠人介绍一些设计时比较常用方法给大家。我们可以借助这些方法来对程序进行更高
效、更多维的规划。
二、程序流程图
1、从一个简单的流程图说起
我们先来看看这个图(参见图 1.1:一个程序流程图例子)。许多人都很熟悉,它的名
称叫“流程图”,或者“程序流程图”。程序流程图是一种传统的、人们对解决问题的方法、
思路或算法的一种描述。它利用图形化的符号框来代表各种不同性质的操作,并用流程线来
连接这些操作。
2、流程图的作用
流程图简单直观,应用广泛,功能卓越。
在程序的规划阶段,通过画流程图,可以帮助我们理清程序思路。尤其是在非结构化的
汇编语言中,流程图的重要性不言而喻。
在程序的调试、除错、升级、维护过程中,作为程序的辅助说明文档,流程图也是很高
效便捷的。
另外,在团队的合作中,流程图还是程序员们相互交流的重要手段。阅读一份简明扼要
的流程图,比阅读一段繁杂的代码更加易于理解。
3、流程图的作图符号
按道理,画流程图应该是每个程序员的基本功。匠人惊讶的是,居然有那么多人不会或
不屑于画流程图。
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 2 页
图 1.1:一个程序流程图例子
在这里,匠人罗列出一些流程图中常用的符号(参见图 1.2:常用的流程图符号)。
A、起止框、程序节点框
B、执行语句框
C、调用子程序框
D、条件判断框
E、散转判判断框
G、程序汇合连接点 H、数据输入、输出框 I、程序流程线
图 1.2:常用的流程图符号
细心的读者会发现,这里给出的一些流程图符号与教科书上的有点出入。
图 1.3:传统的条件判断框
比如说符号 D(条件判断框),书上给出的一般都是四角菱形的(参见图 1.3:传统的
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 3 页
条件判断框),而不是匠人推荐使用的六角菱形。匠人在实践中发现,容纳同样多的文字,
六角菱形比四角菱形可以节省更多的空间。这也就意味着我们可以在同样大小的幅面内画出
更多的内容。因此,除非是您公司里有明文规定必须使用四角菱形,否则就让教科书见鬼去
吧。
另一个不同点,就是如果程序中要调用一个子程序,那么最好给这个子程序一个特别的
符号,就像符号 C(调用子程序框)。这样做的好处是可以更有利于阅读。
4、画流程图软件
匠人推荐您用 Visio 软件来画流程图。这款软件功能非常强大,而画流程图只是它众多
功能中的一个。
您只需新建一个 Visio 文件,点击菜单“文件”-〉“形状”-〉“流程图”-〉“基本流程
图”,就可以得到许多现成的流程图符号。
在 Visio 画好的流程图,可以很方便地复制到 Word 环境中。并且可以在 Word 中进一步
进行修改编辑。
当然,如果您只是偶然画流程图,也可以用 Word 或 Excel 软件的画图功能来实现。它
们一样可以画流程图,只是没有那么专业罢了。
5、流程图的结构化
早期的非结构化语言中都有类似“goto”的语句。它允许程序从一个地方直接跳到另一
个地方去。而随着 C 语言的盛行,对程序的结构化要求,必然在流程图中得到体现。
经过研究,人们发现任何复杂的程序算法,都可以分解为顺序、选择(分支)和循环这
三种基本结构。基本结构之间可以并列、嵌套,但不允许交叉跳转。我们构造一个算法的时
候,也仅以这三种结构为构成单位,并遵守三种基本结构的
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
。
如果说“goto”是孙悟空的“筋斗云”,那么“结构化”就是“如来神掌”。也就是说,
不管你如何翻腾,也不能从一个结构直接跳转到另一个结构的内部去。呵呵!
这就是结构化编程的要求。它的好处就是结构清晰,易于正确性验证,易于纠错。
既然整个算法都是由三种基本结构组成的,那么,我们只要掌握这三种结构的流程图画
法,就可以画出任何算法的流程图,无往而不利了。
(1)顺序结构
图 1.4:顺序结构流程图
顺序结构是简单的线性结构,每条语句按顺序执行(参见图 1.4:顺序结构)。太简单
ShaoQian Xu
高亮
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 4 页
了,实在没啥好说(匠人在这里骗不到稿税了,呜呜!)。
(2)选择(分支)结构
选择(分支)结构是对某个给定条件进行判断,条件为“真”(满足)或为“假”(不
满足)时,分别执行不同的程序语句。当条件不满足时,有时需要执行一些语句,而有时可
能什么都不做,由此分化出两种形态。(参见图 1.5:选择(分支)结构)
图 1.5:选择(分支)结构流程图
对于简单的选择(if)结构,条件判断的结果只有 Yes 和 No 两种。而在更复杂的选择
结构中,比如说对某个表达式的值进行多重条件判断,结果就会有许多。假设这个表达式可
能=0、1、2、3、或者溢出,那么结果就有 5 个分支,我们可以用 4 个选择结构来实现这个
流程图(参见图 1.6:多重选择(分支)结构)。当然,我们也可以用一个散转(Switch)
结构来画(参见图 1.7:散转(switch)结构)。
图 1.6:多重选择(分支)结构流程图
图 1.7:散转(switch)结构流程图
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 5 页
(3)循环结构
循环结构的常见形态,包括当型(While)结构和直到型(Do-While)结构。
当型(While)循环结构中,是在每一轮循环的开始处执行条件判断,“当”条件满足
则继续执行循环体中的语句,否则跳出循环。(参见图 1.8:当型(while)循环结构)。
直到型(Do-While)循环结构中,是先执行循环体中的程序语句,然后再在循环结束处
进行条件判断,如果条件满足则继续开始新一轮循环,周而复始;“直到”条件不满足时跳
出循环。(参见图 1.9:直到型(do-while)循环结构)。
由于直到型循环结构是先执行语句,后进行条件判断,也就是说,在直到型循环结构中,
循环体中的语句起码会被执行 1 次。
图 1.8:当型(while)循环结构流程图
图 1.9:直到型(do-while)循环结构流程图
图 1.10:死循环例子
当条件判断的结果恒为“真”(Yes)时,循环就永远不会退出了。我们称之为“死循环”。
主程序(主函数)就是一个常见的死循环的例子。
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 6 页
一般情况下,我们要避免死循环的产生。因为这样会导致其它任务被挂起——除非我们
有意想那么做。举例说明:比如在掉电处理程序中,当我们检测到系统掉电信号后,需要预
先保存好系统设置、并关闭输出,然后执行一个空操作的死循环。这个时候,我们有意要把
所有任务挂起,让系统无牵无挂地、专心致志地“等死”(这就是“安乐死”,呵呵!)。
说到循环结构,还要额外说说 for 循环语句。因为今天在论坛里有网友问匠人怎么只介
绍了 while 循环和 do- while 循环,却没有介绍 for 循环。让我们先举个例子,先看看下面这
个 for 循环程序:
for(i=0;i
=N)时,结束循环。可以看出,for 循环其实就是
一个当型循环结构(参见图 1.11:for 循环例子)。
图 1.11:for 循环例子
6、流程图的人性化
程序是写给机器看的,因此必须严格遵循编程语言的规范,否则机器就无法解析执行。
而流程图则是写给人看的,因此应当尽可能地人性化。
让我们对比一下这两个流程图(参见图 1.12:“没人性”的流程图和图 1.13:人性化
的流程图)。它们描述的程序功能是一样的。
前者更简洁,但是却给阅读者带来了思维障碍,“Key_Flag”是什么标志?“P1.0”又
是什么功能的 IO 口?阅读者为了了解这些问题,不得不放下流程图去查阅相关的文档。阅
读思路的连贯性被打断了。
很显然,我们更喜欢第二个流程图。这才是无障碍的阅读。
不要吝啬那点打字的功夫,磨刀不误砍柴工。
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 7 页
Key_cnt
Key_Flag=1?N
Y
Key_Flag=0
P1.0=0?
Y
N
Delay_10ms()
P1.0=0?
Y
N
Do_key()
返回
P1.0=1?
P1.0=1?
Delay_10ms()
N
Y
N
Y
图 1.12:“没人性”的流程图
图 1.13:人性化的流程图
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 8 页
7、流程图的简化
一个繁琐的流程图,是画流程图的人的噩梦,同时也是阅读者所不愿意见到的。因此,
我们在画流程图时,不必拘泥于规则和形式,一板一眼。在适当的地方进行简化,不但可以
节省精力和幅面,而且可以让流程图更易于阅读。
让我们对比下面这两个图(参见图 1.14:繁琐的流程图和图 1.15:简洁的流程图)。
这是同一个程序的两种流程图表达方法。程序的功能,是用查询法对脉冲输入口上输入的脉
冲计数,当计数满 100 次后进行一些处理并退出。
很显然,第一个图占用了更多的幅面,却并不易于理解。而第二个图在经过简化处理后,
节省了空间,程序思路反而表达得更加清晰。
我们甚至可以进一步抛弃那些细微末节(参见图 1.16:更简洁的流程图)。反正这个流
程图是给人看的,只要看得懂程序思路,能简化何乐而不为呢?
简单的才是有效的。适当的简化,是人性化的体现。
图 1.14:繁琐的流程图
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 9 页
图 1.15:简洁的流程图
图 1.16:更简洁的流程图
总结一下简化的方法:
(1)合并那些相互关联的条件判断。比如:当“条件 1”满足,且“条件 2”满足执
行某个动作。我们可以把这两个条件判断合并后,放入同一个条件判断框中(参
见图 1.17:分支结构)。
图 1.17:分支结构的简化
(2)省去一些不必要的流程线。对于不会产生歧义的顺序结构流程,可以把那些箭
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 10 页
头省略。节省空间,甚至可以把一些语句合并在一个执行语句框里面。(参见图
1.18:顺序结构的简化)
图 1.18:顺序结构的简化
三、N-S 图(盒图)
1、N-S 图简介
前面讲到流程图的简化时,匠人已经说过:可以把一些不会产生歧义的流程线(箭头)
省略。持这种想法的显然不止是匠人一个,据说有两个美国佬走得更远。这两位名叫 I.Nassi
和 B.Shneiderman 的“国际友人”经过潜心研究发现了个规律:既然任何算法都是由前面介
绍的三种基本结构组成,那么各基本结构之间的流程线就是多余的。
于是他们设计了一种新的算法表示法。用若干个大大小小的框图,通过堆砌或嵌套,来
表示程序的流程。这种流程图被以两个美国天才的名字命名为“N-S 图”。(匠人发现天才也
得赶早,否则好事都会被别人抢了去!)
那一个个框,就像一个个封闭的盒子。所以,N-S 图又被形象地称为“盒图”。
N-S 图(盒图)的特性就像盒子一样,结构性很强。由于取消了流程线,象“goto”这
样乱跳的语句,也就没有了表达的形式。所以,N-S 图又被人称为是“结构化流程图”。也
就是说,对于传统的流程图,结构化编程依赖于程序员的自觉自律;而对于 N-S 图,结构
化编程则是由绘图规则来强制保证的。你想不结构化都不行,呵呵。N-S 图除了表示几种标
准结构的符号之处,不再提供其他如“流程线”这样的描述符号,这就有效地保证程序的质
量。
NS 图的另一个优点是形象直观。例如循环的范围、条件语句的范围都是一目了然的,
所以容易理解设计意图,为编程、排错、调试、维护都带来了便利。
2、N-S 图的画法
在 N-S 图中,一个算法就是一个大矩形框,框内又包含若干小框。其实只要掌握 N-S
图的 3 个基本结构画法,即可掌握 N-S 图。匠人在这里简单介绍如下:
(1)顺序结构
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 11 页
顺序结构(参见图 1.19:顺序结构 N-S 图),语句 1、语句 2、语句 3 依次执行。
图 1.19:顺序结构 N-S 图
(2)选择(分支)结构
选择结构(参见图 1.20:选择(分支)结构 N-S 图),条件为真时执行语句 1,条件为
假时执行语句 2。如果条件为假时不需执行任何语句,则对应的执行语句框中留空。
图 1.20:选择(分支)结构 N-S 图
散转(Switch)结构作为选择(分支)结构的一个特例,在 N-S 图方法中较少被人提及。
其实可以用下面这种方法来画(参见图 1.7:散转(switch)结构)。当表达式结算结果等
于某个对应的值时,执行该值下面的语句。
图 1.21:散转(switch)结构 N-S 图
(3)循环结构
循环结构的两种常见形态,包括当型结构(参见图 1.22:当型(while)循环结构 N-S
图)和直到型结构(参见图 1.23:直到型(do-while)循环结构 N-S 图)。
图 1.22:当型(while)循环结构 N-S 图
图 1.23:直到型(do-while)循环结构 N-S 图
3、N-S 图的实例
我们把前面介绍过的一个“按键处理子程序”的流程图(参见图 1.13:人性化的流程
图),用 N-S 图形式再来画一次,如下图(参见图 1.24:按键处理子程序 N-S 图):
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 12 页
图 1.24:按键处理子程序 N-S 图
4、N-S 图的软肋
说了半天 N-S 图的花好稻好,那为什么在设计中,还是有许多人却放弃使用 N-S 图,
仍旧选择了落后的带箭头的流程图呢?这得说说 N-S 图的软肋。
要说这 N-S 图最大的缺点,就是手工画图时,修改起来没有流程图方便。尤其是在分
支嵌套层次较多时,就比较难画了。
手工画图不便,计算机画图也不便。目前,匠人也没有找到比较适合画 N-S 图的计算
机绘图软件。
这些,可能是阻碍 N-S 图进一步推广应用的原因。
四、PAD 图(问题分析图)
1、PAD 图简介
前面介绍的流程图和 N-S 图,都是自上而下的顺序描述(流程图也可以画成从左往右
或从下往上的形式,不过那不太符合常规习惯)。这种一维的算法描述方法只能表示程序的
流向,而忽视了程序的层次。
为了避免它们的缺陷。在上世纪七八十年代,日本日立公司发明了一种“问题分析法”
PAM(Problem Analysis Method),基于这种方法,他们提出了 PAD 图,即“问题分析图”
(Problem Analysis Diagram)。
PAD 图用二维树形结构图来表示程序的控制流,除了自上而下以外,还有自左向右的
展开。PAD 的强项是能够展现算法的层次结构,更直观易懂。据说是到目前为止最好的详
细设计表示方法之一。
PAD 图的优点如下:
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 13 页
(1)结构化的算法描述方法,有效保证程序质量;
(2)二维树型结构,层次清晰,结构明显,表达直观;
(3)既可用于表示程序流程,也可用于描述数据结构;
(4)支持自顶向下、逐步求精方法的使用。
2、PAD 图的画法
前面已经反复介绍过结构化编程的三种基本结构了,此处不再浪费文字,直接上图。
(1)顺序结构
图 1.25:顺序结构 PAD 图
(2)选择(分支)结构
图 1.26:选择(分支)结构 PAD 图
图 1.27:散转(switch)结构 PAD 图
(3)循环结构
图 1.28:当型(while)循环结构 PAD 图
图 1.29:直到型(do-while)循环结构 PAD 图
3、N-S 图的实例
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 14 页
我们把前面已经画过 N 遍的 “按键处理子程序”的流程图用 PAD 图形式再来画一次(参
见图 1.30:按键处理子程序 PAD 图),请读者对比一下流程图、N-S 图、PAD 三者间的一
些区别。
图 1.30:按键处理子程序 PAD 图
读者如果没有接触过 PAD 图,可能一下不太适应。那就让我们通过这个例图来看看 PAD
的执行顺序(参见图 1.31:按键处理子程序 PAD 图的执行顺序)。具体的流程见图中的虚线
箭头,不同粗细的虚线代表不同层次的流程。
=1(有效)
按键处理
使能标志
=0(无效)
Y
按键闭合?
N
10毫秒消抖延时
Y
按键闭合?
N
执行按键功能
直到型循环:
按键释放后退出
10毫秒消抖延时
按键处理
使能标志=0
直到型循环:
按键释放后退出
按键
处理
返回
图 1.31:按键处理子程序 PAD 图的执行顺序
从最左主干线的上端的结点开始,自上而下依次执行。每遇到分支或循环结构,就自左
而右进入下一层。从表示下一层的纵线上端开始执行,直到该纵线下端,再返回上一层的纵
线的转入处。如此继续,直到执行到主干线的下端为止。
如果仔细观察一下 PAD 图的层次结构,就会发现它的层次与 C 语言程序的语法缩进层
次是对应一致的。这正是我们一直在强调的 PAD 的特色。
五、数据流图(DFD)
1、数据流图简介
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 15 页
前面介绍的三种程序规划方法,都是从算法的角度来分解程序的流程。然而,把程序或
软件理解为算法是片面的。完整的理解是:“程序=数据结构+算法”。因此在程序规划的过
程中,我们可以从另一个角度——数据的流向——来分析系统。
这就是这一节要介绍的数据流图。
数据流图,即 DFD(data flow diagram),又被称为数据流程图。是软件需求分析阶段的
重要描述手段。
数据流图是从数据流向的角度来描写软件功能要求系统的组成和各部分之间联系的一
种方法。它的具有直观、简洁等优点,软件开发人员及用户易于理解和接受。
2、数据流图的 4 要素
在匠人看到的一些资料文献中一般都把数据流图分解为外部实体(数据源和数据终点)、
处理(加工)过程、数据流、数据存储(文件)等四部分。下面依次介绍:
(1)外部实体:又被称为数据源(输入实体)和数据终点(输出实体)。代表了数据
的外部来源和去处。也就是说,外部实体属于系统的外部和界面。它是独立于
系统之外,但又和系统有联系的人或事物。
(2)处理过程:是对数据进行加工的环节。这种加工处理包括算术、逻辑运算处理,
或者进行数据变换。它用来改变数据值。每一个处理过程又包括了数据输入、
加工和输出 3 个部分。
(3)数据流:代表数据处理过程的输入或输出。数据流指示了数据在系统中的传递
流向。
(4)数据存储:代表数据保存的地方,它用来存储数据。系统处理从数据存储中提
取数据,也将处理的数据返回数据存储。
以上介绍的这四个部分又被称为数据流图的 4 要素。
3、数据流图的画法
在不同的文献中,对 4 个要素的定义和描述都不同,甚至连它们的画法也不完全统一。
下面是数据流图的常见画法(参见图 1.32:数据流图举例):
图 1.32:数据流图举例
数据流图的画法没有完全统一的规范,不过这并不影响我们用这一工具来分析我们程序
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 16 页
中的数据流向。
4、数据流图的应用
软件中除了“程序流程”这条显性的主线,还有另一条隐性的主线,就是“数据流向”。
之所以说“数据流向”这条主线是隐性的,那是因为在系统中,对一个特定数据的输入、处
理、存储、输出等过程,往往被分散在许多模块中。
“数据流向”很难通过流程图来描述。甚至于你把流程图画的越详细,“数据流向”这
条线索就越发显得不够清晰。这时,我们就可以考虑用数据流图来描述,使得“数据流向”
显得脉络清晰。
举一个例子,比如一个简单的温度检测与控制系统。整个过程包括以下几个步骤:
(1)CPU 先对负温度系数温度传感器(NTC)进行 AD 转换,取得采样值,并对这
个采样值做递推平均滤波。
(2)然后利用查表方法,把上一步滤波后的采样值转变为温度值。为了消除抖动,
需要进一步做消抖滤波。滤波后的结果即为当前的实际温度。
(3)另一方面,通过人机界面的按键输入系统,取得系统的设定温度。
(4)实际温度和设定温度分别送显,并把这二者做比较,决定加热控制继电器的状
态(闭合/释放)。
整个系统虽然不复杂,但涉及到了数据的输入、加工、输出等诸多环节。这些操作牵涉
到多个模块,包括:ADC 模块、按键功能模块、滤波模块、显示模块、输出控制模块。
这些功能如果用流程图来描述,将需要用到多张流程图;如果用数据流图来描述的话,
则只需要一张图就能把整个数据流表达清楚。(参见图 1.33:温度检测与控制系统数据流
图)。
图 1.33:温度检测与控制系统数据流图
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 17 页
在实际应用中,我们立足于描述一个实际问题,因此在画数据流图时可以不必太过于拘
泥于某一个固定的规范。只要能把思路表达清楚就好。
5、数据流图的分层
对于复杂的系统,单层次的数据流图往往不适合表述。这时我们可以考虑对数据流程进
行分层。
具体方法是:先画一个宏观的总的数据流图,在这个总图中勾勒轮廓,而不展现细节;
然后在总图下面逐层扩展,画出更细致的分图;每个分图对上一层图中某个处理框加以分解。
随着分解的深入,功能趋于具体,数据存储、数据流越来越多,细节得到体现。
层次划分的程度没有绝对
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
,这取决于系统的复杂性。
分层的思想不仅仅体现在数据流图中,在画流程图、N-S 图和 PAD 图时,也可以采取
这种先粗后细,逐步求精的办法。
六、状态机分析方法及相关图表
1、状态机的概念
在匠人的另一篇手记《编程思路漫谈》中,曾经介绍过“状态机”及基于状态机思路的
程序调度机制。这次为了本手记的完整性,不得不旧话重提,为了避免无聊,我们尽量在文
字上做些调整。匠人不要炒冷饭(要炒也得炒“蛋炒饭”,嘿嘿!)。
状态机在大千世界普遍存在着。比如我们的生命之源——水。它就有三个状态:固态、
液态、气态。固态水(冰)经过加热,变成液态水,液态水经过进一步加热,变成气态水(水
蒸气)。——这就是一个鲜活的状态机例子。
甚至有人说,人生其实也是一个状态机。想想看:生、老、病、死,人本身就是在各种
状态中轮回。当然,对生命的思考,这已经超出了《匠人手记》的范畴。
状态机是软件编程中的一个重要概念。比这个概念更重要的是对它的灵活应用。在一个
思路清晰而且高效的程序,必然有状态机的身影浮现。
比如说一个按键命令解析程序,就可以被看作是一个状态机:本来在 A 状态下,触发
一个按键后切换到了 B 状态;再触发另一个键后切换到 C 状态,或者返回到 A 状态。这就
是最简单的按键状态机例子。实际的按键解析程序会比这更复杂些,但这不影响我们对状态
机的认识。
进一步看,击键动作本身,也可以看做是一个状态机。一个细小的击键动作包含了:释
放、抖动、闭合、抖动、重新释放等状态。同样,一个串行通讯的时序(不管它是遵循何种
协议,标准串口也好、I2C 也好;也不管它是有线的、还是红外的、无线的)也都可以看做
是由一系列有限的状态构成的。
显示扫描程序也是状态机;通讯命令解析程序也是状态机;甚至连继电器的吸合/释放
控制、发光管(LED)的亮/灭控制、又何尝不是个状态机?
当我们打开思路,把状态机作为一种思想导入到程序中去时,就会找到解决问题的一条
有效的捷径。有时候,用状态机的思维去思考程序该干什么,比用控制流程的思维去思考,
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 18 页
可能会更有效。这样,状态机便有了更实际的功用。
程序其实就是状态机。
2、状态机的要素
匠人把状态机归纳为 4 个要素,即:现态、条件、动作、次态。这样的归纳,主要是出
于对状态机的内在因果关系的考虑。“现态”和“条件”是因,“动作”和“次态”是果。详
解如下:
(1)现态:是指当前所处的状态;
(2)条件:又称为“事件”。当一个条件被满足,将会触发一个动作,或者执行一次
状态的迁移;
(3)动作:条件满足后执行的动作。动作执行完毕后,可以迁移到新的状态,也可
以仍旧保持原状态。动作不是必需的,当条件满足后,也可以不执行任何动作,
直接迁移到新状态;
(4)次态:条件满足后要迁往的新状态。“次态”是相对于“现态”而言的,“次态”
一旦被激活,就转变成新的“现态”了。
如果我们进一步归纳,把“现态”和“次态”统一起来,而把“动作”忽略(降格处理),
则只剩下两个最关键的要素,即:状态、迁移条件。
3、状态迁移图(STD)
状态迁移图(STD),是一种描述系统的状态、以及相互转化关系的图形方式。状态迁
移图的画法有许多种,不过一般都大同小异。我们结合一个例子(参见图 1.34:状态迁移
图)来说明一下它的画法:
图 1.34:状态迁移图
(1)状态框:用方框表示状态,包括所谓的“现态”和“次态”;
(2)条件及迁移箭头:用箭头表示状态迁移的方向,并在该箭头上标注触发条件。
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 19 页
(3)节点圆圈:当多个箭头指向一个状态时,可以用节点符号(小圆圈)连接汇总;
(4)动作框:用椭圆框表示;
(5)附加条件判断框:用六角菱形框表示;
4、状态迁移表
除了状态迁移图,我们还可以用表格的形式来表示状态之间的关系。这种表一般称为状
态迁移表。
采用表格方式来描述状态机,优点是可容纳更多的文字信息。比如,我们不但可以在状
态迁移表中描述状态的迁移关系,还可以把每个状态的特征描述也包含在内。
下面这张表格,就是图 1.34:状态迁移图的另一种描述形式(参见表 1.1:状态迁移
表)。
状态(现态) 状态描述 条件 动作 次态
条件 1 - 状态 2 状态 1 (略……) 条件 2 动作 1 状态 3
附加条件满足 - 状态 4
条件 3
附加条件不满足 - 状态 3
条件 5 - 状态 1
状态 2 (略……)
条件 6 动作 2 -
条件 4 - 状态 4 状态 3 (略……) 条件 5 - 状态 1
状态 4 (略……) 条件 5 - 状态 1
表 1.1:状态迁移表
如果表格内容较多,我们还可以将状态迁移表进行拆分。
比如,我们可以把状态特征和迁移关系分开列表。被单独拆分出来的描述状态特征的表
格,也可以称为“状态真值表”。如果每一个状态包含的信息量过多,我们也可以把每个状
态单独列表。
状态迁移表作为状态迁移图的有益补充,它的表现形式是灵活的。
状态迁移表的缺点是不够直观,因此,它并不能完全取代状态迁移图。比较理想的是将
图形和表格结合应用。用图形展现宏观,用表格说明细节。二者互为参照,相得益彰。
本来还想就状态迁移图和状态迁移表再多举一些实际例子。不过,在匠人的其它一些手
记里已经给出过一些了实例了。为了避免重复,只好有劳读者们自己去找吧。千万别扔砖头
哦!
5、更复杂的状态机
如果有必要,我们可以建立更复杂的状态机模型。
状态机可以是多级的。在一个分层的多级系统里面,一个“父状态”下可以划分多个“子
状态”,这些子状态共同拥有上级父状态的某些共性,同时又各自拥有自己的一些个性。
状态机也可以是多维的。从不同的角度对系统进行状态的划分,这些状态的某些特性是
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 20 页
交叉的。
这部分思想曾经在《编程思路漫谈》中介绍过,这次就一笔带过。再次强调匠人的一贯
主张——简单的,才是最有效的。
七、真值表、数轴和坐标系
1、简述
前面介绍过的流程图、N-S 图、PAD 图,是用于描述程序的控制流程;数据流图是描述
数据流向;状态迁移图(表)是描述状态及状态的迁移。虽然方法和角度不同,但被描述的
对象都是动态的。
除了这些动态的对象,软件算法中还有一些静态的逻辑关系,比如多重嵌套的条件选择,
用上述图表不易清楚地描述。这时,我们可以用真值表或者数轴和坐标系来表示它们内在逻
辑关系。
2、真值表
把变量的各种可能取值与相对应的函数值,用表格的形式一一列举出来,这种表格就叫
做真值表。真值表有时又被称为判定表。
下面举一个真值表应用例子(参见表 1.2:真值表实例)。这是一个用可控硅来控制加
热的系统。通过控制可控硅的导通角(PWM 方式)来调节温度。在这个系统中,我们定时
(假设是 500 毫秒)采样系统的实际温度,并把本次温度和上次温度以及设定温度作比较,
通过计算或查表,求出 PWM 占空调节量。
温差 1=设定温度-本次温度
需要降温 需要升温 占空调节量
<=-4 -3 -2 -1 0 1 2 3 >=4
<=-3 -1 不变 +1 +2 +3 +4 +5 +6 +7
-2 -2 -1 不变 +1 +2 +3 +4 +5 +6
正
在
降
温
-1 -3 -2 -1 不变 +1 +2 +3 +4 +5
0 -4 -3 -2 -1 不变 +1 +2 +3 +4
1 -5 -4 -3 -2 -1 不变 +1 +2 +3
2 -6 -5 -4 -3 -2 -1 不变 +1 +2
温
差
2=
本
次
温
度
-上
次
温
度
正
在
升
温
>=3 -7 -6 -5 -4 -3 -2 -1 不变 +1
表 1.2:真值表实例
我们知道,在温度反馈控制中,快速和稳定是一对矛盾。片面要求快速,可能会导致过
冲,甚至形成反复振荡。而如果力求稳定,则有可能降低调节速度。为了兼顾快速和稳定的
两方面要求,我们采用了模糊控制。其中包含了以下两条规则:
规则一:根据设定温度与本次实际温度的差值决定 PWM 占空比的调节量。如果本次温
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 21 页
度低于设定温度,代表需要增加加热功率(升温),此时应该增加占空;如果本次温度高于
设定温度,代表需要降低加热功率(降温),此时应该增加占空。当温差较小时,占空的调
节量也要小,以达到稳定输出的目的;当温差较大时,占空的调节量也要增大,以达到快速
调节的目的。
规则二:根据实际温度的变化趋势(即本次温度与上次温度之差)来修正占空比调节量。
如果本次温度低于上次温度,代表温度正在下降;反之,代表温度正在上升。这种趋势可以
让我们预见未来的温度变化,因此可以把它作为一个考量因素,并折算成对占空调节量的修
正量。
当实际温度的变化趋势(正在升温、正在降温)与温度调节方向(需要升温、需要降温)
一致时,PWM 占空比的调节量和修正量将相互抵消;反之则相互叠加。最终我们会得到一
个修正后的调节量。
如何确定调节量呢?这需要一定的经验推导和试验验证。
模糊控制在温控系统中的应用原理,不是本手记的范畴。匠人之所以要废这些口舌,只
是为了帮助读者看懂这张真值表。
真值表的优点是能够简洁,无二义性地描述所有的处理规则。因此这也是我们软件规划
时的一件利器。
当然,真值表表示的是静态逻辑,是在某种条件取值组合情况下可能的结果,它不能表
达控制的流程,也不能表达循环结构,因此真值表只能作为一种设计规划时的辅助方法。
3、数轴
因为工作的关系,匠人有时要与其他一些公司的工程师相互探讨技术问题。交流的时间
是短暂的,初次见面来不及寒暄,就要立即切入正题。这种情况下快速有效的沟通是非常重
要的。匠人力求在最短的时间内,用最简练的方法,让对方明白匠人的想法。也许就像下面
这个数轴一样,只需要一张便签、一支笔,信手画来,寥寥数笔就可以包含一个完整的逻辑
关系。这样做,比用文字或表格说明要快捷得多了。
来看看另一个温控的例子。首先计算温差(温差=设定温度-当前温度)。然后,根据温
差来确定功率档位。温差为正时说明当前温度还没有到达设定温度,需要加热。温差越大,
则功率(档位)越大。温差为负,则停止加热(功率档位=0)。这样一个对应关系,用数轴
来表示,再恰当也不过了(参见图 1.35:数轴实例)。
图 1.35:数轴实例
简单的往往就是最有效的,这句话曾经被匠人反复说过。在实际工作中,匠人也是按照
这一理念去实践的。
4、坐标系
数轴可以是一维的,自然也可以是二维的(甚至更多维的)。二维或多维的数轴组合成
一个坐标系统。
0 8 12 16 20 24 28 32 36 40 温差
功率档位:0 1 2 3 4 5 6 7 8 9 10
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 22 页
坐标系在表现数据的逻辑关系方面,没有真值表那么明确。因此,在描述比较复杂的逻
辑关系时,还是建议使用真值表。鉴于坐标系的应用机会不多,这里就不展开介绍了。
八、程序结构图(层次图、框图)
1、程序结构图简介
程序的结构图,又被称为层次图、框图。一般为树形或网状。用于宏观表达程序的各模
块之间的控制关系。
程序结构图本身并不难画,难的是是如何规划程序的结构。
程序结构图是程序规划的第一步,按理应该放在本手记的最前面介绍。但是因为上面所
述的原因,新手往往难以立即掌握结构的分解方法,因此匠人有意地把这一节内容放在压轴
的位置。(匠人喜欢把难啃的骨头放在最后,呵呵。)
我们在对一个程序进行规划时,一般都是先对需求进行分析,把要求(任务)分成若干
块,并为每个相对独立的任务分配一个或几个模块来实现,如果任务较为复杂,还可以对其
进一步逐步分层,最终导出完整的程序结构。
2、程序结构图的画法
(1)对功能需求分解
下面匠人将举个 LCD 显示密码锁的例子来展示:如何把一个笼统的需求进行分解、整
理、细化,最后画出成程序的结构图。
当我们刚接下这项密码锁程序设计的任务时,如果我们还没有了解程序的具体功能要
求,就像面对一个大面团,无从下手(参见图 1.36:一个需求不明的密码锁程序)。
图 1.36:一个需求不明的密码锁程序
不要害怕,让我们从一个程序员的角度,来对这个密码锁程序的要求进行分解,看看它
究竟需要实现哪些功能?
z 首先,LCD 显示和按键功能作为人机交流界面是必不可少的;
z 其次是密码和开门信息的存取功能,这涉及到对外部 E2PROM 的操作;
z 再次是对门锁(电磁阀)的开/关控制功能;
z 还有,因为密码锁是靠电池供电的,所以一方面对工作电源的欠压状态要进行检测
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 23 页
和处理;另一方面,在不操作时进睡眠模式以降低功耗,这就需要做节电处理。
z 最后,我们还需要一个主程序和一个定时中断服务程序,以及系统计时功能。
现在,我们已经初步把密码锁的各个子功能分解出来了(参见图 1.37:对密码锁程序
功能进行分解)。
图 1.37:对密码锁程序功能进行分解
(2)程序结构的整理
在把程序的各个功能分解出来之后,让我们寻找它们相互之间的控制关系,并调整一下
位置。
z 主程序的任务是负责调度其它程序,因此要放在最高层;
z 一些直接由主程序调度的程序模块,则放在主程序下面的第二层;
z 还有一些底层功能模块,则放在第三层;
z 我们还要把中断服务程序及由中断调用的计时处理程序单独列在一边。
经过整理后,就可以得到下面这张结构图(图 1.38:对密码锁程序结构进行整理)。
图 1.38:对密码锁程序结构进行整理
发现了吗?同样是这几个圆圈圈,我们把它们重新摆布一下,思路也就跟着被理顺了。
3、程序结构的开放性
程序结构图具有开放性的特性,这意味着它可以在横向和纵向两个方向进行扩充和删
减。就像搭积木一样简单。再仔细观察一下图 1.38 的结构图,我们发现还有一些细节被遗
漏了,没有体现在图中。比如:
z 在主程序中,要先调用初始化程序,并在初始化程序中调用数据存取模块去预先设
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 24 页
定初始密码。
z 在按键处理模块中,我们需要调用一个读键子程序去检测按键的闭合情况;
z 在显示处理模块模块中,我们需要把刷新显示缓冲区的程序单独作为一个子程序来
写;
z 在数据存取模块中,要调用 E2PROM 的底层操作;
z 要增加震动信号检测功能,用于防撬防盗;
z 要增加声音报警功能。
我们还会发现,有一些子程序会被几个模块分别调用。比如数据存取程序,会被初始化
和按键模块调用。
好吧,那就让我们把这些细节也画进去吧,这样,我们的程序结构图就趋于完善了(参
见图 1.39:对密码锁程序结构进行完善)。
E2PROM
操作
数据
存取
计时
处理
按键
处理
欠压
检测
节电
处理
显示
处理
主
程序
门锁
控制
中断
程序
刷新
显缓区
按键
检测
初始化 震动检测
声音
报警
图 1.39:对密码锁程序结构进行完善
4、程序结构的多样性
程序的结构,并不是唯一的。不同的人带着不同的设计理念去设计同一个程序。选择的
结构往往是迥异的。这就是程序结构的多样性。
让我们看看这个图(参见图 1.40:同一个项目可以分解出不同的结构),我们可以看到,
同一个软件项目可能存在多种结构分解方法。
结构 1 结构 2 结构 3
图 1.40:同一个项目可以分解出不同的结构
还是拿前面的密码锁来说事,我们也可以把它的结构做一些改变。比如把刷新显缓区、
门锁控制等子程序由主程序直接调用;同时,把计时处理部分由中断中移到后台来进行。
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 25 页
经过调整后的结构图参见图 1.41:密码锁程序结构另一种的分解方法。
图 1.41:密码锁程序结构另一种的分解方法
5、评判程序结构好坏的标准
分解系统结构的过程,其实就是一个模块化的过程。
虽然依据任何一种设计方法总能推导出一个结构来,但是结构总有好坏之分。为什么有
的人写的程序可读性强、鲁棒性好、易于维护?而有的人写的程序却如同一团乱麻,剪不断
理还乱呢?
评判程序结构好坏的主要标准,是看模块是否具有良好的独立性。所谓模块独立性,即:
不同模块相互之间联系尽可能少,尽可能减少公共的变量和数据结构。
模块的根本特征是“相对独立,功能单一”。换言之,一个好的模块应该在逻辑上具有
高度的独立性,并实现完整单一的功能。
我们一般从两个方面来度量模块独立性的程度,即:内聚度和耦合度。
z 内聚度,是指模块内各成份(语句或语句段)之间相互依赖性大小的度量。内聚度
越大,模块各成份之间联系越紧密,其功能越强。内聚度越大,模块独立性就越强,
系统越易理解和维护。
z 耦合度,是指模块之间相互依赖性大小的度量。它用来衡量多个模块间的相互联系。
耦合度越小,模块的相对独立性越大。
综上,低耦合度、高内聚度的程序结构就是我们在模块划分过程中应该追求的目标。
九、后记
这篇手记以连载的形式在 21ICBBS《匠人手记》书友会版面首发。前后历时一个多月,
由于完全是利用业余时间写,难免会断断续续。幸好终于大功告成。
对于匠人自己来说,写这篇手记的过程同时也是一个深入“再学习”的过程。这包含三
个方面:
z 首先,是对原先已经掌握的知识重新梳理,加深理解,并提炼出方法和思想来。
《匠人手记》网络版 《程序规划方法漫谈》 看《匠人手记》,与匠人同行!
第 26 页
z 其次,是原本有一些比较模糊的问题,这次为了写这篇手记,必须要搞明白。匠人
通过上网查阅有关资料,或者经过网友指教后,终于有了进一步的认识。
z 再次,是网友们的发言,给了匠人新的启迪。这种互动,是很有益的。
这篇手记中介绍的一些方法,既可用于规划程序,亦可用于工程师们相互交流时表达自
己的设计思路。而根据匠人的实际接触经验,发现这种交流的技巧往往是许多工程师缺乏的。
曾经见过一些工程师,他们敏于行而讷于言。一肚子才华表达不出来,这样在沟通中显得很
吃亏。
有人说工程师与教授的区别是:“教授会说不会做,工程师会做不会说”。因此,掌握一
些必要的高效的表达技术思路的方法,是很有必要的。
就让这篇裹脚布到此结束吧。