控制流程图和后续程序的圈复杂度

insertion_procedure (int a[], int p [], int N)
{
    int i,j,k;
    for (i=0; i<=N; i++) p[i] = i;
    for (i=2; i<=N; i++)
    {
        k = p[i];
        j = 1;
        while (a[p[j-1]] > a[k]) {p[j] = p[j-1]; j--}
        p[j] = k;
    }
}

I have to find cyclomatic complexity for this code and then suggest some white box test cases and black box test cases. But I am having trouble making a CFG for the code.

我必须找到这个代码的圈复杂度,然后建议一些白盒测试用例和黑盒测试用例。但我无法为代码制作CFG。

Would appreciate some help on test cases as well.

非常感谢对测试用例的一些帮助。

3 个解决方案

#1

Start by numbering the statements:

首先编写语句编号:

 insertion_procedure (int a[], int p [], int N)
 {
(1)    Int i,j,k;
(2)    for ((2a)i=0; (2b)i<=N; (2c)i++) 
(3)        p[i] = i;
(4)    for ((4a)i=2; (4b)i<=N; (4c)i++)
       {
(5)       k=p[i];j=1;
(6)       while (a[p[j-1]] > a[k]) {
(7)           p[j] = p[j-1]; 
(8)           j--
          }
(9)          p[j] = k;
       }

Now you can clearly see which statement executes first and which last etc. so drawing the cfg becomes simple.

现在您可以清楚地看到哪个语句首先执行,哪个语句最后执行等等,因此绘制cfg变得简单。

Now, to calculate cyclomatic complexity you use one of three methods:

现在,要计算圈复杂度,请使用以下三种方法之一:

1. Count the number of regions on the graph: 4

计算图表上的区域数量:4

2. No. of predicates (red on graph) + 1 : 3 + 1 = 4

谓词数量(图表上的红色)+ 1:3 + 1 = 4

3. No of edges - no. of nodes + 2: 14 - 12 + 2 = 4.

没有边缘 - 没有。节点+ 2:14 - 12 + 2 = 4。

#2

The cyclomatic complexity is 4.

圈复杂度为4。

1 for the procedure +1 for the for loop +1 for the while loop +1 for the if condition of the while loop.

1为for循环+1为for循环+1为while循环+1为while循环的if条件。

#3

You can also use McCabe formula M = E-N + 2C
E = edges
N = nodes
C = components
M = cyclomatic complexity

您还可以使用McCabe公式M = E-N + 2C E =边N =节点C =分量M =圈复杂度

E = 14
N = 12
C = 1

M = 14-12 + 2*1 = 4

M = 14-12 + 2 * 1 = 4