ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 20.11.2019
Просмотров: 9493
Скачиваний: 184
пакета
.
Причем
в
мульпрограммных
системах
основная
программа
,
передав
данные
,
продолжает
работать
,
а
не
переходит
в
состояние
ожидания
,
как
изображено
на
рис
. 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.
Разработать
внутреннее
представление
неориентированного
графа
,
над
которым
в
основном
выполняют
операции
определения
смежности
вершин
,
определения
вершин
,
смежных
данной
,
и
удаления
вершины
.