1

In Chapter 6 of K&R, we go over accessing elements of a structure by pointers. We are given a function:

struct key *binsearch(char *word, struct key *tab, int n)
{
    int cond;
    struct key *low = &tab[0];
    struct key *high = &tab[n];
    struct key *mid;

    while (low < high) {
        mid = low + (high-low) / 2;
        if ((cond = strcmp(word, mid->word)) < 0)
            high = mid;
        else if (cond > 0)
            low = mid + 1;
        else
            return mid;
    }
    return NULL;
}

In an earlier version of this program where we weren't using pointers, we could compute mid as mid = (low+high)/2 but now we need to compute mid as mid = low + (high-low) / 2

I understand that you can't add pointers because logically the result doesn't return anything useful, but what I don't understand is aren't we still adding pointers with mid = low + (high-low) / 2? We are adding low to the result of (high-low)/2?

4

3 回答 3

0

我在逻辑上发现了我的误解。当您减去两个指针时，结果是这两个指针之间的距离，可以添加到指针。

于 2013-09-06T15:29:39.840 回答
0

一种看待这个的方法是，计算是：

 temp = ( high - low ) / 2

temp，一个整数值，是高低指针之间距离的一半。

 mid = low + temp

mid 是低地址加上偏移量 temp。temp 不是指针，而是索引量。

因此，此方法不会添加两个指针。

于 2013-09-06T16:20:51.657 回答
0

您的示例中的指针只是指向一个数组，因此指针本身将按顺序编号（在它们指向的每个元素之间增加 4 或 8 个字节）。因此，从低位减去高位指针可以得到数组的范围（以字节为单位）。将其除以二，然后将其添加到基础上以找到中点。它基本上与通过索引数组来执行此操作相同。

更有趣的问题是为什么数学逻辑反转为：

mid = low + (high - low)/2; // Dealing with pointers

而不是：

mid = (low + high) /2; // Indexing an array using integers

快速回答：C 语言禁止添加两个指针 GCC 错误：二进制操作数无效 +

更长的答案：加法（后一种方法）的问题是存在溢出数据类型最大范围的风险。对于 32 位计算机（尽管编写 K&R 时可能是 16 位），整数和指针的最大范围分别是 +/-20 亿和 4Gb。

对于一个数组的索引，数组不可能有超过几百万个条目，所以即使 10,000,000 + 10,000,000 也不会导致溢出。

但是，在处理指针时，您不会从 0 开始。您会被分配一个从大量开始的内存块。取决于操作系统和编译器，特别是如果您正在处理堆栈上的项目，完全有可能添加两个指针时您可能会在 32 位范围内溢出，因此 C 不允许这样做，您需要减去指针。

于 2013-09-06T16:18:26.193 回答