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

Переход от индексов к указателям

Раздел написан студентами 32 группы математического фукультета КубГУ В.В. Малаховым и А.А. Очередько в 2005 году под руководством и на основе лекций В.З. Цалюка.

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

Давайте этим и займёмся на конкретном примере. Рассмотрим следующую задачу:

  Задача 1. Написать функцию, вычисляющую скалярное произведение двух векторов a и b размерности n (Напомним, что скалярное произведение вычисляется по формуле: ).
Решение.

Этап 1.
Для начала надо вспомнить работу с индексами и написать функцию подсчёта скалярного произведения в векторной форме, отладить её.

Вот как она должна выглядеть:

Входящие параметры: a, b - массивы размерности 5 чисел типа Real .
Функция возвращает скалярное произведение векторов, расположенных в массивах a и b.

При желании можно взять этот файл здесь.

Этап 2.
Все размерности вносятся в раздел CONST. А все числа, зависящие от них, заменяются на свои выражения через эти размерности.

Поясним, зачем. Допустим, Вы написали довольно объёмную программу для работы с векторами размерости 10. Она работает, и всё хорошо. Но обстоятельства изменились, и Вам необходима такая же программа, но работающая уже с векторами другой размерности. Придётся изменять старую? Это сравнимо с написанием новой. И где гарантия того, что Вы ничего не забудете. Поиски ошибки в этом случае займут ещё больше времени. Потому хотелось бы, чтобы все базовые значения находились в одном месте, а в самой программе использовались их "виртуальные двойники". Тогда изменение базовых значений повлечёт автоматическую замену их "двойников" на местах. Так вот, раздел CONST как раз и выполняет роль того места, где содержаться все базовые значения Вашей программы, а обозначения констант - это и есть их "виртуальные двойники".

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

Кажется, что всё в порядке. Да и тестовая программа тоже работает. А Вы измените размерность (что, вообще то, делать необходимо, но большинство почему то об этом часто забывает). Например, CONST n = 3. Готовы поспорить, Вы получили совсем не то, что ожидали. Почему? Всё просто. В разделе CONST определена уже новая размерность - n, а вот в самой процедуре, при задании условия выхода из цикла FOR, она осталась прежней - 5. Отсюда и несоответствие длины вектора числу проходов цикла, и, как следствие, полная чушь в ответе. Потому считаем целесообразным сделать следующее замечание:

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

Ну а вот как правильно должна выглядеть функция на этом этапе.

Попробуйте теперь изменить размерность. Работает? Отлично.

Кстати, этот файл тоже можно взять.

Этап 3.
Размерности вносятся в список аргументов функции.

ScalProd (a,b: Vec; n: Word): Real;
Это позволит регулировать размерности внутри программы, т.е. появляется возможность работать с массивами, размерности которых меньше указанных в разделе CONST. А если быть точнее, то достаточно внести минимальные изменения в основную программу: всего лишь добавить строку k := {размерность} ; и передать k функции в качестве аргумента: s := ScalProd (a, b, k);. Теперь наша программа будет работать с векторами любой размерности не более, например, 10. Вот как она будет выглядеть после всех этих преобразований:

И этим файлом мы можем поделиться .

А сейчас, как это ни странно, пришло время нарушить работоспособность полученной функции.

Этап 4.
Удалить все описания типов из раздела TYPE. Сделать размерности переменными (убрать раздел CONST)

Особых комментариев здесь, на наш взгляд, не требуется. Просто готовим программу к более существенным изменениям. Вот как это выглядит.

Может возникнуть вопрос, зачем оставлять пустой раздел TYPE (тем более что компилятор сочтёт это за ошибку и потребует его заполнить)? Отвечаем: он необходим на следующих этапах. Что же касается протестов компилятора, то после наших преобразований программа и так уже вышла из строя: в Turbo Pascal не существует типа данных Vec (он был введён нами), потому компилятор в любом случае откажется компилировать функцию и выдаст сообщение о том, что этот тип данных ему не известен.

А вот раздел CONST нам действительно не понадобится: мы же собираемся работать с массивами произвольной размерности.

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

Следуя написанному выше, мы должны были бы поступить так: FUNCTION ScalProd (a,b: ^Real; n: Word): Real;. Но так как раз делать и нельзя. Дело в том, что компилятор не воспринимает записи ^{тип данных} как идентификаторы типа, если они стоят в списке аргументов функции. Потому давайте вспомним, что существует принятое у нас обозначение такой вещи как ^Real - это уже известный Вам тип данных RealPtr. Поэтому вернёмся в раздел TYPE и опишем его: TYPE RealPtr = ^Real;. А вот что получилось в результате:

Как уже говорилось, сейчас функция не работает. Если Вам интересно - почему, то рассказываем. Всё дело в уже поднабившем оскомину несоответствии типов. Если посмотреть на наши творения несколько повнимательней, то можно заметить, что в качестве аргументов мы передаём функции указатели, а работать она умеет пока только с индексными выражениями. Посему она и не знает, что делать с полученными данными, так как не понимает, что, вообще, мы ей передаём в качестве аргументов.

Ещё одно замечание. Не стоит забывать вносить соответствующие изменения в тестирующую программу: вместо s := ScalProd (a, b, k); уже пора бы написать s := ScalProd (@a, @b, k);.

Несколько слов об операторе @ (или @). Мы привыкли величать его "собакой". Официально же символ @ носит название "ат" или, на английский манер,"at". Этот предлог имеет много значений. В частности, он описывает местоположение предмета ("где находится").Та же функция закрепилась и за @.

