ОБОСНОВАНИЕ ВЫБОРА ПРОГРАММНЫХ СРЕДСТВ

 

Курсовая работа выполнена с помощью программы Microsoft Visual C++ 6.0, одной из наиболее передовых, мощных и современных сред разработки Windows-приложений с богатым инструментарием разработки приложений. Средства работы с контекстом устройства позволяет быстро справиться с задачей и выдать графическое отображение результатов.

ОПИСАНИЕ ИНТЕРФЕЙСА ПОЛЬЗОВАТЕЛЯ

 

После запуска программы, программа ищет файл с описанием графа Graph.dat

 

 

Далее выбираются следующие пиктограммы окна

 

1. Отображение графа по его матрице смежностей

2. Отображение инварианта графа

3. Отображение полного графа

4. Редактор графа

5. Проверка графа на полноту

6. Перестраивает исходный граф в полный граф

Выбираем вторую пиктограмму

 

Теперь выберем последнюю пиктограмму

КОНТРОЛЬНЫЙ ПРИМЕР

 

ЗАКЛЮЧЕНИЕ

 

В результате выполнения работы был изучен алгоритм решения задачи поиска инвариантного и полного графа. На основе алгоритма реализована программа с графическим интерфейсом пользователя. Также реализован удобный редактор графа и вывод полученных результатов в простой и понятной форме.

СПИСОК ЛИТЕРАТУРЫ

 

ü Холзенер С. X71 Visual C++ 6: Учебный курс – СПб: Питер, 2001 – 576 с: ил.

ü Дж. Макконнел. Анализ алгоритмов. Вводный курс – Москва: Техносфера, 2002 – 304 с.

ü Тимофеев В. В.С++ как он есть. Самоучитель. – М.: ООО ≪Бином-Пресс≫,2004 г. – 366с.:ил.

ТЕКСТ ПРОГРАММЫ

 

Файл Graph.h

// Graph.h: interface for the CGraph class.//

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_GRAPH_H__8C8860CB_4D3F_4F0B_9B81_66289DCC2354__INCLUDED_)

#define AFX_GRAPH_H__8C8860CB_4D3F_4F0B_9B81_66289DCC2354__INCLUDED_

 

#if _MSC_VER > 1000

#pragma once

#endif // _MSC_VER > 1000

 

class CGraphV{

public:

    CPoint pt;

    CString Title;

public:

    CGraphV() : pt(CPoint(0,0)), Title(_T("")){};

    virtual ~CGraphV() {};

public:

    CGraphV& operator = (const CGraphV& gV){

              pt = gV.pt; Title = gV.Title;

              return *this;

    }

};

 

class CGraphE{

public:

    BOOL state;

    double len;

public:

    CGraphE() : state(FALSE),len(0.0){};

    virtual ~CGraphE() {};

public:

    CGraphE& operator = (const CGraphE& gE){

              state = gE.state; len = gE.len;

              return *this;

    }

};

 

class CGraph 

{

public:

    CGraphV *V;

    CGraphE *E;

    int          V_count;

    int          curV;

public:

    void Create(int mV_count);

    BOOL IsExist();

    void Destroy();

    void Null(int m_V,double len);

    void SetV(int m_Vpos, CPoint pt, CString m_Title);

    void SetE(int i, int j, double m_len);

    void SetRand(int A_space, int B_space, int m_Len, double m_p);

    void Show(CDC *pDC, COLORREF c = RGB(0,0,0));

    void Save(CString fname);

    void Load(CString fname);

    void MoveV(int m_x, int m_y);

    void SetCurV(int m_cur) { curV = m_cur;};

    void DeleteV(int indexV);

    void AddV(CPoint pt, CString m_Title);

    void MakeFull();

public:

    CGraph();

    virtual ~CGraph();

public:

    CGraph& operator = (const CGraph& g){

              int i=0;

 

              Destroy();

              Create(g.V_count);

              for(i=0;i<V_count;i++) V[i]=g.V[i];

              for(i=0;i<V_count*V_count;i++) E[i]=g.E[i];

              curV = g.curV;

              return *this;

    }

