mapvertex.cpp

常用算法与数据结构原代码

// MapVertex.cpp: implementation of the CMapVertex class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Map.h"
#include "MapVertex.h"
#include "CntrItem.h"

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

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
IMPLEMENT_SERIAL(CMapVertex,CObject,0)
CMapVertex::CMapVertex()
{
	next=NULL;
}
CMapVertex::CMapVertex(CMapVertex&other)
{
/*	m_msg=other.m_msg;
	m_VertexKey=other.m_VertexKey;
	POSITION pos = other.m_next.GetStartPosition();
	UINT key;
	float power;
	while(pos!=NULL)
	{
		other.m_next.GetNextAssoc(pos,key,power);
		m_next[key]=power;
	}
	pos = other.m_pre.GetStartPosition();
	while(pos!=NULL)
	{
		other.m_pre.GetNextAssoc(pos,key,power);
		m_pre[key]=power;
	}*/
	*this=other;
}
CMapVertex::~CMapVertex()
{

}
CMapVertex&CMapVertex:: operator=(CMapVertex&other)
{
	m_msg=other.m_msg;
	m_VertexKey=other.m_VertexKey;
	POSITION pos = other.m_next.GetStartPosition();
	UINT key;
	float power;
	while(pos!=NULL)
	{
		other.m_next.GetNextAssoc(pos,key,power);
		m_next[key]=power;
	}
	pos = other.m_pre.GetStartPosition();
	while(pos!=NULL)
	{
		other.m_pre.GetNextAssoc(pos,key,power);
		m_pre[key]=power;
	}
	return*this;
}
void CMapVertex::Serialize(CArchive &ar)
{
	if(ar.IsStoring())
	{
		ar<<m_VertexKey;
		ar<<m_msg;
	}
	else
	{
		ar>>m_VertexKey;
		ar>>m_msg;
	}
	m_pre.Serialize(ar);
	m_next.Serialize(ar);
	CObject::Serialize(ar);
}
//////////////////////////////////////////////////////////////////////
IMPLEMENT_SERIAL(CMyMap,CObject,0)
CMyMap::CMyMap()
{
	m_TopVertex=NULL;
	m_nVerbflag=m_VertexNum=m_NewKey=0;
}

CMyMap::~CMyMap()
{
	if(m_VertexNum!=0)
	{
		CMapVertex *temp=m_TopVertex;
		while(m_TopVertex!=NULL)
		{
			m_TopVertex=m_TopVertex->next;
			delete temp;
			temp=m_TopVertex;
		}
	}
}

void CMyMap::Serialize(CArchive &ar)
{
	CMapVertex*temp=m_TopVertex;
	if(ar.IsStoring())
	{
		ar<<m_NewKey;
		ar<<m_VertexNum;
		for(UINT i=0;i<m_VertexNum;i++)
		{
			temp->Serialize(ar);
			temp=temp->next;
		}
	}
	else
	{
		ar>>m_NewKey;
		ar>>m_VertexNum;
		if(m_VertexNum!=0)
		{
			temp=m_TopVertex=new CMapVertex;
			m_TopVertex->Serialize(ar);			
		}
		for(UINT i=1;i<m_VertexNum;i++)
		{
			temp->next=new CMapVertex;
			temp=temp->next;
			temp->Serialize(ar);
		}
	}
	CObject::Serialize(ar);
}

void CMyMap::AddVertex(CMapVertex *pVertex)
{
	pVertex->AssertValid();
	pVertex->next=m_TopVertex;
	m_TopVertex=pVertex;
	m_VertexNum++;
}

void CMyMap::DelVertex(UINT key)
{
	CMapVertex*last=m_TopVertex,*temp=last->next;
	if(last->m_VertexKey==key)
	{
		m_TopVertex=temp;
		delete last;
		m_VertexNum--;
	}
	else
	{
		last->m_next.RemoveKey(key);
		last->m_pre.RemoveKey(key);
	}
	while(temp!=NULL)
	{
		if(temp->m_VertexKey==key)
		{
			last->next=temp->next;
			delete temp;
			m_VertexNum--;
			temp=last->next;
		}
		else
		{
			temp->m_next.RemoveKey(key);
			temp->m_pre.RemoveKey(key);
			temp=temp->next;
		}
	}		
}

CMapVertex* CMyMap::GetVertex(UINT key)
{
	CMapVertex*temp=m_TopVertex;
	while(temp!=NULL)
	{
		if(temp->m_VertexKey==key)return temp;
		temp=temp->next;
	}
	return NULL;
}
void CMyMap::Reset()
{
	m_TopVertex=NULL;
	m_VertexNum=m_NewKey=0;
}