В Turbo Pascal он определяет адрес той переменной, перед которой стоит. То есть, @a - это не что иное, как адрес переменной a. Причём оператор @, условно называемый "Взятие адреса", очень удобен тем, что тип его результата такой же, как и у Nil, то есть Pointer, так что этот оператор может применяться для любых типов указателей. Другими словами, он определяет адрес переменной любого типа, будь то хоть Word, хоть ARRAY, хоть String. В связи с этим хотелось бы предупредить, что Turbo Pascal отказывается от проверки типов в этом случае, а потому ответственность за их соответствие полностью лежит на Вас. Заметим ещё, что @ относится к операторам с "первым приоритетом", то есть к тем, что выполняются в первую очередь.

Этап 6.
Преобразования внутри тела функции.

На этом этапе можно воспользоваться одним из следующих подходов:
    1. Постепенно избавляться от индексов и полностью переходить на указатели.
    2. Постараться объединить удобство индексов с эффективностью указателей (использовать массив фиктивной длинны).

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

Подход 1.
Заменить каждое индексное выражение на указатели.

Для этого введём внутри функции новые указатели:
VAR i: Word;  
s: Real;      
pa,pb: RealPtr;
Затем инициализируем их:
pa := a;
pb := b;
Теперь мы имеем два указателя, которые и будут перемещаться по нашим векторам. Осталось каждое индексное выражение заменить на значение переменной, хранящееся по указанному адресу (в данном случае адреса задают указатели pa и pb), а вместо изменения индексов предусмотреть перемещение указателей( напомню, что указатели принято перемещать с помощью процедур Inc и Dec). Вот что Вы должны были получить в итоге:

Важный момент: после этих преобразований программа уже должна работать.
Для заинтересованных: файл можно получить здесь.

Подход 2.
Внести в раздел TYPE тип данных "массив фиктивной длинны". Каждое индексное выражение заменить на его "фиктивный" эквивалент.

Основная теория, необходимая на этом этапе, уже изложена в разделе Указатели (который Вы уже должны были внимательно изучить). Потому для начала приведём исходный текст функции, а уж потом сделаем некоторые комментарии.

Ну, а теперь пояснения.

Как уже было сказано выше, введём новый тип данных
ar = ARRAY [1..1] of Real;
Далее внесём в список локальных переменных функции два новых указателя:
pa: ^ar ABSOLUTE a;
pb: ^ar ABSOLUTE b;
Заметьте, что переменные pa и pb объявлены отдельно друг от друга. Это связано с тем, что эти указатели отвечают за перемещение по разным векторам, а потому и храниться должны в соответствующих участках памяти. Так что если Вы попробуете сделать так: pa, pb:  ar ABSOLUTE a;, то Вы просто получите два указателя, указывающие на один и тот же вектор. А функция выдаст Вам не желаемое скалярное произведение двух векторов, а скалярный квадрат одного из них (в нашем случае, вектора a). И, наконец, так как элементы "реальных" массивов, хранящиеся по адресам a и b, "совпадают" с соответствующими элементами массивов фиктивной длины, которым соответствуют указатели pa и pb, то воспользуемся этим при организации цикла
FOR i := 1 TO n DO          
   s := s + pa^[i] * pb^[i];

Если Вам интересен этот файл, то можете взять его здесь.

Раз уж мы упомянули массивы фиктивной длины, то продемонстрируем ещё один подход к решению поставленной задачи.

Подход 3.

Теперь мы будем использовать не сам массив, а только указатель на него.

Как ни странно, но здесь и пояснять уже нечего. Прошлые этапы сохраняются, а все операции на этом этапе уже описаны ранее для прошлых подходов. Если не верите, взгляните сами:

Увидели сходство? Самое интересное, что в итоге у нас получилось нечто среднее между первым и вторым подходами.

При желании можно взять этот файл здесь

Функция работает, но хорошо ли? Вряд ли. Поэтому давайте не будем лениться и всё-таки поднапряжём свою голову.

Этап 7.
Оптимизация. Здесь не существует конкретных указаний, так как каждая программа нуждается в собственном подходе.

Что же касается разбираемого примера, то здесь доработки будут такие.

Подход 1.

1) Заметим, что проход по обоим векторам осуществляется всего один раз, поэтому от вспомогательных указателей pa и pb можно и отказаться. Вместо них будем использовать уже имеющиеся a и b.

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

2) Для организации цикла используем указатели. Как это осуществить уже рассказывалось в разделе Указатели. Вспомнили? Если нет, то предлагаем вернуться в этот раздел и прочитать его снова.
А вот что должно было получиться в итоге:

Окончательный вариант файла Вы можете взять здесь.

Подход 2.

Этот вариант программы не нуждается в доработке, потому последний этап для него излишен.

Подход 3.

А здесь опять пояснять особо нечего. Просто заметим, что, как и в первом подходе, "проход по обоим векторам осуществляется всего один раз, поэтому от вспомогательных указателей pa и pb можно и отказаться. Вместо них будем использовать уже имеющиеся a и b". Вот, вообще говоря, и всё. Итог:

и окончательный вариант файла.

А теперь

 Задача 2. Дано
Matr = ARRAY [1..3, 1..4] OF Real;
Vec3 = ARRAY [1..3] OF Real;      
Vec4 = ARRAY [1..4] OF Real;     

Написать процедуру умножения матрицы на вектор в векторной форме и перевести её на язык указателей по изложенной выше схеме.

Похожая задача уже была поставлена ранее в разделе Указатели. Там же можно найти и ссылку Решение. Потому предлагаем сравнить полученную Вами программу с уже имеющимся решением и сделать соответствующие выводы.

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