Структурное программирование. Средства описания структурных алгоритмов.

Структу́рное программи́рование — методология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры блоков. Предложена в 70-х годах XX века Э. Дейкстрой, разработана и дополнена Н. Виртом.

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

Различают три вида вычислительного процесса, реализуемого програм­мами: линейный, разветвленный и циклический.

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

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

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

Для реализации указанных вычислительных процессов в программах используют соответствующие управляющие операторы. Первые процедур­ные языки программирования высокого уровня, такие, как FORTRAN, поня­тием «тип вычислительного процесса» не оперировали. Для изменения ли­нейной последовательности операторов в них, как в языках низкого уровня, использовались команды условной (при выполнении некоторого условия) и безусловной передач управления. Потому и программы, написанные на этих языках, имели запутанную структуру, присущую в настоящее время только низкоуровневым (машинным) языкам.

Именно для изображения схем алгоритмов таких программ в свое время был разработан ГОСТ 19.701-90, согласно которому каждой группе дейст­вий ставится в соответствие специальный блок (табл. 2.3). Хотя этот стан­дарт предусматривает блоки для обозначения циклов, он не запрещает и про­извольной передачи управления, т. е. допускает использование команд услов­ной и безусловной передачи управления при реализации алгоритма.

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

Пример 2.1 (вариант 1). Реализовать на языке Ассемблера подпрограм­му поиска минимального элемента массива а(п). На рис. 2.2 приведен пример неудачной реализации этой подпрограммы. Стрелками показаны передачи управления. Даже с комментариями и стрелками понять хорошо известный алгоритм достаточно сложно.

 

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

• следование - обозначает последовательное выполнение действий (рис. 2.3, а);

• ветвление - соответствует выбору одного из двух вариантов действий (рис. 2.3, б);

• цикл-пока - определяет повторение действий, пока не будет нарушено некоторое условие, выполнение которого проверяется в начале цикла (рис. 2.3, в).

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

• выбор - обозначает выбор одного варианта из нескольких в зависимо­сти от значения некоторой величины (рис. 2.4, а);

• цикл-до - обозначает повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле (рис. 2.4, б);

• цикл с заданным числом повторений (счетный цикл) - обозначает по­вторение некоторых действий указанное количество раз (рис. 2.4, в).

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

Примечание. Слово «структурное» в данном названии подчеркивает тот факт, что при программировании использованы только перечисленные конструкции (структуры). Отсюда и понятие «программирование без go to».

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

Несмотря на то, что Ассемблер не предусматривает соответствующих конструкций, «структурно» можно программировать и на нем. Вернемся к примеру 2.1.

Пример 2.1 (вариант 2). Поскольку реализуемый цикл по типу «счет­ный» с количеством повторений п-1, используем соответствующую команду Ассемблера. Уберем и усложняющий понимание возврат на метку less, заме­нив его дубликатом команды сохранения текущего максимального элемента.

Полученный в результате «структурированный» вариант программы по­иска максимального элемента массива приведен на рис. 2.5. Единственный возврат реализует циклический процесс, а передача управления на следую­щие команды - ветвление.

Представление алгоритма программы в виде схемы с точки зрения структурного программирования имеет два недостатка:

• предполагает слишком низкий уровень детализации, что часто скрыва­ет суть сложных алгоритмов;

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

 

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

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

Псевдокоды. Псевдокод - формализованное текстовое описание алго­ритма (текстовая нотация). В литературе были предложены несколько вари­антов псевдокодов. Один из них приведен в табл. 2.4.

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

В качестве примера посмотрим, как будет выглядеть на псевдокоде опи­сание алгоритма поискового цикла, представленного на рис. 2.6:

i:=l

Цикл-пока i < n и A[i] ≠ у

i:=i+l Все -цикл Если i ≤n

то Вывести «Элемент найден»

иначе Вывести «Элемент не найден» Все-если

Flow-формы. Flow-формы представляют собой графическую нотацию описания структурных алгоритмов, которая иллюстрирует вложенность структур. Каждый символ Flow-формы соотвествует управляющей структу­ре и изображается в виде прямоугольника. Для демонстрации вложенности структур символ Flow-формы может быть вписан в соответствующую об­ласть прямоугольника любого другого символа. В прямоугольниках симво­лов содержится текст на естественном языке или в математической нотации. Размер прямоугольника определяется длиной вписанного в него текста и раз­мерами вложенных прямоугольников. Символы Flow-форм, соответствую­щие основным и дополнительным управляющим конструкциям, приведены на рис. 2.7.

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

Диаграммы Насси-Шнейдермана. Диаграммы Насси-Шнейдермана

являются развитием Flow-форм. Основное их отличие от Flow-форм заклю­чается в том, что область обозначения условий и вариантов ветвления изоб­ражают в виде треугольников (рис. 2.9). Такое обозначение обеспечивает большую наглядность представления алгоритма.

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

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