Формирование графовой модели заданного фрагмента принципиальной электрической схемы

Аннотация В данной пояснительной записке приведено описание алгоритма и исходного кода программы формирования графовой модели заданного фрагмента принципиальной электрической схемы. Разработаны схемы алгоритмов решения задачи. В среде Microsoft Visual Studio 2005 (C++) разработана и отлажена программа, реализующая представленные алгоритмы. Также представлены результаты решения контрольных примеров, выполненные с помощью разработанной программы.

В приложении приведён текст программы.

графовая модель программа

1.Описание программы

1.1Общие сведения

1.2Функциональное назначение

1.3Описание логической структуры

1.4Cтруктурная схема основной программы

1.5Алгоритм функции vvod ()

1.6 Алгоритм функции int **matr ()

2.Описание контрольного примера Приложение

1. Описание программы

1.1 Общие сведения Программа формирования графовой модели заданного фрагмента принципиальной электрической схемы написана в среде Microsoft Visual Studio 2005.

Программа имеет имя «PraktikaDasha».

Программа запускается на выполнение при помощи Visual Studio 2005 C++, в случае же присутствия исполняемого файла можно произвести запуск из операционной системы Windows.

1.2 Функциональное назначение Программа предназначена для формирования графовой модели заданного фрагмента принципиальной электрической схемы.

Программа выполняет следующие функции:

1. Чтение списка по цепям из представленного текстового файла.

2. Формирование списка по цепям данного графа (с использованием динамической структуры — линейного списка)

3. Формирование и вывод матрицы свяхности.

4. Рисование графовой модели (цепь-дерево) заданного фрагмента.

1.3 Описание логической структуры Программа разбита на отдельные функциональные части — подпрограммы, которые распределяются по отдельным уровням иерархии. Каждая из подпрограмм решает только свою небольшую задачу по преобразованию данных, что позволяет упростить процесс написания и отладки программы в целом. Далее приводится описания назначения всех функций.

Функция CepCont *vvod_file (char file_name [ ]) позволяет выбрать файл и исходными данными и сформировать линейный динамический список.

Функция void vivod_spis (CepCont *st, HWND hwndEdit) выводит полученный список по цепям на экран.

Функция int kol_elem (CepCont *st) подсчитывает количество элементов.

Функция void del_matr (int **matr, int k) удаляет динамическую матрицу.

Функция int **memory (int k) выделяет память под динамическую матрицу.

Функция int **form_matr (CepCont *st, int k) преобразовывает список в матрицу.

Функция void vivod_matr (int **matr, int k, HWND hwndEdit) выводит полученную матрицу связности на экран.

Функция void save_matr (char file_name [ ], int **matr, int k) сохраняет матрицу в файл.

Функция void del_spis (CepConrt *BegSpis) удаляет динамический список.

Функция MyDlgProc (HWND hwnd, UINT msg, WPARAM wp, LPARAM lp) обработка сообщений диалога.

1.4 Cтруктурная схема основной программы

1.5 Алгоритм функции vvod ():

1.6 Алгоритм функции int **matr ()

2. Описание контрольного примера Дана схема варианта № 12:

Составим входное описание заданной схемы в виде списка по цепям:

1 3

1 1

7 1

7 3

2 2

2 1

7 2

3 2

1 2

3 1

4 4

1 3

2 2

3 2

4 1

5 2

3 3

5 1

6 3

4 2

6 1

7 5

7 2

4 3

6 2

8 3

5 2

6 3

7 4

По входному описанию схемы сформируем матрицу связности

0 1 1 0 0 0 1

1 0 1 0 0 0 1

1 1 0 1 1 0 0

0 0 1 0 0 2 0

0 0 1 0 0 1 0

0 0 0 2 1 0 2

1 1 0 0 0 2 0

Построим граф:

Мы получили верные результаты, что позволяет нам сделать вывод о правильной реализации алгоритма в программе.

Приложение

#include

#include

#include «resource.h»

#include

#include

char file_name[MAX_PATH+1], customfilter[100];

int **matr, k, flag;

OPENFILENAME of, sf;

struct CepCont

{

int ce, kk;

CepCont *adres;

};

CepCont *BegSpis=NULL;

CepCont *vvod_file (char file_name[])

{

int ce, kk;

FILE*f_in;

f_in=fopen (file_name," r");

if (f_in≠NULL)

{

CepCont *st=NULL;

CepCont *sp=NULL;

while (fscanf (f_in," %d%d" ,&ce,&kk)==2)

{

st=new CepCont;

if (BegSpis==NULL) BegSpis=st;

else sp->adres=st;

sp=st;

st->ce=ce;

st->kk=kk;

}

if (sp≠NULL) sp->adres=NULL;

fclose (f_in);

return BegSpis;

}

else

{

return NULL;

}

}

