Основы объектно-ориентированного программирования задач на графах (200,00 руб.)

Стр.2

Стр.3

Стр.4

Стр.5

Стр.6

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» Инженерно-технологическая академия В. А. ЛИТВИНЕНКО ОСНОВЫ ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАММИРОВАНИЯ ЗАДАЧ НА ГРАФАХ Учебное пособие Ростов-на-Дону – Таганрог Издательство Южного федерального университета 2019

Стр.2

УДК 004.438(075.8) ББК 32.973 Л641 Печатается по решению кафедры систем автоматизированного проектирования Института компьютерных технологий и информационной безопасности Южного федерального университета (протокол № 9 от 7 марта 2019 г.) Рецензенты: доктор технических наук, профессор кафедры автоматизации производственных процессов Донского государственного технического университета (ДГТУ) Ю. О. Чернышев кандидат технических наук, доцент кафедры ИБТС Института компьютерных технологий и информационной безопасности ЮФУ С. А. Ховансков Литвиненко, В. А. Л641 Основы объектно-ориентированного программирования задач на графах : учебное пособие / В. А. Литвиненко ; Южный федеральный университет. – Ростов-на-Дону ; Таганрог : Издательство Южного федерального университета, 2019. – 133 с. ISBN 978-5-9275-3472-2 Рассматриваются основы объектно-ориентированного программирования на С++ задач на графах – от создания класса до разработки иерархии классов, основанной на классификации способов задания графов. Пособие предназначено для студентов вузов, обучающихся по направлениям «Информатика и вычислительная техника» и «Информационные системы и технологии». Пособие может быть полезным для специалистов, занятых программированием алгоритмов решения задач на графах и сетях. УДК 004.438(075.8) ББК 32.973 ISBN 978-5-9275-3472-2 © Южный федеральный университет, 2019 © Литвиненко В. А., 2019 © Оформление. Макет. Издательство Южного федерального университета, 2019

Стр.3

ОГЛАВЛЕНИЕ ВВЕДЕНИЕ ..................................................................................................... 6 1. УНИВЕРСАЛЬНОСТЬ ГРАФОВ ............................................................ 9 Вопросы для самоконтроля ......................................................................... 131 2. ПРЕДСТАВЛЕНИЕ ГРАФОВ ................................................................ 13 2.1. Матрица смежности ................................................................................ 13 2.2. Матрица инцидентности ......................................................................... 13 2.3. Списочная форма ..................................................................................... 15 Вопросы для самоконтроля ........................................................................... 16 3. РАЗРАБОТКА КЛАССА ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ ... 17 3.1. Описание класса ...................................................................................... 17 3.2. Объект класса .......................................................................................... 18 3.3. Конструктор класса ................................................................................. 19 3.4. Деструктор класса ................................................................................... 21 3.5. Функции класса ....................................................................................... 24 3.6. Ввод-вывод матрицы смежности графа ................................................. 25 3.7. Определение вершин графа, смежных двум заданным вершинам ...... 27 3.8. Пример выполнения программы ............................................................ 29 3.9. Программа для работы с классом ........................................................... 30 Выводы ........................................................................................................... 32 Вопросы для самоконтроля ........................................................................... 33 4. ПРОСТОЕ НАСЛЕДОВАНИЕ ПРИ РАЗРАБОТКЕ КЛАССОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ .................................................... 35 4.1. Базовый и производный класс ................................................................ 35 4.2. Функция для проверки смежности двух вершин графа ........................ 36 3

Стр.4

Оглавление 4.3. Вызов конструктора базового класса...................................................... 37 4.4. Главная функция ...................................................................................... 37 4.5. Пример выполнения программы ............................................................. 38 Вопросы для самоконтроля ............................................................................ 38 5. ПОЛИМОРФИЗМ ПРИ РАЗРАБОТКЕ КЛАССОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ ..................................................... 40 5.1. Виртуальные функции ............................................................................ 40 5.2. Переопределение функций ...................................................................... 41 5.3. Вызов виртуальных функций .................................................................. 42 5.4. Пример выполнения программы ............................................................. 43 Вопросы для самоконтроля ............................................................................ 44 6. ЗАДАЧИ НА ГРАФАХ И ПЕРЕГРУЗКА ОПЕРАЦИЙ ...................... 45 6.1. Функции-операции .................................................................................. 45 6.2. Унарные функции-операции для ввода-вывода графов ........................ 46 6.3. Унарная функция-операция для проверки смежности двух вершин графа ................................................................................................................ 49 6.4. Перегрузка операций для виртуальных функций .................................. 52 6.5. Результат работы программы для унарных операций ........................... 54 6.6. Бинарные функции-операции .................................................................. 54 6.7. Бинарная функция-операция для определения вершин, смежных заданной вершине графа ................................................................................ 55 6.8. Бинарная функция-операция для объединения двух графов ................ 56 6.9. Пример выполнения программы для бинарных функций-операций .... 60 Вопросы для самоконтроля ............................................................................ 63 7. ИЕРАРХИИ КЛАССОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ ..... 65 7.1. Структура и назначение классов ............................................................. 65 4

Стр.5

Оглавление 7.2. Абстрактные классы и чистые виртуальные функции .......................... 67 7.3. Определение чистых виртуальных функций в классе Маtr .................. 69 7.4. Определение чистых виртуальных функций в классе List .................... 71 7.5. Главная функция ..................................................................................... 76 7.6. Пример выполнения программы для иерархии классов ....................... 77 Вопросы для самоконтроля ........................................................................... 79 8. ЗАДАЧИ НА ГРАФАХ ПОВЫШЕННОЙ СЛОЖНОСТИ ................ 80 8.1. Иерархия и назначение функций классов .............................................. 80 8.2. Программирование функции определения паросочетания графа ........ 84 8.3. Программирование функции выделения семества клик, покрывающего все вершины графа ............................................................... 87 8.4. Структура главной функции в ООП ....................................................... 92 ЗАКЛЮЧЕНИЕ ............................................................................................ 98 СПИСОК ЛИТЕРАТУРЫ........................................................................... 99 ПРИЛОЖЕНИЯ ......................................................................................... 100 Приложение 1 ............................................................................................... 100 Приложение 2 ............................................................................................... 102 Приложение 3 ............................................................................................... 105 Приложение 4 ............................................................................................... 109 Приложение 5 ............................................................................................... 114 Приложение 6 ............................................................................................... 120 Приложение 7 ............................................................................................... 126

Стр.6