C陷阱与缺陷之边界计算与不对称边界(上)

如果一个数组有10个元素,那么这个数组下标的允许取值范围是什么呢?

这个问题对于不同的程序设计语言有着不同的答案。例如,对于Fortran,PL/I以及Snobol4等程序语言,这个数组的下标取值缺省从1开始,而且这些语言也允许编程者另外指定数组下标的起始值。而对于Algol和Pascal语言,数组下标没有缺省的起始值,编程者必须显示地指定每个数组的下界与上界。在标准的Basic中,声明一个拥有10个元素的数组,实际上编译器分配了11个元素的空间,下标范围从0到10.

译注:Basic中声明数组时实际上指定的是上界,而下界默认为0.

Basic中也可以同时指定数组的上界与下界,如:

在C语言中,这个数组的下标范围是0到9.一个拥有10个元素的数组中,存在下标为0的元素,却不存在下标为10的元素。C语言中一个拥有n个元素的数组,却不存在下标为n的元素,它的元素的下标范围是从0到n-1为止,由其他程序语言转而使用C语言的程序员在使用数组时特别要注意。

例如,让我们仔细地看看本书导读中的一段代码:

这段代码的本意是要设置数组a中所有元素为0,却产生了一个出人意料的“副效果”。在for语句的比较部分本来是i<10,却写成了i<=10,因此实际上并不存在的a[10]被设置为0,也就是内存中在数组a之后的一个字(word)的内存被设置为0.如果用来编译这段程序的编译器按照内存地址递减的方式来给变量分配内存,那么内存中数组a之后的一个字(work)实际上是分配给了整型变量i。此时,本循环计数器的值为10,循环体内将并不存在的a[10]设置为0,实际上却是将计数器i的值设置为0,这就陷入了一个死循环。

尽管C语言的数组会让新手感到麻烦,然而C语言中数组的这种特殊设计正是其最大优势所在。要理解这一点,需要作一点解释。

在所有常见的程序设计错误中,最难察觉的一类是“栏杆错误”,也常被称为“差一错误”(off-by-one error)。还记得本书导读中的第2个练习提出的问题吗?那个问题说的是:100英尺长的围栏每隔10英尺需要一根支撑用的栏杆,一共需要多少要栏杆呢?如果不假思索,最“显而易见”的答案是将100除以10,得到的结果是10,即需要10要栏杆。当然这个答案是错误的,正确答案是11.

也许,得出正确答案的最容易的方式是这样考虑:要支撑10英尺长的围栏实际需要2根栏杆,两端各一根。这个问题的另一种考虑方式是:除了最右侧的一段围栏,其他每一段10英尺长的围栏都只在左侧有一根栏杆;而例外的最右侧一段围栏不仅左侧有一根栏杆,右侧也有一根栏杆。

前面一段讨论了解决这个问题的两种方法,实际上提示我们避免“栏杆错误”的两个通用原则:

  • 首先考虑最简单情况下的特例,然后将得到的结果外推,这是原则一;
  • 仔细计算边界,绝不掉以轻心,这是原则二。

将上面总结的内容牢记在心以后,我们现在来看整数范围的计算。例如,假定整数x满足边界条件x>=16且x<=37,那么此范围内x的可能取值有多少?换句话说,整数序列16,17,…,37一共有多个元素?很显然,答案与37-16(亦即21)非常接近,那么到底是20,21还是22呢?

根据原则一,我们考虑最简单的情况下的特例。这里假定整数x与联欢会范围上办与下界重合,即x>=16且x<=16,显然合理的x聚会只有一个整数,即16.所以当下界与下界重合时,此范围内满足条件的整数序列只有1个元素。

再考虑一般的情形,假定下界为l,上界为h。如果满足条件“上界与下界重合”,即1=h,亦即h-1=0.根据特例外推的原则,我们可以得出满足条件的整数序列有h-1+1个元素。在本例 中,就是37-16+1,即22.

造成“栏杆错误”的根源正是“h-1+1”中的“+1”。一个字符串中下标为16到下标为37的字符元素所组成的了串,它的长度是多少呢?稍不留意,就会得到错误的结果21.很自然地,人们会问这样一个问题:是否存在一些编程技巧,能够降低这类错误发生的可能性?