void vivod_spis (CepCont *st, HWND hwndEdit)

{

int n, i;

char buf[25];

while (st≠NULL)

{

sprintf (buf, «Цепь%dtКонтактов%d», st->ce, st->kk);

SendMessage (hwndEdit, EM_REPLACESEL, 0,(LPARAM)buf);

SendMessage (hwndEdit, EM_REPLACESEL, 0,(LPARAM)" rn");

n=st->kk;

st=st->adres;

for (i=0; i

{

sprintf (buf, «Элемент%d Контакт%d», st->ce, st->kk);

SendMessage (hwndEdit, EM_REPLACESEL, 0,(LPARAM)buf);

SendMessage (hwndEdit, EM_REPLACESEL, 0,(LPARAM)" rn");

st=st->adres;

}

SendMessage (hwndEdit, EM_REPLACESEL, 0,(LPARAM)" rn");

}

}

int kol_elem (CepCont *st)

{

int max=0, i, n;

while (st≠NULL)

{

n=st->kk;

st=st->adres;

for (i=0; i

{

if (st->ce>max) max=st->ce;

st=st->adres;

}

}

return max;

}

void del_matr (int **matr, int k)

{

for (int i=0; i

delete []matr[i];

delete []matr;

}

int **memory (int k)

{

int **matr=new int *[k];

if (matr==NULL) return NULL;

for (int i=0; i

{

matr[i]=new int [k];

if (matr[i]==NULL)

{

del_matr (matr, i);

return NULL;

}

}

return matr;

}

int **form_matr (CepCont *st, int k)

{

int i, j, n;

int **matr=memory (k);

CepCont *sp;

if (matr==NULL) return NULL;

for (i=0; i

for (j=0; j

matr[i][j]=0;

while (st≠NULL)

{

n=st->kk;

st=st->adres;

if (n≠0)

{

for (i=0; i

{

sp=st;

st=st->adres;

if (sp->ce≠st->ce)

{

matr[sp->ce-1][st->ce-1]++;

matr[st->ce-1][sp->ce-1]++;

}

}

st=st->adres;

}

}

return matr;

}

void vivod_matr (int **matr, int k, HWND hwndEdit)

{

char buf[256];

for (int i=0;i

{

for (int j=0;j

{

sprintf (buf," %d «, matr[i][j]);

SendMessage (hwndEdit, EM_REPLACESEL, 0,(LPARAM)buf);

}

SendMessage (hwndEdit, EM_REPLACESEL, 0,(LPARAM)" rn");

}

}

void save_matr (char file_name[], int **matr, int k)

{

FILE*f_out;

f_out=fopen (file_name," w");

if (f_out≠NULL)

{

fprintf (f_out," Матрица связностиn");

for (int i=0;i

{

for (int j=0;j

fprintf (f_out," %d «, matr[i][j]);

fprintf (f_out, «n»);

}

fclose (f_out);

}

}

void del_spis (CepCont *BegSpis)

{

CepCont *sp=NULL;

while (BegSpis≠NULL)

{

sp=BegSpis->adres;

delete BegSpis;

BegSpis=sp;

}

}

int CALLBACK MyDlgProc (HWND hwnd, UINT msg, WPARAM wp, LPARAM lp)

{

const double pi=3.14 159;

switch (msg)

{

case WM_INITDIALOG:break;

case WM_COMMAND:

switch (LOWORD (wp))

{

case IDCANCEL:

{

del_spis;

del_matr;

return EndDialog (hwnd, IDCANCEL);

}

case IDOPEN:

{

char initialdir[MAX_PATH+1];

getcwd (initialdir, MAX_PATH+1);

memset (&of, 0, sizeof (of));

of.lStructSize=sizeof (of);

of.lpstrFilter="Текстовые файлы (*.txt)*.txt" «Все файлы (*.*)*.*» ;

of.nFilterIndex=1;

of.lpstrCustomFilter=customfilter;

of.nMaxCustFilter=100;

file_name[0]='';

of.lpstrFile=file_name;

of.nMaxFile=MAX_PATH+1;

of.lpstrInitialDir=initialdir;

of.lpstrTitle="Диалог открытия файла" ;

if (GetOpenFileName (&of)≠0)

{

SetWindowText (GetDlgItem (hwnd, IDC_EDIT1), 0);

SetWindowText (GetDlgItem (hwnd, IDC_EDIT2), 0);

InvalidateRect (hwnd, 0, 0);

if (BegSpis≠NULL)

{

del_spis (BegSpis);

BegSpis=NULL;

}

if (matr≠NULL)

{

del_matr (matr, k);

matr=NULL;

}

if ((BegSpis=vvod_file (file_name))==NULL)

{

MessageBox (hwnd, «Файл не существует, или содержит не верные данные», «Ошибка!», 0);

break;

}

}

break;

}

case IDSPIS:

{

if (BegSpis≠NULL)

{

SetWindowText (GetDlgItem (hwnd, IDC_EDIT1), 0);

vivod_spis (BegSpis, GetDlgItem (hwnd, IDC_EDIT1));

}

else MessageBox (hwnd, «Не загружены исходные данные», «Ошибка!», 0);

break;

}

case IDMATRIX:

{

if (BegSpis≠NULL)

{

if (matr==NULL)

{

k=kol_elem (BegSpis);

matr=form_matr (BegSpis, k);

vivod_matr (matr, k, GetDlgItem (hwnd, IDC_EDIT2));

}

}

else MessageBox (hwnd, «Не загружены исходные данные», «Ошибка!», 0);

break;

}

case IDGRAF:

{

if (matr≠NULL)

{

flag=1;

RECT rect;

rect.left=150;

rect.top=50;

rect.right=550;

rect.bottom=400;

InvalidateRect (hwnd,&rect, 1);

}

else MessageBox (hwnd, «Не сформирована матрица», «Ошибка!», 0);

break;

}

case IDSAVE:

{

char initialdir[MAX_PATH+1];

getcwd (initialdir, MAX_PATH+1);

memset (&of, 0, sizeof (of));

sf.lStructSize=sizeof (of);

sf.lpstrFilter="Текстовые файлы (*.txt)*.txt" «Все файлы (*.*)*.*» ;

sf.nFilterIndex=1;

sf.lpstrCustomFilter=customfilter;

sf.nMaxCustFilter=100;

file_name[0]='';

sf.lpstrFile=file_name;

sf.nMaxFile=MAX_PATH+1;

sf.lpstrInitialDir=initialdir;

sf.lpstrTitle="Диалог сохранения файла" ;

if (GetSaveFileName (&sf)≠0) save_matr (file_name, matr, k);

else MessageBox (hwnd, «Не сформирована матрица», «Ошибка!», 0);

}

default: return 0;

}

case WM_PAINT:

int *xe, *ye, xc, yc, i, j;

char str[10];

float f;

HDC hdc;

HPEN hpen, old_pen;

HBRUSH hbrush, old_brush;

PAINTSTRUCT ps;

hdc=BeginPaint (hwnd,&ps);

if ((matr≠NULL)&&(flag==1))

{

xe=new int [k];

ye=new int [k];

SetBkMode (hdc, TRANSPARENT);

hpen=CreatePen (PS_SOLID, 1, RGB (0,0,255));

hbrush=CreateSolidBrush (RGB (255,0,0));

f=2*pi/k;

for (i=0;i

{

xe[i]=150*cos (f*i)+360;

ye[i]=150*sin (f*i)+230;

}

old_pen=(HPEN)SelectObject (hdc, hpen);

old_brush=(HBRUSH)SelectObject (hdc, hbrush);

for (i=0; i

for (j=0; j

{

if (matr[i][j]>0)

{

MoveToEx (hdc, xe[i], ye[i], 0);

LineTo (hdc, xe[j], ye[j]);

sprintf (str, «%d», matr[i][j]);

xc=(xe[i]+xe[j]-10)/2;

yc=(ye[i]+ye[j]-10)/2;

TextOut (hdc, xc, yc, str, 1);

}

}

for (i=0;i

{

sprintf (str," %d", i+1);

Ellipse (hdc, xe[i]-20,ye[i]-20,xe[i]+20,ye[i]+20);

TextOut (hdc, xe[i]-5,ye[i]-5,str, 1);

}

EndPaint (hwnd,&ps);

DeleteObject (hpen);

DeleteObject (hbrush);

delete[] xe, ye;

}

else EndPaint (hwnd,&ps);

default: return 0;

}

return 1;

}

int WINAPI WinMain

(

HINSTANCE hInstance,

HINSTANCE hPrevInstance,

LPSTR lpCmdLine,

int nCmdShow)

{

DialogBox (0,MAKEINTRESOURCE (IDD_DIALOG), 0, MyDlgProc);

}