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

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

前两天写了这学期 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... */
}