Лабораторная работа по дисциплине «Автоматизация проектирования вычислительных систем»
Постановка задачи.
Разработать программу выполняющую следующие действия:
1) Чтение из файла списка дуг.
2) Преобразование списка дуг в матрицу смежности.
3) Сохранение матрицы смежности в текстовом файле.
Особенности программы.
Полагается, что граф не ориентированный.
Входные данные:
Входные данные должны быть представлены в виде текстового файла.
В первой строке указывается количество вершин графа.
Во второй строке указывается количество дуг графа.
В последующих строках указываются дуги графа в формате:
AB
где A – номер начальной вершина
В – номер конечной вершины
Описание структур данных.
Список дуг – структура данных представляющая собой массив из записей содержащих начальную и конечную вершину.
Массив из 8 байт представляющий собой матрицу смежности в побитовой форме.
Массив из строк представляет собой массив сообщений выдаваемых программой.
Коды ошибок программы.
1 - указанное число дуг в заголовке файла таблицы дуг больше 8
2 - номер вершины графа в таблице дуг выше максимальной размерности
3 - ошибка при записи в выходной файл
4 - ошибка при чтении из файла
5 - размерность матрицы больше 8
Краткое описание алгоритма.
Чтение из файла списка дуг и сохранение в массиве. Определить размерность матрицы. Сформировать матрицу смежности необходимой размерности и заполнить ее нулями. Запуск преобразующей процедуры. Делать количество раз равное размерности матрицы.
i. Считать начальную вершину.
ii. Считать конечную вершину.
iii. Записать в матрицу смежности единицу на пересечении строки равной номеру начальной вершины и столбца равного номеру конечной вершины.
iv. Отразить симметрично диагонали записанную единицу.
Записать полученную матрицу смежности в текстовой файл.
Спецификация процедур и функций.
char matr::readmatr (char i, char j) – возвращает значение элемента матрицы смежности.
Входные данные: i – номер столбца элемента матрицы. j – номер строки элемента матрицы.
Выходные данные: значение элемента матрицы смежности.
char matr::writematr (char i, char j) – устанавливает единицу в заданном элементе матрицы смежности.
Входные данные: i – номер столбца элемента матрицы. j – номер строки элемента матрицы.
Выходные данные: 0
char matr::writefile() – записывает в текстовой файл матрицу смежности.
Выходные данные: 3 – в случае ошибки. 0 – без ошибок
char matr::transform() – функция трансформирования списка дуг в матрицу смежности.
Выходные данные: 0
int readfile() – чтение файла содержащего список дуг.
Выходные данные: 1,2,4 – в случае ошибки. 0 – без ошибок.
Тестирование.
Тестовый пример1.
Входной файл(список дуг):
4
4
12
14
23
24
Сообщение: преобразование завершено.
Матрица смежности:
0101
1011
0100
1100
Тестовый пример2
Входной файл(список дуг):
6
7
12
23
24
25
34
36
65
Сообщение: преобразование завершено.
Матрица смежности:
010000
101110
010101
011000
010001
001010
Тестовый пример3
Входной файл(список дуг):
6
7
17
23
24
25
34
36
65
Сообщение: номер вершины графа в таблице дуг выше максимальной размерности.
Вывод: в ходе лабораторной работы была разработана программа переводящая таблицу дуг графа в таблицу смежности.
Текст кода программы.
/*
коды ошибок
1 - указанное число дуг в заголовке файла таблицы дуг больше 8
2 - номер вершины графа в таблице дуг выше максимальной размерности
3 - ошибка при записи в выходной файл
4 - ошибка при чтении из файла
5 - размерность матрицы больше 8
*/
#include "stdafx. h"
#include <iostream. h>;
#include <fstream. h>;
#include <stdlib. h>;
#include <string. h>;
#include <conio. h>;
const char messages[5] [88] = {
"preobrazovanie zaversheno",
"ukazannoe chislo dug v zaglolvke fajla tablicbl dug bolwe 8 ili nevernblj format faila",
"nomer vershinbl grafa v tablice dug vblwe maximalmoy razmernosti",
"owibka pri zapisi v vblhodnoj fail",
"owibka pri chtenii iz faila"};
struct cell
{
char one;
char two;
};
cell spisok[8];
ifstream infile("in_ka. txt");
ofstream outfile("out_ka. txt");
char readfile();
class matr
{
public:
matr();
char readmatr(char i, char j);
char writematr(char i, char j);
char writefile();
char transform();
char max, cur, sp;
char mas[8];
};
matr m;
char matr::readmatr (char i, char j) // i = x, j = y
{
int a = 0x80;
char r;
a = (a >> i);
r = mas[j];
r = r & a;
if (r) return(1); else return(0);
};
char matr::writefile()
{
char i, j;
char str[11] = " ",emptstr[11] = " ";
try
{
for (i=0;i<=cur-1;i++)
{
strcpy(str, emptstr);
str[9] = 0x0D; str[10] = 0x0A;
for (j=0;j<=cur-1;j++)
{
if (matr::readmatr(j, i)) str[j]='1';else str[j]='0';
};
outfile. write(str, sizeof(str));
};
}
catch(...) {return(3);};
return(0);
};
char matr::writematr (char i, char j)
{
int a = 0x80;
a = (a>>i);
mas[j] = mas[j] | a;
return(0);
};
char matr::transform()
{
char i, t1,t2;
for(i=0;i<=sp-1;i++)
{
t1 = spisok[i].one;
t2 = spisok[i].two;
writematr(t2,t1);
writematr(t1,t2);
};
return(0);
};
matr::matr()
{
max = 8;
char i;
for (i=0;i<=max-1;i++) mas[i] = 0;
};
int _tmain(int argc, _TCHAR* argv[])
{
char e;
e = readfile();
if (e) {cout<<messages[e]<<endl;getch();return(0);};
e = m. transform();
if (e) {cout<<messages[e]<<endl;getch();return(0);};
e = m. writefile();
cout<<messages[e]<<endl;
getch();
return 0;
};
char readfile()
{
/*
коды ошибок
1 - число дуг больше 36
2 - номер вершины графа в таблице дуг выше максимальной размерности
4 - ошибка при чтении из файла
5 - если размерность матрицы больше 8
*/
char str[8],s[2]="0",n, i;
int t1,t2;
infile. getline(str, sizeof(str));
n = atoi(str);
if ((n==0)||(n>m. max)) return(5); //если размерность матрицы больше 8
m. cur = n;
infile. getline(str, sizeof(str));
n = atoi(str);
if ((n==0)||(n>36)) return(1); //если число дуг не больше 36 и больше 0, то продолжаем
m. sp = n;
try
{
for (i=0;i<=n-1;i++)
{
infile. getline(str, sizeof(str));
s[0] = str[0];
t1 = atoi(s);
// получаем в t1 вершину из которой исходит дуга
if ((t1==0)||(t1>m. cur)) return(2);
// проверка на корректность данных.
s[0] = str[1];
t2 = atoi(s);
// получаем в t2 вершину в которою входит дуга
if ((t1==0)||(t2>m. cur)) return(2);
// проверка на корректность данных.
// если не было ошибок записываем считанные данные в массив
spisok[i].one = t1-1;
spisok[i].two = t2-1;
};
}
catch (...) {return(4);};
return(0);
};