Предыдущий раздел

Указатели

Векторы (одномерные массивы)

Должен извиниться за путаницу в терминологии (не я ее придумал). Вектор любой размерности мы изображаем одномерным массивом, а размерности вектора соответствует длина массива. Матрица произвольного размера – это двумерный массив. Массивы высших размерностей соотвествуют еще более сложным математическим объектам.

Сначала ряд типичных ошибок.

  Задача 1. Написать функцию, вычисляющую евклидову норму n-мерного вектора (или, по школьному, выражающую длину трехмерного вектора через его координаты; напомню формулу: ).
Ошибка № 1. Обычная первая попытка решения задачи:
 

 
Наш любимый Turbo Pascal откажется понимать заголовок такой функции. Логика здесь такова: так как типы массива v и формального аргумента – массива x описаны в разных местах, то это разные типы, несмотря на то, что их описания текстуально совпадают!

Как с этим справиться? Обычный ответ – ввести специальный тип данных:
 

Вот это уже рабочая программа (если дописать {Ввод массива v}). Но она уже демонстрирует другую, менее очевидную ошибку.
Ошибка № 2. Я не зря назвал введенный тип так странно: vector10. Предположим, нам теперь надо работать с 12-мерными векторами, а завтра придется иметь дело с 6-мерными, с 50-мерными, и т.д. И что же, каждый раз заводить специальный тип данных и заново компилировать функцию norm? Она, конечно, простенькая, но ведь это – всего лишь демонстрирующий пример.

Еще хуже будут обстоять дела, если нам надо в одной программе вычислять нормы векторов разной размерности. Тогда придется на каждую размерность писать свою функцию: norm10, norm12, norm6, norm50, и т.д. Если мы хотим откомпилировать раз и навсегда процедуру или функцию, работающую с массивами, и иметь возможность пользоваться ею для обработки массивов произвольного размера, то надо поискать других путей.

Запрограммировав в Pascal жесткую систему ограничений на совпадение типов данных, его авторы создали массу неудобств для составления общеполезных процедур и функций вычислительного характера. Поэтому пришлось изобретать обходные лазейки. Одна из них – это использование вместо массивов указателей на их элементы. (Я не утверждаю, что цель введения указателей ограничивается только предоставлением лазеек для обхода ограничений Pascal, но для вычислительных процедур это, похоже, так).

Использование указателей требует значительного напряжения, ибо при неаккуратной работе можно, например, запросто запороть систему и тогда для продолжения работы придется нажимать кнопку "Reset" – с потерей последних данных! Поэтому эту тему надо разобрать внимательно.

Почему математики всего мира, кроме нашей уникальной страны, предпочитают старый добрый FORTRAN (в современной версии FORTRAN-88 или Microsoft FORTRAN PowerStation)? Потому, например, что хотя там тоже работа строится на основе указателей, но это сделано незаметно для рядового программиста.

Вот теперь настало время открыть учебник по языку Pascal и почитать в нем раздел, посвященный указателям.

Почитали? Тогда, наконец, займемся нашей учебной задачей.

Введем тип данных RealPtr – указатель на переменную типа REAL : TYPE RealPtr = ^REAL;. Указатель содержит всего лишь адрес оперативной памяти, а тип REAL указывает компилятору, как он должен работать с битами информации, расположенными по этому адресу. В качестве аргумента функции norm используем указатель p:RealPtr; и будем передавать через него адрес первого элемента массива. Количество элементов придется указать отдельно. Мы используем то обстоятельство, что элементы одномерного числового массива располагаются компилятором в оперативной памяти подряд, начиная с первого и до последнего.

Обращение к элементам обрабатываемого массива, естественно, производится через указатель p. Точнее, элементом массива является выражение p^. Для того, чтобы это выражение обозначало различные элементы массива, указатель p перемещают по массиву посредством операций инкрементирования Inc и декрементирования Dec.

Надо тщательно следить за тем, чтобы перемещающийся по массиву указатель всегда указывал на элемент массива, а не мимо него, причем именно на тот элемент, который нужен. Особенно пристально надо проверять первый и последний проходы тела цикла.

Вот что получается, если применить описанный подход к функции norm:

Можно взять этот файл (d3.pas), если он представляет для вас какой-то интерес.

