Министерство образования Российской Федерации
Государственное образовательное учреждение высшего профессионального образования «Комсомольский - на - Амуре Государственный Технический Университет»
Кафедра МОП ЭВМ
Лабораторная работа №4
по дисциплине:
Структуры и алгоритмы обработки данных
Вариант 6
Группа: 4ВТ-1
Выполнил: ПритыченкоС.В.
Проверил: Изабеков З.А.
2007 г.
Задание.
Найти покрывающее дерево или остовной лес минимального веса с помощью алгоритма Солина. Вершины графа – города. Веса ребер равны ценам билетов.
Текст программы
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
#include <math.h>
#include <memory.h>
//--------------------------------------------------------------------------#pragma package(smart_init)
#pragma resource "*.dfm"
int xMax, yMax, id = 0;
TForm1 *Form1;
//--------------------------------------------------------------------------__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//--------------------------------------------------------------------------int i, j;
int N = 0, r = 15, **ways, v1, v2, **arr, *cx, *cy, count;
struct LPoint
{
int x, y;
LPoint *next;
};
struct Vert
{
int n;
Vert *next;
};
LPoint *list = NULL;
Vert **vertex;
void link(int d, int k)
{
int i;
for (i = 0; i < N; ++i)
{
if (i == d)
{
arr[k][i] = arr[i][k] = 0;
continue;
}
if (arr[k][i])
{
arr[i][k] = arr[k][i] = 0;
Vert *p = vertex[d];
while (p->next) p = p->next;
p->next = vertex[i];
vertex[i] = NULL;
link(d, i);
}
}
}
void solin()
{
int sum = 0; // пееременная для хранения суммы цен билетов
int min, nv1, nv2, m, end = 1;
Vert *v1, *v2; // переменные для указания вершин, рассматриваемых в данный момент
// count = N - 1;
while (end)
{
end = 0;
for (i = 0; i < N; ++i)
{
m = -1;
v1 = vertex[i];
min = 1000000000;
if (!v1) continue;
while (v1)
{
for (j = 0; j < N; ++j)
{
if (i == j) continue;
v2 = vertex[j];
while (v2)
{
if (ways[v1->n][v2->n] && ways[v1->n][v2->n] < min) //если есть путь меж. 2 - мя вершинами и он меньше чем мин.
{
m = j; nv1 = v1->n; nv2 = v2->n; //запоминаем номер второй группы и вершины которые соединяются
min = ways[nv1][nv2];
}
v2 = v2->next;
}
}
v1 = v1->next;
}
if (!arr[i][m] && m != -1) // Если есть еще отдельные группы и они ещё не связаны
{
Form1->Image1->Canvas->MoveTo(cx[nv1], cy[nv1]);
Form1->Image1->Canvas->LineTo(cx[nv2], cy[nv2]);
arr[i][m] = arr[m][i] = 1;
sum += ways[nv1][nv2];
end = 1;
}
}
for (i = 0; i < N; ++i)
if (vertex[i])
{
link(i, i);
}
}
AnsiString str = sum;
MessageBoxA(NULL, str.c_str(), "Минимальное дерево", 0);
}
void __fastcall TForm1::inputClick(TObject *Sender) // Нажатие кнопки ввод вершин
{
Form1->List->Clear();
Image1->Canvas->Brush->Color = RGB(255, 255, 255);
Image1->Canvas->Brush->Style = bsSolid;
Image1->Canvas->Pen->Color = RGB(0, 0, 0);
Image1->Canvas->Pen->Width = 1;
Image1->Canvas->Pen->Mode = pmCopy;
Form1->Image1->Canvas->Rectangle(-2, -2, Image1->ClientWidth + 2, Image1->ClientHeight + 2);
N = 0;
LPoint *p;
while (list)
{
p = list;
list = list->next;
delete p;
}
Form1->Image1->Canvas->Brush->Color = RGB(0, 200, 0);
id = 1;
}
//--------------------------------------------------------------------------void __fastcall TForm1::Image1MouseDown(TObject *Sender, // Нажатие клавиши мыши
TMouseButton Button, TShiftState Shift, int X, int Y)
{
if( id == 1)
{
LPoint *p = new LPoint;
p->next = list; p->x = X; p->y = Y;
list = p;
Image1->Canvas->Ellipse(X - r, Y - r, X + r, Y + r);
Image1->Canvas->TextOutA(X - r / 4, Y - r / 3, N);
++N;
}
if (id == 2)
{
LPoint *p = list;
i = N - 1;
while (p)
{
if (pow(p->x - X, 2) + pow(p->y - Y, 2) <= pow(r, 2)) break;
--i;
p = p->next;
}
if (i >= 0) // Если было нажатие мышкой на городе
{
if (v1 == -1)
{
v1 = i;
Image1->Canvas->Pen->Mode = pmNot; // Инверсия окружности
Image1->Canvas->Ellipse(p->x - r - 1, p->y - r - 1, p->x + r + 1, p->y + r + 1);
}
else
{
LPoint *q = list;
for (j = N - 1; j > v1; --j) q = q->next; // Ищем первую выделенную вершину
ways[i][v1] = ways[v1][i] = StrToInt(InputBox("Цена","Введите цену билета","1")); // Запоминаем цены билетов
AnsiString str = v1; str.Insert(" - ", str.Length() + 1);str.Insert(i, str.Length() + 1);
str.Insert(" = ", str.Length() + 1); str.Insert(ways[i][v1], str.Length() + 1);
Form1->List->AddItem(str, 0); // Вывод информации о ценах в список
Image1->Canvas->Ellipse(q->x - r - 1, q->y - r - 1, q->x + r + 1, q->y + r + 1);
Image1->Canvas->Pen->Mode = pmCopy;
Image1->Canvas->MoveTo(q->x, q->y); // Рисуем ребро
Image1->Canvas->LineTo(p->x, p->y);
v1 = -1;
}
}
}
}
//--------------------------------------------------------------------------//--------------------------------------------------------------------------void __fastcall TForm1::vertClick(TObject *Sender) // Задать цены
{
if (id == 1)
{
Image1->Canvas->Pen->Color = RGB(0, 0, 200);
Image1->Canvas->Pen->Width = 2;
Image1->Canvas->Brush->Style = bsClear;
ways = new int *[N];
for (i = 0; i < N; ++i)
{
ways[i] = new int [N];
memset(ways[i], 0, N * sizeof(int));
}
v1 = -1, v2 = -1;
id = 2;
}
}
//--------------------------------------------------------------------------//--------------------------------------------------------------------------void __fastcall TForm1::searchClick(TObject *Sender)
{
if (id == 2)
{
vertex = new Vert *[N]; //массив указателей на списки вершин
cx = new int [N];
cy = new int [N];
LPoint *p = list;
for (i = N - 1; i >= 0; --i) //запоминаем коор. каждой вершины
{
cx[i] = p->x; cy[i] = p->y;
p = p->next;
}
for (i = 0; i < N; ++i)
{
vertex[i] = new Vert;
vertex[i]->n = i; // Заполняем массив вершин
vertex[i]->next = NULL;
}
arr = new int * [N]; // Массив для хранения кратчайших путей между вершинами
for (i = 0; i < N; ++i)
{
arr[i] = new int [N];
memset(arr[i], 0, N * sizeof(int));
}
Form1->Image1->Canvas->Pen->Color = RGB(200, 0, 0);
solin();
Form1->Image1->Canvas->Pen->Color = RGB(0, 0, 200);
}
}
Экранные формы:
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
