4.6.2. Построение структур данных

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

Пусть имеется некоторый файл F, состоящий из заголовка, за которым следует совокупность дат, завершающаяся признаком окончания. Заголовок может иметь один из двух типов, каждая дата представляет собой летнюю или зимнюю дату, завершитель состоит из восьми символов Z. Структуру файла F можно представить в виде иерархической структуры данных, базируясь на основных конструкциях данных Джексона (см. рис. 4.37).

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

На первый взгляд кажется, что в вышеприведенной структуре компонент «Тело файла» является излишним (см. рис. 4.37). Однако если данный компонент убрать, то последовательность «Файл F» будет состоять из трех подкомпонентов, вторым среди которых будет являться «Дата». Подкомпонент «Дата» представляет собой повторяемый подкомпонент. Следовательно, «Дата» может присутствовать в файле любое число раз. Но в конструкции последовательности данных любой подкомпонент должен встретиться ровно один раз. Поэтому наличие компонента «Тело файла» в структуре данных, представленной на рис. 4.37, является обязательным.

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

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

иреляционная структуры данных.

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

Пример сетевой структуры данных иллюстрирует рис. 4.38 [26]. На рис. 4.39 показан возможный вариант преобразования этих данных к иерархическому виду.

При реляционном подходе структура данных представляется в виде совокупности таблиц. На рис. 4.40 представлена таблица, состоящая из пяти строк и шести столбцов. Очевидно, что сами таблицы имеют иерархическую структуру. На рис. 4.41 показаны два способа иерархического представления таблицы, состоящей из пяти строк и шести столбцов.

115

Таблица Таблица

Рис. 4.41. Иерархическая структура таблиц:

а– представление таблицы в виде набора строк;

б– представление таблицы в виде набора столбцов

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

Представление структур данных в виде иерархий является первым этапом проектирования программы по методу Джексона (методу JSP). На следующих этапах описывается взаимосвязь между структурами данных и программой.

117

Резюме

Большинство структур (иерархическая, сетевая, реляционная) реальных наборов данных может быть сведено к иерархическим структурам, которые могут быть представлены в нотации структур метода JSP Джексона.

4.6.3. Проектирование структур программ

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

Большинство ПС предназначено для обработки некоторых входных данных и получения некоторых выходных данных. Структура выходных данных формируется программой в результате некоторого преобразования структуры входных данных. Таким образом, для проектирования структуры программы необходимо определить взаимосвязь между входными данными, выходными данными и процессом преобразования [26].

Пример 4.6

Рассмотрим простейший пример [26]. Пусть необходимо найти суммы элементов строк в массиве, состоящем из 15 строк и 10 столбцов.

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

* (10)

Элемент

Рис. 4.42. Структуры входных и выходных данных

Очевидно, что между обеими структурами имеется непосредственная взаимосвязь. Компонент «Сумма строки» в структуре «Результат» появляется

118

столько раз, сколько раз компонент «Строка» появляется во входной структуре «Массив», и в том же порядке.

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

Массив Результат

*

Элемент (10)

Рис. 4.43. Соответствие между структурами входных и выходных данных

Каждая пара соответствующих компонентов входных и выходных данных образует основу одного компонента программы. Поэтому проектирование упрощенной структуры программы (ее ядра) выполняется путем «слияния» соответствующих компонентов структур входных и выходных данных. Это значит, что на месте линий соответствия размещаются компоненты программы, которым присваивается соответствующее имя (рис. 4.44). Слияние двух повторяемых N раз компонентов данных сформирует один повторяющийся N раз компонент программы.

Пример 4.7

Рассмотрим более сложный пример [26]. Пусть результат предыдущего примера должен сопровождаться некоторым заголовком и некоторым завершителем. Структуры входных и выходных данных и соответствия между ними для данного случая представлены на рис. 4.45.

На первом подэтапе формирования структуры программы на основании линий соответствия формируется упрощенный вариант структуры (ядро программы, рис. 4.46).

119

По аналогии с компонентом «Элемент» каждый из этих компонентов помещается в то относительное положение в структуре программы, в котором он появляется в структурах данных. И соответственно меняется имя данных компонентов (добавляется слово «Получение», «Формирование», «Обработка» и т. п.). Рис. 4.48 иллюстрирует полученную в результате структуру программы.

*

Обработка (15) строки

*

Обработка (10) элемента

Рис. 4.48. Формирование полной структуры программы

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

Резюме

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

122

4.6.4.Этапы проектирования программного средства

Метод JSP реализуется пятью этапами [26]:

1.Проектирование структур входных и выходных данных.

2.Идентификация соответствий между структурами данных.

3.Проектирование структуры программы.

4.Перечисление и распределение выполняемых операций.

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

Рассмотрим правила выполнения данных этапов на конкретном примере.

Пример 4.8

