cmyview.cpp

最小生成树的具体程序

// CMyView.cpp : implementation of the CMyView class
//

#include "stdafx.h"
#include "最小生成树.h"

#include <math.h>
#include "CMyDoc.h"
#include "CMyView.h"
#include "HelpDlg.h"
#include "AddDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CMyView

IMPLEMENT_DYNCREATE(CMyView, CView)

BEGIN_MESSAGE_MAP(CMyView, CView)
	//{{AFX_MSG_MAP(CMyView)
	ON_WM_LBUTTONUP()
	ON_COMMAND(ID_MENU_HANDLE, OnHandle)
	ON_COMMAND(ID_MENU_AUTO, OnAuto)
	ON_COMMAND(W_HELP, OnHelp)
	ON_WM_TIMER()
	ON_WM_CHAR()
	ON_WM_LBUTTONDBLCLK()
	ON_WM_CANCELMODE()
	ON_WM_CAPTURECHANGED()
	ON_COMMAND(ID_ENDATA, OnEnData)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyView construction/destruction

CMyView::CMyView()
{
	// TODO: add construction code here
	
	w_isstop = true;
	w_ishandle = true;

}

CMyView::~CMyView()
{
}

BOOL CMyView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CMyView drawing

void CMyView::OnDraw(CDC* pDC)
{
	CMyDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here

	//当是第一次读数据时，要初始化w_closedge这个辅助计算数组
	if(pDoc->w_isbegindraw){
		W_InitClosedge(pDoc);
		pDoc->w_isbegindraw = false;
	}

	int x1,y1,x2,y2,k;
	CString str;
	map<int,CPoint>::iterator pos;
	CPen pen[4], *oldpen;
	pen[0].CreatePen(PS_DASHDOT,1,RGB(0,0,0));//画边
	pen[1].CreatePen(PS_SOLID,2,RGB(0,0,0));//画顶点圆
	pen[2].CreatePen(PS_SOLID,4,  RGB(0,255,0));//在图中画最小生成树的线
	pen[3].CreatePen(PS_SOLID,4,RGB(255,0,155));//画输出结果的边框




	//画边、边的值
	oldpen = pDC->SelectObject(&pen[0]);
	for(int i=0; i<pDoc->w_vexnum; ++i)
		for(int j=0; j<pDoc->w_vexnum; ++j){
			if(pDoc->w_arcs[i][j]!=0 && pDoc->w_arcs[i][j]<MAXINT){
				pos = pDoc->w_vecmap.find(i);
				x1 = pos->second.x;
				y1 = pos->second.y;
				pDC->MoveTo(x1, y1);
				pos = pDoc->w_vecmap.find(j);
				x2 = pos->second.x;
				y2 = pos->second.y;
				pDC->LineTo(x2, y2);	
				str.Format("%d", pDoc->w_arcs[i][j]);
				pDC->TextOut( (x1+x2)/2-2,(y1+y2)/2-2,str);
			}
		}

	//画顶点、顶点标签
	pDC->SelectObject(&pen[1]);
	pos = pDoc->w_vecmap.begin();
	while(pos!=pDoc->w_vecmap.end()){
		pDC->Ellipse(pos->second.x-R0,pos->second.y-R0,pos->second.x+R0,pos->second.y+R0);
		pDC->TextOut(pos->second.x-3,pos->second.y-3,pDoc->w_vecname[pos->first]);
		++pos;
	}


	int x0 = 100,
		y0 = 580;
	//画输出结果的边框
	pDC->SelectObject(&pen[3]);
	pDC->Rectangle(0,560,1000,630);
	pDC->Rectangle(0,0,XX-R1-20,560);

	//画出顶点之间的关系
	k = 0;
	for(i=0; i<pDoc->w_vexnum; ++i)
		for(int j=0; j<pDoc->w_vexnum; ++j)
			if(pDoc->w_arcs[i][j]!=0 && pDoc->w_arcs[i][j]<MAXINT){
				str = "";
				str.Format("%s——%s    %d",pDoc->w_vecname[i],pDoc->w_vecname[j],pDoc->w_arcs[i][j]);
				pDC->TextOut(10,50+20*k,str);
				++k;
			}




	//画已搜索到的最小生成树
	pDC->SetTextColor(RGB(255,0,155));
	for(i=0; i<pDoc->w_vexnum; ++i){
		if(i!=w_start && w_closedge[i].value==0){
			//在图中画最小生成树的线
			pDC->SelectObject(&pen[2]);
			pDC->MoveTo(pDoc->w_vecmap[i]);
			pDC->LineTo(pDoc->w_vecmap[w_closedge[i].vex]);
			//同时显示此线的值
			pos = pDoc->w_vecmap.find(i);
			x1 = pos->second.x;
			y1 = pos->second.y;
			pDC->MoveTo(x1, y1);
			pos = pDoc->w_vecmap.find(w_closedge[i].vex);
			x2 = pos->second.x;
			y2 = pos->second.y;
			pDC->LineTo(x2, y2);
			str.Format("%d", pDoc->w_arcs[i][w_closedge[i].vex]);
			pDC->TextOut( (x1+x2)/2-2,(y1+y2)/2-2,str);

			//输出找到的最小生成树
			str = "——";
			pDC->TextOut(x0+i*100,y0, pDoc->w_vecname[i]);
			pDC->TextOut(x0+i*100+20,y0, str);
			pDC->TextOut(x0+i*100+50,y0, pDoc->w_vecname[w_closedge[i].vex]);		
		}
	}
	//画数组


	pDC->SelectObject(oldpen);
}

