Модульное программирование

Основные понятия

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

Модульное программирование включает методы разработки сложных про­грамм путем их декомпозиции, в том числе выбор типов модулей и особенно­сти применения каждого типа. Модуль - это подпрограмма, относительно са­мостоятельный фрагмент программы для функционально законченной обра­ботки данных. Умение определять состав и назначение модулей программы определяет квалификацию и уровень профессионализма программиста. Раз­биение программы на подпрограммы повышает надежность, наглядность и живучесть программы, облегчает понимание программы в процессе ее освое­ния и позволяет вести ее разработку коллективом программистов.

Используя модули, можно:

1. разрабатывать типовые подпрограммы для использования одним или многими программистами;

2. разделять большие алгоритмы на части и разрабатывать их программы разными программистами невысокой квалификации;

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

4. использовать нисходящий метод разработки программ.

В настоящее время модули используют не только как средство для опреде­ления функционально законченной обработки данных, но и как средство для реализации метода структурного проектирования программ. Имеется 2 принципиально различных метода структурного проектирования программ: метод нисходящего (сверху вниз) и метод восходящего (снизу вверх) проек­тирования. Более прогрессивный современный метод разработки программ предполагает использование структурного программирования и метода нисхо­дящего проектирования программ.

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

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

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

В дальнейшем изложении при описании конструкций языка элементы кон­струкций, приведенные в виде русских слов, в том числе разделенных дефи­сом, определяют одно понятие (конструкцию) языка. Конструкции в квадрат­ных скобках [ ] необязательны.

Локализация объектов, используемых подпрограммами

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

Переменные, используемые в подпрограммах, могут быть:

1. глобальные (внешние): объявленные во внешней подпрограмме или про­ грамме и не переопределенные в данной;

2. локальные (внутренние): определенные в данной подпрограмме и доступ­ные и используемые только в ней и во всех вложенных в нее блоках или подпрограммах, в которых они не переобъявлены;

3. формальные, определенные в списке формальных параметров; идентифика­торы формальных параметров локальны в подпрограмме.

Глобальные переменные доступны в программе, в которой они объявлены, и во всех вложенных в нее подпрограммах, в которых они не переобъявлены.

Имена локальных объектов в различных подпрограммах могут совпадать или нет, так как локальные переменные становятся неопределенными при вы­ходе из подпрограммы. Одноименные глобальные и локальные переменные -это разные переменные, с разной областью их действия.

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

Все объекты, расположенные до текстов подпрограмм, яв­ляются глобальными по отношению к ним. При определении области дейст­вия подпрограмм действует правило: текст подпрограммы должен быть до ее вызова либо иметь опережающее описание.

Процедуры

Процедура имеет описание (текст) и вызов. Описание процедуры содержит заголовок процедуры и блок. Причем блок (тело процедуры) имеет такое же строение, как и блок программы. Заголовок процедуры:

PROCEDURE «имя-процедуры» [(список-формальных-параметров)];

где «имя-процедуры» - идентификатор, определяет имя процедуры, по которому она вызывается.

Список формальных параметров в заголовке процедуры необязателен; он может отсутствовать, если используются только глобальные и локальные объ­екты. Более детально список формальных параметров рассмотрен в данном разделе.

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

Форма оператора вызова процедуры:

«Имя-процедуры» [(список-фактических-параметров)];

Если в описании процедуры нет списка формальных параметров, то опера­тор вызова процедуры состоит из одного имени процедуры.

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

PROGRAM PR;

CONST N=20;

TYPE VECT=ARRAY[1..N] OF REAL;

. . . {Описание процедуры MNMX:}

PROCEDURE MNMX(A:VECT;M:INTEGER;VAR MN,MX:REAL);

VAR I:INTEGER;

BEGIN MN:=A[1]; MX:=A[1];

FOR I:=2 TO M DO

IF A[I]<MN THEN MN:=A[I]

ELSE IF A[I]>MX

THEN MX:=A[I]; END;

BEGIN ... MNMX(D,N,MIN,MAX);{ Вызовы процедуры MNMX }

MNMX(E,20,MINI,MAX1);

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

Функции

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

Заголовок функции:

FUNCTION «имя-функции» [(список-формальных-параметров)]:тип-результата;

