Управление указателем K & R

Question

В главе 6 из K & R мы переходим к обращению к элементам структуры указателями. Нам дана функция:

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; 
} 

В более ранней версии этой программы, в которой мы не использовали указатели, мы могли бы вычислить mid как mid = (low+high)/2 но теперь нам нужно вычислить mid, как mid = low + (high-low)/2

Я понимаю, что вы не можете добавлять указатели, потому что логически результат не возвращает ничего полезного, но то, что я не понимаю, - это мы не добавляем указатели с mid = low + (high-low)/2? Мы добавляем low к результату (high-low)/2?

Answer 1

Я понял свое недоразумение в логике. Когда вы вычитаете два указателя, результатом будет расстояние между этими двумя указателями, которое можно добавить к указателю.

Answer 2

Указатели в вашем примере просто указывают на массив, и поэтому сами указатели будут последовательно пронумерованы (увеличиваются на 4 или 8 байт между каждым элементом, на который они указывают). Таким образом, вычитая высокий указатель из нижнего, дайте вам диапазон (в байтах) массива. Разделите это на два, а затем добавьте это на базу, чтобы найти среднюю точку. Это в основном то же самое, что и при индексировании массива.

Более интересный вопрос, почему это математическая логика обратная к:

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

, а не:

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

Быстрый ответ: Язык C запрещает добавление двух указателей GCC Error: Invalid operands to binary +

Более длинный ответ: Проблема с добавлением (последний подход) заключается в том, что существует риск переполнения максимального диапазона типа данных. Для 32-битного компьютера (хотя 16 бит, вероятно, был нормой, когда был записан K & R) максимальный диапазон целого числа и указателя составляет +/- 2billion и 4Gb соответственно.

Для индексирования массива маловероятно, что массив будет содержать более нескольких миллионов записей, поэтому даже 10 000 000 + 10 000 000 не приведет к переполнению.

Однако при работе с указателями вы не начинаете с 0. Вы получаете выделенный блок памяти, начиная с большого числа. В зависимости от операционной системы и компилятора, и особенно если вы имеете дело с элементами в стеке, это вполне возможно при добавлении двух указателей, которые вы можете переполнить в 32-битном диапазоне, поэтому C не позволяет этого, и вам нужно вычесть указатели.

Answer 3

Один из способов смотреть на это, является то, что вычисление:

temp = (high - low)/2 

температура, целое значение, равно половина расстояния между верхними и нижними указателями.

mid = low + temp 

средний - низкий адрес плюс смещение, темп. temp НЕ является указателем, скорее это значение индекса.

Таким образом, этот метод делает NOT Добавить два указателя.