/////////////////////////////////////////////////////////////////////////////
// CMyView diagnostics

#ifdef _DEBUG
void CMyView::AssertValid() const
{
	CView::AssertValid();
}

void CMyView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CMyDoc* CMyView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CMyDoc)));
	return (CMyDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CMyView message handlers

void CMyView::W_Nextspan() //寻找下一个点
{	
	CMyDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);

	static int i=0;
	int max;
	int j,k=0;
	if(i<pDoc->w_vexnum){
		max=MAXINT;
		for(j=0; j<pDoc->w_vexnum; ++j)  {//求出下一个结点
			if(w_closedge[j].value>0 && max>w_closedge[j].value)
			{
				k=j;
				max=w_closedge[j].value;
			}
		}
		w_closedge[k].value=0;
		for(j=0;j<pDoc->w_vexnum; ++j){
			if(pDoc->w_arcs[k][j]<w_closedge[j].value){
				w_closedge[j].vex=k;
				w_closedge[j].value=pDoc->w_arcs[k][j];
			 }//if
		}//for

		++i;
	}//end_if
	else if(i == pDoc->w_vexnum) {//是又一次开始的话
		i = 0;
		pDoc->w_isbegindraw = true;	
	}
	else
		++i;

}

void CMyView::W_InitClosedge(CMyDoc* pDoc)//初始化w_closedge
{
	//初始化w_closedge
	w_start = 0;
	for(int i=0; i<pDoc->w_vexnum; ++i){
		w_closedge[i].vex = w_start;
		w_closedge[i].value = pDoc->w_arcs[w_start][i];
	}
}

void CMyView::OnLButtonUp(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	

	if(w_ishandle){	
		W_Nextspan(); //寻找下一个结点
		Invalidate();
		CView::OnLButtonUp(nFlags, point);
	}
}

void CMyView::OnHandle() //手动演示
{
	// TODO: Add your command handler code here
	CMyDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);

	w_ishandle = true;
	pDoc->w_isbegindraw = true;

	KillTimer(1);
	
}

void CMyView::OnAuto() //自动演示
{
	// TODO: Add your command handler code here
	CMyDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	if(!w_ishandle){
		w_isstop = !w_isstop;
	}
	else if(w_ishandle){
		
		w_ishandle = false;
		w_isstop = false;
		pDoc->w_isbegindraw = true;

		SetTimer(1,1000,NULL);
	}
	
}

void CMyView::OnTimer(UINT nIDEvent) 
{
	// TODO: Add your message handler code here and/or call default
	if(!w_ishandle && !w_isstop){	
		W_Nextspan(); //寻找下一个结点
		Invalidate();
	}
	
	CView::OnTimer(nIDEvent);
}

void CMyView::OnHelp() //操作帮助
{
	// TODO: Add your command handler code here
	HelpDlg help;
	help.DoModal();
	
}


void CMyView::OnChar(UINT nChar, UINT nRepCnt, UINT nFlags) 
{
	// TODO: Add your message handler code here and/or call default
	CView::OnChar(nChar, nRepCnt, nFlags);
}

void CMyView::OnEnData() //输入数据
{
	// TODO: Add your command handler code here
	CMyDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);

	char token[10];
	CString str;
	int i = 0,
		j=0,
		k=0;

	int arcnum,
		vexnum;
	vector<CString> vecname;
	int arcs[10][10];
	
	AddDlg adddlg;
	if(adddlg.DoModal())
	{
		//修改图的值
		arcnum = adddlg.m_arcnum;
		vexnum = adddlg.m_vexnum;

		if(arcnum<=0)
		{
			MessageBox("你输入的顶点数错误！");
			return ;
		}

		//改变vecname
		for(i=0; i<vexnum; ++i)
		{
			k=0;
			if(adddlg.m_vnamestr.GetLength()<=j)
			{
				MessageBox("你输入的顶点和顶点数有冲突！");
				return;
				
			}
			while(adddlg.m_vnamestr.GetLength()>j && adddlg.m_vnamestr[j]==' ') ++j;
			while(adddlg.m_vnamestr.GetLength()>j && adddlg.m_vnamestr[j]!=',' && adddlg.m_vnamestr[j]!=' ')
			{
				token[k++] = adddlg.m_vnamestr[j];
				++j;
			}
			token[k] = '\0';
			++j;
			if(k>0){
				++i;
				str = token;
				vecname.push_back(str);
			}
		}
/*
		//改变arc值
		j = 0;
		k = 0;
		while(j<adddlg.m_arcstr.GetLength()){
			while()
		}

*/
		//从新画图形
		pDoc->w_arcnum = arcnum;
		pDoc->w_vexnum = vexnum;

		pDoc->w_vecname.clear();
		pDoc->w_vecname.resize(vecname.size());
		copy(pDoc->w_vecname.begin(), pDoc->w_vecname.begin(), vecname.begin());

		for(i=0; i<10; ++i)
			for(j=0; j<10; ++j)
				pDoc->w_arcs[i][j] = arcs[i][j];

		int x,y;
		double pi = 3.1415926535;
		double a = 2*pi/vexnum;
		for(int i=0; i<vexnum; ++i){ 
			x = int(XX+R1*sin(i*a));
			y = int(YY-R1*cos(i*a));
			pDoc->w_vecmap.insert(pair<int,CPoint>(i,CPoint(x,y)));
		}


		w_isstop = true;
		w_ishandle = true;
		pDoc->w_isbegindraw = true;
	
	}
	
}