    CGraph& operator ! (){

              int i=0,j=0;

              BOOL fl = FALSE;

 

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

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

                                 if(i!=j) {

                                          fl = !(E[i*V_count+j].state);

                                          E[i*V_count+j].state=fl;

                                 }

              return *this;

    }

};

 

#endif // !defined(AFX_GRAPH_H__8C8860CB_4D3F_4F0B_9B81_66289DCC2354__INCLUDED_)

 

Файл Graph.cpp

// Graph.cpp: implementation of the CGraph class.

//

//////////////////////////////////////////////////////////////////////

 

#include "stdafx.h"

#include "KursovikMin.h"

#include "Graph.h"

 

#ifdef _DEBUG

#undef THIS_FILE

static char THIS_FILE[]=__FILE__;

#define new DEBUG_NEW

#endif

 

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

 

CGraph::CGraph()

{

    V_count = 0;

}

 

CGraph::~CGraph()

{

    Destroy();

}

 

//////////////////////////////////////////////////////////////////////

// Methods

//////////////////////////////////////////////////////////////////////

 

void CGraph::Create(int mV_count)

{

    Destroy();

    if(mV_count <= 0) return;

    curV = -1;

    V_count = mV_count;

    V = new CGraphV[V_count];

    E = new CGraphE[V_count*V_count];

    Null(-1,0.0);

}

 

BOOL CGraph::IsExist()

{

    return V_count > 0;

}

 

void CGraph::Null(int m_V=-1, double m_len = -1)

{

    for(int i=0;i<V_count;i++)

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

              {

                       E[i*V_count+j].state = FALSE;

                       E[i*V_count+j].len = m_len;

              }

}

 

void CGraph::Destroy()

{

    if(IsExist()) {

              delete [] V;

              delete [] E;

              V = NULL;

              E = NULL;

              V_count = 0;

    }

}

 

void CGraph::SetV(int m_Vpos, CPoint m_pt, CString m_Title)

{

    if(m_Vpos < V_count){

              V[m_Vpos].pt = m_pt;

              V[m_Vpos].Title = m_Title;

    }

}

 

void CGraph::SetE(int i, int j, double m_len)

{

    int pos = i*V_count+j;

    if(pos < V_count*V_count)

              {E[pos].state = TRUE;E[pos].len = m_len;}

}

 

void CGraph::SetRand(int A_space, int B_space, int m_Len, double m_p)

{

    int COUNT = V_count;

    CString str;

 

    srand(time(NULL));

    for(int i=0;i<COUNT;i++ )

    {

              str.Format("Point-%i",i);

              SetV(i,CPoint(A_space+rand()%(B_space-A_space+1),A_space+rand()%(B_space-A_space+1)),str);

    }

    for(i=0;i<COUNT*COUNT;i++)

              if((rand()+0.0)/RAND_MAX >= m_p) SetE(i / COUNT, i % COUNT, m_Len*rand()/RAND_MAX);

              else {E[i].state = FALSE;E[i].len = 0.0;}

}

 

void CGraph::Show(CDC *pDC, COLORREF c)

{

    int i=0, j=0, fn = V_count*V_count;

    const int sz = 4;

    CPoint pt1, pt2;

    CPen p(PS_SOLID,1,c), *old_p;

    CString str;

 

    old_p = pDC->SelectObject(&p);

    pDC->SetBkMode(TRANSPARENT);

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

    {

              pDC->Ellipse(V[i].pt.x-sz,V[i].pt.y-sz,V[i].pt.x+sz,V[i].pt.y+sz);

              pDC->TextOut(V[i].pt.x,V[i].pt.y,V[i].Title);

    }

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

              if(E[i].state)

              {       

                       pt1 = V[i/V_count].pt; pt2 = V[i%V_count].pt;

                       //str.Format("%7.3f",E[i].len);

                       pDC->MoveTo(pt1);

                       pDC->LineTo(pt2);

                       //pDC->TextOut((pt1.x+pt2.x)/2,(pt1.y+pt2.y)/2,str);

              }

    pDC->SelectObject(old_p);

}

 

