~childview.~cpp

研究生算法作业著名的旅行者问题

// ChildView.cpp : implementation of the CChildView class
//

#include "stdafx.h"
#include "Traveler.h"
#include "ChildView.h"
#include "math.h"

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

/////////////////////////////////////////////////////////////////////////////
// CChildView

CChildView::CChildView()
{
	m_cityCount = 0;
	m_bmCity.LoadBitmap(IDB_CITY);
	m_bmCity.GetBitmap(&bmp);
	lsAddingList = true;
	m_minDistence = 0;
	a = NULL;
	b = NULL;
	order = NULL;

}

CChildView::~CChildView()
{
	ReleaseMemory();
}


BEGIN_MESSAGE_MAP(CChildView,CWnd )
	//{{AFX_MSG_MAP(CChildView)
	ON_WM_PAINT()
	ON_COMMAND(ID_BEGIN, OnBegin)
	ON_COMMAND(ID_Reset, OnReset)
	ON_WM_LBUTTONUP()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()


/////////////////////////////////////////////////////////////////////////////
// CChildView message handlers

BOOL CChildView::PreCreateWindow(CREATESTRUCT& cs) 
{
	if (!CWnd::PreCreateWindow(cs))
		return FALSE;

	cs.dwExStyle |= WS_EX_CLIENTEDGE;
	cs.style &= ~WS_BORDER;
	cs.lpszClass = AfxRegisterWndClass(CS_HREDRAW|CS_VREDRAW|CS_DBLCLKS, 
		::LoadCursor(NULL, IDC_ARROW), HBRUSH(COLOR_WINDOW+1), NULL);

	return TRUE;
}

void CChildView::OnPaint() 
{
	CPaintDC dc(this); // device context for painting
	
	// TODO: Add your message handler code here
	if(m_cityCount<=0)
		return;

	CDC bmDC;
	bmDC.CreateCompatibleDC(&dc);
	bmDC.SelectObject( &m_bmCity);

	
	POSITION pos = m_cityList.GetHeadPosition();
	
	//画所有的城市
	int cityindex=0;
	while(pos)
	{

		POINT curpt = m_cityList.GetNext(pos);
		dc.BitBlt(curpt.x-bmp.bmWidth/2,curpt.y-bmp.bmHeight/2,bmp.bmWidth,bmp.bmHeight,&bmDC,0,0,SRCCOPY);
		CString index;
		index.Format("%d",cityindex++);
		dc.TextOut(curpt.x,curpt.y-bmp.bmHeight/2-5,index);
	}

	
	//画所有的路线
	for(int j = 0;j<m_cityCount;j++)
	{
		POINT curpt = m_cityList.GetAt(m_cityList.FindIndex(j));
		for(int i = 0;i<j;i++)
		{
			dc.MoveTo(curpt);
			POINT prev = m_cityList.GetAt(m_cityList.FindIndex(i));
			if (!lsAddingList)
			{
				DrawDistence(curpt,prev,b[i][j],dc);
			}
			dc.LineTo(prev);
		}
	}
	//画最佳路线
	
	CPen pen(PS_SOLID,2,RGB(255,0,0));
	CPen *pOldPen = dc.SelectObject(&pen);
	if(order)
	{
		POINT head,curpt,prvpt;
		head = prvpt = m_cityList.GetAt(m_cityList.FindIndex(order[1]));
		dc.MoveTo(prvpt);
		dc.Arc(prvpt.x-bmp.bmWidth/2,prvpt.y-bmp.bmHeight/2,prvpt.x+bmp.bmWidth/2,prvpt.y+bmp.bmHeight/2,prvpt.x-bmp.bmWidth/2,prvpt.y-bmp.bmHeight/2,prvpt.x-bmp.bmWidth/2,prvpt.y-bmp.bmHeight/2);
		for(int i = 2;i<=m_cityCount;i++)
		{
			prvpt = curpt;
			curpt = m_cityList.GetAt(m_cityList.FindIndex(order[i]));
			dc.LineTo(curpt);
			DrawDistence(prvpt,curpt,b[order[i-1]][order[i]],dc);
		}
		dc.LineTo(head);
	}
	dc.SelectObject(pOldPen);
	
	CString result;
	result.Format("最短路径长度%d",m_minDistence);
	dc.TextOut( 10,10,result);
	// Do not call CWnd::OnPaint() for painting messages
}


void CChildView::OnBegin() 
{
	// TODO: Add your command handler code here
	
	lsAddingList = false;
	m_cityCount = m_cityList.GetCount();
	if (m_cityCount<=0)
		return;
	ReleaseMemory();
	MallocMemory();
	
	BeginWaitCursor();
	m_minDistence = trav.TSP(b,order,m_cityCount);
	EndWaitCursor();

	Invalidate();
}

void CChildView::OnReset() 
{
	// TODO: Add your command handler code here
	m_cityList.RemoveAll();
	m_cityCount=0;
	lsAddingList = true;
	m_minDistence=0;
	ReleaseMemory();
	Invalidate();
}

void CChildView::OnLButtonUp(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	if (lsAddingList)
	{
		m_cityList.AddTail(point);
		m_cityCount++;
	}
/*
	//画城市
	CClientDC dc(this);
	CDC bmDC;
	bmDC.CreateCompatibleDC(&dc);
	bmDC.SelectObject( &m_bmCity);
	dc.BitBlt(point.x-bmp.bmWidth/2,point.y-bmp.bmHeight/2,bmp.bmWidth,bmp.bmHeight,&bmDC,0,0,SRCCOPY);
	dc.TextOut(point.x,point.y-bmp.bmHeight/2-5,m_cityCount);
	//画路线
	for(int i = 0;i<m_cityCount-1;i++)
	{	dc.MoveTo(point);
		POINT curpt = m_cityList.GetAt(m_cityList.FindIndex(i));
		dc.LineTo(curpt);
	}
	*/
	Invalidate();
	CWnd ::OnLButtonUp(nFlags, point);
}

void CChildView::ReleaseMemory()
{
	if (order)
	{
		delete[] order;
		order = NULL;
	}
	if (a)
	{
		delete[] a;
		a = NULL;
	}
	if (b)
	{
		delete[] b;
		b = NULL;
	}

}

void CChildView::DrawDistence(POINT curpt, POINT prev, int distence,CPaintDC &dc)
{
	CString str;
	str.Format("%d",distence);

	double angle =180/3.14*atan((1.0*curpt.y-prev.y)/(prev.x-curpt.x));
	if (angle < 0)
		angle = 360+angle;
	CFont font;
	font.CreateFont( 0,0,10*angle,0,FW_NORMAL,false,0,0,
		DEFAULT_CHARSET,OUT_DEFAULT_PRECIS,
		CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,FF_DONTCARE,"宋体");
	UINT old = dc.GetTextAlign();
	dc.SetTextAlign(TA_BASELINE);	
	CFont *oldfont = dc.SelectObject(&font);
	dc.TextOut((curpt.x+prev.x)/2,(curpt.y+prev.y)/2,str);
	dc.SelectObject(oldfont);
	dc.SetTextAlign(old);
}

void CChildView::MallocMemory()
{
	a = new int[m_cityCount * m_cityCount];
	b = new int *[m_cityCount];

	for(int i=0;i<m_cityCount;i++)
		b[i]=&a[i*m_cityCount];

	//邻接矩阵
	for(int p=0;p<m_cityCount; p++)
	{
		b[p][p] = 0;
		for(int q = p+1;q<m_cityCount;q++)
			b[p][q]=b[q][p]= rand()+1;
	}

	order = new int[m_cityCount + 1];
}