基于McCabe的软件复杂性度量与控制策略

摘要：软件复杂性度量与控制是软件开发面临的主要问题。本文通过对软件复杂性的定量分析，提出了软件复杂性的控制策略，该策略对开发高质量、高可靠性与高可维护性软件有一定的指导作用。

关键词：McCabe；软件；复杂性；度量；控制

中图分类号：TP311文献标识码：A文章编号：1009-3044(2007)05-11338-02

1 引言

随着计算机软件规模的日益庞大，软件的复杂性问题越来越突出，人们已经意识到软件复杂性与软件质量、开发成本和生产效率等方面密切相关。从几十年的研究表明，软件复杂性是导致软件错误的主要原因，当软件复杂性超过某一限度值时,软件中的错误就会急剧上升，甚至引起软件开发失败。对软件复杂性进行定量分析与控制，其目的就是减少由软件设计方法和技巧使用不当而带来的复杂性，可以更好地对软件开发过程进行控制，提高软件生产率和软件产品的质量。而软件复杂性的度量结果可以用来估算出软件中存在的错误数量及软件开发需要的工作量和开发成本，也可以用来比较两个不同的设计或两个不同算法的优劣，也可以作为软件中模块规模的精确限度。

2 软件复杂性度量方法

对于软件复杂性的研究己有几十年的历史，到目前为止，人们从不同的角度提出了许多度量方法和标准，它们大体上可以分为基于控制流的度量方法（如McCabe方法和Woodward方法）、基于数据流的度量方法（如Elshoff方法）、基于程序体积的度量方法（如Halstead的软件科学方法）等，还有少数基于软件心理学的度量方法。虽然它们都有各自的缺点和不足，缺乏完整统一的理论根据，但它们都在一定程度上，从不同的侧面反映了软件的复杂性，其中有许多方法已成功地运用于软件开发中，并取得了显著的效益。本文从McCabe度量方法出发，研究其度量方法及过程，并提出控制软件复杂性的途径。

2.2.1 McCabe度量方法

软件复杂性主要表现为程序结构的复杂性，而程序结构的复杂性主要指模块内部程序的复杂性。McCabe度量方法根据图论和程序结构控制理论，当度量程序结构的复杂性时，首先把程序结构的控制流程图转化为有向图（即程序图），然后计算强连通有向图的环数。用McCade度量方法得到的复杂度称为程序结构的环形复杂度。为叙述方便，给出如下几个定义。

定义1：程序图是一种“退化了的”程序流程图。即是把程序流程图中每个处理框都退化成一个结点，原来连接不同处理框的箭头都变成连接不同结点的有向弧，这样得到的有向图称为程序图。

定义2：强连通图是指从图中任一个结点出发都能到达所有其他结点图。

定义3：强连通有向图的环数是指在一个强连通有向图中线性无关环的个数，即有向图G中的弧数m与结点数n的差再加上分离部分的数目p。计算公式定义为V(G)=m-n+p。

对于一个正常的程序来说，其程序图是连通的，也就是说p的值取1，但通常情况下不是强连通的。因为从图中较低的（较靠近出口点的）结点往往不能到过较高的结点，然而，如果从出口点画一条虚弧，则程序图必然成为强连通有向图。理由是：(1) 从入口点总能到达图中任何一点；(2) 从图中任何一点总能到达出口点；(3) 经过从出口点到入口点的弧，可以从出口点到达入口点。

环形复杂度除上述计算方法外，还有其他方法。如，环形复杂度等于程序图中判定结点的数目加1，或环形复杂度等于强连通程序图在平面上围成的区域个数。

2.2.2 McCabe度量方法应用

使用McCabe方法首先需将程序流程图转换成程序图，并使程序图是强连通图，然后，根据程序图中的弧数和结点数计算出程序的环形复杂度V(G)。下面介绍其实际应用过程。

现有将50名学生中成绩在80分以上的学号和成绩打印出来的算法控制流程图，如图1所示，把它转换成程序图后如图2所示。

由于图2不是强连通图，为了使其是强连的，必须从其出口结点6到入口结点1添加一条虚线弧。由图2可知，程序图中的弧数为9（加上虚线弧数1），结点数为7，根据公式V(G)=m-p+1，可计算得到该程序控制流程结构的环形复杂度为3，用程序图中判定结点的数目加1进行验证，同样得到环形复杂度为3。

从McCabe度量方法的计算过程表明，程序的复杂性很大程度上取决于程序结构控制流的复杂性。顺序结构最简单，复杂度为1，分支和循环结构所构成的环路越多，复杂度越大。McCabe在研究大量程序后发现，环形复杂度高的程序往往是最容易出现错误的程序。实践表明，程序规模以V(G)≤10为宜，也就是说，V(G)＝10是程序规模的一个理科学更精确的上限。因此，对于规模超过10的程序，应分成几个小程序，以减少程序中的错误。

3 软件复杂性控制

软件复杂性主要表现为模块内部的复杂性，以及模块之间接口的复杂性，下面就几方面谈谈复杂性控制问题。

3.1 模块化原则

所谓模块化就是根据人类解决问题的一般思想，把程序划分成独立命名且可独立访问的模块，每个模块完成一个特定功能，模块是构成程序的基本构件。模块化使一个大型的复杂软件简单化，从而降低了程序复杂性。经过细分（模块化）之后的程序，将变得容易理解。这一点可由下面的规律得到论证。

