picture.cpp

数据结构中的图最短路径问题

// Picture.cpp: implementation of the CPicture class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "图最短路径.h"
#include "Picture.h"
#include "math.h"

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

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CPicture::CPicture()
{ 
	srand(time(0));
	m_pData = NULL;
	m_npTable = NULL;
	m_pShort = NULL;
	m_nFind = 0;
	m_nSize = 0;
}

CPicture::~CPicture()
{
	delete [] m_pData;
	delete [] m_npTable;
	delete [] m_pShort;
}

bool CPicture::Create(int nSize)
{
	if(m_nSize>0)
		return false;
	if(nSize<=0||nSize>MAX)
		return false;
	m_pData = new PICTURENODE[nSize];
	m_npTable= new PICTURELINE[nSize][MAX];
	m_pShort = new PICTURESHORT[nSize];
	if(!m_pData || !m_npTable || !m_pShort)
		return false;
    m_nSize = nSize;
	m_nFind = 0;
	for(int i=0;i<nSize;i++)
	{
		m_pData[i].letter =	'A'+i;
		m_pData[i].flage=false;
	}
	return true;
}

bool CPicture::Destroy()
{
	delete [] m_pData;
	delete [] m_npTable;
	delete [] m_pShort;
	m_pData = NULL;
	m_npTable = NULL;
	m_pShort = NULL;
	m_nFind = 0;
	m_nSize = 0;
	return true;
}

bool CPicture::Random()
{
	PICTURELINE value;
	if(m_nSize<=0)
		return false;
	for(int i=0;i<m_nSize;i++)
	{
		for(int j=i;j<m_nSize;j++)
		{
			value.number = rand()%150+1;
			if(value.number>=100)
				value.number=-1;
			SetEdge(i,j,value);
		}
	}
	return true;
}

bool CPicture::SetEdge(int nStarNode,int nEndNode,PICTURELINE nValue)
{
	if(m_nSize<=0)
		return false;
	if(nStarNode<0 || nStarNode>=m_nSize || nEndNode<0 || nEndNode>=m_nSize)
		return false;
	if(nEndNode==nStarNode)
	{	
		m_npTable[nStarNode][nEndNode].number=0;
		return true;
	}
	m_npTable[nStarNode][nEndNode]=nValue; 
	m_npTable[nEndNode][nStarNode]=nValue;
	return true;
}

bool CPicture::GetEdge(int nStarNode,int nEndNode,PICTURELINE &nValue)
{
	if(m_nSize<=0)
		return false;
	if(nStarNode<0 || nStarNode>=m_nSize || nEndNode<0 || nEndNode>=m_nSize)
		return false; 
	if(nEndNode==nStarNode)
	{
		nValue.number=0;
		return true;
	}
	nValue=m_npTable[nStarNode][nEndNode]; 
	return true;
}

bool CPicture::Perform(int nStarNode)
{
	int min=MAXVALUE,positionI,positionJ;
	if(m_nSize<=0)
		return false;
	if(nStarNode>-1)
	{
		m_nFind = 1;
		for(int i=0;i<m_nSize;i++)
			m_pData[i].flage = false;
		m_pData[nStarNode].flage=true;
		m_pShort[0].position = nStarNode;
		m_pShort[0].length=0;
		m_pShort[0].parent=-1;
		m_pShort[0].count = 1;
		return true;
	}
	if(m_nFind==m_nSize)
		return false;
	for(int i=0;i<m_nFind;i++)
	{
		for(int j=0;j<m_nSize;j++)
		{
			if(m_npTable[m_pShort[i].position][j].number<=0)
				continue;
			if(m_pData[j].flage)
				continue;
			if(min>m_npTable[m_pShort[i].position][j].number+m_pShort[i].length)
			{
				min=m_npTable[m_pShort[i].position][j].number+m_pShort[i].length;
				positionI=i;
				positionJ=j;
			}
		}
	}
	if(min==MAXVALUE)
		return false;
	m_pData[positionJ].flage = true;
	m_pShort[m_nFind].position = positionJ;
	m_pShort[m_nFind].length = min;
	m_pShort[m_nFind].parent = positionI;
	m_pShort[m_nFind].count = m_pShort[positionI].count+1;
	m_nFind++;
	return true;
}

bool CPicture::Show(CDC * pDC,CRect * pRect)
{
	if(m_nSize<=0)
		return false;
	CPoint * point;
	CPoint midPoint;
	int r;
 	point=new CPoint[m_nSize];
 	r= pRect->Width();
	if(r > pRect->Height())
		r=pRect->Height();
	r=r/2;
 	midPoint.x=pRect->left + r;
	midPoint.y=pRect->top +r;
	for(int i=0;i<m_nSize;i++)
	{ 
		point[i].x=(int)(midPoint.x+r*cos(2.0*3.14/m_nSize*i));
		point[i].y=(int)(midPoint.y-r*sin(2.0*3.14/m_nSize*i));
	}

	for(i=0;i<m_nSize;i++)
		for(int j=i+1;j<m_nSize;j++)
			if(m_npTable[i][j].number>0)
			{
				pDC->MoveTo(point[i]);
				pDC->LineTo(point[j]);
			}
	CPen pen,*pOldpen;
	pen.CreatePen(PS_SOLID,3,RGB(0,0,255));
	pOldpen=pDC->SelectObject(&pen);
    for(i=m_nFind-1;i>0;i--)
	{
		pDC->MoveTo(point[m_pShort[i].position]);
		pDC->LineTo(point[m_pShort[m_pShort[i].parent].position]);
	}
	pDC->SelectObject(pOldpen);
	CBrush brush(RGB(255,255,0)),* pOldbrush;
	pOldbrush=pDC->SelectObject(&brush);
	for(i=0;i<m_nSize;i++)
	{
		if(m_pData[i].flage)
		{
			pDC->SelectObject(&brush);
			pDC->SetBkColor(RGB(255,255,0));
		}
		else
		{
			pDC->SelectObject(pOldbrush);
			pDC->SetBkColor(RGB(255,255,255));
		}
		pDC->Ellipse(point[i].x-15,point[i].y-15,point[i].x+15,point[i].y+15);
		pDC->TextOut(point[i].x-5,point[i].y-10,m_pData[i].letter);
	}
	CString string;
	pDC->SetBkMode(TRANSPARENT);
	for(i=0;i<m_nSize;i++)
		for(int j=i+1;j<m_nSize;j++)
			if(m_npTable[i][j].number>0)
			{
				string.Format("%d",m_npTable[i][j].number);
     			pDC->TextOut(point[i].x+(point[j].x-point[i].x)/5-6,
					point[i].y+(point[j].y-point[i].y)/5-6,string);
			}

	for(i=1;i<m_nFind;i++)
	{
		int count;
		count=m_pShort[i].count;
		for(int j=i;j>=0;)
		{
			pDC->TextOut(pRect->right+20+count*20,pRect->top+i*20,m_pData[m_pShort[j].position].letter);
			count--;
			j=m_pShort[j].parent;
		}
		CString string;
		string.Format("%d",m_pShort[i].length);
		pDC->TextOut(pRect->right+20+10*20,pRect->top+i*20,string);
	}
	return true;
}