Калайда В.Т., Романенко В.В. Технология разработки программного обеспечения (2007), страница 9

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

4.6 — Примеры непростых программРассмотрим программу, которая имеет несколько операторов goto.В этом случае вся программа (или большая ее часть) может быть элементарной. Таким образом, разбор программыможно начать с просмотра всех узлов, поскольку непростыхпрограмм в ней не может быть.Для структурного проектирования обычно используютсяследующие операторы: if — then — else, while — do, последовательность.

Указанные управляющие структуры помогают программистам создать простые программы (функцию, которая преобразует входные данные в выходные). Пусть f(x) —55сегмент программы, состоящей из оператора if — then —else (рис. 4.7).if p(x) then g(x) else h(x)IF – THEN – ELSEРис. 4.7 — Разбиение на элементарные программыФункции g(x) и h(x) проще, чем функция f(x); таким образом, их спецификации должны быть проще. Если их спецификации известны, то функция f(x) определяется следующим образом:f ( x) = ( p ( x)g ( x) )( p ( x)h ( x) ) .Программист может формально определить f(x), зная более простые функции g(x) и h(x) (рис. 4.8).Рис. 4.8 — Сложная программаВ языке PDL используются элементарные подпрограммыс наименьшим числом узлов.

Операторы if и do while являются минимальным набором, поскольку было доказано, что56любая программная функция может быть представлена программой с указанными двумя управляющими структурами. Однако вместо них можно использовать другие конструкции,например repeat — until.repeatнабор операторов;until (выражение);Что эквивалентно следующему:набор операторов;do while (выражение);набор операторов;end;Кроме того, такие же функции может реализовывать оператор do — case с произвольным числом узлов. Для передачиуправления предназначен оператор leave.

При его использовании передача управления принимает вид «остановить выполнение данной функции».Заметим, что «интеллектуальная управляемость», а не«отсутствие операторов goto» является движущей силой процесса проектирования.4.3 Данные4.3.1 Обзор структур данныхЛюбая программа — это формальное описание решениянекоторой задачи реального мира. Как часть этого решенияконкретные данные тоже должны быть формализованы такимобразом, чтобы программа могла проводить вычисления. Дляоблегчения процесса формализации задачи в языки программирования включены наборы различных типов данных.

Но таккак ни один разработчик языка не сможет предвидеть всех возможных применений последнего, набор типов данных неизбежно окажется неполным.57Основным атрибутом переменной является ее тип илимножество значений, которые может принимать переменная.Кроме того, существует набор операторов, который может оперировать с переменной данного типа.Так как программы все более усложняются, требуютсявсе более новые типы данных для того, чтобы моделировать задачи реального мира. Новые типы данных должны создаватьсяпрограммистом на основе уже существующих.Переменные, объявленные как элементарные типы данного языка, называются скалярными переменными, а переменные, состоящие из наборов существующих типов данных, называются агрегативными переменными. Из агрегативных переменных можно строить новые типы данных, для работы с которыми создаются специальные операторы. Цель наших исследований — понять, по какой концепции строятся абстрактные(определенные пользователем) типы данных из агрегативныхструктур.4.3.1.1 МассивыМассивы — это простейшие агрегативные данные в языках программирования.

Массивом называется упорядоченныйнабор данных одного типаdeclare A(10) FIXED BINARY;Объявлен массив A из десяти двоичных переменных с фиксированной точкой с именами A(1), A(2), A(3),…, A(9), A(10).Аналогичноdeclare B(5:10) FIXED BINARY;объявлен массив B из шести элементов с именами B(5), B(6), ...,B(10). Массивы могут быть как одномерными, так и многомерными.4.3.1.2 СтруктурыСамой сложной разновидностью данных в языках программирования являются структуры. Структурой называют поименованную совокупность различных типов данных.declare 1 X,582 Y FIXED BINARY,2 Z BIT(12);Объявляется структура с именем Х, состоящая из двоичной переменной с фиксированной точкой с именем X.Y и строки длиной 12 бит с именем X.Z.Структуры могут использоваться для создания переменных нового типа.4.3.1.3 СпискиСписком называют упорядоченный набор переменных одного типа.

