首页 > 代码库 > C语言中边界计算与不对称边界(二)
C语言中边界计算与不对称边界(二)
尽管C语言的数组会让新手感到麻烦,然而C语言中数组的这种特别的设计正是其最大优势所在。要理解这一点,以下是一些简单解释。
在所有常见的程序设计错误中,最难于察觉的一类是“栏杆错误”,也常被称为“差一错误”(off-by-one error)。例如这个问题:100英尺长的围栏每隔10英尺需要一根支撑用的栏杆,一共需要多少根栏杆呢?如果不加思索,大家会容易以为是100除以10,即为10根。其实,真正需要的是11根。
因为支撑10英尺长的围栏实际需要2根栏杆,即两端各一根。这个问题的另一种思考方式是,除了最右侧的一段围栏,其他每一段10英尺长的围栏都只在左侧有一根栏杆;而例外的最右侧一段围栏不仅左侧有一根栏杆,右侧也有一根栏杆。
为了避免以上问题中所说的“栏杆错误”,以下是两个注意的通用原则:
(1)首先考虑最简单情况下的特例,然后将得到的结果外推;
(2)仔细计算边界,绝不掉以轻心;
将上面这两点牢记住以后,现在看看整数范围的计算。例如,假定整数x满足边界条件x>=16且x<=37,那么此范围内的X的可能取值个数有多少?即16到37之间一共有多少个元素?很显然,答案与37-16(21)非常接近,那么到底是20、21还是22呢?
根据原则1,我们考虑最简单情况下的特例。这里假定整数x的取值范围上界与下界重合,即x>=16且x<=16,显然合理的x取值是只有一个整数,即16。所以当上界与下界重合时,此范围内满足条件的整数序列只有一个元素。
再考虑一般情况,假定下界为l,上界为h。如果满足条件“上界与下界重合”,即l=h,则h-l=0。根据特例外推的原则,我们可以得出满足条件的整数序列有h-l+1个元素。故以上的问题中的x的取值个数为37-16+1=22。
造成“栏杆错误”的根源正是“h-l+1”中的“+1”。一个字符串中由下标为16到下标为37的字符元素所组成的子串,它的长度是多少呢?稍不留意,就会得到错误的结果21。很自然的,我们会想,是否存在一些编程技巧,能够降低这类错误发生的可能性呢?
当然,这个技巧不但存在,而且还可以一言以蔽之:用第一个入界点和第一个出界点来表示一个数值范围。具体而言,前面的例子我们不应该说整数x满足边界条件x>=16且x<=37,而是说整数x满足边界条件x>=16且x<38。注意,这里下界是“入界点”,即包括在取值范围之中;而上界是“出界点”,即不包括在取值范围之中。这种不对称也许从数学上而言并不优美,但是它对于程序设计的简化效果却足以令人吃惊。
(1)取值范围的大小就是上界与下界之差。
(2)如果取值范围为空,那么上界等于下界
(3)即使取值范围为空,上界也永远不可能小于下界。
对于像C这样的数组下标从0开始的语言,不对称边界给程序设计带来的便利尤为明显;这种数组的上界恰是数组元素的个数。因此,在C语言中定义一个拥有10个元素的数组,那么0就是数组下标的第一个“入界点”,而10就是数组下标中的第一个“出界点”。因而我们经常这样写
int a[10], i; for(i=0; i<10; i++) a[i] = 0;而不是这样写:
int a[10], i; for(i=0; i<=9; i++) a[i] = 0;让我们做一个假设,如果C语言的for语句风格类似Algol或者Pascal语言,那么就会带来一个问题:下面这个语句的含义究竟是什么?
for(i=0 to 10) a[i] = 0;如果10是包括在取值范围内的“入界点”,那么i将取11个值,而不是10个值;如果10是不包括在取值范围内的“出界点”,那么原来以其他程序语言为背景的编程者会大为惊讶。
另一种考虑不对称边界的方式是,把上界视作某序列中第一个被占用的元素,而把下界视作序列中第一个被释放的元素。如下图: