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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Аннотация

В данной пояснительной записке приведено описание алгоритма и исходного кода программы формирования графовой модели заданного фрагмента принципиальной электрической схемы. Разработаны схемы алгоритмов решения задачи. В среде 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 <stdio.h>

#include <windows.h>

#include "resource.h"

#include <direct.h>

#include <cmath>

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, "Цепь%d\tКонтактов%d", st->ce, st->kk);

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

SendMessage(hwndEdit,EM_REPLACESEL,0,(LPARAM)"\r\n");

n=st->kk;

st=st->adres;

for (i=0; i<n; i++)

{

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

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

SendMessage(hwndEdit, EM_REPLACESEL, 0,(LPARAM)"\r\n");

st=st->adres;

}

SendMessage(hwndEdit, EM_REPLACESEL, 0,(LPARAM)"\r\n");

}

}

int kol_elem(CepCont *st)

{

int max=0, i, n;

while (st!=NULL)

{

n=st->kk;

st=st->adres;

for (i=0; i<n; 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<k; 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<k; 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<k; i++)

for (j=0; j<k; j++)

matr[i][j]=0;

while (st!=NULL)

{

n=st->kk;

st=st->adres;

if (n!=0)

{

for (i=0; i<n-1; 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<k;i++)

{

for(int j=0;j<k;j++)

{

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

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

}

SendMessage(hwndEdit,EM_REPLACESEL,0,(LPARAM)"\r\n");

}

}

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<k;i++)

{

for(int j=0;j<k;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.14159;

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)\0*.txt\0" "Все файлы (*.*)\0*.*\0";

of.nFilterIndex=1;

of.lpstrCustomFilter=customfilter;

of.nMaxCustFilter=100;

file_name[0]='\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)\0*.txt\0" "Все файлы (*.*)\0*.*\0";

sf.nFilterIndex=1;

sf.lpstrCustomFilter=customfilter;

sf.nMaxCustFilter=100;

file_name[0]='\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<k;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<k; i++)

for(j=0; j<k; 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<k;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);

}

1. Размещено на www.allbest.ru