Список отличается от массива тем, что его размеробычно является переменной величиной, т.е. элементы могутдобавляться в список и изыматься из него.Список может быть объявлен как:declare 1 LIST(N),2 DATA_ENTRIES TYPE (некоторый тип данных),SIZE; /* текущий размер списка */Элементами списка являются DATA_ENTRIES(1),DATA_ENTRIES(2),... , DATA_ENTRIES(SIZE).Если список может расти неограниченно, то такой способописания не годится, поскольку SIZE может стать больше, чемN. Другой способ состоит в реализации совокупности базированных переменных.declare 1 LIST BASED,2 DATA_ENTRIES TYPE (некоторый тип данных);2 FPTR POINTER /* указатель следующей записив списке */LIST_HEAD POINTER; /* указатель первогоэлемента в списке */В первом случае элементами списка являютсяLIST.DATA_ENTRIES(1),59LIST.DATA_ENTRIES(2),LIST.DATA_ENTRIES(3),...LIST.DATA_ENTRIES(SIZE),а во второмLIST_HEAD  DATA_ENTRIES(LIST_HEAD  FPTR)  DATA_ENTRIES((LIST_HEAD  FPTR)  FPTR)  DATA_ENTRIES...Для работы со списками обычно используются следующие операторы (рис.

4.9, а):1) ADD — поместить новый элемент в список;2) DELETE — удалить элемент из списка;3) SEARCH — проверить наличие элемента в списке.60pushpopaddsearch……emptydeleteа) Списокв) Стек…deleteinsertб) Очередьdeletesearchinsertmemberг) Множествоdeleteaddд) ДеревоРис. 4.9 — Агрегативные структуры и соответствующие им операторы4.3.1.4 ОчередиОчередь — это упорядоченный список, в один конец которого элементы добавляются, а из другого изымаются (рис.4.9, б). Очередь называют списком FIFO — Fist In, Fist Out(поступивший первым обслуживается первым). Очередь можетбыть организована любым из рассмотренных выше способов,однако второй способ (использование указателей) более эффективен.

Для обслуживания очереди необходимы две операции:1) INSERT — добавить элемент в очередь;2) DELETE — удалить элемент из очереди.4.3.1.5 СтекиСтек — это упорядоченный список, в один конец которого элементы добавляются и изымаются из этого же конца. Стек61называют списком LIFO — Last In, Fist Out (поступивший последним обслуживается первым). Аналогично очереди, стек может быть организован любым из рассмотренных выше способов,однако использование массивов более эффективно.

Для работы состеком обычно используются три операции (рис. 4.9, в).1) PUSH — поместить элемент в стек;2) POP — извлечь элемент из стека;3) EMPTY — функция, принимающая значение ИСТИННО,если стек не заполнен.4.3.1.6 МножестваМножества — это совокупность переменных одного типа. Множество аналогично списку, за исключением того, чтопорядок расположения элементов не имеет значения. Множества обычно организуются как списки с помощью любого издвух способов.Множества обрабатываются с использованием следующих операторов (рис. 4.9, г):1) INSERT — добавить новый элемент во множество;2) DELETE — удалить элемент из множества;3) MEMBER — функция, которая принимает значение ИСТИННО, если данная переменная находится во множестве.4.3.1.7 ГрафыНаправленный граф — это структура, состоящая из узлови дуг, причем каждая дуга направлена от одного узла к другому.Графы обычно организовываются с помощью базированныхпеременных, где дуги являются переменными типа указатель.Если из каждого узла выходит несколько дуг, то граф можноописать следующим образом:declare 1 GRAPH BASED,2 DATA_ENTPIES TYPE (некоторый тип данных),2 EDGES(N) POINTER;62Для ненаправленных графов дугам соответствуют дванаправления — вперед и назад:declare 1 GRAPH BASED,2 DATA_ENTPIES TYPE (некоторый тип данных),2 FORWARD_EDGES(N) POINTER,2 BACKWARD_EDGES(N) POINTER;Операторы для работы с графами представлены на рис.4.9, д.4.3.1.8 ДеревьяДерево — это направленный граф, обладающий следующими свойствами:1) только один узел не имеет дуг, входящих в него (корневой узел);2) в каждый узел входит не более одной дуги;3) в каждый узел можно попасть из корневого узла занесколько шагов.4.3.2 Абстрактные конструкцииВ современных языках программирования основное внимание уделяется структурам данных.

Управляющие операторыостались почти такими же, какими они были в первых версияхязыка ALGOL. Кроме использования оператора case и заменыоператора goto, обработка операторов if, for и процедур вызова претерпела незначительные изменения.Однако структуры данных за это время изменились в значительной степени. Ранее назначение данных состояло в представлении чисел в системе исчисления, ориентированной наЭВМ. Поэтому в первых языках программирования использовались целочисленные и действительные типы данных, к которымприменялась арифметика с фиксированной и плавающей точкой.В более развитых языках, кроме числовых данных, включались данные, состоящие из строк символов.

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

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

Доступ к даннымосуществляется из этого модуля. Таким образом, внесение изменения в структуру данных не сопряжено с особыми затруднениями, потому что при этом меняется только один модуль. Вязыках высокого уровня имена данных и представление данныхтесно связаны. Если пользователь объявляет стек следующимобразом:declare 1 STACK,2 TOP FIXED,2 ENTRIES(100) FIXED;то в модуле, который производит обращение к стеку, должнабыть известна внутренняя структура последнего, т.е.