|
|
Отчет. План работы Для выполнения курсовой работы требуется умение писать программы на алгоритмическом языке для выполнения предложенного
Цель курсовой работы
Цель курсовой работы по дисциплине «Языки программирования» состоит в закреплении и углублении знаний и навыков, полученных при изучении дисциплины. Курсовая работа предполагает выполнение задания повышенной сложности по проектированию, разработке и тестированию программного обеспечения, а также оформлению сопутствующей документации.
Исходные данные варианта задания:  
Общий план работы
Для выполнения курсовой работы требуется умение писать программы на алгоритмическом языке для выполнения предложенного варианта.
Таким образом, последовательность выполнения курсовой работы следующая:
1. Ознакомится необходимым алгоритмом согласно варианту задания.
2. В соответствии с заданным вариантом написать программу.
3. Описать соответствующий алгоритм.
4. Написать и отладить на компьютере программу
5. Привести контрольную распечатку.
6. Оформить отчет.
Алгоритм решения поставленной задачи
Шаг 1. Подготовка исходных данных для решения задачи.
Подготовить используя средство отрисовки графов yEd Graph Editor (загрузить можно по ссылке https://www.yworks.com/products/yed/ - лицензия GNU) 3 графа:
Граф 1: 7 вершин и 7-14 дуг (необходимое количество дуг в зависимости от варианта)
Граф 2: 15 вершин и 15-20 дуг (необходимое количество дуг в зависимости от варианта)
Граф 3: 20 вершин и 20-40 дуг (необходимое количество дуг в зависимости от варианта)
Необходимо сохранить нарисованные графы в двух форматах:
GraphML — язык описания (иногда упоминается как отдельный формат файлов) графов на основе XML.
Trivial Graph Format («простой формат графов», сокр. TGF) — простой формат файлов, основанный на тексте, для описания графов.
При этом потребуется изобразить неориентированный граф в виде ориентированного графа, но с двунаправленными ребрами, как показано, например, на рисунке ниже.
Для графа 1 необходимо подтвердить полученный результат вручную поэтапно показав, как был получен именно этот результат.
Для графов 2 и 3 нужно привести скриншот работы программы. Необходимо, используя граф 2 и 3, показать наиболее сложные с точки зрения алгоритма случаи работы программы.
Изображения всех тестовых графов необходимо включить в отчет.
Шаг 2. Реализация алгоритма чтения формата хранения графов TGF.
Шаг 3. Реализовать необходимый алгоритм в соответствии с заданным вариантом задания (необходимые материалы приведены в разделе необходимые сведения из теории).
Шаг 4. Адаптировать разработанный алгоритм на шаге 3 для заданного в варианте способа представления графа.
Шаг 5. Протестировать разработанное программное обеспечение.
Шаг 6. Оформить отчет по курсовой работе.
Листинг программы
«Vertex.h»
#pragma once // Защита от двойного подключения заголовочного файла
#include
#include
using namespace std;
class Vertex //Указание класса Вершина
{
public:
/*указание конструктора с параметром, где
_name - имя вершины, являющееся входным параметром*/
Vertex(string _name);
Vertex(); //указание деструктора, освобождающего память
string name; //имя вершины
bool mark; //Отметка о посещении вершины true or false
int countAdjacentVertexs; //Количество смежных вершин
Vertex ** adjacentVertexs; //Массив указателей на смежные вершины
/*Получение индекса смежной вершины по имени
На вход: name - имя вершины
На выход: int:-1 - смежная вершина не найдена / индекс смежной вершины в массиве смежных вершин*/
int indexOfAdjacentVertex(string name);
/*Получение индекса смежной вершины, но! с указателем на смежную вершину, а не с именем добавляемой вершины
На вход: vertex - указатель на смежную вершину
На выход: int:-1 - смежная вершина не найдена / индекс смежной вершины в массиве смежных вершин*/
int indexOfAdjacentVertex(Vertex * vertex);
/*Добавление смежной вершины
На вход: adjancentVertex - указатель на добавляемую смежную вершину
На выход: bool: true - добавлена/ false - не добавлена*/
bool AddAdjacentVertex(Vertex*adjacentVertex);
/*Удаление смежной вершины
На вход: addjacenVertex - указатель на удаляемую вершину
На выход: bool: true - удаление успешно / false - удаление провалено, вершина не удалена*/
bool DeleteAdjacentVertex(Vertex *adjacentVertex);
//Перегруженные операторы вывода (для вывода с помощью cout<<)
friend std::ostream& operator<< (std::ostream &out, const Vertex &vertex);
friend std::ostream& operator<< (std::ostream &out, const Vertex * vertex);
};
«Arc.h»
#pragma once // Защита от двойного подключения заголовочного файла
#include "Vertex.h" //Наследуем
//Создание класса дуги
class Arc
{
public:
/*создание конструктора с параметром(инициализация двумя вершинами и весом), где
На вход: указатели: _vertexFrom - Начальная вершина дуги
_vertexTo - Конечная вершина дуги
вес дуги: _weight (изначально 0) */
Arc(Vertex * _vertexFrom, Vertex * _vertexTo, int _weight = 0);
//Указание деструктора, освобождающего память
Arc();
//Объявление веса дуги
int weight;
//Начальная вершина дуги
Vertex * vertexFrom;
//Конечная вершина дуги
Vertex * vertexTo;
//Перегруженные операторы вывода (для вывода с помощью cout<<)
friend std::ostream& operator<< (std::ostream &out, const Arc &arc);
friend std::ostream& operator<< (std::ostream &out, const Arc * arc);
};
«AdditionallyForGraf.h»
#pragma once // Защита от двойного подключения заголовочного файла
#include "Arc.h" //Наследуем
//Класс дополнительных функций
class AdditionallyForGraf
{ public:
/*Возвращение индекса первой вершиныв графе (виртуальная для реализации функции в наследнике)
На выход: int: -1 - первая вершина не обнаружена / индекс первой вершины в массиве вершин */ virtual int FIRST() = 0;
/*Функция возвращащая индекс вершины, смежной с вершиной vertex, следующей за индексом index
(виртуальная для реализации функции в наследнике)
На вход: vertex - указатель на вершину, для которой ищем следующую за index-ом смежную вершину
index - индекс следующей смежной вершины
На выход: int: -1 - первая вершина не найдена/ индекс первой вершины в массиве вершин */
virtual int NEXT(Vertex * vertex, int index) = 0;
/*Функция, которая возвращает вершину с индексом index из множества вершин, смежных с vertex.
(виртуальная для реализации функции в наследнике)
На вход: vertex - указатель на вершину, для которой ищем i-ю смежную вершину
index - индекс искомой смежной вершины
На выход: Vertex *: NULL - смежная вершина с индексом index не найдена/ указатель на смежную вершину с индексом index */
virtual Vertex * VERTEX(Vertex * vertex, int index) = 0; };
«Graf.h»
#pragma once // Защита от двойного подключения заголовочного файла
#include "AdditionallyForGraf.h" // Наследуем
#include //библиотека для работы с классами
#include
Graf();
/*Удаление всех вхождений указанной строки из строки (Для успешного чтения из файла)
На вход: str - строка, из которой будем удалять
part- строка, все вхождения которой будем удалять
На выход:string - исходная строка после удаления*/
string EraseAll(string str, string part);
/*Загрузка графа из TGF файла
На вход: fileName - имя файла
На выход: bool: true - загрузка выполнена / false - загрузка не выполнена */
bool ReadFromFile(string fileName);
//Линейный список указателей на вершины (для вывода пути)
list lyst;
//Наконец-то я нашел, как сворачивать МНОГО КОДА!!!!!!!
#pragma region Вершины
Vertex ** vertexs; //Массив указателей на вершины
int countVertexs; //Кол-во вершин в графе
void PrintAllVertexs(); //Вывод всех вершин
/*Получение вершины по имени
На вход: vertexName - имя вершины
На выход: Vertex *:NULL - вершина отсутствует / указатель на вершину*/
Vertex * GetVertex(string vertexName);
/*Получение вершины по индексу
На вход: vertexIndex - индекс искомой вершины
На выход: Vertex *:NULL - вершина отсутствует / указатель на вершину*/
Vertex * GetVertex(int vertexIndex);
/*Получение индекса вершины по имени
На вход: name - имя искомой вершины
На выход: int: -1 - вершина отсутствует / индекс вершины в массиве вершин*/
int indexOfVertex(string name);
/*Получение индекса вершины по указателю
На вход: vertex - указатель на искомую вершину
На выход: int: -1 - вершина не найдена / индекс вершины в массиве вершин*/
int indexOfVertex(Vertex * vertex);
/*Добавление вершины по имени
На вход: name - имя добавляемой вершины
На выход: Vertex *: NULL - вершина не добавлена/ - указатель на добавленную вершину*/
Vertex * AddVertex(string name);
/*Добавление вершины по указателю
На вход: vertex - указатель на добавляемую вершину
На выход: bool: true - успешное добавление / false - вершина не добавлена*/
bool AddVertex(Vertex * vertex);
/*Изменение имени вершины по индексу
На вход: index - индекс вершины
newName - новое имя вершины
На выход: bool: true - успешное изменение / false - имя не изменено*/
bool ChangeVertex(int index, string newName);
/*Изменение имени вершины по имени
На вход: oldName - имя вершины
newName - новое имя вершины
На выход: bool: true - успешное изменение / false - имя не изменено*/
bool ChangeVertex(string oldName, string newName);
/*Удаление вершины по имени
На вход: name - имя вершины
На выход: bool: true - успешное удаление / false - вершина не удалена*/
bool DeleteVertex(string name);
/*Удаление вершины по индексу
На вход: index - индекс вершины
На выход: bool: true - успешное удаление/ false - вершина не удалена*/
bool DeleteVertex(int index);
#pragma endregion
//Сворачивание участка для удобства чтения
#pragma region Дуги
Arc ** arcs; //Массив указателей на дуги
int countArcs; //Кол-во дуг в графе
void PrintAllArcs(); //Вывод всех дуг
/*Получение индекса дуги по индексам вершин
На вход: vertexFromIndex - индекс начальной вершины
vertexToIndex - индекс конечной вершины
На выход: Arc *:NULL - дуга отсутствует / указатель на дугу*/
Arc * GetArc(int vertexFromIndex, int vertexToIndex);
/*Получение индекса дуги по именам вершин
На вход: vertexFromName - имя начальной вершины
vertexToName - Имя конечной вершины
На выход: Arc *:NULL - дуга отсутствует / указатель на дугу*/
Arc * GetArc(string vertexFromName, string vertexToName);
/*Получение индекса дуги по указателям на вершины
На вход: vertexFrom - начальная вершина
vertexTo - конечная вершина
На выход: int: -1 - дуга отсутсвует / индекс дуги в массиве дуг*/
int indexOfArc(Vertex * vertexFrom, Vertex * vertexTo);
/*Получение индекса дуги по указателю на дугу
На вход: arc - указатель на искомую дугу
На выход: int: -1 - дуга отсутствует / индекс дуги в массиве дуг*/
int indexOfArc(Arc * arc);
/*Добавление дуги по указателям на вершины
На вход: vertexFrom - указатель на начальную вершину
vertexTo - указатель на конечную вершину
_weight - вес дуги (изначально 0)
На выход: Arc * *: NULL - ошибка добавления / - указатель на добавленную дугу */
Arc * AddArc(Vertex * vertexFrom, Vertex * vertexTo, int _weight = 0);
/*Добавление дуги по именам вершин
На вход: vertexFromName - имя начальной вершины
vertexToName - имя вершины, в которую входит дуга
_weight - вес дуги (по умолчанию 0)
На выход: Arc * *: NULL - ошибка добавления/ - указатель на добавленную дугу*/
Arc * AddArc(string vertexFromName, string vertexToName, int _weight = 0);
/*Добавление дуги по указателю на дугу
На вход: arc - указатель на дугу
На выход: bool: true - успешное добавление/ false - дуга не добавлена*/
bool AddArc(Arc * arc);
/*Изменение дуги по указателям на вершины
На вход: oldVertexFrom - старый указатель на начальную вершину
oldVertexTo - старый указатель на конечную вершину
newVertexFrom - новый указатель на начальную вершину (изначально NULL)
newVertexTo - новый указатель на конечную вершину (изначально NULL)
_weight - новый вес дуги (изначально 0)
На выход: bool: true - успешное изменение / false - дуга не изменена*/
bool ChangeArc(Vertex * oldVertexFrom, Vertex * oldVertexTo, Vertex * newVertexFrom = NULL, Vertex * newVertexTo = NULL, int _weight = 0);
/*Изменение дуги по индексу изменяемой дуги
На вход: indexArc - индекс дуги в массиве дуг
newVertexFrom - новый указатель на начальную вершину (изначально NULL)
newVertexTo - новый указатель на конечную вершину (изначально NULL)
_weight - новый вес дуги (изначально 0)
На выход: bool: true - успешное изменение / false - дуга не изменена*/
bool ChangeArc(int indexArc, Vertex * newVertexFrom = NULL, Vertex * newVertexTo = NULL, int _weight = -1);
/*Удаление дуги по индексу
На вход: indexArc - индекс дуги
На выход: bool: true - успешное удаление / false - дуга не удалена*/
bool DeleteArc(int indexArc);
/*Удаление дуги по указателям на вершины
На вход: vertexFrom - указатель на начальную вершину
vertexTo - указатель на конечную вершину
На выход: bool: true - успешное удаление / false - дуга не удалена*/
bool DeleteArc(Vertex * vertexFrom, Vertex * vertexTo);
#pragma endregion
#pragma region FIRST,NEXT,VERTEX
//описание в базовом классе
virtual int FIRST();
virtual int NEXT(Vertex * vertex, int index);
virtual Vertex * VERTEX(Vertex * vertex, int index);
#pragma endregion
#pragma region Реализация варианта
/*вспомогательная функция, для обхода смежных вершин
На вход: index - индекс текущей вершины в массиве вершин*/
void DFSR(int index);
/*Функция, которая ищет путь, проходящий через ВСЕ вершины орграфа,
причем через вершину можно проходить только один раз, а начальная и
предпоследняя вершины должны быть смежными, и выводить его на экран, если он есть. */
void DFS();
#pragma endregion
};
«Vetex.cpp»
#include "Vertex.h"
Vertex::Vertex(string _name) // Описание класса Вершина
{
name = _name; // записываем имя
mark = false; // вершина не посещена
adjacentVertexs = NULL; //инициализируем список смежных вершин
}
Vertex::
Vertex() // описание деструктора
{
delete[] adjacentVertexs; //очищаем список смежных вершин
}
int Vertex::indexOfAdjacentVertex(string name) // Получение индекса смежной вершины по имени
{
int index = -1;
for (int i = 0; i < countAdjacentVertexs; i++) //Перебираем все элементы массива смежных вершин
{
if (adjacentVertexs[i]->name == name) //если имя очередной вершины совпадает с искомым
{
index = i; //запоминаем индекс
break; //выходим из цикла
}
}
return index; //возвращаем полученный индекс
}
int Vertex::indexOfAdjacentVertex(Vertex * vertex)
//Запускам функцию поиска индекса смежной вершины по имени и возвращаем то, что вернет эта функция (полученный индекс)
{
return indexOfAdjacentVertex(vertex->name);
}
bool Vertex::AddAdjacentVertex(Vertex * adjacentVertex) //Добавление смежной вершины
{
int id = indexOfAdjacentVertex(adjacentVertex); //Ищем добавляемую вершину в массиве смежных вершин
/*если вершина найдена, следовательно вершина уже присутствует в массиве,
т.е мы выходим из функции и возвращаем false (т.к. вершина не добавлена)*/
if (id != -1)
return false;
adjacentVertexs = (Vertex**)realloc(adjacentVertexs, (countAdjacentVertexs + 1) * sizeof(Vertex*)); //расширяем массив смежных вершин
adjacentVertexs[countAdjacentVertexs] = adjacentVertex; //добавляем смежную вершину в массив
countAdjacentVertexs++; //увеличиваем количество смежных вершин
return true; //возвращаем true, т.к. вершина добавлена
}
bool Vertex::DeleteAdjacentVertex(Vertex *adjacentVertex) //Удаление смежной вершины
{
int id = indexOfAdjacentVertex(adjacentVertex); //Ищем удаляемую вершину в массиву смежных вершин
/*если вершина найдена, следовательно вершина уже нет в массиве,
т.е мы выходим из функции и возвращаем false (т.к. вершина не удалена)*/
if (id == -1)
return false;
for (int i = id; i < countAdjacentVertexs - 1; i++) //затираем удаляемую вершину(смещаем на -1 вершины на после удаляемой)
adjacentVertexs[i] = adjacentVertexs[i + 1];
adjacentVertexs = (Vertex**)realloc(adjacentVertexs, (countAdjacentVertexs - 1) * sizeof(Vertex*)); //сокращаем массив смежных вершин (тем самым удалив последний элемент)
countAdjacentVertexs--; //уменьшаем количество смежных вершин
return true; //возвращаем true, т.к. вершина удалена
}
ostream& operator<< (std::ostream &out, const Vertex &vertex) //Перегруженный оператор вывода (для вывода с помощью cout<<)
{
out << vertex.name; //выводим имя вершины
return out;
}
ostream& operator<< (std::ostream &out, const Vertex * vertex) //Перегруженный оператор вывода (для вывода с помощью cout<<)
{
out << vertex->name; //выводим имя вершины
return out; }
«Arc.cpp»
#include "Arc.h"
Arc::Arc(Vertex * _vertexFrom, Vertex * _vertexTo, int _weight) // Описание класса дуги
{ vertexFrom = _vertexFrom; //записываем указатель на начальную вершину
vertexTo = _vertexTo; //записываем указатель на конечную вершину
weight = _weight; //записываем вес дуги
vertexFrom->AddAdjacentVertex(vertexTo); //для вершины, из которой выходит дуга добавляем смежную вершину }
Arc::
Arc() //Описание деструктора
{ vertexFrom->DeleteAdjacentVertex(vertexTo); //для начальной вершины удаляем смежную вершину }
ostream& operator<< (std::ostream &out, const Arc &arc) //Перегруженный оператор вывода (для вывода с помощью cout<<)
{ out << arc.vertexFrom->name << " " << arc.vertexTo->name; //выводим имена начальной и конечной вершин
return out; }
ostream& operator<< (std::ostream &out, const Arc * arc) //Перегруженный оператор вывода (для вывода с помощью cout<<)
{
out << arc->vertexFrom->name << " " << arc->vertexTo->name; //выводим имена начальной и конечной вершин
return out;
}
«Graf.cpp»
#include "Graf.h"
Graf::Graf() //Описание графа
{
vertexs = NULL; //инициализируем список вершин
countVertexs = 0; //задаем количество вершин
arcs = NULL; //инициализируем список дуг
countArcs = 0; //задаем количество дуг
}
Graf::Graf(string fileName)
{
ReadFromFile(fileName); //считываем данные из файла
}
Graf::
Graf() //описание деструктора
{
lyst.clear(); //очищаем линейный список
for (int i = 0; i < countArcs; i++) //очищаем массив дуг
delete arcs[i];
delete[] arcs; //удаляем массив дуг
for (int i = 0; i < countVertexs; i++) //очищаем массив вершин
delete vertexs[i];
delete[] vertexs; //удаляем массив вершин
}
string Graf::EraseAll(string str, string part) //Удаление всех вхождений указанной строки из строки (Для успешного чтения из файла)
{
size_t pos = 0; //текущая позиция в строке
size_t i = 0; //дополнительная переменная
int length = part.length(); //длина искомой строки
while ((i = str.find(part, pos)) != string::npos) //пока удаляемая строка найдена в строка
{
str.erase(i, length); //удаляем строку
pos += i; //переходим к следующему символу
}
return str; //возвращаем измененую строку
}
bool Graf::ReadFromFile(string fileName) //чтение из файла
{
ifstream file(fileName); //объект для работы с файлом
if (!file.is_open()) //если не удалось открыть файл, то возвращаем false (файл не загружен)
return false;
string line; //вспомогательная строка для считывания
Vertex *vertex; //указатель на вершину
string vertexName; //имя вершины
string vertexIndex; //индекс вершины
map maps; //соответсвие индекса вершины и самой вершины
int indexspace = 0;
while (getline(file, line) && (!line._Equal("#"))) //пока файл не кончился и не встречена #
{
indexspace = line.find(' '); //ищем пробел
vertexIndex = line.substr(0, indexspace); //считываем индекс вершины
vertexIndex = EraseAll(vertexIndex, " "); //удаляем пробелы
vertexName = line.substr(indexspace + 1, line.length() - 1 - indexspace); //считываем имя вершины
vertexName = EraseAll(vertexName, " "); //удаляем пробелы
vertex = AddVertex(vertexName); //добавляем вершину в граф
if (vertex != NULL) //если вершина добавлена
{
maps.insert(pair(vertexIndex, vertex)); //добавляем пару(индекс-вершина)
}
}
string arc[2]; //пара индексов вершин
while (getline(file, line)) //пока не конец файла
{
indexspace = line.find(' '); //ищем пробелы
arc[0] = line.substr(0, indexspace); //выделяем индекс начальной вершины
arc[0] = EraseAll(arc[0], " "); //удаляем пробелы
arc[1] = line.substr(indexspace + 1, line.length() - 1 - indexspace); //выделяем индекс конечной вершины
arc[1] = EraseAll(arc[1], " "); //удаляем пробелы
AddArc(maps[arc[0]], maps[arc[1]]); //по полученной паре индексов добавляем дугу
}
file.close(); //закрываем файл
return true; //возвращаем true, т.к. чтение файла прошло успешно
}
#pragma region Вершины
void Graf::PrintAllVertexs() //Вывод всех вершин
{
for (int i = 0; i < countVertexs; i++)
cout << vertexs[i] << endl;
}
Vertex * Graf::GetVertex(string vertexName) //Получение вершины по имени
{
return GetVertex(indexOfVertex(vertexName));
}
Vertex * Graf::GetVertex(int vertexIndex) //Получение вершины по индексу
{
if ((vertexIndex < 0) || (vertexIndex >= countVertexs))
return NULL;
return vertexs[vertexIndex];
}
int Graf::indexOfVertex(string name) //Получение индекса вершины по имени
{
int index = -1;
for (int i = 0; i < countVertexs; i++) //Перебираем все элементы массива вершин
{
if (vertexs[i]->name == name) //если имя вершины совпадает с искомым
{
index = i; //запоминаем индекс
break; //выходим из цикла
}
}
return index; //возвращаем полученный индекс
}
int Graf::indexOfVertex(Vertex * vertex) //Получение индекса вершины по указателю
{
//Запускам функцию поиска индекса вершины по имени и возвращаем то, что вернет эта функция
return indexOfVertex(vertex->name);
}
Vertex * Graf::AddVertex(string nameVertex) //Добавление вершины по имени
{
int id = indexOfVertex(nameVertex); //Ищем добавляемую вершину в массиве вершин
/*если вершина найдена, следовательно вершина уже присутствует в массиве,
т.е мы выходим из функции и возвращаем false (т.к. вершина не добавлена)*/
if (id != -1)
return NULL;
vertexs = (Vertex**)realloc(vertexs, (countVertexs + 1) * sizeof(Vertex *)); //расширяем массив вершин
vertexs[countVertexs] = new Vertex(nameVertex); //создаем вершину,с указанными именем и добавляем её в массив
countVertexs++; //увеличиваем количество вершин
return vertexs[countVertexs - 1]; //возвращаем указатель на последнюю вершину в массиве вершин (добавленную)
}
bool Graf::AddVertex(Vertex * newVertex) //Добавление вершины по указателю
{
int id = indexOfVertex(newVertex); //Ищем добавляемую вершину в массиве вершин
/*если вершина найдена, следовательно вершина уже присутствует в массиве,
т.е мы выходим из функции и возвращаем false (т.к. вершина не добавлена)*/
if (id != -1)
return false;
vertexs = (Vertex**)realloc(vertexs, (countVertexs + 1) * sizeof(Vertex *)); //расширяем массив вершин
vertexs[countVertexs] = newVertex; //добавляем вершину в массив
countVertexs++; //увеличиваем количество вершин
return true; //возвращаем true - вершина добавлена
}
bool Graf::ChangeVertex(int index, string newName) // Изменение имени вершины по индексу
{
/*если индекс изменяемой вершины отрицательный или выходит за границы массива вершин,
то индекс введен неверно, возвращаем false (вершина не изменена)*/
if ((index < 0) || (countVertexs <= index))
return false;
vertexs[index]->name = newName; //изменяем имя вершины под индексом index
return true; //возвращаем true - вершина изменена
}
bool Graf::ChangeVertex(string oldName, string newName) //Изменение имени вершины по имени
{
//Запускам функцию изменения по индексу, и возвращаем то, что вернет эта функция
return ChangeVertex(indexOfVertex(oldName), newName);
}
bool Graf::DeleteVertex(int indexVertex) //Удаление вершины по индексу
{
/*если индекс удаляемой вершины отрицательный или выходит за границы массива вершин,
то индекс введен неверно, возвращаем false (вершина не изменена)*/
if ((indexVertex < 0) || (countVertexs <= indexVertex))
return false;
Vertex * deletingVertex = vertexs[indexVertex]; //запоминаем адрес вершины, которую будем удалять
for (int i = 0; i < countArcs; i++) //проходим по всем дугам
{
//если в очередной дуге имя входной или выходной вершины совпадает с именем удаляемой вершины
if ((arcs[i]->vertexFrom->name == deletingVertex->name) || (arcs[i]->vertexTo->name == deletingVertex->name))
{
DeleteArc(i); //удаляем дугу
i--; //возвращаемся т.к. следующая дуга стала текущей
}
}
for (int i = indexVertex; i < countVertexs - 1; i++) //затираем удаляемую вершину(смещаем на -1 вершины после удаляемой)
vertexs[i] = vertexs[i + 1];
vertexs = (Vertex**)realloc(vertexs, (countVertexs - 1) * sizeof(Vertex*)); //сокращаем массив вершин ( тем самым удалив последний элемент)
countVertexs--; //уменьшаем количество вершин
return true; //возвращаем true - вершина удалена
}
bool Graf::DeleteVertex(string name)
{
/*Запускам функцию удаления вершины по индексу,
и возвращаем то, что вернет эта функция*/
return DeleteVertex(indexOfVertex(name));
}
#pragma endregion
#pragma region Дуги
void Graf::PrintAllArcs() //Вывод всех дуг
{
for (int i = 0; i < countArcs; i++)
cout << arcs[i] << endl;
}
Arc * Graf::GetArc(int vertexFromIndex, int vertexToIndex) //Вывод дуги по индексам
{
//если хоть одна из вершин не найдена
if ((vertexFromIndex < 0) || (vertexToIndex < 0) || (vertexFromIndex >= countArcs) || (vertexToIndex >= countArcs))
return NULL;
int arcIndex = indexOfArc(vertexs[vertexFromIndex], vertexs[vertexToIndex]);
if (arcIndex == -1)
return NULL;
return arcs[arcIndex];
}
Arc * Graf::GetArc(string vertexFromName, string vertexToName) //Вывод дуги по именам вершин
{
return GetArc(indexOfVertex(vertexFromName), indexOfVertex(vertexToName)); //Вывод дуги по индексам
}
int Graf::indexOfArc(Vertex * vertexFrom, Vertex * vertexTo) // Получения индекса дуги по указателям на вершины
{
int index = -1;
for (int i = 0; i < countArcs; i++) //Перебираем все элементы массива дуг
{
//если имена начальной и конечной вершин дуги совпадают с именами искомой дуги
if ((arcs[i]->vertexFrom->name == vertexFrom->name) && (arcs[i]->vertexTo->name == vertexTo->name))
{
index = i; //запоминаем индекс
break; //выходим из цикла
}
}
return index; //возвращаем полученный индекс
}
int Graf::indexOfArc(Arc * arc) //Получения индекса дуги по указателю на дугу
{
return indexOfArc(arc->vertexFrom, arc->vertexTo); // Получения индекса дуги по указателям на вершины
}
Arc * Graf::AddArc(Vertex * vertexFrom, Vertex * vertexTo, int _weight) //Добавление дуги по указателям на вершины
{
int id = indexOfArc(vertexFrom, vertexTo); //Ищем добавляемую дугу в массиве дуг
/*если дуга найдена или не указана начальная или конечная вершины,
то вершины указаны с ошибкой, возвращаем false (дуга не добавлена)*/
if ((id != -1) || (vertexFrom == NULL) || (vertexTo == NULL))
return NULL;
arcs = (Arc**)realloc(arcs, (countArcs + 1) * sizeof(Arc *)); //расширяем массив дуг
arcs[countArcs] = new Arc(vertexFrom, vertexTo, _weight); //добавляем дуга в массив
countArcs++; //увеличиваем количество дуг
return arcs[countArcs - 1]; //возвращаем укащатель на последнюю дугу в массиве дуг(добавленную)
}
Arc * Graf::AddArc(string vertexFromName, string vertexToName, int _weight) // Добавление дуги по именам вершин
{
int vertexFromIndex = indexOfVertex(vertexFromName); //индекс начальной вершины
int vertexToIndex = indexOfVertex(vertexToName); //индекс конечной вершины
/*если хоть одна из вершин не найдена,
то вершины указаны с ошибкой, возвращаем false (дуга не добавлена)*/
if ((vertexFromIndex == -1) || (vertexToIndex == -1))
return false;
return AddArc(vertexs[vertexFromIndex], vertexs[vertexToIndex], _weight); //Добавление дуги по указателям на вершины
}
bool Graf::AddArc(Arc * arc)
{
int id = indexOfArc(arc); //Ищем добавляемую дугу в массиве дуг
if (id != -1) //если дуга найдена, то дуга уже существует, возвращаем false (дуга не добавлена)
return false;
arcs = (Arc**)realloc(arcs, (countArcs + 1) * sizeof(Arc *)); //расширяем массив дуг
arcs[countArcs] = arc; //добавляем дуга в массив
countArcs++; //увеличиваем количество дуг
return true; //возвращаем true - дуга добавлена
}
bool Graf::ChangeArc(int indexArc, Vertex * newVertexFrom, Vertex * newVertexTo, int _weight) //Изменение дуги по указателям на вершины
{
/*если индекс изменяемой дуги отрицательный или выходит за границы массива вершин,
то указатели переданы неверно, возвращаем false (дуга не изменена)*/
if ((indexArc < 0) || (countArcs <= indexArc))
return false;
Arc *arc = arcs[indexArc]; //запоминаем изменяемую дугу
if ((_weight > 0) && (arc->weight != _weight)) //если указанный вес положительный и равен текущему
{
arc->weight = _weight; //изменяем вес
}
//если указатель на новую начальную вершину не пустой и имя этой вершины != имени текущей
if ((newVertexFrom != NULL) && (arc->vertexFrom->name != newVertexFrom->name))
{
arc->vertexFrom->DeleteAdjacentVertex(arc->vertexTo); //удаляем из старой вершины, из которой выходит дуга смежную вершину
arc->vertexFrom = newVertexFrom; //изменяем вершину, из которой выходит дуга
newVertexFrom->AddAdjacentVertex(newVertexTo); //добавляем в вершину, из которой выходит дуга смежную дугу
}
else
{
//если указатель на новую конечную вершину не пустой и имя этой вершины не равно имени текущей
if ((newVertexTo != NULL) && (arc->vertexTo->name != newVertexTo->name))
{
arcs[indexArc]->vertexTo = newVertexTo; //изменяем вершину, в которую входит дуга
}
}
return true; //возвращаем true - дуга изменена
}
//Изменение дуги по указателям на вершины
bool Graf::ChangeArc(Vertex * oldVertexFrom, Vertex * oldVertexTo, Vertex * newVertexFrom, Vertex * newVertexTo, int _weight)
{
//Запускам функцию изменения дуги по индексу
return ChangeArc(indexOfArc(oldVertexFrom, oldVertexTo), newVertexFrom, newVertexTo, _weight);
}
bool Graf::DeleteArc(int indexArc) //Удаление дуги по индексу
{
/*если индекс удаляемой дуги отрицательный или выходит за границы массива дуг,
то индекс указан с ошибкой, возвращаем false (дуга не удалена)*/
if ((indexArc < 0) || (countArcs <= indexArc))
return false;
Arc *arc = arcs[indexArc]; //запоминаем удаляемую дугу
for (int i = indexArc; i < countArcs - 1; i++) //затираем удаляемую дугу(смещаем на -1 дугу на после удаляемой)
arcs[i] = arcs[i + 1];
arcs = (Arc**)realloc(arcs, (countArcs - 1) * sizeof(Arc*)); //сокращаем массив дуг ( тем самым удалив последний элемент)
countArcs--; //уменьшаем количество дуг
return true; //возвращаем true - дуга удалена
}
bool Graf::DeleteArc(Vertex * vertexFrom, Vertex * vertexTo) //Удаление дуги по указателям на вершины
{
return DeleteArc(indexOfArc(vertexFrom, vertexTo)); //Удаление дуги по индексу
}
#pragma endregion
#pragma region FIRST,NEXT,VERTEX
int Graf::FIRST() //Возвращения индекса первой вершины в графе
{
if (countVertexs < 1) //если массив вершин пуст - возвращаем -1
return -1;
return indexOfVertex(vertexs[0]); //возвращаем индекс первой вершины в массиве вершин
}
int Graf::NEXT(Vertex * vertex, int index) //Возвращения индекса вершины, смежной с вершиной v, следующей за индексом i
{
int indexVertex = indexOfVertex(vertex); //вычисляем индекс текущей вершины
/*если указанный индекс+1 отрицательный или превышает количество смежных вершин для указанной вершины,
то индекс указан с ошибкой, возвращаем -1(индекс не найден)*/
if (((index + 1) < 0) || (vertexs[indexVertex]->countAdjacentVertexs <= (index + 1)))
return -1;
//получаем указатель на смежную для текущей вершины вершину с индексом index+1
Vertex * nextAdjacentVertex = vertexs[indexVertex]->adjacentVertexs[index + 1];
return indexOfVertex(nextAdjacentVertex); //возвращаем индекс этой вершины
}
Vertex * Graf::VERTEX(Vertex *vertex, int index) //Возвращение вершины с индексом i из множества вершин, смежных с v
{
/*если указанный индекс отрицательный или превышает количество смежных вершин для указанной вершины,
то индекс указан с ошибкой, возвращаем NULL(индекс не найден)*/
if ((index < 0) || (vertex->countAdjacentVertexs <= index))
return NULL;
//возвращаем указатель на смежную вершину с индексом index
return vertex->adjacentVertexs[index];
}
#pragma endregion
#pragma region Реализация варианта
void Graf::DFSR(int index)
{
//добавляем вершину в список
lyst.push_back(vertexs[index]);
//отмечаем вершину как посещенную
vertexs[index]->mark = true;
//для всех смежных для текущей вершины вершин
for (int i = 0; i < vertexs[index]->countAdjacentVertexs; i++)
{
//если вершина не посещена
if (vertexs[index]->adjacentVertexs[i]->mark == false)
{
//делаем тоже самое
DFSR(indexOfVertex(vertexs[index]->adjacentVertexs[i]));
}
}
if (lyst.size() == countVertexs) //если путь содержит количество элементов равное количеству вершин в массиве вершин
{
//проверяем смежность начальной и последней вершин пути
bool firstDontAdjacentLast = (lyst.front()->indexOfAdjacentVertex(lyst.back())!=-1);
bool lastDontAdjacentFirst = (lyst.back()->indexOfAdjacentVertex(lyst.front()))!=-1;
if (firstDontAdjacentLast&&lastDontAdjacentFirst) //если вершины смежны
{
//выводим путь
copy(lyst.begin(), lyst.end(), ostream_iterator(cout));
cout << lyst.front();
cout << endl;
}
}
lyst.pop_back(); //удаляем вершину из пути
//отмечаем вершину как непосещенную для всевозможного обхода графа
vertexs[index]->mark = false;
}
void Graf::DFS()
{
for (int i = 0; i < countVertexs; i++) //для всех вершин
{
if (!vertexs[i]->mark) //если вершина не посещена
DFSR(i);
}
}
#pragma endregion
«Main.cpp»
#include //Ввод, вывод, считывание
#include "Graf.h" //Наследуем
#include //Для подключения русского языка в консоль
int main()
{
SetConsoleCP(1251); SetConsoleOutputCP(1251); //Подключаем поддержку русского языка в консоль
setlocale(LC_ALL, "Russian");
Graf * graf = new Graf(); //создаем граф
//Запускаем интерфейс программы в консоли
#pragma region Интерфейс
int *cofw = new int;
*cofw = 0;
string *NameOfVertex1 = new string;
string *NameOfVertex2 = new string;
string *NameOfVertex3 = new string;
string *NameOfVertex4 = new string;
string *reader = new string;
int *IndexOfVertex1 = new int;
int *WeightOfArc = new int;
while (*cofw != 13) {
cout << endl<< "1-Считать граф из файла и вывести на экран в текстовом виде" << endl;
cout << "2-Добавить вершину в граф" << endl;
cout << "3-Добавить дугу между вершинами" << endl;
cout << "4-Удалить вершину из графа" << endl;
cout << "5-Удалить дугу между вершинами" << endl;
cout << "6-Изменить имя вершины" << endl;
cout << "7-Изменить дугу" << endl;
cout << "8-Вывести на экран граф в текстовом виде" << endl;
cout << "9-Выполнение функции FIRST (Возвращение индекса первой вершины в графе)" << endl;
cout << "10-Выполнение функции NEXT (Возвращение индекса вершины смежной с вершиной v,следующей за индексом i)" << endl;
cout << "11-Выполнение функции VERTEX (Возвращение вершины с индексом i из множества вершин, смежных с v)" << endl;
cout << "12-Поиск маршрутов, удовлетворяющих условию задания (путь через все вершины по 1 разу, начальная и конечная совпадают)" << endl;
cout << "13-Очистка памяти, выход из программы" << endl;
cout << "Введите номер операции: ";
cin >> *cofw;
switch (*cofw) {
case 1:
cout << "Введите полное название файла (с расширением), пример: graph1.tgf" << endl;
cin >> *reader;
graf->ReadFromFile(*reader);
graf->PrintAllVertexs();
graf->PrintAllArcs();
break;
case 2:
cout << "Введите имя вершины, пример: v44" << endl;
cin >> *NameOfVertex1;
graf->AddVertex(*NameOfVertex1);
break;
case 3:
cout << "Введите начальную вершину, пример: v44 " << endl;
cin >> *NameOfVertex1;
cout << "Введите конечную вершину, пример: v44 " << endl;
cin >> *NameOfVertex2;
cout << "Ввести вес дуги? 1-да, 2-нет" << endl;
cin >> *WeightOfArc;
if (*WeightOfArc == 1) {
cout << "Введите вес дуги, пример:20" << endl;
cin >> *WeightOfArc;
graf->AddArc(*NameOfVertex1, *NameOfVertex2, *WeightOfArc);
}
else {
graf->AddArc(*NameOfVertex1, *NameOfVertex2);
}
break;
case 4:
cout << "Введите удаляемую вершину, пример: v1 " << endl;
cin >> *NameOfVertex1;
graf->DeleteVertex(*NameOfVertex1);
break;
case 5:
cout << "Введите начальную вершину, пример: v44 " << endl;
cin >> *NameOfVertex1;
cout << "Введите конечную вершину, пример: v44 " << endl;
cin >> *NameOfVertex2;
graf->DeleteArc(graf->GetVertex(*NameOfVertex1), graf->GetVertex(*NameOfVertex2));
break;
case 6:
cout << "Введите имя старой вершины, пример: v1" << endl;
cin >> *NameOfVertex1;
cout << "Введите новое имя вершины, пример: v44" << endl;
cin >> *NameOfVertex2;
graf->ChangeVertex(*NameOfVertex1, *NameOfVertex2);
break;
case 7:
cout << "Введите начальную вершину существующей дуги, пример: v1 " << endl;
cin >> *NameOfVertex1;
cout << "Введите конечную вершину существующей дуги , пример: v2 " << endl;
cin >> *NameOfVertex2;
cout << "Введите начальную вершину желаемой дуги, пример: v1 " << endl;
cin >> *NameOfVertex3;
cout << "Введите конечную вершину желаемой дуги , пример: v6 " << endl;
cin >> *NameOfVertex4;
graf->ChangeArc(graf->indexOfArc(graf->GetVertex(*NameOfVertex1), graf->GetVertex(*NameOfVertex2)), graf->GetVertex(*NameOfVertex3), graf->GetVertex(*NameOfVertex4));
break;
case 8:
graf->PrintAllVertexs();
graf->PrintAllArcs();
break;
case 9:
cout << "Индекс первой вершины в графе: " << graf->indexOfVertex("v7") << endl; //<< graf->FIRST() << endl;
break;
case 10:
cout << "Индекс вершины смежной с вершиной v,следующей за индексом i" << endl;
cout << "Введите вершину v, пример v4" << endl;
cin >> *NameOfVertex1;
cout << "Введите индекс i, пример 5" << endl;
cin >> *IndexOfVertex1;
cout << "Индекс вершины смежной с вершиной " << *NameOfVertex1 << " ,следующей за индексом " << *IndexOfVertex1 << " ";
cout << graf->NEXT(graf->GetVertex(*NameOfVertex1), *IndexOfVertex1)<
break;
case 11:
cout << "Вершина с индексом i из множества вершин, смежных с v" << endl;
cout << "Введите вершину v, пример v4" << endl;
cin >> *NameOfVertex1;
cout << "Введите индекс i, пример 5" << endl;
cin >> *IndexOfVertex1;
cout << "Вершина с индексом " << *IndexOfVertex1 << " из множества вершин смежных с " << *NameOfVertex1 << " ";
cout << graf->NEXT(graf->GetVertex(*NameOfVertex1), *IndexOfVertex1);
break;
case 12:
graf->DFS();
break;
case 13:
break;
default:
cout << "Ошибка ввода. Вы можете ввести цифры от 1 до 13" << endl << endl;
break;
}
}
delete cofw;
delete NameOfVertex1; delete NameOfVertex2; delete NameOfVertex3; delete NameOfVertex4;
delete reader; delete IndexOfVertex1; delete WeightOfArc;
#pragma endregion
delete graf; //Удаляем граф, очищаем память
system("pause"); //Чтобы консоль не закрылась после выполнения программы
return 0;
}
Анализ результатов
Граф №1 (7 вершин, 15 дуг)
Граф №2(15 вершин, 20 дуг)
Граф №3 (20 вершин, 27 дуг)
  
Вывод
Благодаря данной работе, я приобрел и закрепил свои навыки в проектировании, разработке и тестировании программного обеспечения. Я научился оформлять документацию курсовой работы, соблюдать требования к оформлению работ.
С помощью методических указаний я укрепил свои знания в использовании некоторых сложных и не очень команд, таких как FIRST, NEXT и пр., использовании динамических массивов и создании проектов. |
|
|
Скачать 281.52 Kb.