Информатика_Гуда

Глава 6. Алгоритмизация и программирование

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

Примеры рекурсивных подпрограмм.

1. Описать рекурсивную функцию digit без параметров, которая под- считывает количество цифр в тексте, заданном во входном файле (за текстом следует точка).

Program rec_4; Var k:integer;

Function digits:integer; Var

ñ:char;

d:integer; Begin

Read (c); d := 0;

If c<> ' · ' Then

If (c <= '9') and (c >= '0') Then d := 1 + digits

Else d := digits; digits := d;

End;

Begin

Write ('Введите текст, последний символ — точка '); k := digits;

writeln(k);

end.

Напечатать в обратном порядке заданный во входном файле текст (за текстом следует точка).

Program rec_5; Procedure perevert;

Var c:char;

Begin

281

Информатика

Read (c);

if c <> '·' then perevert; write(c);

End; Begin

Write('Введите текст'); Perevert;

End.

6.12. Программные модули

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

Модуль имеет имя и может содержать описание многих процедур и функций, а также описания констант, типов данных и переменных. Каждый программный модуль транслируется отдельно, оттранслированные модули объединяются в выполнимую программу — этот процесс называется «сборкой».

Однажды написанный и оттранслированный модуль можно многократно использовать в различных программах. Это позволяет:

•сэкономить время и силы программиста;

•сократить время трансляции;

•уберечь от искажений исходный текст модуля.

Чтобы подключить модуль к программе и сделать видимым его содержимое, достаточно упомянуть его имя в разделе USES <имя модуля> (должно быть первым предложением программы).

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

•для размещения в памяти большой программы может не хватить одного сегмента памяти (его размер максимум 64 Кб). Количество используемых модулей ограничивается лишь доступной памятью;

•в большинстве реальных применений ЭВМ нужны библиотеки блоков (процедур и функций) с простым доступом к блокам.

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

282

Глава 6. Алгоритмизация и программирование

6.12.1. Структура программного модуля

UNIT <имя модуля> (заголовок модуля)

. . . .

INTERFACE — интерфейсные раздел («видимая» часть модуля)

. . . .

IMPLEMENTATION — раздел реализации («черный ящик»)

. . . .

[BEGIN] — раздел инициализации (необязательный)

. . . .

END.

Имя модуля должно совпадать с именем дискового файла, в который помещается исходный текст модуля. Имя модуля служит для его связи с другими модулями и основной программой. Эта связь устанавливается предложением UNIT USES <список модулей>.

Âосновной программе с USES должен начинаться раздел описаний.

Âмодулях USES может следовать сразу за зарезервированным словом INTERFACE, либо за IMPLEMENTATION (либо и там, и там).

Интерфейсный раздел содержит объявления всех глобальных объектов, констант, переменных, типов, подпрограмм модуля, которые должны быть доступны основной программе и другим модулям. При объявлении глобальных подпрограмм в интерфейсной части указывается только их заголовок. Зачем? Без информации о формальных параметрах блоков нельзя правильно «собрать» программу из модулей.

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

èускоряет подготовку исходных текстов.

Например:

UNIT M1;

Interface

Var x:integer;

Procedure Sum(a,b: integer, var s: integer);

.. .

Если теперь в программе написать предложение USES M1;, то в основной программе станет доступным переменная Х и процедура Sum.

283

Информатика

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

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

Например:

. . .

Implementation Procedure Sum;

Begin

S:= a + b End;

Раздел инициализации завершает модуль, может отсутствовать (тогда нет и BEGIN) или быть пустым. Описывает «разовые» подготовительные действия, восполняемые при загрузке программы в память. Содержит исполняемые операторы, которые выполняются до передачи управления основной программе и обычно используются для подготовки е¸ работы. Если модулей несколько, то операторы данного раздела выполняются в порядке указания им¸н в USES. Например, здесь могут инициализироваться (задаваться начальными значениями) переменные, открываться файлы и т. д.

