nrstpath.cpp

程序编写环境为Visual Studio.NET 2002

#include "StdAfx.h"
#include "nrstpath.h"
#include "AppApi.h"
#include "Crack.h"
#include "Mainfrm.h"

//-----------------------------------------------------------------------------------------
CNrstPath::CNrstPath(void)
{
	m_nTimeLimit = 3;
	m_pRoutine = NULL;
	m_pRoutine = new Routine[1000];
	for(int i=0; i<1000; i++)
		m_pRoutine[i].szStaionName = NULL;
	m_pStations = NULL;
	m_pStations = new Station[5000];
	for(int i=0; i<5000; i++)
	{
		m_pStations[i].pnOrder = NULL;
		m_pStations[i].pnRoutineID = NULL;
	}
}
//-----------------------------------------------------------------------------------------
CNrstPath::~CNrstPath(void)
{
	if(m_pRoutine)
	{
		for(int i=0; i<1000; i++)
		{
			if(m_pRoutine[i].szStaionName)
			{
				delete []m_pRoutine[i].szStaionName;
				m_pRoutine[i].szStaionName = NULL;
			}
		}
		delete []m_pRoutine;
		m_pRoutine = NULL;
	}

	if(m_pStations)
	{
		for(int i=0; i<5000; i++)
		{
			if(m_pStations[i].pnOrder)
			{
				delete []m_pStations[i].pnOrder;
				m_pStations[i].pnOrder = NULL;
			}
			if(m_pStations[i].pnRoutineID)
			{
				delete []m_pStations[i].pnRoutineID;
				m_pStations[i].pnRoutineID = NULL;
			}
		}
		delete []m_pStations;
		m_pStations = NULL;
	}
}
//-----------------------------------------------------------------------------------------
void CNrstPath::Build()
{
	// 初始化m_pRoutine成员变量
	m_nRCount = BuildRoutine(m_pRoutine);
	// 初始化m_pStations成员变量
	m_nSCount = BuildStationIndex(m_pRoutine, m_nRCount, m_pStations);
}
//-----------------------------------------------------------------------------------------
short CNrstPath::BuildRoutine(Routine* pRoutine)
{
	CMainFrame* pMainWnd = (CMainFrame*)AfxGetMainWnd();
	CEnvironment* env = &(pMainWnd->m_environment);
	CDaoDatabase* tmpDB = new CDaoDatabase;
	try
	{
		tmpDB->Open(env->m_szDBName);
	}
	catch (CDaoException* e)
	{
		DisplayDaoException(e);
		delete tmpDB;
		e->Delete();
		return FALSE;
	}

	CDaoRecordset rs(tmpDB);
	short nCount = 0;
	short nSCount = 0;
	try
	{
		CString szSQL = "Select * from 公交车站路线 ";
		if (env->m_szBusFilter != "")
		{
			szSQL += "Where ";
			szSQL += env->m_szBusFilter;
			szSQL += " Order By 线路名";
		}
		else
			szSQL += " Order By 线路名";
		rs.Open(dbOpenDynaset, szSQL);

		CString rName;
		CString sName;
		CString sTemp1;
		CString sTemp2;
		CString* sNames = new CString[350];
		
		while(!rs.IsEOF())
		{
			COleVariant var;
			var = rs.GetFieldValue(0);
			rName = CCrack::strVARIANT(var);
			var = rs.GetFieldValue(1);
			sTemp1 = CCrack::strVARIANT(var);
			var = rs.GetFieldValue(2);
			sName = CCrack::strVARIANT(var);
			var = rs.GetFieldValue(0);
			sTemp2 = CCrack::strVARIANT(var);
            
			if(nCount == 0)
			{
				pRoutine[nCount].szRoutineName = rName;				
				if(rName.GetLength() > 4 && rName.Right(4) =="上行")
					pRoutine[nCount].nFlag = 1;
				else if(rName.GetLength() > 4 && rName.Right(4) == "下行")
					pRoutine[nCount].nFlag = 2;
				else 
					pRoutine[nCount].nFlag = 0;
				nCount++;
				nSCount = 0;
				sNames[nSCount] = sName;
				nSCount = 1;
			}
			else
			{
				if(pRoutine[nCount-1].szRoutineName == rName)
				{
					sNames[nSCount] = sName;
					nSCount++;
				}
				else
				{
					//结束上一站
					pRoutine[nCount-1].nStationNumber = nSCount;
					pRoutine[nCount-1].szStaionName = new CString [nSCount];
					for(short i=0; i<nSCount; i++)
						pRoutine[nCount-1].szStaionName[i] = sNames[i];
                    
					if(rName.GetLength() > 4 && rName.Right(4) == "上行")
						pRoutine[nCount].nFlag = 1;
					else if(rName.GetLength() > 4 && rName.Right(4) == "下行")
						pRoutine[nCount].nFlag = 2;
					else 			
						pRoutine[nCount].nFlag = 0;
					pRoutine[nCount].szRoutineName = rName;
					nCount++;
					nSCount = 0;
					sNames[nSCount] = sName;
					nSCount = 1;
				}
			}

			rs.MoveNext();
		}

		pRoutine[nCount-1].nStationNumber = nSCount;
		pRoutine[nCount-1].szStaionName = new CString [nSCount];
		for(short i=0; i<nSCount; i++)
			pRoutine[nCount-1].szStaionName[i] = sNames[i];

		delete []sNames;
		sNames = NULL;
	}
	catch (CDaoException* e)
	{
		DisplayDaoException(e);
		tmpDB->Close();
		delete tmpDB;
		e->Delete();
		return FALSE;
	}

	if(tmpDB)
	{
		if(tmpDB->IsOpen())
		{
			tmpDB->Close();
		}

		delete tmpDB;
		tmpDB = NULL;
	}
    
	return nCount;
}
//-----------------------------------------------------------------------------------------
short CNrstPath::BuildStationIndex(Routine* pAllRoutines, short nSize, Station* pStations)
{
	short nCount = 0;
	for(short i=0; i<nSize; i++)
	{
		for(short j=0; j<pAllRoutines[i].nStationNumber; j++)
		{
			short k;
			for( k=0;k<nCount;k++)
			{
				if(pStations[k].szStationName == pAllRoutines[i].szStaionName[j])
					break;
			}
			if(k == nCount)
			{
				// 添加一个新站
				pStations[k].szStationName = pAllRoutines[i].szStaionName[j];
				pStations[k].nRoutineNumber = 1;
				nCount++;
			}
			else
				pStations[k].nRoutineNumber ++;
		}
	}
	// 为各个站的信息分配内存
	for(int i=0; i<nCount; i++)
	{
		pStations[i].pnRoutineID = new short[pStations[i].nRoutineNumber];
		pStations[i].pnOrder = new short[pStations[i].nRoutineNumber];
		pStations[i].nRoutineNumber = 0;		// 下面重新数
	}
    
	// 重新设置信息
	for(int i=0; i<nSize; i++)
	{
		for(short j=0; j<pAllRoutines[i].nStationNumber; j++)
		{
			short k;
			for(k=0; k<nCount; k++)
			{
				if(pStations[k].szStationName == pAllRoutines[i].szStaionName[j])
					break;
			}
			
			pStations[k].pnRoutineID[pStations[k].nRoutineNumber] = (short)i;
			pStations[k].pnOrder[pStations[k].nRoutineNumber] = j;
			pStations[k].nRoutineNumber ++;
		}
	}
	
	return nCount;
}
//-----------------------------------------------------------------------------------------
void CNrstPath::Search(CString sz1, CString sz2, CList<PathNode, PathNode&>* array)
{
	Search(m_pRoutine, m_nRCount, m_pStations, m_nSCount, sz1, sz2, array);
}
//-----------------------------------------------------------------------------------------
short CNrstPath::Search(Routine* pAllRoutines, short nSize, Station* pStations, 
		         short nSCount, CString szFrom, CString szTo, 
				 CList<PathNode, PathNode&>* pResPath)
{
	short nCount = 0;
	short nStationOrder;
	Node nodeCurrent  ;
	CList<Node, Node&> queueNodes;	// 存储需要访问的节点
	short nRoutineCurrent;
	short nStationCurrent;
	short i;
	short nMinChangeTimes=1000;		// 第一次找到的换乘次数
    
	//先得到起点站的线路
	for(i=0; i<nSize; i++)
	{
		nStationOrder = HasStation(pAllRoutines[i],szFrom,0,0);
		if(nStationOrder >= 0)
		{	
			nodeCurrent.nNodeNumber = 1;
			nodeCurrent.nRoutineOrder = new short [10];
			nodeCurrent.nStationOrder = new short [10];
            
			nodeCurrent.nRoutineOrder[0] = i;
			nodeCurrent.nStationOrder[0] = nStationOrder;
			// 入队列操作
			queueNodes.AddTail(nodeCurrent);
		}
	}

	while(!(0 == queueNodes.GetCount()))
	{
		nodeCurrent = (Node)queueNodes.GetHead();
		queueNodes.RemoveHead();
        
		if((nodeCurrent.nNodeNumber >= m_nTimeLimit + 1) 
			|| (nodeCurrent.nNodeNumber > nMinChangeTimes-1) 
			|| (queueNodes.GetCount() > 1500000))		//换乘次数限制
			break;

		// 得到队列头
		// 从队头站点序列的最后一个站开始检索是否能够找到到站
		nRoutineCurrent = nodeCurrent.nRoutineOrder[nodeCurrent.nNodeNumber-1];
		nStationCurrent = nodeCurrent.nStationOrder[nodeCurrent.nNodeNumber-1];
        
		nStationOrder = HasStation( pAllRoutines[nRoutineCurrent], szTo, 
			nStationCurrent, pAllRoutines[nRoutineCurrent].nFlag);
		if(nStationOrder >= 0)  //表示找到
		{
			nodeCurrent.nRoutineOrder[nodeCurrent.nNodeNumber] = nRoutineCurrent;
			nodeCurrent.nStationOrder[nodeCurrent.nNodeNumber] = nStationOrder;
			nodeCurrent.nNodeNumber ++;

			if(nodeCurrent.nNodeNumber > nMinChangeTimes)
				break;
            
			PathNode pPathTempNode;
			pPathTempNode.nSegNumber = (short)(nodeCurrent.nNodeNumber-1);
			pPathTempNode.szRoutineName = 
				new CString[pPathTempNode.nSegNumber];
			pPathTempNode.szFromStationName = 
				new CString[pPathTempNode.nSegNumber];
			pPathTempNode.szToStationName = 
				new CString[pPathTempNode.nSegNumber];
			for(i=0; i<pPathTempNode.nSegNumber; i++)
			{
				pPathTempNode.szRoutineName[i] = 
					pAllRoutines[nodeCurrent.nRoutineOrder[i]].szRoutineName;
				pPathTempNode.szFromStationName[i] = pAllRoutines[nodeCurrent.
					nRoutineOrder[i]].szStaionName[nodeCurrent.nStationOrder[i]];
				pPathTempNode.szToStationName[i] = pAllRoutines[nodeCurrent.
					nRoutineOrder[i+1]].szStaionName[nodeCurrent.nStationOrder[i+1]];
			}
			pResPath->AddTail(pPathTempNode);
            
			if(nCount == 0)
				nMinChangeTimes = nodeCurrent.nNodeNumber;
			nCount++;
			if(nCount > 20)
				break;
		}
		else  // 要将所有可能的路径加入队列
		{
			for(i=(short)(nStationCurrent+1); 
				i<pAllRoutines[nRoutineCurrent].nStationNumber; i++)
			{
				CString szTheStation;
				szTheStation= pAllRoutines[nRoutineCurrent].szStaionName[i];
                
				short j = SearchStation(pStations,nSCount,szTheStation);
				for(short k=0; k<pStations[j].nRoutineNumber; k++)
				{
					short l;
					for(l=0; l<nodeCurrent.nNodeNumber; l++)
						if(pStations[j].pnRoutineID[k] == nodeCurrent.nRoutineOrder[l])
							break;
					if(l < nodeCurrent.nNodeNumber)		// 说明已经处理过该线路
						continue;
                    
					Node nodeTemp;
					nodeTemp.nNodeNumber = (short)(nodeCurrent.nNodeNumber+1);
					nodeTemp.nRoutineOrder = new short [10];
					nodeTemp.nStationOrder = new short [10];
					for(l=0; l<nodeCurrent.nNodeNumber; l++)
					{
						nodeTemp.nRoutineOrder[l] = nodeCurrent.nRoutineOrder[l];
						nodeTemp.nStationOrder[l] = nodeCurrent.nStationOrder[l];
					}
					nodeTemp.nRoutineOrder[nodeCurrent.nNodeNumber] = 
						pStations[j].pnRoutineID[k];
					nodeTemp.nStationOrder[nodeCurrent.nNodeNumber] = 
						pStations[j].pnOrder[k];
					queueNodes.AddTail(nodeTemp);
				}
			}

			// 双向线路，需要两个方向查询
			if( pAllRoutines[nRoutineCurrent].nFlag == 0 )	
			{
				for(i=(short)(nStationCurrent-1); i>=0; i--)
				{
					CString szTheStation;
					szTheStation = pAllRoutines[nRoutineCurrent].szStaionName[i];
                    
					short j = SearchStation(pStations,nSCount,szTheStation);
					for(short k=0;k<pStations[j].nRoutineNumber;k++)
					{
						short l;
						for(l=0; l<nodeCurrent.nNodeNumber; l++)
							if(pStations[j].pnRoutineID[k] ==
								nodeCurrent.nRoutineOrder[l])
								break;
						if(l < nodeCurrent.nNodeNumber)	// 说明已经处理过该线路
							continue;
						Node nodeTemp;
						nodeTemp.nNodeNumber = (short)(nodeCurrent.nNodeNumber+1);
						nodeTemp.nRoutineOrder = new short [10];
						nodeTemp.nStationOrder = new short [10];
						for(l=0; l<nodeCurrent.nNodeNumber; l++)
						{
							nodeTemp.nRoutineOrder[l] = 
								nodeCurrent.nRoutineOrder[l];
							nodeTemp.nStationOrder[l] = 
								nodeCurrent.nStationOrder[l];
						}
						nodeTemp.nRoutineOrder[nodeCurrent.nNodeNumber] = 
							pStations[j].pnRoutineID[k];
						nodeTemp.nStationOrder[nodeCurrent.nNodeNumber] =
							pStations[j].pnOrder[k];
						queueNodes.AddTail(nodeTemp);
					}
				}
			}
		}

		if(nodeCurrent.nRoutineOrder)
		{
			delete []nodeCurrent.nRoutineOrder;
			nodeCurrent.nRoutineOrder = NULL;
			delete []nodeCurrent.nStationOrder;
			nodeCurrent.nStationOrder = NULL;
		}
	}

	int nsCount = queueNodes.GetCount();
	for(int i=0; i<nsCount; i++)
	{
		Node node = queueNodes.RemoveTail();
		delete []node.nRoutineOrder;
		node.nRoutineOrder = NULL;
		delete []node.nStationOrder;
		node.nStationOrder = NULL;		
	}
	return nCount;
}
//-----------------------------------------------------------------------------------------
// 根据站名得到它是一条公交线路上第几站,基0,-1表示没有
// nSearchFrom为开始搜寻的站序号
// nFlag标记向那个方向搜索,0表示双方向,1表示单向
short CNrstPath::HasStation(Routine theRoutine, CString szStation, 
							short nSearchFrom, short nFlag)
{
	if( nFlag != 0)
	{
		for(short i=nSearchFrom; i<theRoutine.nStationNumber; i++)
			if(theRoutine.szStaionName[i] == szStation)
				return i;
	}
	else if( nFlag == 0 )
	{
		for(short i=nSearchFrom;i<theRoutine.nStationNumber;i++) // 正向搜索
			if(theRoutine.szStaionName[i] == szStation)
				return i;
		for(short i=nSearchFrom; i>=0; i--) // 反向搜索
			if(theRoutine.szStaionName[i] == szStation)
				return i;
	}
	return -1;
}
//-----------------------------------------------------------------------------------------
short CNrstPath::SearchStation(Station* pStations, short nSCount, CString theName)
{
	short j = -1;
	//用于统计时间
	for(j=0; j<nSCount; j++)
	{
		if(pStations[j].szStationName == theName)
		{
			return j;
		}
	}	
	return j;
}
//-----------------------------------------------------------------------------------------