collegemap.cpp

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

		return FALSE;
	CPath* path = vertex1->paths;
	//设置访问标志
	SetVisitedTag();
	while(path)	//预置与原顶点相邻接的顶点的距离，本程序中vertex1作为原顶点
	{
		//如果还没有访问
		if(path->GetIsVisited() != GetVisitedTag())
		{
			path->SetIsVisited();	//设置访问标志
			if(path->GetLocation1() == vertex1->GetLocation())
			{
				//预置与原顶点相邻接的顶点的距离，本程序中vertex1作为原顶点
				int k = GetIndex(point,m_totalOfVertexs,path->GetLocation2());
				d[k] = path->GetLength();
				p[k] = v1;
				path = path->GetPath1();
			}					
			else
			{
				//预置与原顶点相邻接的顶点的距离，本程序中vertex1作为原顶点
				int k = GetIndex(point,m_totalOfVertexs,path->GetLocation1());
				d[k] = path->GetLength();
				p[k] = v1;
				path = path->GetPath2();
			}				
		}
		else	//如果已经访问，继续遍历下一条边
		{
			if(path->GetLocation1() == vertex1->GetLocation())
				path = path->GetPath1();
			else path = path->GetPath2();
		}
	}	

	d[v1] = 0;	//v1导v1的距离为零，本程序中vertex1作为原顶点
	s[v1] = TRUE;//将v1加入集合s，

	int t;	//记录当前点
	for( i = 1; i < m_totalOfVertexs; i++)//m_totalOfVertexs - 1循环次，寻找剩余点中距离v1最近的点
	{
		double temp = MAX;
		t = v1;	//从v1开始
		//寻找剩余点中到v1最近的点，并用t记录
		for(int j = 0;j < m_totalOfVertexs;j ++)
			if(!s[j] && d[j] < temp)
			{
				t = j;
				temp = d[j];
			}
		if(t == v1)	break;	//找不到则结束循环
		s[t] = TRUE;		//否则将v1并入s集合
		path = GetPathAt(t);//得到与序号为t的顶点相连的路径
		//更新与序号为t的顶点相邻的顶点到v1的距离
		while(path)
		{
			vertex = GetVertexAt(t);//得到与序号为t的顶点
			int k;
			if(path->GetIsVisited() != GetVisitedTag())//如果还没有访问
			{
				path->SetIsVisited();//设置访问标志
				if(path->GetLocation1() == vertex->GetLocation())
				{
					k = GetIndex(point,m_totalOfVertexs,path->GetLocation2());
					//如果剩余集合中的点到v1的距离大于
					//t到v1的距离加上此点与t的距离之和，则此点到v1的距离更新为后者，
					//同时与此点相邻的点更新为t
					if(!s[k] && (d[k] > d[t] + path->GetLength()))
					{
						d[k] = d[t] + path->GetLength();
						p[k] = t;
					}
					path = path->GetPath1();//遍历下一条边
				}
				else
				{
					//如果剩余集合中的点到v1的距离大于
					//t到v1的距离加上此点与t的距离之和，则此点到v1的距离更新为后者，
					//同时与此点相邻的点更新为t
					k = GetIndex(point,m_totalOfVertexs,path->GetLocation1());
					if(!s[k] && (d[k] > d[t] + path->GetLength()))
					{
						d[k] = d[t] + path->GetLength();
						p[k] = t;
					}
					path = path->GetPath2();//遍历下一条边
				}
			}
			else//如已经访问过
			{	//遍历下一条边
				if(path->GetLocation1() == vertex->GetLocation())
					path = path->GetPath1();
				else
					path = path->GetPath2();
			}
		}
	}
	//绘图
	int j = v2;
	int k = p[v2];
	if(k == -1)
		return FALSE;
	while(j != v1)
	{
		//DrawPath()用来在给定两点序号时绘出两点间直线
		if(DrawPath(j,k))
		{
			j = k;
			k = p[k];	
		}
		else
			return FALSE;
	}		

	//显示路径权值
	//在状态栏显示提示信息
	CMainFrame * pWnd = (CMainFrame *)AfxGetMainWnd();
	pWnd->m_wndStatusBar.SetPaneInfo(0,ID_SEPARATOR,SBPS_NORMAL,625);
	CString strInfo;
	strInfo.Format("%s%f%s","此最短路径总长: ",d[v2],"米");
	pWnd->m_wndStatusBar.SetPaneText(0,strInfo);
	//删除申请空间
	delete s;
	delete p;
	delete d;
	delete point;
	return TRUE;
}
/////////////////////////////////////////////////////////////////////////////
//得到选定的两景点或建筑间的全部路径
BOOL CCollegeMap::GetAllPaths(CVertex* vertex1, CVertex *vertex2)
{	////////////极有可能死循环！！！！！！！！！！！！！！！111111
	////////////极有可能死循环！！！！！！！！！！！！！！！111111
	BOOL isFind = FALSE;
	CVertexStack vertexStack;	//栈
	CPath* path = vertex1->GetPaths();
	while(path)//将与vertex1相连的都进栈,如果是vertex2则仅仅绘出图形即可
	{
		if(vertex1->GetLocation() == path->GetLocation1())
		{
			if(vertex2->GetLocation() != path->GetLocation2())
			{
				CVertex* temp = vertexList;
				while(temp)
				{
					if(temp->GetLocation() == path->GetLocation2())
						break;
					temp = temp->GetNext();
				}
				if(temp)
					vertexStack.Push(temp);
			}
			else
			{
				//绘图
				CDC* pDC = g_pView->GetDC();
				COLORREF color = RGB(255,0,0);//定义一个颜色变量	
				CPen pen(PS_INSIDEFRAME,2,color);
				CPen* oldPen = pDC->SelectObject(&pen);
				pDC->MoveTo(path->GetLocation1());	
				pDC->LineTo(path->GetLocation2());
				pDC->SelectObject(oldPen);
				g_pView->ReleaseDC(pDC);
				isFind = TRUE;
			}
			path = path->GetPath1();
		}
		else
		{
			if(vertex2->GetLocation() != path->GetLocation1())
			{
				CVertex* temp = vertexList;
				while(temp)
				{
					if(temp->GetLocation() == path->GetLocation1())
						break;
					temp = temp->GetNext();
				}
				vertexStack.Push(temp);
			}
			else 
			{
				//绘图
				CDC* pDC = g_pView->GetDC();
				COLORREF color = RGB(255,0,0);//定义一个颜色变量	
				CPen pen(PS_INSIDEFRAME,2,color);
				CPen* oldPen = pDC->SelectObject(&pen);
				pDC->MoveTo(path->GetLocation1());	
				pDC->LineTo(path->GetLocation2());
				pDC->SelectObject(oldPen);
				g_pView->ReleaseDC(pDC);
				isFind = TRUE;
			}
			path = path->GetPath2();
		}
	}
	//对栈中元素操作
	while(!vertexStack.IsEmpty())
	{
		CVertex* temp = vertexStack.Pop();
		if(GetAllPaths(temp,vertex2))		//递归调用
		{
			CDC* pDC = g_pView->GetDC();
			COLORREF color = RGB(255,0,0);//定义一个颜色变量	
			CPen pen(PS_INSIDEFRAME,2,color);
			CPen* oldPen = pDC->SelectObject(&pen);
			pDC->MoveTo(vertex1->GetLocation());	
			pDC->LineTo(temp->GetLocation());
			pDC->SelectObject(oldPen);
			g_pView->ReleaseDC(pDC);
			isFind = TRUE;
		}
	}
			
	return isFind;
}
/////////////////////////////////////////////////////////////////////////////
//返回point[n]中location的下标
int CCollegeMap::GetIndex(CPoint point[],int n,CPoint location)
{
	for(int i = 0; i < n; i++)
		if(point[i] == location)
			return i;
	return -1;
}
/////////////////////////////////////////////////////////////////////////////
//返回vertexList中下标为index的道路
CPath* CCollegeMap::GetPathAt(int index)
{
	CVertex* vertex = vertexList;
	for(int i = 0; i < index; i++)
	{
		vertex = vertex->GetNext();
	}
	return vertex->paths;
}
/////////////////////////////////////////////////////////////////////////////
//返回vertexList中下标为index的景点或建筑
CVertex* CCollegeMap::GetVertexAt(int index)
{
	CVertex* vertex = vertexList;
	for(int i = 0; i < index; i++)
	{
		vertex = vertex->GetNext();
	}
	return vertex;
}
/////////////////////////////////////////////////////////////////////////////
//在给定两点序号时绘出两点间直线
BOOL CCollegeMap::DrawPath(int j, int k)
{
	if(j < 0 || k < 0)
		return FALSE;
	CVertex* temp1 = GetVertexAt(j);
	CVertex* temp2 = GetVertexAt(k);	
	
	CDC* pDC = g_pView->GetDC();
	COLORREF color = RGB(255,0,0);//定义一个颜色变量	
	CPen pen(PS_INSIDEFRAME,2,color);
	CPen* oldPen = pDC->SelectObject(&pen);
	pDC->MoveTo(temp1->GetLocation());	
	pDC->LineTo(temp2->GetLocation());
	pDC->SelectObject(oldPen);
	g_pView->ReleaseDC(pDC);

	return TRUE;
}
/////////////////////////////////////////////////////////////////////////////
//判断一个点是否落在地图内，是则返回所在景点、建筑或道路的指针，否则返回NULL
//如果坐标到直线的距离小于等于DISTANCE，则认为已选中该直线
int CCollegeMap::IsLocatedIn(CPoint point)
{
	CVertex* vertex = vertexList;
	SetVisitedTag();
	while(vertex)
	{
		//CVertex类的IsLocatedIn()用来判断point是否落在其内
		//是返回TRUE ,否则返回FALSE
		if(vertex->IsLocatedIn(point))
		{
			g_pDoc->m_path = NULL;
			//如果g_pDoc->m_selected1尚没有记录则用其记录选中点，
			//否则用g_pDoc->m_selected2记录
			if(!g_pDoc->m_selected1)
				g_pDoc->m_selected1 = vertex;
			else g_pDoc->m_selected2 = vertex;			
		}
		CPath* path = vertex->paths;
		while(path)
		{
			//CPath类的IsLocatedIn()用来判断point是否落在其内
			//是返回TRUE ,否则返回FALSE
			if(path->GetIsVisited() != GetVisitedTag())
			{
				path->SetIsVisited();
				if(path->IsLocatedIn(point))
				{	//用g_pDoc->m_path记录选中道路，
					//同时清空g_pDoc->m_selected1和g_pDoc->m_selected2
					g_pDoc->m_path = path;
					g_pDoc->m_selected1 = NULL;
					g_pDoc->m_selected2 = NULL;
				}
			}
			//遍历下一条边
			if(vertex->GetLocation() == path->GetLocation1())
				path = path->GetPath1();
			else
				path = path->GetPath2();				
		}
		vertex = vertex->GetNext();//遍历下一个点
	}
	//设置返回值类型
	if(g_pDoc->m_selected1)
		return 1;
	if(!g_pDoc->m_selected2)
		return 2;
	if(g_pDoc->m_path)
		return 3;
	else
		return 0;
}
/////////////////////////////////////////////////////////////////////////////
//寻找编号为serialNum的景点或建筑，存在则返回该点指针，否则返回NULL；
CVertex* CCollegeMap::SearchVertex(CPoint point)
{
	CVertex* vertex = vertexList;
	while(vertex)
	{
		if(vertex->GetLocation() == point)
			return vertex;
		vertex = vertex->GetNext();
	}
	return NULL;
}
/////////////////////////////////////////////////////////////////////////////
BOOL CCollegeMap::GetVisitedTag()
{
	return m_VisitedTag;
}
/////////////////////////////////////////////////////////////////////////////
void CCollegeMap::SetVisitedTag()
{
	m_VisitedTag = !GetVisitedTag();
}
/////////////////////////////////////////////////////////////////////////////
BOOL CCollegeMap::GetInformation(CPath *path)
{
	path->ShowInformation();
	return TRUE;
}
/////////////////////////////////////////////////////////////////////////////