Пример:

{Модуль} UNIT M1; Interface

Var x:integer;

Procedure Sum(a,b:integer; var s:integer); Implementation

Procedure Sum; Begin S := a + b; End;

end.

284

Глава 6. Алгоритмизация и программирование

{Основная программа} Program main;

Uses M1;

Var y,z:integer; Begin

Readln(x,y);

sum(x,y,z);

Writeln(z)

end.

Модуль следует хранить в одноим¸нном файле с расширением PAS.

6.12.2. Трансляция модуля. «Сборка» программы

Результатом трансляции модуля является файл с тем же именем и расширением TRU. Он должен записываться на диск, тогда как результат трансляции программы в целом (EXE — файл) может оставаться в оперативной памяти.

Интерфейсная часть нужна для того, чтобы при получении файла проверить правильность обращения к блокам модуля.

В интерфейсной среде Паскаля в главном меню следует использовать подменю Compile. Пункты этого меню :

Compile (Alt — F9) Make F9

Build

Destination Memory Primary file

Первые три предназначены для запуска трансляции.

I. Если использовать Compile, то необходимо установить «Destination Disk», оттранслировать модуль, затем оттранслировать программу. Файл с расширением TRU должен находиться в каталоге, указанном в опции UNIT DIRECTORIES.

Пункты Make и Build — удобнее.

II. Make — для каждого модуля проверяет:

•существование TRU-файла. Если его нет, то он созда¸тся пут¸м трансляции исходного текста модуля;

•соответствие TRU-файла исходному тексту модуля (в него могут быть внесены изменения, в этом случае TRU-файл созда¸тся заново автоматически);

285

Информатика

• неизменность интерфейсного раздела модуля (в противном случае перекомпилируются все модули, в начале которых данный модуль указан в разделе USES).

Эти пункты не требуют обязательных исходных текстов модулей. III. Build — в отличии от Make, требует наличия исходных текстов

вcех модулей, так как все они компилируются (дольше!), в остальном совпадает.

IV. Run (выполнение).

Âслучаях II — IV программа и модули транслируются совместно. Активнымдолжнобытьокноосновнойпрограммы.(Иначе—имяфайла основной программы должно быть указано в опции Primary file).

Âобщем случае, ссылки модулей друг на друга могут образовывать сложные структуры.

6.12.3. Ссылки на модули

Модуль как программа может использовать объекты, описанные в других модулях. Если эти объекты находятся в интерфейсном разделе, то он должен начинаться со слова USES, в котором перечисляются имена всех модулей.

Если на объекты есть ссылки только из раздела реализации, предложение USES может находиться в разделе реализации.

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

Основная программа	Unit A1;	Unit A2;
USES A1;	interface	interface
.	USES A2;	…
.	…	implementation
.	implementation	…
begin	…
end.	end.	end.

Рис. 6.2

Взаимные ссылки двух модулей возможны только из разделов реализации (рис. 6.3).

286

Глава 6. Алгоритмизация и программирование

Unit A1; interface

…

implementation USES A2;

…

end.

Рис. 6.3

Unit A2; interface

…

implementation USES A1;

…

end.

Пример:

{Модуль hlp_sr — вспомогательные расч¸ты} UNIT hlp_sr;

Interface USES crt;

Var a,b,c:real;

{глобальные переменные будут «видны» основной программе}

Function S(x1,y1,x2,y2,x3,y3:integer):real; {функция расч¸та треугольника с заданными вершинами} Implementation

Var p: real; {локальная переменная}

Function r(x1,y1,x2,y2:integer):real; {локальная функция расч¸та расстояния между двумя точками}

Begin

R := SQRT(SQR(x1 - x2) + SQR (y1 - y2)) End;

Function S; {можно не описывать параметры}

Begin

a:= r (x1, y1, x2, y2); b:= r (x1, y1, x3, y3); c:= r (x3, y3, x2, y2); p:= (a + b + c)/2; S:= SQRT(p*(p — a)*(p — b)*(p — c));

