Структурными называются программы написанные. Принципы структурного программирования. Двумерное структурное программирование

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

Принцип 1 . Следует отказаться от использования оператора безусловного перехода GoTo.

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

• Последовательность - однократное выполнение операций в том порядке, в котором они записаны в тексте программы. Бертран Мейер поясняет: «Последовательное соединение: используйте выход одного элемента как вход к другому, подобно тому, как электрики соединяют выход сопротивления со входом конденсатора» .
• Ветвление - однократное выполнение одной из двух или более операций, в зависимости от выполнения заданного условия.
• Цикл - многократное исполнение одной и той же операции до тех пор, пока выполняется заданное условие (условие продолжения цикла).

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

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

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

Бертран Мейер поясняет: «Преобразуйте элемент, возможно, с внутренними элементами, в подпрограмму, характеризуемую одним входом и одним выходом в потоке управления».

Принцип 5 . Каждую логически законченную группу инструкций следует оформить как блок (block). Блоки являются основой структурного программирования.

Блок - это логически сгруппированная часть исходного кода, например, набор инструкций, записанных подряд в исходном коде программы. Понятие блок означает, что к блоку инструкций следует обращаться как к единой инструкции. Блоки служат для ограничения области видимости переменных и функций. Блоки могут быть пустыми или вложенными один в другой. Границы блока строго определены. Например, в if-инструкции блок ограничен кодом BEGIN..END (в языке Паскаль) или фигурными скобками {...} (в языке C) или отступами (в языке Питон).

Принцип 6 . Все перечисленные конструкции должны иметь один вход и один выход.

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

Принцип 7 . Разработка программы ведётся пошагово, методом «сверху вниз» (top-down method) .

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

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

Простой последовательности;

Условий или альтернатив;

Повторений, то есть циклов и итераций.

Использоваться может один или два любых вида одновременно. Каждой структуре присуща единая черта - единственная точка передачи управления в структуру и единственная точка входа в структуру. Такой вид конструкции имеет дисциплинирующее и систематизирующее значение.

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

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

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

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

Для облегчения чтения программы часто добавляют пустые строки между разделами. Стоит писать текст программы со сдвигами, чтобы можно было прочитать последовательность действий и количество вложений.

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

Используя язык высокого уровня (такой как Фортран) программисты могли писать программы до несколько тысяч строк длиной. Однако язык программирования, легко понимаемый в коротких программах, когда дело касается больших программ, становится нечитабельным (и неуправляемым). Избавление от таких неструктурированных программ пришло после создания в 1960 году языков структурного программирования. К ним относятся языки Алгол, Паскаль и С.

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

Структурное программирование тесно связано такими понятиями как «нисходящее проектирование» и «модульное программирование».

Метод нисходящего проектирования предполагает последовательное разложение функции обработки данных на простые функциональные элементы («сверху-вниз»).

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

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

1) определяются цели автоматизации предметной области и их иерархия;

2) устанавливается состав приложений (задач обработки), обеспечивающих реализацию поставленных целей;

3) уточняется характер взаимосвязи приложений и их основные характеристики (информация для решения задач, время и периодичность решения и др.);

4) определяются необходимые для решения задач функции обработки данных;

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

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

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

Модульное программирование основано на понятии модуля – логически взаимосвязанной совокупности функциональных элементов, оформленных в виде отдельных программных модулей. Модульное программирование рассматривается в разд 7.

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

· линейной (следование);

· нелинейной (развилка);

· циклической (цикл, или повторение).

Эта теорема была сформулирована в 1966 г. Боймом и Якопини (Corrado Bohm, Guiseppe Jacopini). Главная идея теоремы – преобразовать каждую часть программы в одну из трех основных структур или их комбинацию так, чтобы неструктурированная часть программы уменьшилась. После достаточного числа таких преобразований оставшаяся неструктурированной часть либо исчезнет, либо становится ненужной. В теореме доказывается, что в результате получится программа, эквивалентная исходной и использующая лишь упоминавшиеся основные структуры.

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

В алгоритмическом языке С (С++) для реализации структурного кодирования используются следующие операторы:

· составной-оператор;

· оператор-выражение;

· оператор-выбора;

· оператор-с-меткой;

· оператор-перехода;

· оператор-итерации;

· asm-оператор;

· объявление (только в С++).

Структура «следование» (рис. 5.1, а) реализуется составным оператором, оператором-выражение, asm-оператором и др.

Составной оператор , или блок, представляет собой список (возможно, пустой) операторов, заключенных в фигурные скобки {…} . Синтаксически блок рассматривается как единый оператор, но он влияет на контекст идентификаторов, объявленных в нем. Блоки могут иметь любую глубину вложенности.

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

<выражение>;

Компилятор языка C++ выполняет операторы-выражения, вычисляя выражения. Все побочные эффекты от этого вычисления завершаются до начала выполнения следующего оператора. Большинство операторов-выражений представляют собой операторы присваивания или вызовы функций (например, printf(), scanf()). Особым случаем является пустой оператор, состоящий из одной точки с запятой (; ). Пустой оператор не выполняет никаких действий. Однако он полезен в тех случаях, когда синтаксис C++ ожидает наличия некоторого оператора, но по программе он не требуется (например, бесконечный цикл for).

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

