2020-07-12
110
{
gr1 = new NeorGraf();
gr2 = new NeorGraf();
}
public void Sravnenie(bool fileEkran,OpenFileDialog
openFileDialog,NumericUpDown nUDn1,
NumericUpDown nUDm1,TextBox tBFO1,
NumericUpDown nUDn2,NumericUpDown nUDm2,
TextBox tBFO2)
{
//тело метода
}
}
Приступим к проектированию метода Sravnenie.
Для обработки ошибок будем использовать исключение.
public class MyExcept: ApplicationException
{
public MyExcept(string msg): base(msg) { }
}
public void Sravnenie(bool fileEkran,OpenFileDialog
openFileDialog,NumericUpDown nUDn1, NumericUpDown nUDm1,TextBox tBFO1,NumericUpDown nUDn2,NumericUpDown nUDm2,TextBox tBFO2)
НАЧАЛО
try//контроль переписи с файла и ввода с экрана
{
ЕСЛИ(fileEkran)ТО //данные на файле
ЕСЛИ(неподключение к файлу и создание потока)ТО
//в условии подзадача(1.1)
Вывод("Файл не выбран! Повторите ввод");
Выход
КЕСЛИ
try//контроль переписи с файла
{
перепись 1-го графа с частичным контролем
из файла на экран; (1.2)
перепись 2-го графа с частичным контролем
из файла на экран;
}
// обработка исключений при переписи с файла
catch (MyExcept e)
{
//здесь исключение вновь создается с
уточнением места ошибки
throw new MyExcept(e.Message + " с файла");
}
КЕСЛИ
try//контроль ввода с экрана
{
Ввод с экрана 1-го графа с полным контролем и
построением матрицы смежности MS1 (1.3)
Ввод с экрана 2-го графа с полным контролем и
построением матрицы смежности MS2
}
// обработка исключений при вводе с экрана
catch (MyExcept e)
{
//здесь исключение вновь создается с уточнением
места ошибки
throw new MyExcept(e.Message + " с экрана");
}
}
//обработка всех исключений
catch (MyExcept e)
{
Вывод(e.Message);
Выход;
}
Расчет диаметра графа 1(1.4)
Расчет диаметра графа 2
ЕСЛИ (характеристики равны(1.5)) ТО
Вывод("Графы эквивалентны");
ИНАЧЕ
Вывод("Графы не эквивалентны");
КЕСЛИ
КОНЕЦ
Из текста алгоритма видно, что в нем имеется 5 подзадач (1.1) –(1.5).
Дальнейшее проектирование можно выполнять двумя способами, которые были описаны ранее. Продолжаем проектирование вторым способом. Первые две подзадачи (метода) включим в класс Kurs_Proekt, а остальные - в класс NeorGraf, так как они свяаны с созданием и обработкой графов.
Реализация заглушки метода (1.1) – это подключение к файлу и создание потока.
public bool ConectFile(OpenFileDialog openFileDialog1)
{
MessageBox.Show("Подключение к файлу и создание
потока");
//return true;
return false;
}
Оставляя один из операторов return, можно создать ситуацию ошибки подключения к файлу.
Реализация заглушки метода (1.2) - перепись графа с частичным контролем из файла на экран.
public void Move_Gr_fileToEcran(NumericUpDown nUDn, NumericUpDown nUDm,TextBox tBFO
{
MessageBox.Show("Выполняется перенос графа с файла на экран");
throw new MyExcept("В данных на файле ошибка");
}
Комментируя или оставляя оператор throw, можно создать ситуацию ошибки при переписи с файла.
Реализация заглушки метода (1.3) - ввод с экрана графа с полным контролем и построением матрицы смежности MS1.
public void Input_GrInEkran(NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBFO)
{
MessageBox.Show ("Выполняется ввод графа с экрана и построение
матрицы смежности");
throw new MyExcept ("В данных на форме ошибка");
}
Аналогично комментируя или оставляя оператор throw, можно создать ситуацию ошибки при вводе с экрана.
Реализация заглушки метода (1.4) - расчет диаметра графа.
public void Diametr()
{
MessageBox.Show("Расчет диаметра графа");
diametr = 2;
}
Реализация метода (1.5) -характеристики равны.
public bool Equals(NorGraf obj)
{
if (this.diametr == obj.diametr)
return true;
else
return false;
}
Подставим реализованные заглушки в метод Sravnenie.
public void Sravnenie(bool fileEkran,OpenFileDialog
openFileDialog,NumericUpDown nUDn1, NumericUpDown nUDm1,TextBox tBFO1,NumericUpDown nUDn2,NumericUpDown nUDm2,TextBox tBFO2)
НАЧАЛО
try//контроль переписи с файла и ввода с экрана
{
ЕСЛИ(fileEkran)ТО //данные на файле
ЕСЛИ(!ConectFile(openFileDialog1)/*
неподключение к файлу и создание потока*/)ТО
Вывод("Файл не выбран! Повторите ввод");
Выход
КЕСЛИ
try//контроль переписи с файла
{
//перепись 1-го графа с частичным контролем
из файла на экран; (1.2)
Move_Gr_fileToEcran(nUDn1,nUDm1,tBFO1);
//перепись 2-го графа с частичным контролем
из файла на экран;
Move_Gr_fileToEcran(nUDn2,nUDm2,tBFO2);
}
// обработка исключений при переписи с файла
catch (MyExcept e)
{
//здесь исключение вновь создается с
уточнением места ошибки
throw new MyExcept(e.Message + " с файла");
}
КЕСЛИ
try//контроль ввода с экрана
{
//Ввод с экрана 1-го графа с полным контролем и
построением матрицы смежности MS1 (1.3)
gr1.Input_GrInEkran(nUDn1, nUDm1, tBFO1);
//Ввод с экрана 2-го графа с полным контролем и
построением матрицы смежности MS2
gr2.Input_GrInEkran(nUDn2, nUDm2, tBFO2);
}
// обработка исключений при вводе с экрана
catch (MyExcept e)
{
//здесь исключение вновь создается с уточнением
места ошибки
throw new MyExcept(e.Message + " с экрана");
}
}
//обработка всех исключений
catch (MyExcept e)
{
Вывод(e.Message);
Выход;
}
//Расчет диаметра графа 1(1.4)
gr1.Diametr();
//Расчет диаметра графа 2
gr2.Diametr();
ЕСЛИ (gr1.Equals(gr2)/*характер.равны(1.5)*/) ТО
Вывод("Графы эквивалентны");
ИНАЧЕ
Вывод("Графы не эквивалентны");
КЕСЛИ
КОНЕЦ
Записываем алгоритм Sravnenie на С#, создаем классы, включаем в классы методы и заглушки, вызываем метод Sravnenie и выполняем отладку.
public void Sravnenie(bool fileEkran,OpenFileDialog openFileDialog,NumericUpDown nUDn1, NumericUpDown nUDm1,TextBox tBFO1,NumericUpDown nUDn2,NumericUpDown nUDm2, TextBox tBFO2)
{
try//контроль переписи с файла и ввода с экрана
{
if (fileEkran)
{
if (!ConectFile(openFileDialog))//подключение к
файлу и создание потока (1.1)
{
MessageBox.Show("Файл не выбран! Повторите
ввод");
return;
}
try//контроль переписи с файла
{
//перепись 1-го графа с частичным контролем
из файла на экран; (1.2)
Move_Gr_fileToEcran(gr1.ng,nUDn1,nUDm1,tBFO1);
//перепись 2-го графа с частичным контролем
из файла на экран;
Move_Gr_fileToEcran(gr2.ng, nUDn2,nUDm2,tBFO2);
}
// обработка исключений при переписи с файла
catch (MyExcept e)
//здесь исключение вновь создается с уточнением
места ошибки
{
throw new MyExcept(e.Message + " с файла");
}
}
try//контроль ввода с экрана
{
//Ввод с экрана 1-го графа с полным контролем и
построением матрицы смежности MS1 (1.3)
gr1.Input_GrInEkran(nUDn1, nUDm1, tBFO1);
//Ввод с экрана 2-го графа с полным контролем и
построением матрицы смежности MS2
gr2.Input_GrInEkran(nUDn2, nUDm2, tBFO2);
}
// обработка исключений при вводе с экрана
catch (MyExcept e)
{
//здесь исключение вновь создается с уточнением
места ошибки
throw new MyExcept(e.Message + " с экрана");
}
}
//обработка всех исключений
catch (MyExcept e)
{
MessageBox.Show(e.Message);
return;
}
//Расчет диаметра графа 1(1.4)
gr1.Diametr();
//Расчет диаметра графа 2
gr2.Diametr();
if (gr1.Equals(gr2))//сравнение характеристик (1.5)
MessageBox.Show("Графы эквивалентны");
else
MessageBox.Show("Графы не эквивалентны")
}
Не забываем включить оператор создания экземпляра проекта
Kurs_Proekt KP = new Kurs_Proekt();
И в клике кнопки вызвать метод Sravnenie
KP.Sravnenie(radioButton1.Checked, openFileDialog1,nUDn1, nUDm1,
tBFO1,nUDn2, nUDm2, tBFO2);
Приступаем к проектированию подзадачи 1.1 - подключение к файлу и создание потока.
public bool ConectFile(OpenFileDialog openFileDialog1)
{
//Выбор файла и создание потока (1.1)
if(openFileDialog1.ShowDialog() == DialogResult.OK)
{
filename = openFileDialog1.FileName;
//создание потока и подсоединение к файлу
Potok = new StreamReader(filename);
return true;
}
else
return false;
}
Приступаем к проектированию подзадачи 1.2 - переписываем граф с файла на экран с частичным контролем.
public void Move_Gr_fileToEcran(NumericUpDown nUDn, NumericUpDown nUDm,TextBox tBFO)
НАЧАЛО
Перенос чисел n и m на форму в компоненты nUDn, nUDm.
Считываем строку с файла и преобразуем ее в вектор строк (vect)
В vect[0] будет n, а в vect[1] будет m (см. в спецификации размещение данных)
Выполняем контроль n и m и заносим их в компоненты nUDn и nUDm
Переносим FO на форму в компоненту tbFO;
Считываем FO (может занимать несколько строк) с файла в строку S и преобразуем ее в вектор строк (vect), который переписываем в tbFO без контроля.
КОНЕЦ
В подзадаче 1.2 есть подзадачи, но они реализуются простыми средствами языка C#, без оформления их отдельными методами. Реализуем данную подзадачу на C#.
void Move_Gr_fileToEcran(int ng, NumericUpDown nUDn,
NumericUpDown nUDm,TextBox tBFO)
{
//Перенос чисел n и m на форму в компоненты
numericUpDown
//Считываем строку с файла и преобразуем ее в
вектор строк (veсt)
//В vect[0] будет n, а в vect[1] будет m (см.в
спецификации размещение данных)
char ch = ' ';
string str = Potok.ReadLine();
string[] vect = str.Split(ch);
int n, m;
try// контроль формата чисел
{
n = int.Parse(vect[0]);
m = int.Parse(vect[1]);
}
catch (FormatException e)
{
//добавим в класс графа поле целого типа ng,
//которое позволит уточнить, в каком графе ошибка
throw new MyExcept("В числах n или m
недопустимый символ в графе"+ ng.ToString());
}
//Выполняем контроль n и m и заносим их в
компоненты nUDn и nUDm
if ((n < 1) || (n > 20))
throw new MyExcept("Ошибка ввода количества вершин
графа " + ng.ToString());
nUDn.Value = n;
if ((m < 1) || (m > 50))
throw new MyExcept("Ошибка ввода количества ребер
графа " + ng.ToString());
nUDm.Value = m;
//Перенос FO на форму в компоненту tbFO
//Считываем FO(может занимать несколько строк) с
файла в строку S и преобразуем
// ее в вектор строк (vect), который переписываем
в tbFO без контроля
string strp = "";
while ((str = Potok.ReadLine())!= "")
strp += str;
vect = strp.Split(ch);
int k = vect.Length;
tBFO.Clear();
for (int i = 0; i < k - 1; i++)
tBFO.AppendText(vect[i] + "\r\n");
tBFO.AppendText(vect[k - 1]);
}
Методы 1.1 и 1.2 вставим вместо заглушек в класс Kurs_Proekt.
Приступаем к проектированию подзадачи 1.3 - ввод данных с экрана с контролем и построение матрицы смежности
Input_GrInEkran (NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBFO)
НАЧАЛО
Считываем с экрана n, m;
n =(int) nUDn.Value;//преобразуем в целое, так как Value типа decimal
m = (int)nUDm.Value;
Проверка количества элементов FO
int k=tBFO.Lines.Length;
ЕСЛИ k<> n+2*m ТО
throw new MyExcept("Количество элементов FO
неверно в графе " + ng.ToString());
КЕСЛИ
Считываем FO и строим матрицу смежности (1.3.1)
Контроль симметричности матрицы смежности (1.3.2)
КОНЕЦ
В данном алгоритме есть две подзадачи - (1.3.1) и (1.3.2). Реализуем их в виде методов с логическим типом.
Реализация подзадачи (1.3.1) - считывание FO и построение матрицы смежности.
bool CreatMS(TextBox tBFO)
{
// создаем и обнуляем матрицу смежности
MS =new int[n,n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
MS[I,j]=0;
int L = 0;//индекс строки в компоненте tBFO
for (int i = 0; i < n; i++) //по вершинам графа
{
try //контроль формата чисел
{
// считываем первую вершину, следующую за i
int j = int.Parse(tBFO.Lines[L]);
//контроль j
if ((j < 0) || (j > n))
throw new MyExcept("Элемент FO - неверный в
графе "+ng.ToString());
//считываем остальные вершины, следующие за i
while (j!= 0)
{
MS[i, j - 1] = 1;
L++;
j = int.Parse(tBFO.Lines[L]);
//контроль j
if ((j < 0) || (j > n))
throw new MyExcept ("Элемент FO - неверный
в графе " + ng.ToString());
}
L++;
}
catch (FormatException e)
{
throw new MyExcept ("В элементе FO недопустимый
символ в графе "+ng.ToString());
}
}
return true;
}
Реализация подзадачи (1.3.2) - контроль симметричности матрицы смежности.
bool SimetrMS(ref string msg)
{
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (MS[i, j]!= MS[j, i])
msg = msg + "[(" + i.ToString() + "," +
j.ToString()+")и("+j.ToString()+","+
i.ToString()+")]";
if (msg!= "")
return false;
else
return true;
}
Подставим подзадачи 1.3.1, 1.3.2 в подзадачу 1.3.
Input_GrInEkran (NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBFO)
НАЧАЛО
Считываем с экрана n, m;
n =(int) nUDn.Value;//преобразуем в целое, так как Value типа decimal
m = (int)nUDm.Value;
Проверка количества элементов FO
int k=tBFO.Lines.Length;
ЕСЛИ k<> n+2*m ТО
throw new MyExcept("Количество элементов FO
неверно в графе " + ng.ToString());
КЕСЛИ
//Считываем FO и строим матрицу смежности(1.3.1)
CreatMS(TextBox tBFO)
//Контроль симметричности матрицы смежности(1.3.2)
string msg = "";
ЕСЛИ (!SimetrMS(ref msg))
throw new MyExcept("Проверьте ребра " + msg + " в
графе " + ng.ToString());
КЕСЛИ
КОНЕЦ
Запишем метод 1.3 на C# и включим все три метода в класс NeorGraf.
public void Input_GrInEkran(NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBFO)
{
//Считываем с экрана n, m;
n = (int)nUDn.Value;//преобразуем в целое, так как
Value типа decimal
m = (int)nUDm.Value;
// Проверка количества элементов FO
int k = tBFO.Lines.Length;
if (k!= n + 2 * m)
throw new MyExcept("Количество элементов FO
неверно в графе " + ng.ToString());
//Считываем FO и строим матрицу смежности (1.3.1)
CreatMS(tBFO);
//Контроль симметричности матрицы смежности (1.3.2)
string msg = "";
if (!SimetrMS(ref msg))
throw new MyExcept("Проверьте ребра " + msg + " в
графе " + ng.ToString());
}
Переходим к проектированию подзадачи 1.4 - расчёт радиуса графа.
int Diametr()
НАЧАЛО
int r=1;
int[,] MR=new int[n,n];
int[,] B1=new int[n,n];
int[,] B2=new int[n,n];
bool pr =true;
копировать матрицу MS в MR(1.4.1)
копировать матрицу MS в В1
ПОКА pr ЦИКЛ
Pr=false;
r=r+1;
Умножение матриц В2=В1*MS(1.4.2)
ДЛЯ i=1 ДО n ЦИКЛ
ДЛЯ j=1 ДО n ЦИКЛ
ЕСЛИ (MR[I,j]=0) и (B2[I,j]<>0) ТО
MR[I,j]=r;
Pr=true;
КЕСЛИ
КЦИКЛ
КЦИКЛ
копировать матрицу B2 в В1
КЦИКЛ
Возврат r-1
КОНЕЦ
В данном алгоритме есть две подзадачи (1.4.1 и 1.4.2). Реализуем их.
Подзадача 1.4.1 - копирование матрицы.
CopyMatr(int [,] A,ref int [,] B)
НАЧАЛО
ДЛЯ i=1 ДО n ЦИКЛ
ДЛЯ j=1 ДО n ЦИКЛ
B[I,j]=A[I,j];
КЦИКЛ
КЦИКЛ
КОНЕЦ
Подзадача 1.4.2 - умножение матриц С=А*В
MulMatr(int [,] A, int [,] B,ref int[,]C)
НАЧАЛО
int S;
ДЛЯ i=1 ДО n ЦИКЛ
ДЛЯ j=1 ДО n ЦИКЛ
S=0;
ДЛЯkj=1 ДО n ЦИКЛ
S=S+A[I,k]*B[k,j]
КЦИКЛ
C[I,j]=S;
КЦИКЛ
КЦИКЛ
КОНЕЦ
Обе подзадачи запишем на языке C# и подставим в алгоритм 1.4.
public void CopyMatr(int [,] A,ref int [,] B)
{
for(int i=0;i< n; i++)
for(int j=0;j< n; j++)
B[i,j]=A[i,j];
}
public void MulMatr(int [,] A, int [,] B,ref int[,]C)
{
int S;
for(int i=0;i< n; i++)
for(int j=0;j< n; j++)
{
S=0;
for(int k=0;k< n; k++)
S=S+A[i,k]*B[k,j]
C[i,j]=S;
}
}
int Diametr()
НАЧАЛО
int r=1;
int[,] MR=new int[n,n];
int[,] B1=new int[n,n];
int[,] B2=new int[n,n];
bool pr =true;
//копировать матрицу MS в MR (1.4.1)
CopyMatr(MS,ref MR)
// копировать матрицу MS в В1
CopyMatr(MS,ref B1)
ПОКА pr ЦИКЛ
pr=false;
r=r+1;
// Умножение матриц В2=В1*MS (1.4.2)
MulMatr(B1, MS, ref B2)
ДЛЯ i=1 ДО n ЦИКЛ
ДЛЯ j=1 ДО n ЦИКЛ
ЕСЛИ (MR[I,j]=0) и (B2[I,j]<>0) ТО
MR[I,j]=r;
Pr=true;
КЕСЛИ
КЦИКЛ
КЦИКЛ
//копировать матрицу B2 в В1
CopyMatr(B2,ref B1)
КЦИКЛ
Возврат r-1
КОНЕЦ
Запишем алгоритм на C# и подставим его вместо заглушки 1.4.
public int Diametr()
{
int r=1;
int[,] MR=new int[n,n];
int[,] B1=new int[n,n];
int[,] B2=new int[n,n];
bool pr =true;
//копировать матрицу MS в MR (1.4.1)
CopyMatr(MS,ref MR);
// копировать матрицу MS в В1
CopyMatr(MS,ref B1);
while (pr)
{
pr=false;
r=r+1;
// Умножение матриц В2=В1*MS (1.4.2)
MulMatr(B1, MS, ref B2);
for(int i=0; i< n; i++)
for(int j=0; j< n; j++)
if((MR[i,j]==0) && (B2[i,j]!=0))
{
MR[i,j]=r;
pr=true;
}
//копировать матрицу B2 в В1
CopyMatr(B2,ref B1);
}
return r-1;
}
Включим все три метода в класс NeorGraf.
Библиографический список
Методические рекомендации по выполнению курсовых работ по конструированию программ [Текст]. Сост: Н. Г. Мокляк, В. И. Московец, А. Ю. Соколов. – Х.: Нац. аэрокосм. ун-т им. Н. Е. Жуковского «Харьк. авиац. ин-т», 1993. – 23 с.
Кормен, Т. Алгоритмы: построение и анализ [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Риверст. – М.: МЦНМО, 2000. – 960 с.
Оре, О. Теория графов [Текст] / О. Оре. - М.: Наука, 1980. – 336 с.
Иванов, Б. Дискретная математика. Алгоритмы и программы [Текст] / Б. Н. Иванов. - М.: Лаборатория Базовых Знаний, 2003. – 288 с.
Ахо, А. Структуры данных и алгоритмы [Текст] / А. Ахо, Д. Хопкрофт, Д. Ульман. - М.: Издательский дом «Вильямс», 2003. – 384 с.
Содержание
1..... Общие положения. 5
2..... Цель и задачи курсовой работы.. 6
3..... Порядок выполнения. 6
4..... Требования к оформлению пояснительной записки. 8
5..... Краткие теоретические сведения. 9
5.1. Основные определения теории графов. 9
5.2. Способы представления графов в памяти ЭВМ.. 18
5.2.1. Матрица смежностей графа. 18
5.2.2. Матрица инцидентностей графа. 19
5.2.3. Задание графа массивом преемников вершин (FO - представление графа) 20
5.2.4. Задание графа массивом предшественником вершин (FI - представление) 21
5.2.5. Модифицированное FO-представление графа (MFO - представление) 21
5.2.6. Модифицированное FI-представление графа (MFI - представление) 21
5.2.7. Сокращенные MFО и MFI - представления неорграфов. 22
6. Нисходящее проектирование. 22
6.1. Технология проектирования алгоритмов. 22
6.2. Принципы нисходящего проектирования: 23
7..... Варианты заданий для курсовой работы.. 27
7.1. Варианты расчетных заданий. 27
8..... Организация защиты курсовой работы.. 28
9..... Пример. 28
9.1. Постановка задачи. 28
9.2. Входные данные. 28
9.3. Входные формы.. 29
9.4. Входной формат текстового файла. 30
9.5. Выходные данные. 30
9.6. Выходные формы.. 30
9.7. Метод решения. 30
9.8. Аномалии. 31
9.9. Функциональные тесты.. 32
10. Нисходящее проектирование. 35
10.1................................................................................................ Основной алгоритм.. 35
10.2................................................ Нисходящее проектирование на класcах. 49
Библиографический список. 63
