Иванова Г.С. Технология программирования
Подождите немного. Документ загружается.
пакета. Причем в мульпрограммных системах основная программа, передав данные, продолжает
работать, а не переходит в состояние ожидания, как изображено на рис. 5.9, б.
Если стрелка, изображающая вызов, касается блока, то обращение происходит к модулю
целиком, а если входит в блок, то - к элементу внутри модуля.
При необходимости на структурной карте можно уточнить особые условия вызова (рис. 5.10):
циклический вызов, условный вызов и однократный вызов - при повторном вызове основного
модуля однократно вызываемый модуль не активизируется!
Связи по данным и управлению обозначают стрелками, параллельными дуге вызова,
направление стрелки указывает направление связи (рис. 5.11).
Структурные карты Константайна позволяют наглядно представить результат декомпозиции
программы на модули и оценить ее качество, т. е. соответствие рекомендациям структурного
программирования (сцепление и связность).
Пример 5.3. Представим в виде структурной карты Константайна полную структурную схему,
полученную в предыдущем примере (см. рис. 5.6).
Подпрограммы Очистка окна, Вывод прямоугольника, Вывод строки текста, Вывод отрезка
прямой, Задание цвета рисования и Задания цвета фона являются частью библиотеки графических
примитивов практически в любой среде программирования универсального языка, поэтому их
включать в структурную карту не будем.
Для остальных подпрограмм покажем особые условия вызова
и типы связей (рис. 5.12).
Модули Расчет значений функции, Вывод таблицы и Построение графика связаны с основной
программой по образцу, так как параметры X и Y структурные (массивы), следовательно
программа считается сцепленной по образцу.
Анализ показывает, что количество сцеплений по образцу в программе можно уменьшить,
если подпрограмму Расчет значений функции перенести на следующий уровень (рис. 5.13).
Однако в этом случае при смене вида результата таблица значений будет рассчитываться заново.
Аналогично можно перенести подпрограмму Разбор функции на более низкий уровень и
вызывать ее, например, из подпрограммы Расчет значений функции, но поскольку велика
вероятность многократного вычисления значений одной функции на разных интервалах, вряд ли
это целесообразно.
После внесения соответствующих изменений в алгоритм следует определить полную
спецификацию модулей. Спецификация должна включать: имя, краткое описание назначения,
перечень входных и выходных параметров с указанием типа и области допустимых входных и
выходных значений. Затем можно приступать к реализации модулей.
В соответствии с требованиями нисходящей разработки (комбинированный подход) можно
предложить следующий порядок реализации модулей:
• Основная программа,
• Вывод окна с текстом,
• Вывод заголовка и меню,
• Разбор функции,
• Вычисление значений функции,
• Вывод таблицы,
• Расчет значений функции,
• Построение графика.
Структурные карты Джексона будут рассмотрены вместе с предложенной им методикой
проектирования программ, основанной на декомпозиции данных в §5.5. .
5.4. Проектирование структур данных
Под проектированием структур данных понимают разработку их представлений в памяти.
Основными параметрами, которые необходимо учитывать при проектировании структур данных,
являются:
• вид хранимой информации каждого элемента данных;
• связи элементов данных и вложенных структур;
• время хранения данных структуры («время жизни»);
• совокупность операции над элементами данных, вложенными структурами и структурами в
целом.
Вид хранимой информации определяет тип соответствующего поля памяти. В качестве
элементов данных в зависимости от используемого языка 'программирования могут
рассматриваться:
• целые и вещественные числа различных форматов;
• символы;
• булевские значения: true и false;
а также некоторые структурные типы данных, например:
• строки;
• записи;
• специально объявленные классы. .
При этом для числовых полей очень важно правильно определить диапазон возможных
значений, а для строковых данных - максимально возможную длину строки.
Связи элементов и вложенных структур, а также их устойчивость и совокупность операций
над элементами и вложенными структурами определяют структуры памяти, используемые для
представления данных. Время жизни учитывают при размещении данных в статической или
динамической памяти, а также во внешней памяти.
Рассмотрим существующие варианты внутреннего представления данных, их элементов и
связей между ними более подробно.
Представление данных в оперативной памяти. Различают две базовые структуры
организации данных в оперативной памяти: векторную и списковую.
Векторная структура представляет собой последовательность байт памяти, которые исполь-
зуются для размещения полей данных (рис. 5.14). Последовательное размещение организованных
структур данных позволяет осуществлять прямой доступ к элементам: по индексу (совокупности
индексов) - в массивах или строках или по имени поля - в записях или объектах.
Однако выполнение операций добавления и удаления элементов при использовании
векторных структур для размещения элементов массивов может потребовать осуществления
многократных сдвигов элементов.
Структуры данных в векторном представлении можно размещать как в статической, так и в
динамической памяти. Расположение векторных представлений в динамической памяти иногда
позволяет существенно увеличить эффективность использования оперативной памяти.
Желательно размещать в динамической памяти временные структуры, хранящие промежуточные
результаты, и структуры, размер которых сильно зависит от вводимых исходных данных.
Списковые структуры строят из специальных элементов, включающих помимо
информационной части еще и один или несколько указателей-адресов элементов или вложенных
структур, связанных с данным элементом. Размещая подобные элементы в динамической памяти
можно организовывать различные внутренние структуры (рис. 5.15).
Однако при использовании списковых структур следует помнить, что:
• для хранения указателей необходима дополнительная память;
• поиск информации в линейных списках осуществляется последовательно, а потому требует
больше времени;
• построение списков и выполнение операций над элементами данных, хранящимися в
списках, требует более высокой квалификации программистов, более трудоемко, а
соответствующие подпрограммы содержат больше ошибок и, следовательно, требуют более
тщательного тестирования.
Обычно векторное представление используют для хранения статических множеств, таблиц
(одномерных и многомерных), например, матриц, строк, записей, а также графов, представленных
матрицей смежности, матрицей инцидентности или аналитически [55]. Списковое представление
удобно для хранения динамических (изменяемых) структур и структур со сложными связями.
В наиболее ответственных случаях при выборе внутреннего представления целесообразно
определять вычислительную сложность [24,55] выполнения наиболее часто встречающихся
операций со структурой данных или ее элементами для различных вариантов. А также оценивать
их емкостную сложность. .
Пример 5.3. Разработать внутреннее представление неориентированного графа, над которым в
основном выполняют операции определения смежности вершин, определения вершин, смежных
данной, и удаления вершины.
В [27,55] предложены 10 вариантов внутреннего представления неориентированного графа,
приведённого на рис. 5.16, а. Причем представление в виде матрицы смежности (рис. 5.16, б)
использует табличный способ описания связности вершин. Комбинации векторов и односвязных
списков (рис. 5.16, в-и) реализуют аналитическое задание графа, а вектор и список n-связных
списков напрямую отображают связи вершин. Интересно также, что структуры, изображенные на
рис. 5.16, б, в и д, могут быть размещены в статической памяти.
Для выбора структуры необходимы исследования. В табл. 5.2 приведены результаты расчета
временной сложности указанных операций на уровне машинных команд в тактах
микропроцессора для каждого представления и емкостной сложности этих представлений.
(Оценка временной сложности выполнялась по методике, предложенной в [27, 55].)
Анализ результатов показывает, что, если число вершин n ≈ 100, то с точки зрения
уменьшения времени выполнения наиболее эффективное представление - массив списков. Если же
существенно экономное использование оперативной памяти, то наиболее эффективное
представление - массив динамических векторов.
Представление данных во внешней памяти. Современные операционные системы
поддерживают два способа организации данных во внешней памяти: последовательный и с
прямым доступом.
Примечание. В таблице использованы следующие обозначения:
n – размерность задачи (количество вершин графа);
p
и
max
p - среднее и максимальное количество вершин, смежных данной.
В круглых скобках под выражениями приведены результаты расчета по ним – для n=100,
.10,5
max
== pиp
При последовательном доступе к данным возможно выполнение только последовательного
чтения элементов данных или последовательная их запись. Такой вариант предполагается при
работе с логическими устройствами типа клавиатуры или дисплея, при обработке текстовых
файлов или файлов, формат записей которых меняется в процессе работы.
Прямой доступ возможен только для дисковых файлов, обмен информацией с которыми
осуществляется записями фиксированной длины (двоичные файлы С или типизированные файлы
Pascal). Адрес записи такого файла можно определить по ее номеру, что и позволяет напрямую
обращаться к нужной записи.
При выборе типа памяти для размещения структур данных следует иметь в виду, что:
• в оперативной памяти размещают данные, к которым необходим быстрый доступ как для
чтения, так и для их изменения;
• во внешней - данные, которые должны сохраняться после завершения программы.
Возможно, что во время работы данные целесообразно хранить в оперативной памяти для
ускорения доступа к ним, а при ее завершении - переписывать во внешнюю память для
длительного хранения. Именно этот способ используют большинство текстовых редакторов: во
время работы с текстом он весь или его часть размещается в оперативной памяти, откуда по мере
надобности переписывается во внешнюю память. В подобных случаях разрабатывают два
представления данных: в оперативной и во внешней памяти.
Правильный выбор структур во многом определяет эффективность разрабатываемого
программного обеспечения и его технологические качества, поэтому данному вопросу должно
уделяться достаточное внимание независимо от используемого подхода.
5.5. Проектирование программного обеспечения,
основанное на декомпозиции данных
В § 4.5 уже упоминалось, что практически одновременно были предложены методики
проектирования программного обеспечения Джексона и Варнье-Орра, основанные на
декомпозиции данных. Обе методики предназначены для создания «простых» программ,
работающих со сложными, но иерархически организованными структурами данных. При
необходимости разработки программных систем в обоих случаях предлагается вначале разбить
систему на отдельные программы, а затем использовать данные методики.
Методика Джексона. При создании своей методики М. Джексон исходил из того, что
структуры исходных данных и результатов определяют структуру программы.
Методика основана на поиске соответствий структур исходных данных и результатов. Однако
при ее применении возможны ситуации, когда на каких-то уровнях соответствия отсутствуют.
Например, записи исходного файла сортированы не в том порядке, в котором соответствующие
строки должны появляться в отчете. Такие ситуации были названы «столкновениями». Выделяют
несколько типов столкновений, которые разрешают по-разному. При различной
последовательности записей их просто сортируют до обработки. Более подробно способы
разрешения столкновений изложены в [33].
Разработка структуры программы в соответствии с методикой выполняется следующим
образом:
• строят изображение структур входных и выходных данных;
• выполняют идентификацию связей обработки (соответствия) между этими данными;
• формируют структуру программы на основании структур данных и обнаруженных
соответствий;
• добавляют блоки обработки элементов, для которых не обнаружены соответствия;
• анализируют и обрабатывают несоответствия, т.е. разрешают «столкновения»;
• добавляют необходимые операции (ввод, вывод, открытие/закрытие файлов и т. п.);
• записывают программу в структурной нотации (псевдокоде).
Пример 5.4. Разработать структуру программы, которая читает записи
об успеваемости студентов и формирует список неуспевающих студентов группы.
На рис. 5.17 представлены структуры входных и выходных данных программы. Анализ этих
структур показывает, что между ними есть соответствия (на рис. 5.17 эти соответствия показаны
полужирными дугами). Помимо полного соответствия, имеет место еще частичное соответствие
— соответствие, отмечаемое только, если студент имеет задолженности (на рис. 5.17 оно отмечено
полужирным пунктиром).
Используя найденные полные и неполные соответствия, строим «каркас» программы
(затемненные блоки на рис. 5.18). Согласно методике добавляем блоки, которые позволят
разрешить «столкновения» (светлые блоки на рис. 5.18).
Далее строим полный список операций, которые должна выполнять программа, учитывая, что
не каждой записи исходного файла соответствует строка отчета (признак «формировать запись
вывода» установлен), и выводить надо названия только тех предметов, по которым у студента есть
задолженности (признак «задолженность» установлен):
1 - завершить работу;
2 - открыть входной файл;
3 - открыть выходной файл;
4 - закрыть входной файл;
5 - закрыть выходной файл;
6 - вывести заголовок;
7 - вывести завершитель;
8 - ввести запись входного файла;
9 - вывести строку отчета (при включенном состоянии признака «формировать запись
вывода»);
10-очистить буфер вывода;
11-установить признак «формировать запись вывода»;
12- сбросить признак «формировать запись вывода»;
13- поместить в строку вывода ФИО;
14-установить признак «задолженность»;
15- сбросить признак «задолженность»;
16- занести название предмета в строку вывода;
17- стереть название предмета из буфера.