Структура «развилка» (рис. 5.1, б, в) реализуется операторами выбора. Операторы выбора , или операторы управления потоком, выполняют выбор одной из альтернативных ветвей программы, проверяя для этого определенные значения. Существует два типа операторов выбора: if...else и switch.

Базовый оператор if (рис. 5.1, б) имеет следующий формат:

if(условное_выражение)оператор_если_"истина"оператор_если_"ложь";

Язык C++ в отличие от, например, языка Паскаль не имеет специального булевого типа данных. В условных проверках роль такого типа может играть целочисленная переменная или указатель на тип. Условное_выражение должно быть записано в круглых скобках. Это выражение вычисляется. Если оно является нулевым (или пустым в случае типа указателя), мы говорим, что условное_выражение ложно (false) ; в противном случае оно истинно (true).

Если предложение else отсутствует, а условное_выражение дает значение "истина", то выполняется оператор_если_"истина"; в противном случае он игнорируется.

Если задано предложение оператор_если_"ложь", а условное_выражение дает значение "истина", то выполняется оператор_если_"истина"; в противном случае выполняется оператор_если"ложь".

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

if (!ptr)... или if (ptr = = 0)....

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

Например, запись:

if (x == 1)

if (y == 1) puts("x=1 и y=1");

else puts("x != 1");

дает неверное решение, так как else, независимо от стиля записи, сопоставляется не с первым, а со вторым if. Поэтому правильная запись последней строчки должна быть такой:

else puts("x=1 и y!=1");

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

if (x = = 1)

if (y = = 1) puts("x = и y=1");

else puts("x != 1"); // правильное решение

Оператор switch (см. рис. 5.1, в) использует следующий базовый формат:

switch (переключающее_выражение) case_оператор;

Он позволяет передавать управление одному из нескольких операторов с меткой case в зависимости от значения переключающего_выражения. Любой оператор в case_операторе (включая пустой оператор) может быть помечен одной (или более) меткой варианта:

case константное_выражение_i : case_оператор_i;

где каждое константное_выражение_i должно иметь уникальное целочисленное значение (преобразуемое к типу переключающего_выражения) в пределах объемлющего оператора switch.

Допускается иметь в одном операторе switch повторяющиеся константы case.

Оператор может иметь также не более одной метки default:

default: оператор_умолчания;

После вычисления переключающего_выражения выполняется сопоставление результата с одним из константных_выражений_i. Если найдено соответствие, то управление передается case_оператору_i с меткой, для которой найдено соответствие. Если соответствия не найдено и имеется метка default, то управление передается оператору_умолчания. Если соответствие не найдено, а метка default отсутствует, то никакие операторы не выполняются. Для того чтобы остановить выполнение группы операторов для конкретного варианта, следует использовать оператор break.

Структурное программирование – это проектирование, написание и тестирование программы в соответствии с жестким соблюдением определенных правил.

Основная цель структурного программирования – повышение производительности программистов. Другими целями являются:

– избавиться от плохой структуры программы;

– создавать программы и документацию к ним, которые можно было бы понимать, сопровождать и модифицировать без участия авторов (стоимость сопровождения и модификации, как правило, в 3-5 раз больше стоимости разработки).

Структурное программирование (или метод пошаговой детализации) включает:

1. Метод нисходящего проектирования. Его еще называют методом «сверху вниз» или «от общего к частному». Он предполагает разбиение задачи на несколько более простых частей или подзадач. Их выделяют таким образом, чтобы проектирование подзадач было независимым. При этом составляют план решения всей задачи, пунктами которого и являются выделенные части. План записывают графически в виде функциональной схемы (схемы иерархии, подчинения), где определяют головную и подчиненные подзадачи и связи между ними, т.е. интерфейс. Здесь же устанавливается, какие начальные данные (или значения) получает каждая подзадача для правильного функционирования и какие результаты она выдает. Затем производят детализацию каждой подзадачи. Число шагов детализации может быть произвольным. Детализацию продолжают до тех пор, пока не станет ясно, как программировать данный фрагмент алгоритма.

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

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

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

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

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

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

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

Функциональный блок алгоритма относится к простому типу блоков.

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

1) выполняется каждый блок;

2) каждый блок выполняется не более одного раза.

При структурной организации алгоритма можно выделить три типа потоков управления.

Поток управления, в котором выполняются оба указанных свойства, называется линейным.

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

2. Ветвящийся поток управления. В этом типе выполняется свойство (2), а свойство (1) не выполняется.

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

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

В данном типе потока управления выполняется свойство (1), но не выполняется свойство (2).

Если алгоритм представляет собой комбинацию трех рассмотренных типов потоков управления (базовых алгоритмических структур), то его называют структурным алгоритмом.

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

1. понятность и простота восприятия алгоритма;

2. проверяемость (для проверки любой из основных структур достаточно убедиться в правильности входящих в нее функциональных блоков);

