循环数组 C 语言实现中一个不易发现的 bug

Circular-array

前两天写了这学期 Foundamentals of Data Structures 课里最后一个 Project 的程序。题目的难点本来在于思路,可是老师上课已经提醒了很多,于是编程上并没有太大困难。布置下来以后我花了两个小时的时间,把整个程序写完,通过了 PAT 上的测试,把程序交给小组的测试员,又和文档员说了一下这个题的思路,觉得自己已经 Mission Acomplish 了。

昨天测试员回复我说有一个数据通不过,程序陷入了死循环。我的第一反应就是她给的数据有问题。因为这妹子懒得写程序,数据竟然是手算出来的。我看到 N = 50 觉得她肯定出错了。不过为了放心,还是不耐烦地自己写了一个数据生成器,对比之后发现,程序真的错了。

具体的算法不再详述,思路上都没有问题。bug 出在一个循环数组上。把每一步结果打印出来后,发现程序卡在这个地方不停循环:

for (j = k; j != i; ++j) {
 if (j == n)
  j -= n;
 /* do something... */
}


你可以先不要看我接下来的分析,自己看一下这段代码有什么问题,不是很难。

我把这个循环体内部的 i 和 j 变量全部打印出来以后,发现即使 j == i 成立,循环也不会停止。想了好久,才发现,这样的写法是有问题的。如果你还没有看出来,我把它展成下面的 while 语句:

j = k;
while (j != i) {
 if (j == n)
  j -= n;
 /* do something... */
 j++;
}


这段程序会在 i == 0 的时候陷入死循环。若在循环语句开始时 j == n 成立,在执行操作的时候 j 会变成 0,而在循环体末尾,j 又做了自增操作,因此判断语句中 j != i 永远成立。

这个问题不难,但有些隐晦,如果当初这样写,那么发现错误可能就比较容易了:

for (j = k; j != i; ++j) {
 /* do something... */
 if (j == n)
  j -= n;
}


这样在执行操作的时候 j 的值就等于 n,可能会出现数组越界、访问无效内存等等错误,就比较好排查了。

这个问题改起来也比较容易,只需要把 for 语句中的最后一句写得丑一点就行了:

for (j = k; j != i; j = (j + 1) % n) {
 /* do something... */
}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/6c635a599b328ef3be1e0c6676ef4d27.html