Здесь хочется сделать нескольно замечаний.
1. Работоспособность функции norm теперь не ограничена заданной фиксированной размерностью массива v, без перекомпиляции функция нормально справится с любым другим вектором с любой разумной размерностью, которая сообщается ей через параметр n.
2. Ошибка в значении параметра n в сторону увеличения приведет к использованию в качестве компонент вектора совершенно бессмысленных значений. Такая ошибка была невозможна в предыдущем решении, а здесь надо проявить внимание. Зато возможность уменьшения n может даже оказаться полезной, если нас интересует, например, норма вектора, составленного из части компонент вектора v.
3. После последнего прохода цикла указатель p станет указывать уже куда-то мимо вектора v, но это не важно, т.к. "значение", на которое стал указывать p, нигде не будет использовано.

Этот подход эффективнее и удобнее, если в ходе выполнения процедуры элементы вспомогательного массива (один или несколько раз) просматриваются подряд, один за другим, в порядке возрастания или убывания номера.

Надо только заметить, что после прохода указателя по массиву он уже не показывает на его начало. Поэтому если нужен повторный просмотр массива, то приходится специально перемещать его в нужное место. Это можно сделать, выполняя Inc или Dec на подходящее число шагов. Другой способ проще и спокойнее: объявить локальный вспомогательный указатель, скажем, VAR pp:RealPtr;, присвоить ему pp := p;, после чего для прохода по массиву использовать указатель pp. Таким образом, указатель p остается неизменным и при необходимости повторного просмотра массива можно снова присвоить pp := p;.

Другой подход к использованию массива заранее неизвестной длины можно предложить для тех, кто продолжает испытывать неуверенность в своем умении перемещать указатели и хочет по-прежнему работать с индексом массива. Должен сказать, что с программистской точки зрения он выглядит неизящно и использует потенциально опасные приемы. Я продемонстрирую его на той же задаче.

Можно взять и этот файл (d4.pas).

Теперь комментарии.
    1
. После объявление переменной-указателя pp:^ar выражение pp^ означает массив из действительных чисел, а pp^[i] – его i-тый элемент. Формально массив pp^ содержит лишь один элемент.
    2. Конструкция ABSOLUTE p размещает указатель pp там же в оперативной памяти, в тех же байтах, где расположен и указатель p. Т.е. оба этих указателя ВСЕГДА содержат один и тот же адрес, хотя адресуют данные разных типов. Использование такой конструкции противоречит основным принципам структурного программирования и языка Pascal и поэтому категорически не рекомендуется. Нетрудно представить, сколько трудно обнаруживаемых ошибок можно наделать при широком использовании совмещения в памяти данных разных типов! Однако, в указанной ситуации это сравнительно безопасно.
    3. Но именно благодаря такому фокусу первый элемент массива pp^ совпадает с первым элементом массива v, адрес которого был передан функции norm в качестве параметра. А следовательно, совпадают и следующие элементы, до тех пор, пока они существуют.
    4. Комментарий {$R-} является в действительности директивой компилятора, отключающей проверку соотвествия индекса элемента массива объявленной размерности массива. Иначе способ использования элементов массива pp^ будет противоречить объявлению ARRAY[1..] OF REAL;. Благодаря директиве компилятора в массиве pp^ может быть использовано любое количество элементов.

Разработчик процедуры (функции) должен тщательно следить за тем, чтобы номер используемого элемента массива не превосходил передаваемой в качестве параметра реальной размерности массива, а на пользователя процедуры возлагается ответственность за правильность значения этого параметра.

    5. Комментарий { $R+} является просто комментарием, но может стать директивой компилятора, включающей контроль за правильностью значений индекса массива, если удалить пробел между знаками { и $. Режим контроля за индексами управляется также флажком Options/Compiler/Range checking. По умолчанию режим проверки индексов отключен, но пока идет отладка, его бывает целесообразно включать. Так как перед функцией norm нам приходится его отключать, то после нее следует предусмотреть восстановление режима контроля. Вот тогда и надо (временно, до завершения отладки) удалить указанный пробел.

С точки зрения скорости работы второй подход чуть менее эффективен, чем первый. Но на мой взгляд, его основной недостаток не в этом. Просто он как-то менее эстетичен.

А вот как просто и симпатично выглядит эта же функция, написанная на языке FORTRAN:
В действительности функции передается только адрес первого элемента массива, обращение же к его элементам тоже осуществляется через указатели. Но наша голова от этого не болит.

  Задача 2. Спланировать и написать модуль vector.tpu, содержащий функцию norm и другие процедуры и функции, осуществляющие стандартный набор операций над векторами.

Начало работы над этой задачей – планирование, т.е.
1) определение набора операций над векторами для внесения в модуль;
2) составление заголовков процедур и функций;
3) сочинение (в первой редакции) документации на модуль.

Эта работа проделана (возможно, далеко не идеально) и результат вы можете увидеть здесь.

Внимание! Опасная ошибка