这个编程技巧不仅存在,而且可以一言以蔽之:用一个入界点和第一个出界点来表示一个数值范围。具体而言,前面的例子我们不应说整数x满足边界条件x>=16且x<=37,而是说整数x满足边界条件x>=16且x<38.注意,这里下界是“入界点”,即包括在取值范围之中;而上界是“出界点”,即不包括取值范围之中。这种不对称也许从数学而言并不优美,但是它对于程序设计的简单效果却中以令人吃惊。

  1. 取值范围的大小就是上界与下界之差。38-16的值是22,恰恰 是不对称边界16和38之间所包括的元素数目。
  2. 如果取值范围为空,那么上界等于下界。这是第1条下拉推论。
  3. 即使取值范围为空,上界也永远不可能小于下界。

对于像C这样的数组下标从0开始的语言,不对称边界给程序设计带来的便利尤其明显;这种数组的上界(即第一个“出界点”)恰是数组元素的个数!因此,如果我们要在C语言中定义一个拥有10个元素的数组,那么0就是娄组下标的第一个“入界点”(指处于数组下标范围内的点,包括边界点),而10就是数组下标中的第一个“出界点”(指不在数组下标范围内的点,不含边界点)。正因为此,我们这样写:

而不是写成下面这样:

让我们作一个假设,如果C语言的for语句风格类似Algol或者Pascal语言,那么就会带来一个问题:下而这个语句的含义空间是什么?

如果10是包括取值范围内的“入界点”,那以i将取11个值,而不是10个值。如果10是不包括取值范围内的“出界点”,那么原来其他程序语言为背景的编程者会大为惊讶。

另一种考虑不对称边界的方式是,把上界视作某序列中第一个被占用的元素,而把下界视作序列中第一个被释放的元素。如图3.2所示:

当处理各种不同类型的缓冲区时,这种看待问题的方式就特别有用。例如,考虑这样一个函数,该函数的功能是将长度无规律的输入数据送到缓冲区(即一块能够容纳N个字符的内存)中去,每当这块内存被“填满”时,就将缓冲区的内容写出。缓冲区的声明可能是下面这个样子:

我们再设置一个指针变量,让它指向缓冲区的当前位置。

对于指针bufptr,我们应该把重点放在哪个方面呢?是让指针bufptr始终指向缓冲区中最后一个已占用的字符,还是让它指向缓冲区中第一个未占用字符?前一种很有吸引,但是考虑到我们对“不对称边界”的偏好,后一种选择更为适合。

按照“不对称边界”的惯例,我们可以这样编写语句:

这个语句把输入字符c放到缓冲区,然后指针bufptr递增1,又指向缓冲区中第1个未占用的字符。

根据前面对“不对称边界“的考察,当指针bufptr与&buffer[0]相等时,缓冲区存放的内容为空,因此初始化时声明缓冲区为空可以这样写:

或者,更简洁一点,直接写成:

任何时候缓冲区已存放的字符数都是bufptr-buffer,因此我们可以通过将这个表达式与N作比较,来判断疑问区是否已满。当缓冲区全部“填满”时,表达式bufptr-buffer就等于N,可以推断缓冲区中未占用的字符数为N-(bufptr-buffer)。

前面所有的这些预备知识一旦掌握,我们就可以开始编写程序了,假设这个函数的名称bufwrite。函数bufwrite有两个参数,第一个参数是一个指针,指向将要写入缓冲区的第1个字符;第二个参数是一个整数,代表将要写入缓冲区的字符数。假定我们可以调用函数flushbuffer来把缓冲区中的内容写出,而且函数flushbuffer会重置bufptr,使其指向缓冲区的起始位置。如下所示:

重复执行表达—n>=0只是进行n次迭代的一种方法。要验证这一点,我们可以考察是简单的特例情况,n=1.因为循环执行n次,每次迭代从输入缓冲区中取走一个字符,所以输入的每个字符都将得到处理,而且也不会额外执行多余的处理操作

注:在大多数C语言实现中,–n>=0至少与等效的n–>0一样快,甚至在某些C实现中还要更快,第一个表达式—n>=0的大小首先从n中减去1,然后将结果与0比较;第二个表达式则首先保存n,从n中减去1,然后比较保存值与0的大小。某些编译器如果其“智能”足够高,可以发现后一个操作有可以按照经写出来的更有效率的方式执行。但我们不应该依赖一点。

未经允许不得转载:TacuLee » C陷阱与缺陷之边界计算与不对称边界(上)

赞 (0)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址