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