Пусть имеется входной файл, состоящий из заголовка, за которым следует совокупность дат, завершающаяся признаком окончания (завершителем). Заголовок начинается символом Н (Heading), за которым следует содержимое заголовка, состоящее из типа файла и даты создания файла. Тип файла может иметь одно из двух значений – «Тип 1» или «Тип 2». Каждая дата представляет собой летнюю или зимнюю дату. Завершитель состоит из восьми символов Z.

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

Этап 1. Проектирование структур входных и выходных данных

Данный этап является самым важным этапом метода JSP, так как структуры данных образуют основу формируемой структуры программы.

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

А. Таблицы для идентификации компонентов данных. Б. Графическое представление структур данных.

В. Контрольные перечни вопросов для анализа структур данных.

А. Таблицы для идентификации компонентов данных

Формат таблицы для идентификации компонентов входных данных иллюстрирует табл. 4.2. Эта таблица содержит структуру входных данных, соответствующую примеру 4.8. Данная структура представлена в иерархическом виде и построена на базе конструкций Джексона. Аналогичная таблица заполняется для полного набора выходных данных (табл. 4.3).

123

124

Для заполнения таблиц необходимо выполнить следующие действия. 1-й шаг. Представить совокупность всех входных и выходных данных в

виде компонентов самого высокого уровня (например, «Файл», «Отчет» и т.д.). 2-й шаг. Перечислить подкомпоненты данных, которые содержит компонент из 1-го или 4-го шагов. Этот компонент должен быть либо последователь-

ностью, либо повторением, либо выбором.

3-й шаг. Снабдить иерархическими номерами все подкомпоненты. Указать имя, тип, номер и условие появления.

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

125

Б. Графическое представление структур данных

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

На рис. 4.49 содержится результат графического представления структуры входных данных. Основу для данного представления составляет табл. 4.2.

1.1.2.1.1 1.1.2.1.2

Рис. 4.49. Графическое представление структуры входного файла

Рис. 4.50 содержит графическое представление структуры выходного файла. Данное представление получено на основе табл. 4.3.

В. Контрольный перечень вопросов для анализа структур данных

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

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

идентифицирован ли каждый вход и выход?

126

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

идентифицирован ли каждый компонент данных именем?

идентифицированы ли все объекты прикладного уровня (заголовки, типы строк отчетов и т.п.)?

можно ли идентифицировать дополнительные структуры данных? Вторая часть перечня предназначена для оценки корректности структур

данных. Примеры вопросов, относящихся к данной части:

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

изображена ли структура данных сверху вниз и слева направо с точки зрения появления компонентов данных?

является ли каждый компонент данных корректной последовательностью, выбором, повторением или элементарным компонентом?

1

Выходной файл

Рис. 4.50. Графическое представление структуры выходного файла

Этап 2. Идентификация соответствий между структурами данных

Второй этап метода JSP Джексона заключается в идентификации соответствий между структурами входных и выходных данных, созданными на первом этапе. Общие правила установления соответствий между компонентами входной и выходной структур данных:

1)должно совпадать количество соответствующих друг другу компонентов данных;

2)соответствующие компоненты должны появляться в одинаковом

порядке;

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

127

Наиболее эффективный способ идентификации всех соответствий состо-

ит в том, чтобы начать со структуры данных с наименьшим числом компонентов. В рассматриваемом примере такой структурой является структура выходных данных (сравните рис. 4.49 и рис. 4.50). Используя три приведенных выше правила, необходимо начинать с вершины структуры и при работе продвигаться вниз.

На рис. 4.51 представлен результат идентификации соответствий рассмотренных структур входных и выходных данных.

Этап 3. Создание структуры программы

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

Подэтап 1. Слияние соответствующих компонентов входных и выходных данных для формирования компонентов программы.

В результате получается упрощенная структура (ядро) программы. Каждый из ее сформированных компонентов снабжается соответствующим именем (например, вида «Обработка Х для создания Y»).

На рис. 4.52 показан результат данного подэтапа для рассматриваемого примера. В этом случае имеется пять линий соответствия между входными и выходными данными (см. рис. 4.51). Каждая линия заменяется соответствующим компонентом программы. Поэтому упрощенная структура программы также состоит из пяти компонентов.

Подэтап 2. Включение не имеющих соответствия компонентов структуры входных данных в формируемую структуру программы на те же относительные иерархические места и присвоение им соответствующих имен.

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

Подэтап 3. Включение не имеющих соответствия компонентов структуры выходных данных в формируемую структуру программы на те же относительные иерархические места и присвоение им соответствующих имен.

На рис. 4.54 представлен результат выполнения данного подэтапа. На данном рисунке двойной линией справа выделены добавленные на данном подэтапе компоненты программы.

128

129

ОО

Тип 1 Тип 2

Рис. 4.51. Идентификация соответствий между входной и выходной структурами данных

129

