Структурное и «неструктурное» программирование. Средства описания структурных алгоритмов
Различают три вида вычислительного процесса, реализуемого программами: линейный, разветвленный и циклический.
Линейная структура процесса вычислений предполагает, что для получения результата необходимо выполнить некоторые операции в определенной последовательности.
Разветвленная структура процесса вычислений предполагает, что конкретная последовательность операций зависит от значений одной или нескольких переменных.
Циклическая структура процесса вычислений предполагает, что для получения результата некоторые действия необходимо выполнить несколько раз.
Для реализации указанных вычислительных процессов в программах используют соответствующие управляющие операторы. Первые процедурные языки программирования высокого уровня, такие как FORTRAN, понятием «тип вычислительного процесса» не оперировали. Для изменения линейной последовательности операторов в них, как в языках низкого уровня, использовались команды условной (при выполнении некоторого условия) и безусловной передач управления. Потому и программы, написанные на этих языках, имели запутанную структуру, присущую в настоящее время только низкоуровневым (машинным) языкам.
Именно для изображения схем алгоритмов таких программ в свое время был разработан ГОСТ 19.701-90, согласно которому каждой группе действий ставится в соответствие специальный блок (табл. 2.3). Хотя этот стандарт предусматривает блоки для обозначения циклов, он не запрещает и произвольной передачи управления, т. е. допускает использование команд условной и безусловной передачи управления при реализации алгоритма.
В качестве примера, демонстрирующего особенности использования команд передачи управления для организации требуемого типа вычислительного процесса, рассмотрим программу на языке Ассемблера.
Пример 2.1 (вариант 1). Реализовать на языке Ассемблера подпрограмму поиска минимального элемента массива а(п). На рисунке 2.2 приведен пример неудачной реализации этой подпрограммы. Стрелками показаны передачи управления. Даже с комментариями и стрелками понять хорошо известный алгоритм достаточно сложно.
Рис. 2.2. Подпрограмма поиска минимального элемента (неудачная реализация на Ассемблере)
Начало, завершение программы или подпрограммы
Обработка данных (вычисления, пересылки и т. п.)
Ветвления, выбор, итерационные и поисковые циклы
Счетные циклы Любые циклы
Вызов процедур Маркировка разрывов линий
После того, как в 60-х годах XX в. было доказано, что любой сколь угодно сложный алгоритм можно представить с использованием трех основных управляющих конструкций, в языках программирования высокого уровня появились управляющие операторы для реализации соответствующих конструкций. Эти три конструкции принято считать базовыми. К ним относят конструкции:
- • следование — обозначает последовательное выполнение действий (рис. 2.3, а);
- • ветвление — соответствует выбору одного из двух вариантов действий (рис. 2.3, б);
Рис. 2.3. Базовые алгоритмические структуры:
а — следование; б — ветвление; в — цикл-пока
• цикл-пока — определяет повторение действий, пока не будет нарушено некоторое условие, выполнение которого проверяется в начале цикла (рис. 2.3, в).
Помимо базовых процедурные языки программирования высокого уровня обычно используют еще три конструкции, которые можно составить из базовых:
- • выбор — обозначает выбор одного варианта из нескольких в зависимости от значения некоторой величины (рис. 2.4, а);
- • цикл-до — обозначает повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле (рис. 2.4, б);
- • цикл с заданным числом повторений (счетный цикл) — обозначает повторение некоторых действий указанное количество раз (рис. 2.4, в).
Любая из дополнительных конструкций легко реализуется через базовые.
Перечисленные шесть конструкций были положены в основу структурного программирования.
Рис. 2.4. Дополнительные структуры алгоритмов:
а — выбор; б — цикл-до; в — цикл с заданным числом повторений
Примечание. Слово «структурное» в данном названии подчеркивает тот факт, что при программировании использованы только перечисленные конструкции (структуры). Отсюда и понятие «программирование без go to».
Программы, написанные с использованием только структурных операторов передачи управления, называют структурными, чтобы подчеркнуть их отличие от программ, при проектировании или реализации которых использовались низкоуровневые способы передачи управления.
Несмотря на то, что Ассемблер не предусматривает соответствующих конструкций, «структурно» можно программировать и на нем. Вернемся к примеру 2.1.
Пример 2.1 (вариант 2). Поскольку реализуемый цикл по типу «счетный» с количеством повторений n-1, используем соответствующую команду Ассемблера. Уберем и усложняющий понимание возврат на метку less, заменив его дубликатом команды сохранения текущего максимального элемента.
Полученный в результате «структурный» вариант программы поиска максимального элемента массива приведен на рис. 2.5. Единственный возврат реализует циклический процесс, а передача управления на следующие команды — ветвление.
Представление алгоритма программы в виде схемы с точки зрения структурного программирования имеет два недостатка:
- • предполагает слишком низкий уровень детализации, что часто скрывает суть сложных алгоритмов;
- • позволяет использовать неструктурные способы передачи управления, причем часто на схеме алгоритма они выглядят проще, чем эквивалентные структурные.
Рис. 2.5. Подпрограмма поиска максимального элемента массива («структурный» вариант)
Рис. 2.6. Схема алгоритма реализации поискового цикла:
а — неструктурный вариант; б — структурный вариант
Классическим примером последнего является организация поискового цикла с использованием неструктурной передачи управления (рис. 2.6, а) и эквивалентный структурный вариант (рис. 2.6, б).
Кроме схем для описания алгоритмов можно использовать псевдокоды, Flow-формы и диаграммы ]-1асси-Шнейдермана. Все перечисленные нотации, с одной стороны, базируются на тех же основных структурах, что и структурное программирование, а с другой — допускают разные уровни детализации.
Псевдокоды. Псевдокод — формализованное текстовое описание алгоритма (текстовая нотация). В литературе были предложены несколько вариантов псевдокодов. Один из них приведен в табл. 2.4.
Описать с помощью псевдокодов неструктурный алгоритм невозможно. Использование псевдокодов изначально ориентирует проектировщика только на структурные способы передачи управления, а потому требует более тщательного анализа разрабатываемого алгоритма. В отличие от схем алгоритмов, псевдокоды не ограничивают степень детализации проектируемых операций. Они позволяют соизмерять степень детализации действия с уровнем абстракции, на котором это действие рассматривают, и хорошо согласуются с основным методом структурного программирования — методом пошаговой детализации.
8.2. Структурное программирование.
При программировании модуля следует иметь в виду, что программа должна быть понятной не только компьютеру, но и человеку: и разработчик модуля, и лица, проверяющие модуль, и тестовики, готовящие тесты для отладки модуля, и сопроводители ПС, осуществляющие требуемые изменения модуля, вынуждены будут многократно разбирать логику работы модуля. В современных языках программирования достаточно средств, чтобы запутать эту логику сколь угодно сильно, тем самым, сделать модуль трудно понимаемым для человека и, как следствие этого, сделать его ненадежным или трудно сопровождаемым. Поэтому необходимо принимать меры для выбора подходящих языковых средств и следовать определенной дисциплине программирования. В связи с этим Дейкстра [8.2] и предложил строить программу как композицию из нескольких типов управляющих конструкций (структур), которые позволяют сильно повысить понимаемость логики работы программы. Программирование с использованием только таких конструкций назвали структурным.
Рис. 8.1. Основные управляющие конструкции структурного программирования.
Основными конструкциями структурного программирования являются: следование, разветвление и повторение (см. Рис. 8.1). Компонентами этих конструкций являются обобщенные операторы (узлы обработки [8.5]) S, S1, S2 и условие (предикат) P. В качестве обобщенного оператора может быть либо простой оператор используемого языка программирования (операторы присваивания, ввода, вывода, обращения к процедуре), либо фрагмент программы, являющийся композицией основных управляющих конструкций структурного программирования. Существенно, что каждая из этих конструкций имеет по управлению только один вход и один выход. Тем самым, и обобщенный оператор имеет только один вход и один выход.
Весьма важно также, что эти конструкции являются уже математическими объектами (что, по существу, и объясняет причину успеха структурного программирования). Доказано, что для каждой неструктурированной программы можно построить функционально эквивалентную (т.е. решающую ту же задачу) структурированную программу. Для структурированных программ можно математически доказывать некоторые свойства, что позволяет обнаруживать в программе некоторые ошибки. Этому вопросу будет посвящена отдельная лекция.
Структурное программирование иногда называют еще «программированием без GO TO». Однако дело здесь не в операторе GO TO, а в его беспорядочном использовании. Очень часто при воплощении структурного программирования на некоторых языках программирования (например, на ФОРТРАНе) оператор перехода (GO TO) используется для реализации структурных конструкций, что не нарушает принципов структурного программирования. Запутывают программу как раз «неструктурные» операторы перехода, особенно переход к оператору, расположенному в тексте модуля выше (раньше) выполняемого оператора перехода. Тем не менее, попытка избежать оператора перехода в некоторых простых случаях может привести к слишком громоздким структурированным программам, что не улучшает их ясность и содержит опасность появления в тексте модуля дополнительных ошибок. Поэтому можно рекомендовать избегать употребления оператора перехода всюду, где это возможно, но не ценой ясности программы [8.1].
К полезным случаям использования оператора перехода можно отнести выход из цикла или процедуры по особому условию, «досрочно» прекращающего работу данного цикла или данной процедуры, т.е. завершающего работу некоторой структурной единицы (обобщенного оператора) и тем самым лишь локально нарушающего структурированность программы. Большие трудности (и усложнение структуры) вызывает структурная реализация реакции на возникающие исключительные (часто ошибочные) ситуации, так как при этом требуется не только осуществить досрочный выход из структурной единицы, но и произвести необходимую обработку (исключение) этой ситуации (например, выдачу подходящей диагностической информации). Обработчик исключительной ситуации может находиться на любом уровне структуры программы, а обращение к нему может производиться с разных нижних уровней. Вполне приемлемой с технологической точки зрения является следующая «неструктурная» реализация реакции на исключительные ситуации [8.7]. Обработчики исключительных ситуаций помещаются в конце той или иной структурной единицы и каждый такой обработчик программируется таким образом, что после окончания своей работы производит выход из той структурной единицы, в конце которой он помещен. Обращение к такому обработчику производится оператором перехода из данной структурной единицы (включая любую вложенную в нее структурную единицу).