3. модифицируемость.

Структурная теорема : любой алгоритм может быть сведен к структурному алгоритму.

Значение структурной теоремы для практики программирования состоит в том, что на ее основе разработан и широко используется структурный метод программирования. Основой метода является использование принципа модульности построения сложных программ. При этом каждый программный модуль организуется в виде стандартного функционального блока (строится из трех базовых структур) и выполняет лишь одну функцию по обработке данных. Модули обладают определенной автономностью, что позволяет их отладку (поиск и устранение ошибок) вести независимо от остальной программы и обеспечивает относительно простую модифицируемость как отдельного модуля, так и программы в целом. Эффективность структурного программирования особенно заметна при разработке сложных программ – модульный принцип позволяет разбить общую задачу на составные и относительно автономные части, каждая из которых может создаваться и отлаживаться независимо. Безусловно, такое разбиение требует согласования входных и выходных параметров модулей.

Исходя из структурного подхода к разработке алгоритма, типовыми этапами этого процесса являются:

1. Описание общего замысла алгоритма;

2. Формализация задачи;

3. Разработка обобщенной схемы алгоритма;

4. Разработка отдельных блоков алгоритма;

5. Стыковка блоков;

6. Определение возможности использования стандартных блоков;

7. Разработка блоков логического контроля;

8. Оптимизация схемы алгоритма;

9. Уточнение параметров;

10. Оценка машинного ресурса.

Языки и технологии программирования

Первые программы заключались в установке ключевых переключателей на передней панели вычислительного устройства. Очевидно, таким способом можно было составить только небольшие программы. С развитием компьютерной техники появился машинный язык, с помощью которого программист мог задавать команды, оперируя с ячейками памяти, полностью используя возможности машины. Однако использование большинства компьютеров на уровне машинного языка затруднительно, особенно это касается ввода-вывода. Поэтому от его использования пришлось отказаться. Например, для организации чтения блока данных с гибкого диска программист может использовать 16 различных команд, каждая из которых требует 13 параметров, таких как номер блока на диске, номер сектора на дорожке и т. п. Когда выполнение операции с диском завершается, контроллер возвращает 23 значения, отражающие наличие и типы ошибок, которые надо анализировать.«Слова» на машинном языке называются инструкции, каждая из которых представляет собой одно элементарное действие для центрального процессора, такое, например, как считывание информации из ячейки памяти. Каждая модель процессора имеет свой собственный набор машинных команд, хотя большинство из них совпадает. Если Процессор А полностью понимает язык Процессора Б, то говорится, что Процессор А совместим с Процессором Б. Процессор Б будет называться не совместимым с Процессором А если А имеет команды, не распознаваемые Процессором Б. В случае, когда нужно иметь эффективную программу, вместо машинных языков используются близкие к ним машинно-ориентированные языки - ассемблеры. Люди используют мнемонические команды взамен машинных команд.

Но даже работа с ассемблером достаточно сложна и требует специальной подготовки.Например, для процессора Zilog Z80 машинная команда 00000101 предписывает процессору уменьшить на единицу свой регистр B. На языке ассемблера это же будет записано как DEC B.

Структурное программирование

Следующий шаг был сделан в 1954 году, когда был создан первый язык высокого уровня - Фортран (англ. FORTRAN - FORmula TRANslator ). Языки высокого уровня имитируют естественные языки, используя некоторые слова разговорного языка и общепринятые математические символы. Эти языки более удобны для человека, с помощью них, можно писать программы до нескольких тысяч строк длиной. Однако легко понимаемый в коротких программах, этот язык становился нечитаемым и трудно управляемым, когда дело касалось больших программ. Решение этой проблемы пришло после изобретения языков структурного программирования (англ. structured programming language ), таких как Алгол(1958), Паскаль(1970), Си(1972).

Структурное программирование предполагает точно обозначенные управляющие структуры, программные блоки, отсутствие инструкций безусловного перехода (GOTO), автономные подпрограммы, поддержка рекурсии и локальных переменных. Суть такого подхода заключается в возможности разбиения программы на составляющие элементы. Также создавались функциональные (аппликативные) языки (Пример: Lisp - англ. LISt Processing , 1958) и логические языки (пример: Prolog - англ. PROgramming in LOGic , 1972). Хотя структурное программирование, при его использовании, дало выдающиеся результаты, даже оно оказывалось несостоятельным тогда, когда программа достигала определенной длины. Для того чтобы написать более сложную (и длинную) программу, нужен был новый подход к программированию.

В итоге в конце 1970-х и начале 1980-х были разработаны принципы объектно-ориентированного программирования. ООП сочетает лучшие принципы структурного программирования с новыми мощными концепциями, базовые из которых называются инкапсуляцией, полиморфизмом и наследованием. Примером объектно-ориентированных языков являются: Object Pascal, C++, Java и др. ООП позволяет оптимально организовывать программы, разбивая проблему на составные части, и работая с каждой по отдельности. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути, описывает часть мира, относящуюся к этой задаче.