void CGraph::Save(CString fname)

{

    int i=0,j=0,len = 0;

    const UINT Separator = 0xffff;

    char buf[81];

 

    FILE *file = NULL;

    file = fopen(fname,"wb");

    if(file != NULL){

              fwrite(&V_count,sizeof(V_count),1,file);

              for(i=0;i<V_count;i++){

                       fwrite(&V[i].pt.x,sizeof(V[i].pt.x),1,file);

                       fwrite(&V[i].pt.y,sizeof(V[i].pt.y),1,file); len = V[i].Title.GetLength();

                       fwrite(&len,sizeof(int),1,file);

                       //fwrite(&V[i].Title,len,1,file);

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

                                 buf[j] = V[i].Title[j];

                       buf[len]=0;

                       fwrite(&buf[0],len,1,file);

              }

              for(i=0;i<V_count*V_count;i++)

              {

                       fwrite(&E[i].state,sizeof(E[i].state),1,file);

                       fwrite(&E[i].len,sizeof(E[i].len),1,file);

              }

              fclose(file);

    }

}

 

void CGraph::Load(CString fname)

{

    int i=0, len = 0;

    const UINT Separator = 0xffff;

    char buf[81];

 

    FILE *file = NULL;

    file = fopen(fname,"rb");

    if(file != NULL){

              Destroy();

              fread(&i,sizeof(i),1,file);

              Create(i);

              for(i=0;i<V_count;i++){

                       fread(&V[i].pt.x,sizeof(V[i].pt.x),1,file);

                       fread(&V[i].pt.y,sizeof(V[i].pt.y),1,file);

                       fread(&len,sizeof(int),1,file);

                       fread(&buf[0],len,1,file); buf[len] = 0;

                       V[i].Title = buf;

              }

              for(i=0;i<V_count*V_count;i++)

        {

                       fread(&E[i].state,sizeof(E[i].state),1,file);

                       fread(&E[i].len,sizeof(E[i].len),1,file);

              }

              fclose(file);

    }

}

 

void CGraph::MoveV(int m_x, int m_y)

{

    if(curV >=0 && curV < V_count)

              V[curV].pt = CPoint(m_x,m_y);

}

 

void CGraph::DeleteV(int indexV)

{

    int i=0, j=0;

 

    if(!IsExist()) return;

    if(indexV>=0 && indexV<V_count)

    {

              CGraph g;

              int i1 = 0, j1 = 0;

              g.Create(V_count-1);

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

                       if(i != indexV) g.V[i1++] = V[i];

              i1 = 0; j1 = 0;

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

              {

                       if(i != indexV){

                       j1 = 0;

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

                                 if(j != indexV) {g.E[i1*(V_count-1)+j1] = E[i*V_count+j];j1++;}

                       i1++;

                       }

              }

              Destroy();

              *this = g;

    }

}

 

void CGraph::AddV(CPoint pt, CString m_Title)

{

    int i=0;

    CGraphV *V1 = new CGraphV[V_count+1];

    CGraphE *E1 = new CGraphE[(V_count+1)*(V_count+1)];

 

    for(i=0;i<V_count;i++) {V1[i].pt = V[i].pt; V1[i].Title = V[i].Title;}

    V1[i].pt = pt; V1[i].Title = m_Title;

    for(i=0;i<V_count*V_count;i++)

    {

              E1[i].state = E[i].state;

              E1[i].len = E[i].len;

    }

    for(i=0;i<V_count*V_count;i++) {

              E1[(V_count-1)*V_count+i].state = FALSE;

              E1[(V_count-1)*V_count+i].len = 0.0;

    }

    Create(V_count+1);

    for(i=0;i<V_count;i++) {V[i].pt = V1[i].pt; V[i].Title = V1[i].Title;}

    for(i=0;i<V_count*V_count;i++)

    {

              E[i].state = E1[i].state;

              E[i].len = E1[i].len;

    }

    delete [] V1;

    delete [] E1;

}

 

void CGraph::MakeFull()

{

    for(int i=0;i<V_count*V_count;i++)

              E[i].state = TRUE;

}