End; End.

{Основная программа} Program main;

USES hlp_rs;

Var xa, ya, xb, yb, xc, yc: integer; S_ tr: real;

Begin

Readln (xa, ya, xb, yb, xc, yc);

287

Информатика

S_tr:= S; Writeln(a, b, c);

{a,b,c — могут быть далее использованы }

Writeln(S_tr); End.

6.13. Динамическая память

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

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

•сама программа пользователя;

•системные программы, которые осуществляют вспомогательные действия при выполнении программ пользователя;

•определяемые пользователем константы и структуры данных (переменные);

•временная память для хранения промежуточных результатов при вычислении выражений;

•адреса возврата для подпрограмм;

•временная память при передаче параметров;

•буферы ввода/вывода, в которых хранятся данные между моментом их реальной передачи с периферийного устройства или на него и моментом инициации в программе операций ввода или вывода;

•различные системные данные (например, информация о статусе устройств ввода/вывода).

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

Практика программирования часто выдвигает на передний план два конфликтующих фактора: время выполнения программы и объем занимаемой памяти. И иногда для экономии памяти приходится поступиться быстродействием. Статическое распределение памяти эффективно потому, что на управление памяти в этом случае не тратится ни время, ни память. Но рассмотрим пример. Пусть в некоторой задаче обрабатывается матрица размером 300½300 целых чисел. Тогда необходимо описание: var a1: array[1..300,1..300] of integer. Такие переменные, описанные в разделе var, Н. Вирт назвал статическими за то, что они могут обрабатываться компилятором без выполнения программы, на основа-

288

Глава 6. Алгоритмизация и программирование

нии одного только статического (неизменного) текста программы. В нашем примере общее количество элементов 90000, необходимый объем памяти равен 90000½2 = 180000 байт. При этом маловероятно, что программе могут одновременно понадобиться все 90000 элементов. Кроме того, все переменные, объявленные в программе, располагаются в одной непрерывной области памяти «сегменте данных», длина которого (определяется архитектурой микропроцессора) равна 64 кбайта, что также вызывает затруднения при обработке больших массивов.

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

KПеременные, которые создаются и уничтожаются во время выполнения программы, называются динамическими.

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

Итак, работа с переменными в различных языках программирования может быть организована различными способами:

I. Статический: место для хранения переменных отводится компилятором. В программе обращение к переменной происходит по имени, а компилятор связывает это имя с конкретным адресом в памяти. Эта связь постоянна в течение всего времени выполнения программы. В Паскале таким образом можно объявлять переменные размером до 64 кбайт.

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

III. Совмещение статической и динамической памяти: выделение места для локальных параметров подпрограмм.

KДинамическая память — это оперативная память ПК, предоставляемая программе при ее работе за вычетом сегмента данных (64 Кбайта), стека (также до 64 кбайт) и размера самой программы. Распределение памяти показано на рис. 6.4.

289

Информатика

старшие	системные программы	HEAPEND
адреса		←aaaaaaa
	еще не распределенная память	HEAPPTR
	---------------------------	←aaaaaaa
	динамическая память	HEAPORG
	(расширяется в сторону	←aaaaaaa
	увеличения адресов)
до 64 кбайт	сегмент стека
	(расширяется в сторону
	уменьшения
	адресов)
	--------------------------
	свободная память стека
до 64 кбайт	сегмент данных основной
	программы
	(глобальные переменные, тип
	const)
до 64 кбайт	сегменты кодов включаемых
каждый	модулей
	каждый
до 64 кбайт	сегмент кода основной
	программы
младшие	Паскаль
адреса	системные программы
памяти

Рис. 6.4

6.13.1. Указатели

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

KУказатель — переменная, значением которой является адрес (первого байта памяти), по которому записаны данные.

Указатель занимает в памяти 4 байта. При этом данные, на которые он указывает, могут простираться на десятки килобайт.

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

290