close

Вход

Забыли?

вход по аккаунту

?

Krivorutchenko

код для вставкиСкачать
 Оглавление
Введение 3
1.Спецификация5
1.1.Постановка задачи5
1.2.Входные данные5
1.3.Входные формы6
1.4.Входной формат текстового файла6
1.5.Выходные данные7
1.6.Выходные формы7
1.7.Метод решения7
1.8.Аномалии8
1.9.Функциональные тесты8
2.Нисходящее проектирование10
2.1.Основной алгоритм11
3. Тестирование......................................................................17
4. Листинг..............................................................................23
Литература...............................................................................29
Введение
В курсовой работе необходимо с помощью нисходящего проектирования сделать целый, готовый проект. Он заключается в последовательном разбиении задачи на все более мелкие участки, т.е. процесс программирования идет "сверху вниз". Модульное программирование предполагает создание для каждого такого участка отдельной автономной программы - модуля. Специально созданная программа объединяет все модули в целое и управляет их работой.
Метод нисходящего проектирования, заключается в декомпозиции исходной задачи на более простые подзадачи. Затем подзадачи в свою очередь разбиваются на подзадачи, и т.д. Процесс такого разбиения можно вести более упорядоченно, если использовать основные управляющие конструкции: следование, развилку и цикл. При проектировании алгоритма подзадачи реализованы в виде подзадач-функций либо подзадач-блоков.
MFo представления оринтированного графа. В MFO-представлении графа вместо разделителей 0 используется дополнительный массив P длинной N, в котором указываются верхние границы окончания списков номеров вершин в массиве G, смежных с заданной вершиной по выходящим дугам.
Пример задания векторов G и P для графа изображённого ниже:
P = {1 3 4 5}; G = {0 2 3 4 4};
Рисунок 1 - Пример графа
Матрица расстояний представляет собой, двумерную матрицу, в которой на пересечении строк и столбцов записаны расстояния из i-й вершины в j-ю.
Для данного графа данная матрица будет иметь следующий вид:
12345100000210123300012400001500000Таблица 1 - Матрица расстояний
Число вершин, удаленных от заданной дуги, по кратчайшим маршрутам каждой из следующих длин: 1, 2, 3 и т.д., для каждой дуги представляет собой матрицу, в которой длина строки равна максимальному значению в матрице расстояний, а длина столбца числу вершин, для этого графа данная матрица будет иметь следующий вид:
1232-11112-32213-41104-5000Таблица 2 - Характеристика
1. Спецификация
Спецификация - документ, в котором описаны требования к проектированию программного продукта
1.1 Постановка задачи
Используя технологию нисходящего проектирования написать программу для сравнения на эквивалентность двух ориентированных графов с числом вершин n<20 и числом дуг m<50 по числу вершин, удаленных от заданной дуги, по кратчайшим маршрутам каждой из следующих длин: 1, 2, 3 и т.д., для каждой дуги. Ввод графа задаётся в модифицированном FO представлении в виде 2-х векторов (Вектор ограничителей и вектор списков выходных дуг). Предусмотреть ввод графа с файла и экрана.
1.2 Входные данные
Входные данные приведены в таблице 3, входные формы изображены на рисунке 2, входной формат текстового файла показан на рисунках 3 и 4:
Таблица 3
№НаименованиеТипДиапазонНазначение1n1Целый1<=n1<=20Кол-во вершин 1-го графа2m1Целый0<=m1<=50Кол-во дуг 1-го графа3G1iМассив целых чисел1<=G11<=n1
0<=i<=m1
Вектор ограничителей 1-го графа4P1iМассив целых чисел0<=P1i<=m1
1<=i<=n1
P1<=P1i+1Вектор списков дуг 1-го графа5n2Целый1<=n2<=20Кол-во вершин 2-го графа6m2Целый0<=m2<=50Кол-во дуг 2-го графа7G2iМассив целых чисел0<=G21<=n1
1<=i<=m1
Вектор ограничителей 2-го графа8P2iМассив целых чисел0<=P2i<=m2
1<=i<=n2
P2<=P2i+1Вектор списков дуг 2-го графа 1.3 Входные формы
Рисунок 2 - Окно программы
1.4 Входной формат текстового файла n1 m1
G1i.......................................G1m1
P1i.......................................P120
.......................................................
..........................P1n1
Рисунок 3 - Текстовый файл содержащий MFo представление 1-го графа n2 m2
G2i.......................................G2m2
P2i.......................................P220
.......................................................
..........................P2n2
Рисунок 4 - Текстовый файл содержащий MFo представление 2-го графа
1.5 Выходные данные
В зависимости от полученного результата сравнения графов пользователю будет выдано текстовое сообщение. Если графы эквивалентны, то результатом будет сообщение:
"Графы эквивалентны"
В противном случае результатом работы программы будет сообщение:
"Графы не эквивалентны"
1.6 Выходные формы
Рисунок 5 - Графы эквивалентны
Рисунок 6 - Графы не эквивалентны
1.7 Метод решения
В зависимости от значения переключателей на форме осуществляется ввод данных с клавиатуры или из текстового файла, с контролем корректности ввода данных. При вводе графов строятся матрицы смежности (MS1 и МS2). Для получения числа вершин, удаленных для каждой из следующих длин: 1, 2, 3 и т.д., для каждой дуги, необходимо в начале вычислить матрицу расстояний графа (MR). Затем по матрице расстояний построить характеристику, для каждой дуги. Ниже представлен алгоритм получения матрицы MR.
Пусть r вычисленные значения расстояний в матрице MR. Используем две вспомогательные матрицы В1 и В2.
п1. r=1, В1= MS , MR= MS
п2. В2=В1* MS, r=r+1; // умножение матриц
п3. если (MR[i,j]=0 и B2[i,j] <>0) то MR[I,j]= r п4. если в п3 матрица расстояний не изменялась ,то конец вычислений, иначе В1=В2 и повторить п2. Характеристика представляет собой матрицу, в которой строки - это дуги, количество строк равно количеству вершин, а столбцы - числу вершин, удаленных от заданной дуги, число столбцов равно максимальному значению в матрице расстояний. После получения данных матриц их необходимо сравнить и если они будут равны, то графы эквивалентны в противном случае нет.
1.8 Аномалии В нашей программе аномалии в основном связаны с контролем входных данных.
Все возможные аномалии представлены в таблице 4.
Таблица 4
№ п/пНаименованиеУсловие возникновенияРеакция1Некорректный ввод количества вершин 1-го графа (при вводе с файла)(n>20) или (n<=0)Вывод сообщения: "Ошибка ввода количества вершин графа!"2Некорректный ввод количества ребер 1-го графа (при вводе с файла)(m>50) или (m<0)Вывод сообщения: "Ошибка ввода количества ребер графа!"3Элемент массива G 1-го графа недопустим(G[i]>n) или (G[i] <=0)Вывод сообщения: "Элемент G графа недопустим!"4Количество элементов массива G 1-го графа неверноi!=mВывод сообщения: "Количество элементов G графа неверно!"5Элемент массива P 1-го графа недопустим(P[i] >m) или (P[i] <0)Вывод сообщения: "Элемент P графа недопустим!"6Количество элементов массива P 1-го графа неверноi!=nВывод сообщения: "Количество элементов P графа неверно!"7Недопустимые символыch !є {0,1,2,3,4,5,6,7,8,9, '_','новая строка'}Вывод сообщения: "Недопустимые символы!" 1.9 Функциональные тесты
Функциональные тесты приведены в таблице 5:
Таблица 5
Номер п/пНазначение тестаВходные данныеРеакция1Проверка аномалии 10 18
..........
Вывод сообщения: "Ошибка ввода количества вершин графа!"2Проверка аномалии 121 4
..........Вывод сообщения: "Ошибка ввода количества вершин графа!"3Проверка аномалии 25 51
..........Вывод сообщения: "Ошибка ввода количества ребер графа!"4Проверка аномалии 26 -10
..........Вывод сообщения: "Ошибка ввода количества ребер графа!"5Проверка аномалии 35 4
1 2 7 5
.................Вывод сообщения: "Элемент G графа недопустим!"6Проверка аномалии 45 4
1 2 1 5 4
.................Вывод сообщения: "Количество элементов G графа неверно!"7Проверка аномалии 55 4
1 2 3 5 0 1 2 4 5Вывод сообщения: "Элемент P графа недопустим!"8Проверка аномалии 65 4
1 2 3 5 0 1 2 4 4 4Вывод сообщения: "Количество элементов P графа неверно!"9Проверка аномалии 7q 0
..........
..........Вывод сообщения: "Входная строка имела неверный формат"10Нормальная работа5 4
1 3 4 5
0 2 3 4 45 4
1 2 3 5
0 1 2 4 4Вывод сообщения: "Графы эквивалентны"11Нормальная работа5 4
1 3 4 5
0 2 3 4 45 4
2 3 4 5
1 2 3 4 4Вывод сообщения: "Графы не эквивалентны" 2 Нисходящее проектирование
Технология проектирования алгоритмов
Существенным шагом на пути снижения трудоемкости процесса программирования стал структурный подход к проектированию алгоритмов. Его основными принципами являются нисходящее проектирование и модульное программирование. Нисходящее проектирование заключается в последовательном разбиении задачи на все более мелкие участки, т.е. процесс программирования идет "сверху вниз". Модульное программирование предполагает создание для каждого такого участка отдельной автономной программы - модуля. Специально созданная программа объединяет все модули в целое и управляет их работой.
Метод нисходящего проектирования, заключается в декомпозиции исходной задачи на более простые подзадачи. Затем подзадачи в свою очередь разбиваются на подзадачи, и т.д. Процесс такого разбиения можно вести более упорядоченно, если использовать основные управляющие конструкции: следование, развилку и цикл. При проектировании алгоритма подзадача может быть реализована в виде подзадачи-функции либо подзадачи-блока.
Подзадача описывается в процедурной форме, если она реализует некоторый типовой алгоритм, или же в данной задаче используется многократно.
Подзадача реализуется в виде блока, если она выделена с целью облегчения анализа и разработки алгоритма.
После разработки подзадачу-блок подставляют целиком (без внутренних спецификаций) в порождающую подзадачу. Сама же она в порождающей подзадаче остается в виде комментария. Описание промежуточных и исходных данных добавляется к соответствующим описаниям порождающей задачи.
Совокупность подзадач-функций и подзадач-блоков вместе с корневой задачей составляет рабочий проект программы. В дереве подчинения задачи-блоки будем обозначать в виде квадратов, а подзадачи-функции - в виде кружков.
После подстановки подзадач-блоков в порождающие их подзадачи получится следующий окончательный проект.
2.1 Основной алгоритм
Алгоритм сравнения графов на эквивалентность:
НАЧАЛО
Начало слежения за исключениями
ЕСЛИ CBfile1.Checked ТО
Выбор файла и создание потока(1.2)
Ввод первого графа с файла с полным контролем (1.3)
ИНАЧЕ
Ввод первого графа с экрана с полным контролем (1.1)
КЕСЛИ
ЕСЛИ CBfile2.Checked ТО
Выбор файла и создание потока
Ввод второго графа с файла с полным контролем ИНАЧЕ
Ввод второго графа с экрана с полным контролем КЕСЛИ
Построение матрицы смежности MS1. (1.4)
Построение матрицы смежности MS2. Построение матрицы расстояний MR1. (1.5)
Построение матрицы расстояний MR2. Поиск MaxMR1 максимального значения в MR1 Поиск MaxMR2 максимального значения в MR2
ЕСЛИ (MaxMR1=MaxMR2) ТО Создание характеристики первого графа MK1 (1.6)
Создание характеристики второго графа MK2
Сортировка первой характеристики MK1
Сортировка второй характеристики MK2
ЕСЛИ (Сравнение(MK1, MK2) (1.7) ) ТО Вывод ("Графы эквивалентны");
ИНАЧЕ Вывод ("Графы не эквивалентны");
КЕСЛИ
ИНАЧЕ
Вывод ("Графы не эквивалентны");
КЕСЛИ
Начало обработки исключений
Обработка исключений
Конец обработки исключений
Конец слежения за исключениями
Конец
Из текста алгоритма видно, что в нем имеется 7 подзадач (рисунок 7).
Рисунок 7 - Схема подзадач программы
(1.1)Алгоритм ввода графа с экрана:
Void FForm(ref n, ref m, ref G, ref P, nUD_n, nUD_m, tB_G, tB_P)
{
MessageBox.Show("Выполняется ввод с экрана");
}
(1.2)Алгоритм выбора файла и создания потока:
if (rB_s_faila_grahp1.Checked)
{
if (openFileDialog1.ShowDialog() == DialogResult.OK)
{
filename = openFileDialog1.FileName;
Potok = new StreamReader(filename);
}
else
{
MessageBox.Show("Файл не выбран!");
return;
}
(1.3)Алгоритм ввода графа с файла:
Void FFile(ref n, ref m, ref G, ref P, tB_G, tB_P, nUD_n, nUD_m1, OpenFile.FileName)
{
MessageBox.Show("Выполняется перенос графа с файла на экран");
}
(1.4)Алгоритм построения матрицы смежности:
public void MS(ref int n, ref int m, ref int[] G, ref int[] P, ref int[,] a)
{
int j = 0;
for (int i = 0; i < n; i++)
{while (j < P[i])
{a[i, G[j] - 1] = 1;j++}}
}
(1.5)Алгоритм построения матрицы расстояний:
public void MR(int n, ref int[,] MS, ref int[,] MR)
{
int[,] B1 = new int[n, n];
int[,] B2 = new int[n, n];
bool pr = true;
int w = 1;
MR = (int[,])MS.Clone();
B1 = (int[,])MS.Clone();
while (pr)
{
pr = false;
MM(n, B1, MS, ref B2);
w += 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (MR[i, j] == 0 && i != j && B2[i, j] != MR[i, j])
{
MR[i, j] = w;
pr = true;
}}
}
B1 = (int[,])B2.Clone();
}
}
(1.5.1)Умножение матриц
public void MM(int n, int[,] A, int[,] B, ref int[,] C)
{
int i, j, k, s;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
C[i, j] = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
s = 0;
for (k = 0; k < n; k++)
s += A[i, k] * B[k, j];
C[i, j] = s;
}
}
(1.5.2)Алгоритм поиска максимального значения в MR
public int MaxMR(int n,ref int[,] MR)
{
int max = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (MR[i, j] > max)
{max = MR[i, j];
}} }
return max;
}
(1.6)Алгоритм характеристики графа MK:
public void MKR(int m, int max, int n, ref int[,] MR, ref int[,] MK)
{int z = -1;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (MR[i, j] == 1)
{z = z + 1;
for (int x = 1; x <= max; x++)
{int k1 = kolvo(ref MR, x, i, n);int k2 = kolvo(ref MR, x, j, n);int k = 0;
if (x != 1)
k = k1 + k2;
else
k = k1 + k2 - 1;
int o = x - 1;
MK[z, o] = k;
}
}
}
(1.6.1)Подзадача нахождения количества вхождений заданного числа в строке:
public int kolvoref int[,] MR, int nujnint stroke, int n)
{
int kol = 0;
for (int j = 0; j < n; j++)
if (MR[stroka, j] == nujn)
kol++;
return kol;
}
(1.6.2)Подзадача сортировка характеристики графа MK:
public void Sortirovka(ref int[,] MK, int dlinastroki, int dlina_stolbca)
{
int[] arr;//временный массив
for (int j = 0; j < dlina_stolbca; j++)
{
arr = new int[dlinastroki];
//переносим столбец во временный массив
for (int i = 0; i < dlinastroki; i++)
{
arr[i] = MK[i, j];
}
Array.Sort(arr);//сортируем
//заменяем столбец на отсортированный
for (int f = 0; f < dlinastroki; f++)
{
MK[f, j] = arr[f];
}
}
}
(1.7)Алгоритм сравнения характеристик:
bool Sravn(ref int[,] Khar1, ref int[,] Khar2,int m1,int maxMR1)
{
for (int i = 0; i < maxMR1; i++)
{
for (int j = 0; j < m1; j++)
if (Khar1[i,j] != Khar2[i,j])
{
return false;
}
}
return true;
}
Окончательная схема проекта показана на рисунке 8.
Машинный листинг программы см. в приложении А.
Рисунок 8 - Окончательная схема проекта
3. Тестирование
Тестирование завершающий этап разработки программы. Тестирование выполняется на основе функциональных тестов. Ниже на рисунке приведены тестовые примеры.
Рисунок 9 - Первая тестовая проверка
Рисунок 10 - Вторая тестовая проверка
Рисунок 11 - Третья тестовая проверка
Рисунок 12 - Четвертая тестовая проверка
Рисунок 13 - Пятая тестовая проверка
Рисунок 14 - Шестая тестовая проверка
Рисунок 15 - Седьмая тестовая проверка
Рисунок 16 - Восьмая тестовая проверка
Рисунок 17 - Девятая тестовая проверка
Рисунок 18 - Десятая тестовая проверка
Рисунок 19 - Одиннадцатая тестовая проверка
4. Листинг программы
Приложение А
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.IO;
namespace Kursovoi
{
public partial class Form1 : Form
{
//**********************************************************************
//************************Аномалии**************************************
public string
Error1 = "Ошибка ввода количества вершин!",
Error2 = "Ошибка ввода количества ребер!",
Error3 = "Количество элементов вектора G неверно!",
Error4 = "Элемент вектора G недопустим!",
Error5 = "Количество элементов вектора P неверно!",
Error6 = "Элемент вектора P недопустим!",
Error7 = "Элементы вектора P расположены не в порядке возрастания!";
//**********************************************************************
//**************************Чтение с файла******************************
//*******************(1.3)Перепись графа с файла************************
public void FFile(ref int n, ref int m, ref int[] G, ref int[] P, TextBox G1, TextBox P1, NumericUpDown n1, NumericUpDown m1, string FileName)
{
string s;
StreamReader f = new StreamReader(FileName);
s = f.ReadLine();
s = s.TrimEnd();
string[] string1 = s.Split(new Char[] { ' ' });
n = int.Parse(string1[0]);
if (n < 1 || n > 20) throw new Exception(Error1);
n1.Value = n;
m = int.Parse(string1[1]);
if (m < 0 || m > 50) throw new Exception(Error2);
m1.Value = m;
Array.Resize(ref G, m);
Array.Resize(ref P, n);
string g = "";
string p = "";
s = f.ReadLine();
s = s.TrimEnd();
string[] string2 = s.Split(new Char[] { ' ' });
for (int i = 0; i < m; i++)
{
G[i] = int.Parse(string2[i]);
g += G[i].ToString() + "\r\n";
if (G[i] < 1 || G[i] > n) { throw new Exception(Error4); }
}
G1.Text = g;
if (string2.Length != m) { throw new Exception(Error3); }
else
s = f.ReadLine();
string[] string3 = s.Split(new Char[] { ' ' });
if (string3.Length != n) throw new Exception(Error5);
else
for (int i = 0; i < n; i++)
{
P[i] = int.Parse(string3[i]);
p += P[i].ToString() + "\r\n";
if (P[i] < 0 || P[i] > m) { throw new Exception(Error6); }
}
P1.Text = p;
for (int i = 1; i < n; i++)
{
if (P[i - 1] > P[i]) { throw new Exception(Error7); }
}
}
//**********************************************************************
//***************************Чтение с формы***************************** //*********************(1.2)Ввод данных с экрана************************
public void FForm(ref int n, ref int m, ref int[] G, ref int[] P, NumericUpDown n1, NumericUpDown m1, TextBox G1, TextBox P1)
{
n = (int)n1.Value;
m = (int)m1.Value;
n1.Value = n;
m1.Value = m;
string s1 = G1.Text;
if (n < 1 || n > 20) throw new Exception(Error1);
string s2 = P1.Text;
if (m < 0 || m > 50) throw new Exception(Error2);
s1 = s1.TrimEnd();
s2 = s2.TrimEnd();
string[] string1 = s1.Split(new Char[] { '\n' });
Array.Resize(ref G, m);
Array.Resize(ref P, n);
for (int i = 0; i < m; i++)
{
G[i] = int.Parse(string1[i]);
if (G[i] < 1 || G[i] > n) { throw new Exception(Error4); }
}
if (string1.Length != m) {throw new Exception(Error3); }
string[] string2 = s2.Split(new Char[] { '\n' });
for (int i = 0; i < n; i++)
{
P[i] = int.Parse(string2[i]);
if (P[i] < 0 || P[i] > m) { throw new Exception(Error6); }
}
if (string2.Length != n) { throw new Exception(Error5); }
for (int i = 1; i < n; i++)
{
if (P[i - 1] > P[i]) { throw new Exception(Error7); }
}
}
//**********************************************************************
//***********************Матрица смежности******************************
//*********Реализация задачи(1.4) Построение матрицсмежности************
public void MS(ref int n, ref int m, ref int[] G, ref int[] P, ref int[,] a)
{
int j = 0;
for (int i = 0; i < n; i++)
{
while (j < P[i])
{
a[i, G[j] - 1] = 1;
j++;
}
}
}
//**********************************************************************
//********************Функция умножения матриц**************************
//**********Реализация подзадачи (1.5.1). Умножение матриц**************
public void MM(int n, int[,] A, int[,] B, ref int[,] C)
{
int i, j, k, s;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
C[i, j] = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
s = 0;
for (k = 0; k < n; k++)
s += A[i, k] * B[k, j];
C[i, j] = s;
}
}
//**********************************************************************
//**********************Матрица расстояния******************************
//********Реализация задачи (1.5). Создание матрицы расстояний**********
public void MR(int n, ref int[,] MS, ref int[,] MR)
{
int[,] B1 = new int[n, n];
int[,] B2 = new int[n, n];
bool pr = true;
int w = 1;
MR = (int[,])MS.Clone();
B1 = (int[,])MS.Clone();
while (pr)
{
pr = false;
MM(n, B1, MS, ref B2);
w += 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (MR[i, j] == 0 && i != j && B2[i, j] != MR[i, j])
{
MR[i, j] = w;
pr = true;
}
}
}
B1 = (int[,])B2.Clone();
}
}
//***********************************************************
//*********Максимум в матрице расстояний расстояний**********
//Реализация подзадачи (1.5.2) Поиск максимального значения в МR
public int MaxMR(int n,ref int[,] MR)
{
int max = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (MR[i, j] > max)
{
max = MR[i, j];
}
}
}
return max;
}
//****************************************************************************
//****************Количество заданных расстояний в строке*********************
//Реализация подзадачи (1.6.1) Нахождение количества вхождений заданного числа public int kolvo(/*матрица расстояний*/ref int[,] MR, /*нужный элемент*/ int nujn,/*нужная строка*/ int stroka,/*длина этой строки*/ int n)
{
int kol = 0;
for (int j = 0; j < n; j++)
if (MR[stroka, j] == nujn)
kol++;
return kol;
}
//************************************************************************
//**Создание матриицы количество вершин удаленных от заданной дуги********
//***в матрице строки это дуги, а слобцы - расстояния*********************
//***********Реализация задачи (1.6) Создание характеристики**************
public void MKR(int m,/*длина строки полученной матрицы*/ int max, int n, /*пподсчет будет происходить в матрице расстояний*/ ref int[,] MR,/*получим єту матрицу кратчайших расстояний*/ ref int[,] MK)
{
int z = -1;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (MR[i, j] == 1)
{
z = z + 1;
for (int x = 1; x <= max; x++)
{
int k1 = kolvo(ref MR, x, i, n);
int k2 = kolvo(ref MR, x, j, n);
int k = 0;
if (x != 1)
k = k1 + k2;
else
k = k1 + k2 - 1;
int o = x - 1;
MK[z, o] = k;
}
}
}
//**********************************************************************
//*****************Сортировка столбцов по возрастанию*******************
//********Реализация подзадачи (1.6.2) Сортировка характеристики********
public void Sortirovka(ref int[,] MK, int dlinastroki, int dlina_stolbca)
{
int[] arr;//временный массив
for (int j = 0; j < dlina_stolbca; j++)
{
arr = new int[dlinastroki];
//переносим столбец во временный массив
for (int i = 0; i < dlinastroki; i++)
{
arr[i] = MK[i, j];
}
Array.Sort(arr);//сортируем
//заменяем столбец на отсортированный
for (int f = 0; f < dlinastroki; f++)
{
MK[f, j] = arr[f];
}
}
}
//**********************************************************************
//**********************Сравнение характеристик*************************
//************будем сравнивать количество вершин от заданной дуги*******
//******Реализация задачи (1.7) Сравнение характеристик*****************
bool Sravn(ref int[,] Khar1, ref int[,] Khar2,int m1,int maxMR1)
{
for (int i = 0; i < maxMR1; i++)
{
for (int j = 0; j < m1; j++)
if (Khar1[i,j] != Khar2[i,j])
{
return false;
}
}
return true;
}
//**************************************************************************
//****************************Работа программы******************************
//**************************************************************************
public Form1()
{
InitializeComponent();
}
//**************************************************************************
//нажатие на кнопку выход
private void btn_exit_Click(object sender, EventArgs e)
{
Application.Exit();
}
//**************************************************************************
//нажатие на кнопку расчитать
private void btn_Calc_Click(object sender, EventArgs e)
{
//**************описание переменных***********
OpenFileDialog OpenFile = new OpenFileDialog();
int n1 = 0, m1 = 0, n2 = 0, m2 = 0;
int[] G1 = new int[0];
int[] G2 = new int[0];
int[] P1 = new int[0];
int[] P2 = new int[0];
//начало проверок на ошибки
try
{ //Ввод первого графа
//Если активен переключатель ввода с файла
if (rB_s_faila_grahp1.Checked)
{
OpenFile.ShowDialog();
//если выбран файл
if (OpenFile.FileName != "")
{
//ввод данных с файла
FFile(ref n1, ref m1, ref G1, ref P1, tB_G1, tB_P1, nUD_n1, nUD_m1, OpenFile.FileName);
}
else
{
MessageBox.Show("Не выбран файл!");
return;
}
}
//Если активен переключатель ввода с экрана
if (rB_s_ekrana_grahp1.Checked)
{
//ввод данных с формы
FForm(ref n1, ref m1, ref G1, ref P1, nUD_n1, nUD_m1, tB_G1, tB_P1);
}
//*****************************************************
//Ввод второго графа
//Если активен переключатель ввода с файла
if (rB_s_faila_grahp2.Checked)
{
OpenFile.ShowDialog();
//если выбран файл
if (OpenFile.FileName != "")
{
//ввод данных с файла
FFile(ref n2, ref m2, ref G2, ref P2, tB_G2, tB_P2, nUD_n2, nUD_m2, OpenFile.FileName);
}
else
{
MessageBox.Show("Не выбран файл!");
return;
}
}
//Если активен переключатель ввода с экрана
if (rB_s_ekrana_grahp2.Checked)
{
//ввод данных с формы
FForm(ref n2, ref m2, ref G2, ref P2, nUD_n2, nUD_m2, tB_G2, tB_P2);
}
//Инициализация матриц смежности
int[,] MS1 = new int[n1, n1];
int[,] MS2 = new int[n2, n2];
//строим матрицу смежности МS1
MS(ref n1, ref m1, ref G1, ref P1, ref MS1);
MS(ref n2, ref m2, ref G2, ref P2, ref MS2);
//Инициализация матриц расстояний
int[,] MR1 = new int[n1, n1];
int[,] MR2 = new int[n2, n2];
//строим матрицу расстояний МR1
MR(n1, ref MS1, ref MR1);
MR(n2, ref MS2, ref MR2);
//Инициализация матриц кратчайших расстояний расстояний
// int maxMR1 = 0, maxMR2 = 0;
int maxMR1 = MaxMR(n1, ref MR1);
int maxMR2 = MaxMR(n2, ref MR2);
if (maxMR1 == maxMR2)
{
int[,] MK1 = new int[m1, maxMR1];
int[,] MK2 = new int[m2, maxMR2];
// строим матрицу кратчайших расстояний МK1
MKR(m1, maxMR1, n1, ref MR1, ref MK1);
//строим матрицу кратчайших расстояний МK2
MKR(m2, maxMR2, n2, ref MR2, ref MK2);
//отсортируем по столбцам матриці кратчайших расстояний
Sortirovka(ref MK1, m1, maxMR1);
Sortirovka(ref MK2, m2, maxMR2);
// Array.Sort(MK1[]);
if (Sravn(ref MK1, ref MK2, maxMR1, m1))
MessageBox.Show("Графы эквивалентны","Результат работы программы");
else
MessageBox.Show("Графы не эквивалентны","Результат работы программы");
}
else
MessageBox.Show("Графы не эквивалентны", "Результат работы программы"); }
catch (Exception end)
{
MessageBox.Show(end.Message);
MessageBox.Show("Завершение считывания ошибок");
}
}
private void tB_G1_KeyPress(object sender, KeyPressEventArgs e)
{
char l = e.KeyChar;
if ((l < '0' || l > '9') && l != '\b' && l != '\r')
{
e.Handled = true;
}
}}}
Список литературы
Методические рекомендации по выполнению курсовых работ по конструированию программ [Текст] /. Сост: Н. Г. Мокляк, В. И. Моско-вец, А. Ю. Соколов. - X. : Нац. аэрокосм, ун-т им. Н. Е. Жуковского "Харьк. авиац. ин-т", 1993. - 23 с.
Кормен, Т. Алгоритмы: построение и анализ [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Риверст. - М.: МЦНМО, 2000. - 960 с.
Оре, О. Теория графов [Текст] / О. Оре. - М.: Наука, 1980. -336 с.
Иванов, Б. Дискретная математика. Алгоритмы и программы [Текст] / Б. Н. Иванов. - М.: Лаборатория Базовых Знаний, 2003. -288 с.
Ахо, А. Структуры данных и алгоритмы [Текст] / А. Ахо, Д. Хоп-крофт, Д. Ульман. - М.: Издательский дом "Вильяме", 2003. - 384 с.
2
Документ
Категория
Рефераты
Просмотров
112
Размер файла
2 102 Кб
Теги
krivorutchenko
1/--страниц
Пожаловаться на содержимое документа