Рисунок 4. Рабочее меню программы
Рисунок 5. Пользователь рисует на image вершины и рёбра
Рисунок 6. Вводим данные в таблицу смежности
Рисунок 7. Выполнение задания
3.3 Описание модулей программы
Unit1 – модуль главного окна программы, его код приведен в приложении
Блок-схема основного алгоритма программы
|
 |
Приложение
Код модуля Unit1
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
#include <vector>
#include <math.h>
using namespace std;
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
int col = 0;
struct point {
int x, y;
int number;
};
struct rib{
int x1, x2;
bool k;
};
bool fr = false;
int xr, yr, ir;
vector<point> points;
vector<rib> ribs;
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
//Функция для рисования линии со стрелкой
void DrawLine(TCanvas* Canvas, double x0, double y0, double x1, double y1, double ArrowAngle, int ArrowLen){
ArrowAngle = ArrowAngle*M_PI/180;
//Длина основной линии
int Len = sqrt((x0-x1)*(x0-x1) + (y0-y1)*(y0-y1));
//Угол наклона основной линии
double Angle;
if(x0==x1 && y0<y1){
Angle = M_PI/2;
}
else if(x0==x1 && y0>y1){
Angle = 3*M_PI/2;
}
else if(x0>x1 && y0==y1){
Angle = 0;
}
else if(x0<x1 && y0==y1){
Angle = M_PI;
}
else if(x0>x1 && y0<y1){
Angle = asin((y1-y0)/Len);
}
else if(x0<x1 && y0<y1){
Angle = M_PI - asin((y1-y0)/Len);
}
else if(x0<x1 && y0>y1){
Angle = M_PI-asin((y1-y0)/Len);
}
else if(x0>x1 && y0>y1){
Angle = 2*M_PI+asin((y1-y0)/Len);
}
int x2 = x1 + ArrowLen * cos(Angle+ArrowAngle); // конец первого лепестка по X
int y2 = y1 - ArrowLen * sin(Angle+ArrowAngle); // конец первого лепестка по Y
int x3 = x1 + ArrowLen * cos(Angle-ArrowAngle); // конец второго лепестка по X
int y3 = y1 - ArrowLen * sin(Angle-ArrowAngle); // конец конец второго лепестка по Y
// рисуем саму линию
Canvas->MoveTo(x0,y0);
Canvas->LineTo(x1,y1);
//Рисуем лепестки
TPoint points[3];
points[0] = Point(x1,y1);
points[1] = Point(x2,y2);
points[2] = Point(x3,y3);
Canvas->Polygon(points, 2);
}
int res = 0;
void __fastcall TForm1::Image1MouseDown(TObject *Sender,
TMouseButton Button, TShiftState Shift, int X, int Y)
{
if (res==0){
this->Image1->Canvas->Pen->Color=RGB(2, 0, 0);
point el;
el.x = X;
el.y = Y;
el.number = col;
points.push_back(el);
this->Image1->Canvas->Ellipse(X-10, Y-10, X+10, Y+10);
this->Image1->Canvas->TextOutA(X+10, Y, IntToStr(col));
this->Image1->Canvas->MoveTo(X, Y);
this->StringGrid1->RowCount = col+2;
this->StringGrid1->ColCount = col+2;
this->StringGrid1->Cells[col+1][0] = IntToStr(col);
this->StringGrid1->Cells[0][col+1] = IntToStr(col);
for (int i=1; i<this->StringGrid1->ColCount; i++){
this->StringGrid1->Cells[i][col+1] = "0";
this->StringGrid1->Cells[col+1][i] = "0";
}
col++;
}
if (res==1){//если не используем матрицу смежности
this->Image1->Canvas->Pen->Color=RGB(208, 20, 201);
bool f = false;
for (int i=0; i<col; i++){
int x= point(points[i]).x;
if ((point(points[i]).x>(X-10))&&(point(points[i]).x<(X+10))&&(point(points[i]).y>(Y-10))&&(point(points[i]).y<(Y+10))) {
if (!fr) {f=true; ir =i; fr=true;this->Image1->Canvas->MoveTo(point(points[i]).x, point(points[i]).y);}
else {
DrawLine(this->Image1->Canvas,point(points[ir]).x, point(points[ir]).y,point(points[i]).x, point(points[i]).y, 10,20);
this->StringGrid1->Cells[i+1][ir+1] = "1";
fr=false;
}
}
}
fr=f;
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::BitBtn1Click(TObject *Sender)
{
res=0;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::BitBtn2Click(TObject *Sender)
{
res=1;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::BitBtn3Click(TObject *Sender)
{
points.clear();
ribs.clear();
col=0;
Image1->Canvas->FillRect(Image1->Canvas->ClipRect);
this->StringGrid1->ColCount = 1;
this->StringGrid1->RowCount = 1;
this->Memo1->Lines->Clear();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::StringGrid1EndDock(TObject *Sender,
TObject *Target, int X, int Y)
{
int k=0;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::StringGrid1SetEditText(TObject *Sender, int ACol,
int ARow, const AnsiString Value)
{
if (!StringGrid1->EditorMode){
this->Image1->Canvas->Pen->Color=RGB(208, 20, 201);
DrawLine(this->Image1->Canvas,point(points[ARow-1]).x, point(points[ARow-1]).y,point(points[ACol-1]).x, point(points[ACol-1]).y, 10,20);
}
}
struct el{
int v;
};
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{
int n =this->StringGrid1->ColCount-1; // Количество вершин в графе
float **a;// Матрица смежности графа
a=new float *[n];
for (int i=0; i<n; i++)
a[i]=new float [n];
//инициализация
for (int i=1; i<this->StringGrid1->ColCount; i++){
for (int j=1; j<this->StringGrid1->ColCount; j++){
a[i-1][j-1] = StrToFloat(this->StringGrid1->Cells[j][i]);
}
}
int infinity=10000; // Бесконечность
el * put;
put= new el [n];
int sumDl =10000;
int punkt=-1;
for (int versh=0; versh<n; versh++){
int sumB = 0;
for (int kversh=0; kversh<n; kversh++){
if (kversh!=versh){
int s=versh;// Номер исходной вершины
int g=kversh; // Номер конечной вершины
int * x; //Массив, содержащий единицы и нули для каждой вершины,
// x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
// x[i]=1 - кратчайший путь в i-ю вершину уже найден
x = new int [n];
int *t; //t[i] - длина кратчайшего пути от вершины s в i
t = new int [n];
el * h; //h[i] - вершина, предшествующая i-й вершине
// на кратчайшем пути
h = new el [n];
//int * tr; //транспорт. 1-жд, 0-шоссе
//tr = new int [n];
// Инициализируем начальные значения массивов
int u; // Счетчик вершин
for (u=0;u<n;u++)
{
t[u]=infinity; //Сначала все кратчайшие пути из s в i
//равны бесконечности
x[u]=0; // и нет кратчайшего пути ни для одной вершины
}
int v;
h[s].v=0; // s - начало пути, поэтому этой вершине ничего не предшествует
t[s]=0; // Кратчайший путь из s в s равен 0
x[s]=1; // Для вершины s найден кратчайший путь
v=s; // Делаем s текущей вершиной
while(1)
{
// Перебираем все вершины, смежные v, и ищем для них кратчайший путь
for(u=0;u<n;u++)
{
if(a[v][u]==0) continue; // Вершины u и v несмежные
if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не
//найден кратчайший путь
// и новый путь в u короче чем
//старый, то
{
t[u]=t[v]+a[v][u]; //запоминаем более короткую длину пути в
//массив t и
h[u].v=v; //запоминаем, что v->u часть кратчайшего
//пути из s->u
}
}
// Ищем из всех длин некратчайших путей самый короткий
int w=infinity; // Для поиска самого короткого пути
v=-1; // В конце поиска v - вершина, в которую будет
// найден новый кратчайший путь. Она станет
// текущей вершиной
for(u=0;u<n;u++) // Перебираем все вершины.
{
if(x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший
// путь и если длина пути в вершину u меньше
// уже найденной, то
{
v=u; // текущей вершиной становится u-я вершина
w=t[u];
}
}
if(v==-1)
{
sumB+=infinity;
//Memo1->Lines->Add("Нет пути из вершины ");
break;
}
if(v==g && t[g]<100) // Найден кратчайший путь,
{ // выводим его
sumB+= t[g];
break;
}
x[v]=1;
}
}
}
if (sumDl>sumB) {
punkt = versh;
sumDl = sumB;
}
}
if (punkt!=-1){
Memo1->Lines->Add("Это пункт "+IntToStr(punkt));
Memo1->Lines->Add("-----Выводим маршруты------");
//теперь высчитывем маршруты до каждого пункта и выводим их
for (int versh=0; versh<n; versh++){
if (punkt!=versh){
int s=punkt;// Номер исходной вершины
int g=versh; // Номер конечной вершины
int * x; //Массив, содержащий единицы и нули для каждой вершины,
// x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
// x[i]=1 - кратчайший путь в i-ю вершину уже найден
x = new int [n];
int *t; //t[i] - длина кратчайшего пути от вершины s в i
t = new int [n];
el * h; //h[i] - вершина, предшествующая i-й вершине
// на кратчайшем пути
h = new el [n];
// Инициализируем начальные значения массивов
int u; // Счетчик вершин
for (u=0;u<n;u++)
{
t[u]=infinity; //Сначала все кратчайшие пути из s в i
//равны бесконечности
x[u]=0; // и нет кратчайшего пути ни для одной вершины
}
int v;
h[s].v=0; // s - начало пути, поэтому этой вершине ничего не предшествует
t[s]=0; // Кратчайший путь из s в s равен 0
x[s]=1; // Для вершины s найден кратчайший путь
v=s; // Делаем s текущей вершиной
while(1)
{
// Перебираем все вершины, смежные v, и ищем для них кратчайший путь
for(u=0;u<n;u++)
{
if(a[v][u]==0)continue; // Вершины u и v несмежные
if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не
//найден кратчайший путь
// и новый путь в u короче чем
//старый, то
{
t[u]=t[v]+a[v][u]; //запоминаем более короткую длину пути в
//массив t и
h[u].v=v; //запоминаем, что v->u часть кратчайшего
//пути из s->u
}
}
// Ищем из всех длин некратчайших путей самый короткий
int w=infinity; // Для поиска самого короткого пути
v=-1; // В конце поиска v - вершина, в которую будет
// найден новый кратчайший путь. Она станет
// текущей вершиной
for(u=0;u<n;u++) // Перебираем все вершины.
{
if(x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший
// путь и если длина пути в вершину u меньше
// уже найденной, то
{
v=u; // текущей вершиной становится u-я вершина
w=t[u];
}
}
if(v==-1)
{
Memo1->Lines->Add("Нет пути из вершины ");
break;
}
if(v==g) // Найден кратчайший путь,
{ // выводим его
Memo1->Lines->Add("Путь с минимальной величиной из вершины "+IntToStr(s)+" в вершину "+IntToStr(g)+"(в обратном порядке)");
u=g;
this->Image1->Canvas->Pen->Color=RGB(0, 0, 255);
int k=0;
while(u!=s)
{
k++;
this->Memo1->Lines->Add(IntToStr(u));
this->Image1->Canvas->Pen->Color=RGB(208, 158, 20);
DrawLine(this->Image1->Canvas,point(points[h[u].v]).x, point(points[h[u].v]).y,point(points[u]).x, point(points[u]).y, 10,20);
u=h[u].v;
}
this->Memo1->Lines->Add(IntToStr(u));
this->Memo1->Lines->Add("Длина пути = "+IntToStr(t[g]));
break;
}
x[v]=1;
}
}
}
}
else
{
Memo1->Lines->Add("Нет такого пункта. Возможно не все пункты соединены");
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
Image1->Canvas->FillRect(Image1->Canvas->ClipRect);
this->Image1->Canvas->Pen->Color=RGB(2, 0, 0);
for (int i=0;i<col; i++){
int X = point(points[i]).x;
int Y = point(points[i]).y;
this->Image1->Canvas->Ellipse(X-10, Y-10, X+10, Y+10);
this->Image1->Canvas->TextOutA(X+10, Y, IntToStr(i));
this->Image1->Canvas->MoveTo(X, Y);
}
this->Image1->Canvas->Pen->Color=RGB(208, 20, 201);
for (int i=1; i<this->StringGrid1->ColCount; i++){
for (int j=1; j<this->StringGrid1->ColCount; j++){
if (this->StringGrid1->Cells[j][i]!="0")
DrawLine(this->Image1->Canvas,point(points[i-1]).x, point(points[i-1]).y,point(points[j-1]).x, point(points[j-1]).y, 10,20);
}
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button3Click(TObject *Sender)
{
res=1;
}
//---------------------------------------------------------------------------
Заключение
В ходе данного курсового проекта была проанализирована поставленная задача, создана и протестирована программа определения достижимости населенного пункта в системе односторонних дорог. Тестирование программы показало, что она находит кратчайший путь верно, при отсутствие пути выводит ошибку.
Можем констатировать, что курсовой проект сделан верно.
Список используемой литературы
1. Программирование в С++ Builder 6 / А.Я. Архангельский, 2006 г. с. 1304.
2. Программирование. Принципы и практика использования C++ / Бьерн Издательство Вильямс, 2013 г. с. 1248
3. C++ для начинающих. Серия «Шаг за шагом» Г. Шилдт, 2010 г.с. 640 с
