Разработка абстрактного типа данных «Простой, статический граф»

Министерство образования и науки Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра вычислительной техники

РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА

по дисциплине

«Структуры и алгоритмы обработки данных»

на тему

Разработка АТД «Простой, статический граф»

Выполнил:                                                                                Преподаватель:

Студент:Кайгородов Д.Р.                                                          Романенко Т. А.

Группа: АВТ-911

Вариант: 5/8

Новосибирск, 2012

Оглавление

Оглавление. 2

1.  Цель работы.. 2

2.  Общее задание. 3

3.  Вариант задания. 4

4.  Диаграмма взаимосвязи объектов. 5

5.  «Простой граф». 6

5.1 Формат АТД «Простой граф». 6

5.2 Клиентское определение класса «Простой граф». 10

6.  «Дескриптор ребра». 12

6.1 АТД “Дескриптор ребра”. 12

6.2 Клиентское определение класса «Дескриптор ребра». 13

7.  «Итератор вершин». 14

7.1 АТД “Итератор вершин”. 14

7.2 Клиентское определение класса «Итератор вершин». 16

8.  «Итератор ребер». 18

8.1 АТД “Итератор рёбер”. 18

8.2 Клиентское определение класса «Итератор рёбер». 20

9.  «Итератор исходящих ребер». 24

9.1 АТД “Итератор исходящих рёбер”. 24

9.2 Клиентское определение класса «Итератор исходящих рёбер». 26

10.                                                                                      «Итератор входящих ребер». 29

10.1 АТД “Итератор входящих рёбер”. 29

10.2 Клиентское определение класса «Итератор входящих рёбер». 31

11.                                                                                                                      Заключение. 33

12.                                                                             Список используемой литературы.. 34

13.                                                                                                                 Приложение А. 35

1.  Цель работы

Освоение технологии разработки комплексного программного обеспечения для решения задач в различных прикладных областях.

2.  Общее задание

1)  Спроектировать и реализовать универсальную программную коллекцию для АТД «Простой, статический граф» и использовать коллекцию для решения задач для неориентированных, ориентированных и взвешенных графов.

Интерфейс АТД «Простой, статический граф» включает операции:

·  Опрос формы представления графа (L-граф/M-граф)

·  Опрос типа графа (Ориентированный/Неориентированный)

·  Опрос числа вершин в графе

·  Опрос числа рёбер в графе

·  Опрос коэффициента насыщенности графа

·  Преобразования графа к L-графу

·  Преобразование графа к M-графу

·  Вставка вершины с заданным номером

·  Удаление вершины с заданным номером

·  Вставка ребра соединяющего заданные вершины

·  Удаление ребра соединяющего заданные вершины

·  Опрос признака существования ребра, соединяющего заданные вершины

·  Опрос веса ребра, соединяющего заданные вершины

·  Установка веса ребра, соединяющего заданные вершины

·  Опрос данных ребра, соединяющего заданные вершины

·  Установка данных ребра, соединяющего заданные вершины

2)  Реализовать следующие итераторы для АТД «Простой, статический граф»

·  Итератор вершин графа

o  Установка итератора на первую вершину графа

o  Опрос признака соответствующего окончанию переходов итератора

o  Переход к следующей вершине графа

o  Возврат номера вершины графа, на которую указывает итератор

·  Итератор рёбер графа

o  Установка итератора на первое ребро графа

o  Опрос признака соответствующего окончанию переходов итератора

o  Переход к следующему ребру графа

o  Возврат дескриптора ребра графа, на которое указывает итератор

·  Итератор исходящих рёбер вершины

o  Установка итератора на первое исходящее ребро вершины

o  Опрос признака соответствующего окончанию переходов итератора

o  Переход к следующему исходящему ребру

o  Возврат дескриптора исходящего ребра вершины, на которое указывает итератор

·  Итератор входящих рёбер вершины

o  Установка итератора на первое входящее ребро вершины

o  Опрос признака соответствующего окончанию переходов итератора

o  Переход к следующему входящему ребру

o  Возврат дескриптора входящего ребра вершины, на которое указывает итератор

3)  Спроектировать и реализовать шаблонный класс для АТД «Задача 1». Интерфейс АТД «Задача 1» включает операции

·  Связывание объекта задачи с заданным графом и выполнение решения задачи 1 для этого графа

·  Повторное выполнение решения задачи 1

·  Возврат результата решения задачи 1

3.  Вариант задания

Задача 1 – определение в орграфе кратчайшего по числу ребер пути между заданной парой вершин на основе алгоритма Флойда – Уоршалла.

4.  Диаграмма взаимосвязи объектов

5.  «Простой граф»