c - 以下过程的控制流程图和圈复杂度

Question

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;
    }
}

我必须找到这段代码的圈复杂度，然后提出一些白盒测试用例和黑盒测试用例。但是我在为代码制作 CFG 时遇到了麻烦。

也希望对测试用例有一些帮助。

Answer 1

首先为语句编号：

 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;
       }

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

现在，要计算圈复杂度，您可以使用以下三种方法之一：

1. 计算图上的区域数：4
2. 谓词数（图上的红色）+ 1 : 3 + 1 = 4
3. 没有边缘 - 没有。节点数 + 2：14 - 12 + 2 = 4。

Answer 2

圈复杂度为 4。

1 表示过程 +1 表示 for 循环 +1 表示 while 循环 +1 表示 while 循环的 if 条件。

Answer 3

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

E = 14
N = 12
C = 1

M = 14-12 + 2*1 = 4