"TCPL/3.3_Else-If"版本比较

<<Navigation: 执行失败 ['AllContext' object has no attribute 'values'] (see also the log)>>

3.3 Else-If else-if语句

The construction

   if (expression)
       statement
   else if (expression)
       statement
   else if (expression)
       statement
   else if (expression)
       statement
   else
       statement

occurs so often that it is worth a brief separate discussion. This sequence of if statements is the most general way of writing a multi-way decision. The expressions are evaluated in order; if an expression is true, the statement associated with it is executed, and this terminates the whole chain. As always, the code for each statement is either a single statement, or a group of them in braces.

在C语言中我们会经常用到下列结构：

   if (expression)
       statement
   else if (expression)
       statement
   else if (expression)
       statement
   else if (expression)
       statement
   else
       statement

因此我们在这里单独说明一下。这种if语句序列是编写多路判定最常用的方法。其中的各表达式将被依次求值，一旦某个表达式结果为真，则执行与之相关的语句，并终止整个语句序列的执行。同样，其中各语句既可以是单条语句，也可以是用花括号括住的复合语句。

The last else part handles the "none of the above" or default case where none of the other conditions is satisfied. Sometimes there is no explicit action for the default; in that case the trailing

   else
       statement

can be omitted, or it may be used for error checking to catch an "impossible" condition.

最后一个else部分用于处理“上述条件均不成立”的情况或默认情况，也就是当上面各条件都不满足时的情形。有时候并不需要针对默认情况执行显式的操作，这种情况下，可以把该结构末尾的

   else
       statement

部分省略掉；该部分也可以用来检查错误，以捕获“不可能”的条件。

To illustrate a three-way decision, here is a binary search function that decides if a particular value x occurs in the sorted array v. The elements of v must be in increasing order. The function returns the position (a number between 0 and n-1) if x occurs in v, and -1 if not.

这里通过一个折半查找函数说明三路判定程序的用法。该函数用于判定已排序的数组v中是否存在某个特定的值x。数组v的元素必须以升序排列。如果v中包含x，则该函数返回x在v中的位置(介于0～n-1之间的一个整数)；否则，该函数返回-1。

Binary search first compares the input value x to the middle element of the array v. If x is less than the middle value, searching focuses on the lower half of the table, otherwise on the upper half. In either case, the next step is to compare x to the middle element of the selected half. This process of dividing the range in two continues until the value is found or the range is empty.

   1    /* binsearch:  find x in v[0] <= v[1] <= ... <= v[n-1] */
   2    int binsearch(int x, int v[], int n)
   3    {
   4        int low, high, mid;
   5 
   6        low = 0;
   7        high = n - 1;
   8        while (low <= high) {
   9            mid = (low+high)/2;
  10            if (x < v[mid])
  11                high = mid + 1;
  12            else if (x  > v[mid])
  13                low = mid + 1;
  14            else    /* found match */
  15                return mid;
  16        }
  17        return -1;   /* no match */
  18    }

The fundamental decision is whether x is less than, greater than, or equal to the middle element v[mid] at each step; this is a natural for else-if.

在折半查找时，首先将输入值x与数组v的中间元素进行比较。如果x小于中间元素的值，则在该数组的前半部分查找；否则，在该数组的后半部分查找。在这两种情况下，下一步都是将x与所选部分的中间元素进行比较。这个过程一直进行下去，直到找到指定的值或查找范围为空。

   1    /* binsearch:  find x in v[0] <= v[1] <= ... <= v[n-1] */
   2    int binsearch(int x, int v[], int n)
   3    {
   4        int low, high, mid;
   5 
   6        low = 0;
   7        high = n - 1;
   8        while (low <= high) {
   9            mid = (low+high)/2;
  10            if (x < v[mid])
  11                high = mid + 1;
  12            else if (x  > v[mid])
  13                low = mid + 1;
  14            else    /* found match */
  15                return mid;
  16        }
  17        return -1;   /* no match */
  18    }

该函数的基本判定是：在每一步判断x小于、大于还是等于中间元素v[mid]。使用else-if结构执行这种判定很自然。

Exercise 3-1. Our binary search makes two tests inside the loop, when one would suffice (at the price of more tests outside.) Write a version with only one test inside the loop and measure the difference in run-time.

练习3-1 在上面有关折半查找的例子中，while循环语句内共执行了两次测试，其实只要一次就足够(代价是将更多的测试在循环外执行)。重写该函数，使得在循环内部只执行一次测试。比较两种版本函数的运行时间。