Следующий пример показывает очень опасную ошибку, часто совершаемую новичками при работе с указателями.
 

Выполнение такой программы обычно приводит к тому, что компьютер приходится аварийно перезагружать! Возьмите файл d5.pas и (осторожно!) выполните эту программу пошагово под отладчиком, включив окно Watch из меню Debug и внеся в список наблюдаемых величин указатель pv. Можно заметить, что до первого прохода цикла pv = nil, что в переводе на понятный язык означает просто-напросто PTR($0, $0) – указатель на начало оперативной памяти компьютера. Но там находится жизненно важная для операционной системы информация – таблица векторов прерываний, – а мы записываем по этому адресу 10 * 6 = 60 байт собственных глупостей.
Не бойтесь выполнять эту программу пошагово под отладчиком. Как правило, он предусматривает возможность таких ошибок и предохраняет систему от их последствий. К сожалению, он не сообщает нам об этой ошибке, а система программирования Turbo Pascal никак на нее не реагирует. Поэтому выполнение откомпилированной программы приведет к катастрофе.
В качестве средства предохранения сформулируем

Правило. Перед использованием указателя его надо инициализировать, т.е. придать ему значение адреса той переменной, которую мы хотим обрабатывать.

Правильный вариант программы:
 

Здесь можно отметить, что в языках семейства FORTRAN подобные ошибки невозможны, так как эти языки не предоставляют программисту возможности непосредственно оперировать с указателями. Для математика это даже лучше!

Матрицы (двумерные массивы)

Буквально несколько слов. Если процедура (функция) должна работать с матрицей вида A: ARRAY[1..3, 1..5] OF REAL;, то мы передаем ей указатель на первый элемент матрицы (@(A[1,1])) и обе размерности матрицы (в нашем примере 3 и 5). Соответствующие формальные аргументы обозначим
p: RealPtr; n,m:WORD;  ...               
{p - указатель на первый элемент матрицы,
 n - количество строк,                   
 m - количество столбцов матрицы}        

Важно, чтобы переданное значение m точно соответствовало количеству столбцов в объявлении матрицы A (в данном примере 5). Тогда расположение элементов массива A в памяти можно изобразить следующим образом:

A[1,1] A[1,2]...A[1,m] A[2,1] A[2,2]...A[2,m] A[3,1] и т.д.

В этом случае все нужные элементы матрицы расположены в памяти подряд. Внутри процедуры (функции) элементы матрицы представляются выстроенными в одномерный массив. Способ обращения к элементу A[i,j] зависит от выбранного подхода к организации работы с элементами одномерного массива (см. по этому поводу тему "Векторы (одномерные массивы)").

При первом подходе он производится следующим образом:

VAR pp: RealPtr;     
...                  
pp := p;             
Inc(pp, (i-1)*m+j-1);


после чего выражение pp^ содержит требуемое значение. (Подсчитайте, например, насколько надо передвинуть указатель, чтобы он перешел с элемента A[1,1] на элемент A[2,3].)

При втором подходе все выглядит проще: элемент матрицы представляется в виде

pp^[(i-1)*m+j].

Первый подход заметно эффективнее второго, когда элементы матрицы используются не произвольным образом, подряд, а в порядке возрастания или убывания номера. Это можно проиллюстирировать на примере следующей несложной задачи.

  Задача 3. Добавить в модуль vector.tpu процедуру умножения вектора на матрицу (линейное преобразование вектора).

Решение.

Использование указателя для организации цикла

Вернемся еще раз к написанной функции norm для вычисления нормы вектора. Обратите внимание, что индекс цикла i использовался там лишь для счета повторений цикла. При каждом проходе тела цикла индекс i увеличивался на 1 до тех пор, пока его значение не превзойдет длины обрабатываемого массива. Элементы же массива перебирались с помощью указателя, который перемещается параллельно с увеличением i. Следовательно, обнаружить конец массива и прекратить повторения цикла можно просто обнаружив, что перемещающийся указатель вышел за пределы массива. Тогда индекс цикла i окажется лишним! На этой идее основан следующий "крутой" программистский вариант написания функции norm. Он оказывается эффективнее с точки зрения количества операций:
 

Вот теперь, в ходе выполнения цикла, указатель p будет перемещаться вправо по массиву до тех пор, пока не сравняется с указателем pp. Значение, на которое указывает pp, обработано уже не будет, т.к. выполнение цикла как раз перед этим завершится. Это осуществляется следующим участком кода программы:


 
Получившуюся функцию вы можете взять (в файле d6.pas) для использования (и для образца при проектировании других подобных процедур и функций).

Следующий раздел