设函数C(x)定义问题x的复杂程度，函数E(x)确定解决问题x需要的工作量（时间）。对于两个问题P1和P2，如果 C(P1)>C(P2)，显然，E(P1)>E(P2)，根据经验，一个有趣的规律是C(P1+P2)>C(P1)+C(P2)。即，如果一个问题由P1和P2两个问题组合而成，那么它的复杂程度大于分别考虑每个问题时的复杂程度之和。如果把这一式子进行推广，则可推出如下结论：C(P1+P2+…+Pn)>C(P1)+C(P2)+…+C(Pn)，也就是说，如果无限地分解一个复杂软件，那么开发该软件的复杂度就可以小到忽略不计了。事实如何？请看图3所示。

图3 模块化和工作量

从图3可看出，当模块数目增加时每个模块的复杂度将降低，开发单个模块确实也容易了，但是，随着模块数目增加，模块间接口复杂度将增加，使模块接口的设计变得困难。根据这两个因素，得出了图2中的软件总复杂度曲线，即每个软件都相应地有一个最适当的模块数，而使得系统的开发复杂度最小。虽然目前还不能精确地计算出最适当的模块数，但是在考虑模块化的时候软件总复杂度曲线确实是有用的指南。

3.2 模块独立性原则

模块独立是模块化的直接结果。设计功能相对独立且与其他模块之间没有过多联系的模块，是控制软件复杂性的一种重要手段。这是因为：第一，独立性强的模块，其功能比较单一，接口相结简单，整体复杂性低，容易开发；第二，独立性强的模块，与其他模块联系少，错误范围得到有效控制，容易测试和维护。那么，怎样才能做到模块独立呢？有两方面措施：

3.2.1 降低模块间的耦合度

耦合是指一个软件结构内部不同模块之间相对独立程度的度量，是影响软件复杂度的一个重要因素，按模块间耦合度由弱至强的顺序，可分为数据耦合、控制耦合、特征耦合、公共环境耦合和内容耦合等五类。模块耦合的强弱主要取决于模块间接口的复杂性，如果模块间的接口复杂，则耦合度强；如果模块间的接口简单，则耦合度弱。因此，在开发软件系统中的每一个模块时都应该使其尽可能地独立工作，而不过多地依赖于其他模块，要做到这一点，就必须坚持如下四个设计原则：(1)尽量使用数据耦合；(2)少用控制耦合；(3)限制公共环境耦合的范围；(4)完全不用内容耦合。

3.2.2 提高模块内的内聚度

内聚是指一个模块内部各元素(如数据、语句、程序段等)之间彼此联系的紧密程度的度量，是影响软件复杂度的又一个重要因素。按内聚度由低至高的顺序，可分为偶然内聚、逻辑内聚、时间内聚、通信内聚、顺序内聚和功能内聚等六类，它们从模块功能的角度来衡量信息隐蔽和局部化的程度，是模块化的有力工具。内聚和耦合紧密相关，模块内的高内聚往往体现出模块间的松耦合，实践表明，内聚比耦合更重要，因此，在设计模块时应把更多的精力放到提高模块的内聚程度上，力争做到高内聚低耦合，要达到这个目标可采取如下措施：(1)开发功能相对独立的模块；(2)尽量使用功能内聚、顺序内聚和通信内聚；(3)少用过程内聚和时间内聚，不使用偶然内聚和逻辑内聚；(4)模块间尽量少用公共信息，多传递数据类型的参数。

3.3 模块规模优化原则

在设计出软件的模块之后，应该对其规模进行审查、评估和优化，通过结构调整、分解或合并，降低其耦合度，提高其内聚度，继而达到控制模块复杂性的目的。为便于模块规模的优化，下面介绍几条常用原则：

3.3.1 模块规模适中

实践经验表明，一个模块的规模不应过大或过小。模块过大，复杂性就大，不利于开发和理解，需要进行分解；如果过小，模块数量过多，软件接口复杂，且开销太大，需要进行合并。

3.3.2 模块扇出与扇入适中

扇出是一个模块直接控制其它模块的数量，是影响模块宽度的主要因素。扇出过大,说明控制的下级模块过多，模块过于复杂，需适当增加中间层次的控制模块；扇出过小，说明下级模块过于复杂或过于简单，如果下级模块过于复杂，则需将其进一步分解成若干子功能模块；如果下级模块过于简单，则需将其合并到它的上级模块中去。实践表明，合理的扇出数通常是3或4，上限是5～9。扇入是一个模块的上级模块直接调用它的数量。扇入越大，调用它的上级模块数就越大，说明其通用性强，这对设计虽有好处，但不提倡为追求高扇入而违背模块独立性原则。

3.3.3 降低模块接口的复杂程度

接口的复杂性直接关系到模块的耦合和内聚程度，是软件发生错误的主要根源。如果接口过于复杂，则应分析其独立性，并使其传递简单信息。要降低接口的复杂性，可采取以下措施：(1)提高模块独立性；(2)避免模块间的紧耦合；(3)设计功能相对独立的模块；(4)设计单入口单出口的模块。

4 结束语

软件复杂性度量是对软件复杂程度的定量计算，它从本质上揭示了软件复杂性产生的真正原因，为软件设计过程进行软件复杂性分析和控制提供了科学依据。本文通过对软件复杂性的定量分析，提出了软件复杂性的控制措施，对开发高质量、高可靠性与高可维护性软件有一定的指导作用。

参考文献：

[1] 王振宁. 程序复杂性度量[M]. 北京：国防工业出版社,1997.

[2] 汤庸. 软件工程方法学及应用[M]. 北京：中国三峡出版社,1998.

[3] 张海藩. 软件工程导论(第4版)[M]. 北京：清华大学出版社,2003.12.

[4] Zase H. Software Complexity Measured and Methods[M]. Yourdon Press, 1987.

[5] Thomas J McCabe. A Complexity Measure[J]. IEEE Trans On Software Eng. 1976.

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。