Спецификация переменных и функций




Переменные:

const char file[]="c:\\Goroda.txt" - имя файла на жестком диске, хранящим названия городов.from, to - начальная и конечная точки маршрута.w[N][N] - весовая матрица графа.g[N] - массив, хранящий список городов.*way - динамический массив для хранения маршрута.

Функции:

void Initial(string *Arr) - используется в программе для заполнения массива string g[] списком городов из файла file.

int *minimalLengthWay(int wm[N][N], int fromNode, int toNode, int *length, int *weight) - находит кратчайший путь в графе

 

Описание работы программы

 

После запуска программы на экран выводится список городов и расстояния между ними. Нужно будет ввести город отправления и город назначения.

После работы программы, на экране появится маршрут следования и длина пути.

 

Тестирование программы

 

Вывод список городов

 

 

Вывод расстояний между городами

 


 

Ввод данных

 

 

Вывод результата

 

 


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

. Шилдт Герберт «Си ++. Руководство для начинающих, 2-е издание», М.; Издательский дом «Вильямс», 2005 г.

. Кубенский А. А. «Структура и алгоритмы обработки данных: объектно-ориентированный подход и реализация на Си ++», Спб.; БХВ-Петербург, 2004 г.

. Седжвик Роберт «Фундаментальные алгоритмы на Си++», К.; Издательство «ДиаСофт», 2001 г.

4. Уильям Топп, Уильям Форд «Структуры данных в Си ++», М.; ЗАО «Издательство БИНОМ», 1999 г.


Приложение А

Схема алгоритма

 

 


Приложение Б

Листинг программы

#include <iostream.h>

#include <stdio.h>

#include <string>

#include <fstream.h>

#include <windows.h>

#define N 12char file[]="c:\\Goroda.txt";Initial(string *Arr) {fin;.open(file);(fin==NULL)

{<<"Error open file";("Pause");(1);

}n=0;>>Arr[n];(fin.good())

{++;>>Arr[n];

}.close();

}*minimalLengthWay(int wm[N][N], int fromNode, int toNode, int *length, int *weight){ **minWeights; // Для хранения фронта волны

int i, j, k;

int *way; // Для хранения найденного пути и уже однажды пройденных вершин

bool find;tempLength;currNode;= new int*[N];(i = 0; i < N; i++) {[i] = new int[N];

}= new int[N];(i = 0; i < N; i ++)(j = 0; j < N; j ++)[i][j] = -1;(i = 0; i < N; i ++)[i] = -1;(i = 0; i < N; i ++)[fromNode][i] = 0;= false;(k = 0; k < N - 1; k ++) {(i = 0; i < N; i ++) {= minWeights[i][k];(j = 0; j < N; j++) {(minWeights[j][k]!= -1 && wm[j][i]!= -1) {((tempLength!= -1 && tempLength > minWeights[j][k] + wm[j][i]) || tempLength == -1) {= minWeights[j][k] + wm[j][i];

}

}

}[i][k+1] = tempLength;

}

}= minWeights[toNode][N-1]!= -1; // проверяем найден ли какй-либо путь(find) *weight = minWeights[toNode][N-1]; (find) { // если путь найден - вычисляем его но в обратной последовательности

j = 0;[0] = toNode;= toNode;(k = N - 2; k >= 0; k--) {(minWeights[currNode][k]!= minWeights[currNode][k + 1]) {(i = 0; i < N; i ++) {(minWeights[i][k] + wm[i][currNode] == minWeights[currNode][k + 1]) {++;[j] = i;= i;;

}

}

}

}

*length = j;

}way;

}main() {(1251);(1251);i, j;from, to;f,t;*way;length, weight;g[N];(g); w[N][N]={0,250,-1,320,-1,-1,-1,-1,-1,-1,-1,-1,

,0,300,-1,-1,-1,-1,-1,-1,-1,-1,-1,

,300,0,-1,-1,-1,423,-1,-1,-1,-1,-1,

,-1,-1,0,640,412,830,-1,-1,-1,-1,-1,

,-1,-1,640,0,-1,-1,550,-1,-1,-1,-1,

,-1,-1,412,-1,0,-1,300,-1,-1,-1,-1,

,-1,423,830,-1,-1,0,520,540,580,-1,-1,

,-1,-1,-1,550,300,520,0,-1,430,280,-1,

,-1,-1,-1,-1,-1,540,-1,0,400,-1,-1,

,-1,-1,-1,-1,-1,580,430,400,0,-1,650,

,-1,-1,-1,-1,-1,-1,280,-1,-1,0,360,

,-1,-1,-1,-1,-1,-1,-1,-1,650,360,0 };

cout << "Список городов, обслуживаемых компанией:" << endl << endl;

for (int i = 0; i < N; i++) {<<g[i]<< endl;

}<< endl;(int i = 0; i < N; i++) {(j = 0; j < i; j++) {(w[i][j]>0) {<< g[i] << " - " << g[j] << " " << w[i][j] << " км " << endl;

}

}

}

cout << endl;

cout << "Введите исходный город: ";

cin >> from;

cout << "Введите пункт назначения: ";

cin >> to;(i = 0; i < N; i++) {(g[i]==from) f=i;(g[i]==to) t=i;

}= minimalLengthWay(w, f, t, &length, &weight); (way[0] == -1)

cout << "Невозможно приготовить маршрут!";

else {(i = length; i >= 0; i--){(i!= length) cout << " -> ";<< g[way[i]];

}<< "\nДлина пути: " << weight << endl << endl;

}("Pause");0.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2020-04-01 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: