collegemap.cpp

这是我写的数据结构的课设

// CollegeMap.cpp: implementation of the CCollegeMap class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "CollegeWizard.h"
#include <afx.h>//包含类CObject
#include "CollegeMap.h"
#include "CollegeWizardDoc.h"
#include "CollegeWizardView.h"
#include "VertexStack.h"
#include "MainFrm.h"
#include "Vertex.h"
#include "Path.h"

#define MAX 1.7E+308  //浮点数的最大值

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

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

CCollegeMap::CCollegeMap()
{
	m_totalOfVertexs = 0;	//总景点、建筑点数
	m_totalOfPaths = 0;		//总道路数
	vertexList  = NULL;		//存储景点、建筑的链表	
	m_VisitedTag = FALSE;	//访问标志
}

CCollegeMap::~CCollegeMap()
{
//未完成
}
/////////////////////////////////////////////////////////////////////////////
//插入一个景点或建筑
BOOL CCollegeMap::InsertVertex(CVertex * vertex)
{
	vertex->next = vertexList;
	vertexList = vertex;
	m_totalOfVertexs++;
	return TRUE;
}
/////////////////////////////////////////////////////////////////////////////
//删除景点、建筑
BOOL CCollegeMap::DeleteVertex(CVertex *object)
{
	CVertex* vertex = vertexList;
	//先删除与该点相连的所有道路
	while(object->paths)
	{
		//调用删除道路函数，删除与该点相连的道路
		DeletePath(object->paths);
	}
	//如果该点为链中第一个点
	if(object == vertexList)
		vertexList = object->GetNext();//从链中删除该点
	else//如果该点不是链中第一个点
	{
		//用vertex得到object的前一个点的位置
		while(vertex->GetNext() != object)
		{
			vertex = vertex->GetNext();
		}
		//从链中删除该点
		vertex->SetNext(object->GetNext());
	}
	delete object;//释放该点空间
	m_totalOfVertexs--;//总点数减一
	return TRUE;
}
/////////////////////////////////////////////////////////////////////////////
//插入一条道路
BOOL CCollegeMap::InsertPath(CPath * path)
{
	//将新的道路的访问标志设成与其他道路一致
	if(path->GetIsVisited() != m_VisitedTag)
		path->SetIsVisited();
	//得到道路的两个端点
	CPoint point1 = path->GetLocation1();
	CPoint point2 = path->GetLocation2();
	CVertex *temp = vertexList;
	int status = 0;//标记找到几个顶点
	CVertex *temp1,*temp2;//记录找到的两顶点
	//查询道路两端点在链中的位置，并用temp1和temp2记录
	while(temp != NULL)
	{
		if(temp->GetLocation() == point1)
		{
			status++;
			temp1 = temp;
		}
		if(temp->GetLocation() == point2)
		{
			status++;
			temp2 = temp;
		}
		if(status == 2)
		{
			//将道路插入图中
			path->m_path1 = temp1->paths;
			temp1->paths = path;
			
			path->m_path2 = temp2->paths;
			temp2->paths = path;
			//总点数加一
			m_totalOfPaths++;
			return TRUE;
		}
		temp = temp->next;
	}

	return FALSE;
}
/////////////////////////////////////////////////////////////////////////////
//删除道路
BOOL CCollegeMap::DeletePath(CPath *path)
{
	CVertex* vertex = vertexList;
	CPath* path1 = NULL;//记录指向该路径的两个指针之一
	CPath* path2 = NULL;//记录指向该路径的两个指针之一
	CPath* temp = NULL;//临时变量
	//设置访问标志
	SetVisitedTag();
	//查找指向该路径的两个指针
	//此次遍历将不记录目标道路直接连在vertex->paths的情况：
	//即vertex->paths == path
	while(vertex)
	{
		//temp指向与vertex相连的道路
		temp = vertex->paths;
		//遍历与vertex相连的道路
		while(temp)
		{
			if(temp->GetIsVisited() != GetVisitedTag())	//如果尚未访问
			{
				//如果该条道路的指针之一指向目标道路则path1或path2用记录
				if((temp->GetPath1() == path) || (temp->GetPath2() == path))
				{
					if(!path1)
						path1 = temp;
					else
						path2 = temp;
				}
				temp->SetIsVisited();	//设置访问标志
			}
			//遍历下一条与vertex相连的道路
			if(vertex->GetLocation() == temp->GetLocation1())
				temp = temp->GetPath1();
			else
				temp = temp->GetPath2();				
		}
		vertex = vertex->GetNext();//遍历下一个顶点
	}
	//删除该路径，此时有三种情况：
	//CASE1：path1和path2均为空
	//CASE2: path1非空，path2为空
	//CASE1：path1和path2均不为空（不可能有path2非空，path1为空）
	CPath* p = NULL;	//临时指针,记录另一路径
	
	if(path1)//path1非空
	{
		if(path1->GetPath1() == path)//path1的GetPath1()指向path
		{
			//寻找path中指向的下一条路径,从path1中将path删除
			if(path->GetLocation1() == path1->GetLocation1())
			{
				path1->SetPath1(path->GetPath1());
				//记录path的另一个指针，以方便path2删除path
				p = path->GetPath2();
			}
			else
			{
				path1->SetPath1(path->GetPath2());
				//记录path的另一个指针，以方便path2删除path
				p = path->GetPath1();
			}
		}
		else	//path1的GetPath2()指向path
		{
			//寻找path中指向的下一条路径,从path1中将path删除
			if(path->GetLocation1() == path1->GetLocation2())
			{
				path1->SetPath2(path->GetPath1());
				//记录path的另一个指针，以方便path2删除path
				p = path->GetPath2();
			}
			else
			{
				path1->SetPath2(path->GetPath2());
				//记录path的另一个指针，以方便path2删除path
				p = path->GetPath1();
			}
		}
	}
	else//path1为空,此时即CASE1：path1和path2均为空
	{
		//用vertex查找是哪个点的paths直接指向path		
		vertex = vertexList;
		while(vertex)
		{
			//将path从与vertex相邻的路径中删除
			if(vertex->paths == path)
			{
				if(path->GetLocation1() == vertex->GetLocation())
					vertex->paths = path->GetPath1();
				else
					vertex->paths = path->GetPath2();
				break;
			}
			else
				vertex = vertex->GetNext();//遍历下一个点
		}
	}
	if(path2)//path2非空
		//将path从path2中删除
		if(path2->GetPath1() == path)
			path2->SetPath1(p);
		else path2->SetPath2(p);	
	else//path2为空,此时即CASE1：path1和path2均为空
	{	//但程序运行到此，path1已经得到新的值，且vertex仍然记录着path1的顶点的位置
		if(vertex)
		{
			//用vertex查找下一个paths直接指向path的点
			vertex = vertex->GetNext();
			while(vertex)
			{
				//将path从与vertex相邻的路径中删除
				if(vertex->paths == path)
				{
					if(path->GetLocation1() == vertex->GetLocation())
						vertex->paths = path->GetPath1();
					else
						vertex->paths = path->GetPath2();
					break;
				}
				else
					vertex = vertex->GetNext();//遍历下一个点
			}
		}
		else		//即CASE2: path1非空，path2为空
		{
			//用vertex查找是哪个点的paths直接指向path
			vertex = vertexList;
			while(vertex)
			{
				//将path从与vertex相邻的路径中删除
				if(vertex->paths == path)
				{
					if(path->GetLocation1() == vertex->GetLocation())
						vertex->paths = path->GetPath1();
					else
						vertex->paths = path->GetPath2();
					break;
				}
				else
					vertex = vertex->GetNext();//遍历下一个点
			}
		}	
	}
	delete path;	//释放该道路的空间
	m_totalOfPaths--;//总点数减一
	return TRUE;	
}
/////////////////////////////////////////////////////////////////////////////
int CCollegeMap::GetTotalOfVertexs()
{
	return m_totalOfVertexs;
}
/////////////////////////////////////////////////////////////////////////////
void CCollegeMap::SetTotalOfVertexs(int totalOfVertexs)
{
	m_totalOfVertexs = totalOfVertexs;
}
/////////////////////////////////////////////////////////////////////////////
int CCollegeMap::GetTotalOfPaths()
{
	return m_totalOfPaths;
}
/////////////////////////////////////////////////////////////////////////////
void CCollegeMap::SetTotalOfPaths(int totalOfPaths)
{
	m_totalOfPaths = totalOfPaths;
}
/////////////////////////////////////////////////////////////////////////////
CVertex * CCollegeMap::GetVertexList()
{
	return vertexList;
}
/////////////////////////////////////////////////////////////////////////////
void CCollegeMap::SetVertexList(CVertex *VERTEXLIST)
{
	vertexList = VERTEXLIST;
}
/////////////////////////////////////////////////////////////////////////////
//得到选定景点\建筑的信息
BOOL CCollegeMap::GetInformation(CVertex* vertex)
{
	vertex->ShowInformation();	
	return TRUE;
}
/////////////////////////////////////////////////////////////////////////////
//判断选定两景点或建筑间是否存在最短路径,
//存在则返回TRUE,并在图中一红线绘出最短路径,在状态栏显示该最短路径总长度
//否则返回FALSE
//用的是Dijkstra算法，但本函数仅用到其中部分数据
BOOL CCollegeMap::GetShortestPath(CVertex *vertex1, CVertex *vertex2){
	
	CVertex* vertex = vertexList;	
	int v1,v2;//用来记录vertex1和vertex2在链中的位置
	int i = 0;
	//定位vertex1
	while(vertex && (vertex != vertex1))
	{
		vertex = vertex->GetNext();
		i++;
	}
	v1 = i;
	i = 0;
	vertex = vertexList;
	//定位vertex2
	while(vertex && (vertex != vertex2))
	{
		vertex = vertex->GetNext();
		i++;
	}
	v2 = i;
	//记录第个i节点的位置坐标，以便后面的程序中进行比较
	CPoint* point = new CPoint[m_totalOfVertexs];
	//int标志进入S的顺序，s为虚构的一个集合																						
	BOOL* s = new BOOL[m_totalOfVertexs];
	//int标志前一个节点
	int* p = new int[m_totalOfVertexs];
	//最短权值
	double* d = new double[m_totalOfVertexs];
	vertex = vertexList;
	//初始化s[],d[],p[],point[]
	for(i = 0; i < m_totalOfVertexs; i++)		
	{
		d[i] = MAX;
		s[i] = FALSE;
		p[i] = -1;
		point[i] = vertex->GetLocation();
		vertex = vertex->GetNext();
	}
	//如果vertex1或vertex2没有道路与之相连，则直接返回FALSE
	if(!vertex1->paths || !vertex2->paths)