где имя-функции - идентификатор (имя-входа), определяет имя, по кото­рому функция вызывается;

тип-результата - тип возвращаемого значения.

Тип результата может быть любым простым типом: ординальным, вещест­венным или строковым. Он не может быть сложным типом: массивом, запи­сью. Причем значение результата должно быть совместимо с типом результа­та функции, определенным в операторе FUNCTION.

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

«имя-функции» := выражение;

Пример: Функция для вычисления значения N!.

FUNCTION FACT(N:INTEGER):INTEGER ;

VAR F,I:INTEGER; {тип результата} BEGIN F:=1;

FOR I:=2 TO N DO F:= F*I;

FACT :=F; { - определение результата FACT } END;

BEGIN ... { Примеры вызова функции FACT:}

A := FACT(20); В:=FACT(M+1); END.

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

Например, можно изменять значения глобальных переменных, изменять значения формальных параметров-переменных. Результат выполнения подобных действий называют побочным эффектом функции. Функции с побочным эффектом нежелательны в про­граммах для широкого распространения.

Рекурсия и опережающее описание

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

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

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

Например, вычислить N!. При N = 0 или N = 1 решение тривиально (результат равен l) и используется для начала обратного хода рекурсив­ных вычислений.

Опере­жающее описание обеспечивает взаимную рекурсию подпрограмм: ранее опи­санная подпрограмма может вызвать другую подпрограмму с опережающим описанием, текст которой расположен после вызывающей подпрограммы. Опе­режающие описания не допускаются в интерфейсной части модуля (unit).

Модули

Объем программы в Паскале должен быть не более 64 Кбайт. Но если текст программы должен быть более 64 Кбайт, надо разбить программу на ряд модулей: основную программу и один или более модулей (unit). Текст каж­дого из них должен быть не более 64 Кбайт.

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

Модули могут быть в виде PAS-файлов с исходными текстами и в виде объектных модулей (TPU-файлов). Компилятор Паскаля размещает объект­ные модули в отдельном сегменте памяти: в файлах с расширением .TPU (Turbo Pascal Uses). Максимальная длина сегмента модуля может быть не более 64 Кбайт. Но количество используемых модулей ограничивается только доступной внешней памятью.

Лекция №8.

Статические и динамические переменные

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

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

Динамическая память (куча) необходима в следующих случаях:

1. для больших массивов, которые не используются одновременно;

2. для массива или записи, размер которых превышает 64 Кбайт;

3. для массивов, требуемый объем ОП для которых определяется в процессе выполнения программы;

4. для временного запоминания данных при работе с графическими и звуко­выми средствами ПК.

Достоинства динамической памяти:

1. экономичность и эффективность использования ОП;

1. возможность динамического изменения (в процессе выполнения программы) количества элементов массивов и связанных структур;

3) динамические переменные существуют в случае необходимости до оконча­ния работы программы.

Переменная, размещаемая динамически, объявляется в разделе var как указатель на данные определенного типа.

Свободные массивы (коллекции массивов)

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

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

Для рабо­ты со свободными, так же как и для работы с большими, массивами исполь­зуются массивы указателей. Каждый элемент массива указателей содержит адрес начала строки значений свободного массива, т. е. одномерного массива из коллекции массивов. ОП выделяется для каждой строки свободного масси­ва (для каждого массива коллекции) динамически с помощью процедуры GetMem и освобождается процедурой FreeMem.

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

Бинарное дерево

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

Дерево, в котором каждый узел связан не более чем с двумя другими уз­лами, называют бинарным деревом. В такой структуре запись каждого узла содержит 2 указателя: для связи с левым и правым поддеревом (ветвью). Обычно дерево изображается корневым узлом кверху.

На данном рисунке число 20 содержит узел корня дерева, нулевой уровень дере­ва; числа 10, 30 - узлы его левого и правого поддеревьев, первый уровень; числа 8, 12, 22, 34 - листья - узлы без ветвей.

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

Базовые операции над бинарным деревом:

1. добавление нового элемента к дереву;

2. поиск по дереву по заданному значению ключа;

3. обход дерева для получения и вывода сортированной последовательности записей дерева;

4. удаление из дерева узла с заданным значением ключа;

5. уничтожение дерева и освобождение ОП, которую оно занимало.

Лекция №9.