又是数组越界造成的bug.

又一次遇到数组越界造成的奇怪的,难以调试的,诡异的bug.

前几天做ACM题。‘简单的马周游’。

http://blog.ykyi.net/2011/11/acm-%E9%A9%AC%E5%91%A8%E6%B8%B8%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A/

因为我的解法用了函数递归调用,函数求到最终解的栈的调用层次非常深。第一版用置一个全局变量的方式让这么深调用的函数快速依次退出。但我也知道还有另外一种解法就是用C语言的setjmp 和 longjmp。用这两个函数可以快速退栈。

 

今天晚上就想用setjmplongjmp改写一下。本来以为是非常简单的事情。结果改完以的程序只能正确求解第一个请求,然后程序看起来就像是死了。Debug时发现程序似乎跑飞了。哎(脑子不灵光,发现程序跑飞竟然没有立即想到是数组越界把堆栈写坏了)。因为我改动的代码非常少,只是用setjmplongjmp快速退出递归取代之前的稍微比较慢的做法。而其它的代码改动的非常之少。于是我当时分析错误的出发点就是比较两份代码的异同。比较来比较去,就只有退出方式不同而已。相当相当地困惑。费了很多时间都没有找到原因。

实在搞不定了。冲了个热水澡,又回来看代码。还是没有发现这个改动在哪里引入了错误。不断反复地看代码,突然灵光一现看到写一个全局数组的语句,下标变量越界!越界!越界!!!啊~~惊喜!于是把数组下标的相关的代码纠正了,于是setjmp版本的代码也运行正常啊。

这次的经验是。操作数组的时候一定要一定要一定要非常非常非常之小心~~在调试程序发现程序跑飞的情况下马上要意识到是写坏了堆栈。

 

另外还有一个疑问是第一版的代码也有写坏栈的问题为什么就一切正常呢。这就是C/C++程序数组危险的地方啊~~第一版本的代码退栈的方式和第二版不一样,于是这个bug就在第一版隐藏了起来。于是第二版出问题时我的思路集中在比较代码差异是如何引入问题的。而这个bug并不是新代码引入的,而是在旧代码隐藏起来的,第二代的新代码让触发了这个bug

总结下经验:

一定要一定要非常小心C/C++的数组越界问题啊!!!操作很多数组时,有很多下标要计算时。千万要注意是从0还是从1开始计算下标。要根据约定多下诊断!!!及时发现隐藏的错误。越界写数组的bug有时发生,可能在引入的当时被隐藏,隐藏的很深很深。但越界读数组的bug隐藏得更深更深更深啊。

copyright blog.ykyi.net