Пример 3. Анализ временной сложности:
Исходный граф:
Граф после удаления:
Анализ временной сложности: Воспользовавшись формулой 1, рассчитаем временную сложность программы для данного примера (количество дуг M = 181,
7601 проход по циклам. Анализ ёмкостной сложности: В данном примере количество дуг M = 181, количество вершин N = 77. Исходя из этого, вычислим ёмкостную сложность программы для данного примера по формуле 2:
3309 байт памяти. Результаты работы программы:
7. Исходный код программы: #include "stdafx.h" #include <iostream> #include <fstream> #include <string> #include <Windows.h>
using namespace std;
struct ArcGraph { int outVertexId; int inVertexId; };
struct DirectedGraph { ArcGraph oneArc; DirectedGraph *previousArc; DirectedGraph *nextArc; };
void _input(int &var) { int BAD_STATE = 2;
do { cin.clear(); cin.sync();
cin >> var; } while(cin.rdstate() == BAD_STATE); }
void _input(char &output, char mode = 'b') { const char OUTPUT_MODE = 'o', ASK_MODE = 'b', MAIN_MODE = 'm', SOME_ACTIONS_MODE = 's'; bool successfulInput;
do { cin.sync();
cin >> output; if(output == 'e') exit(0);
switch(mode) { case OUTPUT_MODE: successfulInput = (output == 'f' || output == 's'); break; case ASK_MODE: successfulInput = (output == 'y' || output == 'n'); break; case MAIN_MODE: successfulInput = (output == 'p' || output == 'm' || output == 'd' || output == 'r'); break; case SOME_ACTIONS_MODE: successfulInput = (output == 'p' || output == 'm' || output == 's' || output == 'r'); break; } } while(!successfulInput); }
void _input(string &var) { cin.sync();
getline(cin, var); }
bool fileExists(string fileName) { return (ifstream(fileName)!= NULL); }
void main() { setlocale(LC_ALL, "Russian"); system("cls");
static DirectedGraph *firstArc, *sideNode;
static ostream *out; static fstream fileForOutput; static string fileForOutputName;
static short CURRENT_STAGE = 0; static int vertexWithMaxLevel, maxLevel, NUM_VERTEX = 0; static bool **adjacencyMatrix, fileOutput; static char action;
const static short START_EXECUTION = 0, INPUT_DATA = 1, THE_MAIN_PART = 2, SOME_ACTIONS_PERFORMED = 3; const static char ASK_MODE = 'b', MAIN_MODE = 'm', SOME_ACTIONS_MODE = 's', YES = 'y', NO = 'n', ON_THE_SCREEN = 's', INTO_A_FILE = 'f', FOR_INPUT = 'i', FOR_OUTPUT = 'o', FOR_APPEND = 'a', PRINT_NEIBORHOODS = 'p', MAKE_ADJACENCY_MATRIX = 'm', DELETE_VERTEX = 'd', RESTART_PROGRAM = 'r', SAVE_NEW_GRAPH = 's', EXIT = 'e';
DirectedGraph *assembleGraph(int &NUM_VERTEX, ostream *stream); fstream openFile(string fileName, char mode); int findVertexAndPrintNewList(DirectedGraph *firstNode, int NUM_VERTEX, int &maxLevel, ostream *stream); bool **completeAdjacencyMatrix(DirectedGraph *firstNode, int NUM_VERTEX); bool saveGraph(string fileName, DirectedGraph *firstNode, int NUM_VERTEX); void removeAdjacentVertex(DirectedGraph *&firstArc, int NUM_VERTEX, int vertexId, int vertexLevel); void removeNode(DirectedGraph *node, DirectedGraph *&firstNode); void printNeiborhoodsList(DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, bool saveMode, string title = ""); void printMatrix(bool **matrix, int dimension, ostream *stream, string title = ""); void clearMatrix(bool **matrix, int dimention);
switch(CURRENT_STAGE) { case START_EXECUTION: cout << "Режим ввода данных (f - в файл, s - на экран, e - выход): "; _input(action, FOR_OUTPUT); switch(action) { case ON_THE_SCREEN: out = &cout; fileOutput = false; break; case INTO_A_FILE: cout << "Имя файла для записи (расширение не требуется): "; _input(fileForOutputName);
if(fileExists("output/"+fileForOutputName+".txt")) fileForOutput = openFile("output/"+fileForOutputName+".txt", FOR_APPEND); else fileForOutput = openFile("output/"+fileForOutputName+".txt", FOR_OUTPUT);
out = &fileForOutput; fileOutput = true; break; } CURRENT_STAGE = INPUT_DATA; break; case INPUT_DATA: firstArc = assembleGraph(NUM_VERTEX, out); CURRENT_STAGE = THE_MAIN_PART; break; case THE_MAIN_PART: cout << "Список доступных действий:" << endl; cout << PRINT_NEIBORHOODS << " - вывести список окрестностей" << endl; cout << MAKE_ADJACENCY_MATRIX << " - составить и вывести матрицу смежности" << endl; cout << DELETE_VERTEX << " - удалить смежные с вершиной, имеющей наибольшую степень исхода, вершины" << endl; cout << RESTART_PROGRAM << " - начать выполнение программы сначала" << endl; cout << EXIT << " - выход" << endl; _input(action, MAIN_MODE); switch(action) { case PRINT_NEIBORHOODS: printNeiborhoodsList(firstArc, out, NUM_VERTEX, false, "Граф задан следующим списком окрестностей:"); *out << endl << endl; if(fileOutput) cout << "Список окрестностей исходного графа записан в файл." << endl; break; case MAKE_ADJACENCY_MATRIX: adjacencyMatrix = completeAdjacencyMatrix(firstArc, NUM_VERTEX); printMatrix(adjacencyMatrix, NUM_VERTEX, out, "Матрица смежности исходного графа: "); clearMatrix(adjacencyMatrix, NUM_VERTEX); *out << endl << endl; if(fileOutput) cout << "Матрица смежности исходного графа записана в файл." << endl; break; case DELETE_VERTEX: vertexWithMaxLevel = findVertexAndPrintNewList(firstArc, NUM_VERTEX, maxLevel, out); *out << endl; NUM_VERTEX -= maxLevel; removeAdjacentVertex(firstArc, NUM_VERTEX, vertexWithMaxLevel, maxLevel); if(fileOutput) cout << "Вершины, смежные с вершиной, имеющей максимальную степень исхода, удалены," << endl << "Степени исхода всех вершин записаны в файл." << endl; CURRENT_STAGE = SOME_ACTIONS_PERFORMED; break; case RESTART_PROGRAM: while(firstArc!= NULL) { sideNode = firstArc; firstArc = firstArc->nextArc; delete sideNode; }
if(fileOutput) { fileForOutput.close(); *out << endl << endl; cout << "Запись в файл успешно завершена!" << endl; } CURRENT_STAGE = START_EXECUTION; break; } break; case SOME_ACTIONS_PERFORMED: cout << "Список доступных действий:" << endl; cout << PRINT_NEIBORHOODS << " - вывести список окрестностей" << endl; cout << MAKE_ADJACENCY_MATRIX << " - соствить и вывести матрицу смежности" << endl; cout << SAVE_NEW_GRAPH << " - сохранить новый граф" << endl; cout << RESTART_PROGRAM << " - начать выполнение программы сначала" << endl; cout << EXIT << " - выход" << endl; _input(action, SOME_ACTIONS_MODE); switch(action) { case PRINT_NEIBORHOODS: printNeiborhoodsList(firstArc, out, NUM_VERTEX, false, "Список окрестностей графа после удаления вершин, смежных с вершиной, имеющей максимальную степень исхода:"); *out << endl << endl; if(fileOutput) cout << "Список окрестностей нового графа записан в файл." << endl; break; case MAKE_ADJACENCY_MATRIX: adjacencyMatrix = completeAdjacencyMatrix(firstArc, NUM_VERTEX); printMatrix(adjacencyMatrix, NUM_VERTEX, out, "Матрица смежности нового графа: "); clearMatrix(adjacencyMatrix, NUM_VERTEX); *out << endl << endl; if(fileOutput) cout << "Матрица смежности нового графа записана в файл." << endl; break; case SAVE_NEW_GRAPH: cout << "Введите имя нового графа: "; _input(fileForOutputName); if(!saveGraph(fileForOutputName, firstArc, NUM_VERTEX)) cout << "Граф с таким именем " << fileForOutputName << " уже существует!" << endl; else cout << "Сохранение графа произведено успешно." << endl; break; case RESTART_PROGRAM: while(firstArc!= NULL) { sideNode = firstArc; firstArc = firstArc->nextArc; delete sideNode; }
if(fileOutput) { fileForOutput.close(); *out << endl << endl; cout << "Запись в файл успешно завершена!" << endl; } CURRENT_STAGE = START_EXECUTION; break; } }
system("pause"); main(); }
DirectedGraph *assembleGraph(int &NUM_VERTEX, ostream *stream) { DirectedGraph *firstNode = NULL, *lastNode = NULL, *currentNode;
bool getArcData(string graphName, int &NUM_VERTEX, DirectedGraph *&lastNode, ostream *stream = &cout);
string graphName;
cout << "Имя графа: "; _input(graphName);
if(getArcData(graphName, NUM_VERTEX, firstNode, stream)) { currentNode = firstNode;
while(getArcData(graphName, NUM_VERTEX, lastNode)) { lastNode->previousArc = currentNode; lastNode->nextArc = NULL;
currentNode->nextArc = lastNode; currentNode = lastNode; } }
return firstNode; }
bool getArcData(string graphName, int &NUM_VERTEX, DirectedGraph *&lastNode, ostream *stream = &cout) { static fstream fileForReadGraph; string filePath = "graphs/";
int inVertexId; static int counter = 0; char sideChar; static bool firstIn = true;
bool fileExists(string fileName); fstream openFile(string fileName, char mode);
if(firstIn) { if(!fileExists(filePath+graphName+".txt")) { cout << "Графа с таким именем не существует!" << endl << "Будет загружен стандартный файл..." << endl; graphName = "default"; } fileForReadGraph = openFile(filePath+graphName+".txt", 'i');
*stream << "Граф " << graphName << endl;
firstIn = false; counter++; } if(fileForReadGraph.eof()) { firstIn = true; NUM_VERTEX = counter; counter = 0; fileForReadGraph.close(); return false; }
lastNode = (DirectedGraph*) new (DirectedGraph); lastNode->previousArc = NULL; lastNode->nextArc = NULL; if(lastNode == NULL) { cout << "Память не выделилась!" << endl << "Выполнение программы завершено..."; Sleep(1000); exit(1); }
fileForReadGraph >> inVertexId;
lastNode->oneArc.inVertexId = inVertexId; lastNode->oneArc.outVertexId = counter;
sideChar = fileForReadGraph.get();
if(sideChar == '\n') counter++;
return true; }
int findVertexAndPrintNewList(DirectedGraph *firstNode, int NUM_VERTEX, int &maxLevelOfVertex, ostream *stream) { int counter, inVertexCounter, vertexWithMaxLevel = 0;
maxLevelOfVertex = 0; for(counter = 1; counter <= NUM_VERTEX; counter++) { inVertexCounter = 0; while((firstNode!= NULL) && (firstNode->oneArc.outVertexId == counter)) { inVertexCounter++; firstNode = firstNode->nextArc; } *stream << "Степень исхода вершины " << counter << ": " << inVertexCounter << endl;
if(inVertexCounter > maxLevelOfVertex) { maxLevelOfVertex = inVertexCounter; vertexWithMaxLevel = counter; } }
*stream << "Вершина с максимальной степенью исхода: " << vertexWithMaxLevel << endl;
return vertexWithMaxLevel; }
int foundInArray(int value, int *arr, int rightBound) { int counter, middle, leftBound = 0;
if((value > arr[rightBound]) || (value < arr[leftBound])) return -1;
counter = 0; while((rightBound-leftBound) > 1) { middle = (rightBound+leftBound)/2;
if(arr[middle] < value) leftBound = middle; else rightBound = middle; }
for(counter = 0; counter <= rightBound; counter++) { if(arr[counter] == value) return counter; }
return -1; }
fstream openFile(string fileName, char mode) { fstream filePointer;
switch(mode) { case 'i': filePointer.open(fileName, ios_base::in); break; case 'o': filePointer.open(fileName, ios_base::out); break; case 'a': filePointer.open(fileName, ios_base::app); break; }
return filePointer; }
void removeNode(DirectedGraph *node, DirectedGraph *&firstNode) { if((node->previousArc!= NULL) && (node->nextArc!= NULL)) { node->previousArc->nextArc = node->nextArc; node->nextArc->previousArc = node->previousArc; } else if((node->previousArc == NULL) && (node->nextArc!= NULL)) { node->nextArc->previousArc = NULL; firstNode = node->nextArc; } else if((node->previousArc!= NULL) && (node->nextArc == NULL)) { node->previousArc->nextArc = NULL; } else if((node->previousArc == NULL) && (node->nextArc == NULL)) { firstNode = NULL; }
delete node; }
bool saveGraph(string fileName, DirectedGraph *firstNode, int NUM_VERTEX) { bool fileExists(string fileName); void printNeiborhoodsList(DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, bool saveMode, string title = ""); fstream openFile(string fileName, char mode);
if(fileExists("graphs/"+fileName+".txt")) return false;
fstream file; file = openFile("graphs/"+fileName+".txt", 'o'); printNeiborhoodsList(firstNode, &file, NUM_VERTEX, true); return true; }
void removeAdjacentVertex(DirectedGraph *&firstArc, int NUM_VERTEX, int vertexId, int vertexLevel) { DirectedGraph *currentNode, *nodePointer, *sidePointer; int counter, currentId, *adjacentVertex, *newVertexId, NOT_FOUND = -1; bool noOneBefore;
void removeNode(DirectedGraph *node, DirectedGraph *&firstNode); int foundInArray(int value, int *arr, int rightBound);
currentNode = firstArc; while((currentNode!= NULL) && (currentNode->oneArc.outVertexId!= vertexId)) currentNode = currentNode->nextArc;
counter = 1; adjacentVertex = new int [vertexLevel]; adjacentVertex[0] = currentNode->oneArc.inVertexId; currentNode->oneArc.inVertexId = 0; currentNode = currentNode->nextArc; while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == vertexId)) { adjacentVertex[counter] = currentNode->oneArc.inVertexId; nodePointer = currentNode; currentNode = currentNode->nextArc; removeNode(nodePointer, firstArc); counter++; }
currentNode = firstArc; while(currentNode!= NULL) { currentId = currentNode->oneArc.outVertexId; if(foundInArray(currentId, adjacentVertex, vertexLevel-1)!= NOT_FOUND) { while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == currentId)) { nodePointer = currentNode; currentNode = currentNode->nextArc; removeNode(nodePointer, firstArc); } continue; }
while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == currentId)) currentNode = currentNode->nextArc; }
currentNode = firstArc; newVertexId = new int [NUM_VERTEX]; counter = 0; while(currentNode!= NULL) { newVertexId[counter] = currentNode->oneArc.outVertexId;
if(currentNode->oneArc.inVertexId!= 0) { noOneBefore = true; sidePointer = NULL; while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == newVertexId[counter])) { currentNode->oneArc.outVertexId = counter+1; if(sidePointer!= NULL) { removeNode(sidePointer, firstArc); sidePointer = NULL; }
if(foundInArray(currentNode->oneArc.inVertexId, adjacentVertex, vertexLevel-1)!= NOT_FOUND) { if(noOneBefore) { currentNode->oneArc.inVertexId = 0; sidePointer = currentNode; currentNode = currentNode->nextArc; } else { nodePointer = currentNode; currentNode = currentNode->nextArc; removeNode(nodePointer, firstArc); }
continue; }
if(noOneBefore) noOneBefore = false; currentNode = currentNode->nextArc; } } else { currentNode->oneArc.outVertexId = counter+1; currentNode = currentNode->nextArc; }
counter++; }
currentNode = firstArc; while(currentNode!= NULL) { if(currentNode->oneArc.inVertexId == 0) { currentNode = currentNode->nextArc; continue; }
currentId = currentNode->oneArc.outVertexId; while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == currentId)) { currentNode->oneArc.inVertexId = foundInArray(currentNode->oneArc.inVertexId, newVertexId, NUM_VERTEX-1)+1; currentNode = currentNode->nextArc; } } }
void printNeiborhoodsList(DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, bool saveMode, string title = "") { DirectedGraph *currentNode = firstNode; int currentVertex;
if(!title.empty()) *stream << title;
if(saveMode) { while(currentNode!= NULL) { currentVertex = currentNode->oneArc.outVertexId; *stream << endl << currentNode->oneArc.inVertexId; currentNode = currentNode->nextArc; while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == currentVertex)) { *stream << ' ' << currentNode->oneArc.inVertexId; currentNode = currentNode->nextArc; } }
} else { while(currentNode!= NULL) { *stream << endl << (currentVertex = currentNode->oneArc.outVertexId) << ": ";
*stream << currentNode->oneArc.inVertexId; currentNode = currentNode->nextArc; while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == currentVertex)) { *stream << ' ' << currentNode->oneArc.inVertexId; currentNode = currentNode->nextArc; } } } }
bool **completeAdjacencyMatrix(DirectedGraph *firstNode, int NUM_VERTEX) { DirectedGraph *currentNode = firstNode; int currentId, rowCounter, colCounter; bool **adjacencyMatrix = new bool* [NUM_VERTEX];
for(rowCounter = 0; rowCounter < NUM_VERTEX; rowCounter++) { adjacencyMatrix[rowCounter] = new bool [NUM_VERTEX]; for(colCounter = 0; colCounter < NUM_VERTEX; colCounter++) adjacencyMatrix[rowCounter][colCounter] = false; } currentNode = firstNode;
while(currentNode!= NULL) { if(currentNode->oneArc.inVertexId!= 0) adjacencyMatrix[currentNode->oneArc.outVertexId-1][currentNode->oneArc.inVertexId-1] = true;
currentNode = currentNode->nextArc; }
return adjacencyMatrix; }
void printMatrix(bool **matrix, int dimension, ostream *stream, string title = "") { int rowCounter, colCounter;
if(!title.empty()) *stream << title;
for(rowCounter = 0; rowCounter < dimension; rowCounter++) { *stream << endl << ' ' << matrix[rowCounter][0]; for(colCounter = 1; colCounter < dimension; colCounter++) { *stream << ' ' << matrix[rowCounter][colCounter]; } } }
void clearMatrix(bool **matrix, int dimention) { for(int counter = 0; counter < dimention; counter++) delete [] matrix[counter];
delete [] matrix; }
|
, N = 77):
