ргр по алгоритмам и структурам данных. АиСД РГР, ключников. Разработка атд Простой граф

• Название: Разработка атд Простой граф
• Анкор: ргр по алгоритмам и структурам данных
• Дата: 20.12.2022
• Размер: 135.4 Kb.
• Имя файла: АиСД РГР, ключников.docx
• Тип: Документы; #854773
• страница: 1 из 12

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ


«НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Кафедра вычислительной техники

РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА
ПО ДИСЦИПЛИНЕ «Алгоритмы и структуры данных»

НА ТЕМУ

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

Выполнил:	Проверила:
Студент гр. АВТ-709, АВТФ	старший преподаватель каф. ВТ
Ключников Р. Я.	Романенко Татьяна Александровна
«»2022 г.	«»2022 г.
(подпись)	(подпись)

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

2. Содержание

Содержание 2

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

1.1 АТД «простой граф» 3

1.2. АТД «дескриптор вершины графа» 4

1.3. АТД «дескриптор ребра графа» 4

1.4. АТД «итератор вершин графа» 5

1.5. АТД «итератор ребер графа» 5

1.6. АТД «итератор исходящих ребер вершины» 5

1.7. АТД «итератор входящих ребер вершины» 5

1.8. АТД «задача 2» 6

2. Вариант задания 6

3. АТД «простой граф 7

3.1. Формат АТД «простой граф» 7

3.2. Клиентское определение класса «простой граф» 11

4. АТД «дескриптор вершины» 11

4.1. Формат АТД «дескриптор вершины» 11

Постусловия: нет 13

4.2. Клиентское определение класса «дескриптор вершины» 13

5. АТД «дескриптор ребра» 13

5.1. Формат АТД «дескриптор ребра» 13

5.2. Клиентское определение класса «дескриптор ребра» 16

6. АТД «итератор вершин» 16

6.1. Формат АТД «итератор вершин» 16

6.2. Клиентское определение класса «итератор вершин» 18

7. АТД «итератор ребер» 18

7.1. Формат АТД «итератор ребер» 18

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

8.1. Формат АТД «итератор исходящих ребер» 20

8.2. Клиентское определение класса «итератор исходящих ребер» 22

9. АТД «итератор входящих ребер» 22

9.1. Формат АТД «итератор входящих ребер» 22

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

10. АТД «Задача 2» 24

10.1. Формат АТД «задача 2» 24

10.2. Клиентское определение класса «Задача 2» 25

Заключение 26

Список литературы 27

Приложение 28

Program.cs 28

AbstractGraph.cs 39

MGraph.cs 43

LGraph.cs 50

Graph.cs 59

AdjacencyList.cs 62

Task1.cs 64

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

   1. 1.1 АТД «простой граф»

Спроектировать и реализовать шаблонный класс для коллекции «Простой граф» и использовать коллекцию для решения задач для неориентированных, ориентированных и взвешенных графов.

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

• 
  Конструктор( ) по умолчанию – создает пустой L - граф с нулевым числом вершин и ребер;
  
• 
  Конструктор(V, D, F) – создает граф с V вершинами, без ребер, типа D (ориентированный / неориентированный), формы представления F (L- граф/M-граф);
  
• 
  Конструктор(V, E, D, F) – создает граф с V вершинами, с E случайными ребрами, типа D (ориентированный / неориентированный), формы представления F (L- граф/M-граф);
  
• 
  Конструктор (G) – конструктор копирования создает объект – копию графа G;
  
• 
  Деструктор ( ) – уничтожает внутренние структуры графа;
  
• 
  V( ) – возвращает число вершин в графе;
  
• 
  E( ) – возвращает число ребер в графе;
  
• 
  Directed( ) – возвращает тип графа (ориентированный / неориентированный);
  
• 
  Dense( ) – возвращает форму представления графа (L- граф / M- граф);
  
• 
  K( ) – возвращает коэффициент насыщенности графа;
  
• 
  ToListGraph() – преобразует граф к L- графу;
  
• 
  ToMatrixGraph() – преобразует граф к M- графу;
  
• 
  InsertV( ) – добавляет вершину к графу и возвращает адрес дескриптора вновь созданной вершины;
  
• 
  DeleteV (v) - удаляет вершину из графа, заданную адресом дескриптора v,InsertE(v1, v2) – добавляет ребро (v1, v2)к графу, соединяющую вершины, заданные адресами дескрипторов v1 и v2, и возвращает адрес дескриптора вновь созданного ребра – e;
  
• 
  DeleteE (v1, v2) – удаляет ребро, соединяющее вершины, заданные адресами дескрипторов v1 и v2;
  
• 
  GetEdge(v1, v2) – возвращает адрес дескриптора ребра соединяющего вершины, заданные дескрипторами v1 и v2.
  

Разработать ассоциированные с графом типы:

• 
  АТД «дескриптор вершины графа»;
  
• 
  АТД «дескриптор ребра графа»;
  
• 
  АТД «итератор вершин графа»;
  
• 
  АТД «итератор ребер графа»;
  
• 
  АТД «итератор исходящих ребер вершины»;
  
• 
  АТД «итератор входящих ребер вершины».