В структуре выходных данных не имеют соответствия компоненты «Количество летних дат» и «Количество зимних дат». Это подкомпоненты компонента «Тело файла» выходных данных (см. рис. 4.50 и рис. 4.51). Следовательно, в проектируемой структуре программы компоненты, обрабатывающие «Количество летних дат» и «Количество зимних дат», должны стать подкомпонентами компонента «Обработка тела файла». Однако они не должны содержаться в подкомпоненте «Обработка даты» последнего (см. рис. 4.51 и рис. 4.53). Поэтому их нужно поместить вне этого подкомпонента. Так как подкомпоненты «Количество летних дат» и «Количество зимних дат» могут возникнуть только после обработки всего набора дат, то соответствующие компоненты программы нужно поместить за компонентом «Обработка даты». Поэтому в это место структуры программы добавляется компонент «Обработка количества».

Добавление изменяет структуру компонента «Обработка тела файла». Ранее этот компонент был повторением с повторяемой частью «Обработка даты». Теперь он стал последовательностью. Напомним, что среди последовательных подкомпонентов не должно быть повторяемых. Поэтому в структуру компонента «Обработка тела файла» добавляется подкомпонент «Обработка набора дат».

Таким образом, в результате трех подэтапов третьего этапа сформирована управляющая структура программы (см. рис. 4.54).

На следующем этапе необходимо снабдить управляющую структуру программы выполняемыми операциями.

Этап 4. Перечисление и распределение выполняемых операций

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

спецификацию того, что должно делать программное средство;

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

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

I.Операции завершения, служащие для прекращения работы программы – по одной на программу (например «Стоп», «Конец» и т.п.).

II. Операции открытия и закрытия (например для файлов). III. Операции вывода результатов (например «Писать»). IV. Вычисления.

V. Операции ввода входных данных (например «Читать»).

VI. Управление внутренними переменными (например запоминание, инициализация и т.п.).

132

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

называемый метаязыком структурированного изложения [26].

I. Операции завершения

Как уже отмечалось, для проектируемой программы необходима одна операция данной группы:

1.Стоп.

II.Операции открытия и закрытия

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

2.Открыть входной файл.

3.Открыть выходной файл.

4.Закрыть входной файл.

5.Закрыть выходной файл.

III.Операции вывода результатов

Для определения операций вывода исследуется структура выходных данных (см. рис. 4.50). Каждому элементарному компоненту данной структуры соответствует своя операция вывода:

6.Писать тип файла.

7.Писать дату создания файла.

8.Писать количество летних дат.

9.Писать количество зимних дат.

IV. Вычисления

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

Врассматриваемом примере для операций 6 и 7 вычислений не нужно – информация по условию задачи должна просто переписываться из входного файла в выходной (см. условие примера 4.8).

Для операций 8, 9 необходим подсчет количества летних (Кл) и зимних (Кз) дат. Поэтому появляются операции:

10.Кл := Кл + 1.

11.Кз := Кз + 1.

V. Операции ввода входных данных

Врассматриваемом примере используется один входной файл. Поэтому необходима одна операция ввода:

12.Читать из входного файла.

VI. Управление внутренними переменными

Внутренние переменные используются, как правило, в вычислениях. Переменными, участвующими в вычислениях, в рассматриваемом примере явля-

133

ются счетчики Кл и Кз (см. операции 10, 11). Вначале их нужно обнулить:

13.Кл := 0.

14.Кз := 0.

Итак, полный набор выполняемых операций в рассматриваемом примере содержит 14 операций.

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

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

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

3)на каком последовательном месте должна появиться операция в компоненте программы (слева или справа – в начале или в конце компонента).

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

Операция 1 (Стоп) встречается один раз на файл. Файл обрабатывается компонентом «Программа подсчета дат». Поэтому операция «Стоп» должна являться последовательным подкомпонентом этого компонента. Данная операция встречается в самом конце программы. Поэтому размещается на правом краю компонента «Программа подсчета дат».

По аналогии операции 2 – 5 (Открытие и закрытие файлов) также явля-

ются последовательными подкомпонентами компонента «Программа подсчета дат». Но операции 2, 3 (Открытие входного и выходного файлов) необходимо поместить вначале (слева) программы, а операции 4, 5 (Закрытие файлов) – справа, но перед операцией 1 (Стоп).

Операция 6 (Писать тип файла) выполняется один раз на тип файла. Тип файла обрабатывается компонентом «Обработка типа файла». Но у него уже есть два выбираемых подкомпонента «Обработка типа 1», «Обработка типа 2». Операция 6 должна появляться после любого из этих подкомпонентов. Таким образом, компонент «Обработка типа файла» должен превратиться из выбора в последовательность двух подкомпонентов: сначала выбор, затем операция 6. Поэтому в программу вводится дополнительный компонент «Обработка содержимого типа».

Очевидно, что операция 7 (Писать дату создания файла) является под-

компонентом компонента «Обработка даты создания файла».

Аналогично, операции 8, 9 (Писать количество летних дат, Писать ко-

личество зимних дат) распределяются по компонентам «Обработка количества летних дат», «Обработка количества зимних дат».

134