void CMyMap::WithTraval()
{
	if(m_TopVertex==NULL)return;
	CMapVertex*temp=m_TopVertex;
	CList<CMapVertex*,CMapVertex*>Queue;
	CString msg;
	int id=0;
	while(temp!=NULL)
	{
		temp->flag=0;
		temp->m_msg.Empty();
		temp=temp->next;
	}
	Queue.AddTail(m_TopVertex);
Again:
	while(!Queue.IsEmpty())
	{
		temp=Queue.RemoveHead();
		if(temp->flag==0)
		{
			temp->flag=1;
			temp->m_msg.Format("%d",id++);
			POSITION pos=temp->m_next.GetStartPosition();
			while(pos!=NULL)
			{
				UINT key;
				float e;
				temp->m_next.GetNextAssoc(pos,key,e);
				CMapVertex*t=GetVertex(key);
				if(t->flag==0)
				{
					Queue.AddTail(t);
				}
			}
		}
	}
	temp=m_TopVertex;
	while(temp!=NULL)
	{
		if(temp->flag==0)
		{
			Queue.AddTail(temp);
			goto Again;
		}
		temp=temp->next;
	}

}

void CMyMap::DepthTraval()
{
	if(m_TopVertex==NULL)return;
	CMapVertex*temp=m_TopVertex;
	CList<CMapVertex*,CMapVertex*>Stack;
	CString msg;
	int id=0;
	while(temp!=NULL)
	{
		temp->flag=0;
		temp->m_msg.Empty();
		temp=temp->next;
	}
	Stack.AddTail(m_TopVertex);
Again:
	while(!Stack.IsEmpty())
	{
		temp=Stack.RemoveTail();
		if(temp->flag==0)
		{
			temp->flag=1;
			temp->m_msg.Format("%d",id++);
			POSITION pos=temp->m_next.GetStartPosition();
			while(pos!=NULL)
			{
				UINT key;
				float e;
				temp->m_next.GetNextAssoc(pos,key,e);
				Stack.AddTail(GetVertex(key));
			}
		}
	}
	temp=m_TopVertex;
	while(temp!=NULL)
	{
		if(temp->flag==0)
		{
			Stack.AddTail(temp);
			goto Again;
		}
		temp=temp->next;
	}

}

bool CMyMap::TopSort()
{
	if(m_TopVertex==NULL)return true;
	CMapVertex*temp=m_TopVertex;
	CList<CMapVertex*,CMapVertex*>Queue;
	CString msg;
	int id=0;
	while(temp!=NULL)
	{
		temp->flag=temp->m_pre.GetCount();
		temp->m_msg.Empty();
		if(temp->flag==0)
		{
			Queue.AddTail(temp);
		}
		temp=temp->next;
	}
	while(!Queue.IsEmpty())
	{
		temp=Queue.RemoveHead();
		temp->m_msg.Format("%d",id++);
		POSITION pos=temp->m_next.GetStartPosition();
		while(pos!=NULL)
		{
			UINT key;
			float e;
			temp->m_next.GetNextAssoc(pos,key,e);
			CMapVertex*t=GetVertex(key);
			if(t->flag--==1)
			{
				Queue.AddTail(t);
			}
		}
	}
	temp=m_TopVertex;
	while(temp!=NULL)
	{
		if(temp->flag!=0)return false;
		temp=temp->next;
	}
	return true;
}

CString CMyMap::MinDistance(UINT fir, UINT sec,float&distance)
{
	static UINT id=0;
	float overflow,temp=0;
	CString result,str;
	distance=overflow=1/temp;
	CMapVertex *vertex=GetVertex(fir);
	if(fir==sec)
	{
		distance=0;
		return vertex->m_msg;
	}
	if(vertex->m_next.GetCount()==0)
	{
		return "";
	}
	POSITION pos=vertex->m_next.GetStartPosition();
	while(pos!=NULL)
	{
		UINT key;
		float fPower;
		vertex->m_next.GetNextAssoc(pos,key,fPower);
		str=MinDistance(key,sec,temp);
		if(temp==overflow)continue;
		temp+=fPower;
		if(distance>temp)
		{
			distance=temp;
			result=vertex->m_msg+" "+str;
		}
	}
	return result;
}

void CMyMap::ClearMsg()
{
	CMapVertex *temp=m_TopVertex;
	while(temp!=NULL)
	{
		temp->m_msg.Empty();
		temp=temp->next;
	}

}