eightnumber.cpp

用VC编制的集成的野人和八数码演示程序。其中野人程序用动态的效果演示

		i_nDispX = i_pResultList->nBreadth;
		i_nDispX = 10;
        i_nDispY = 20 + ( i_nDispY -1 ) * 80;   
		if ( i_pResultList->bIsSolution )
		{
			pDC->SetTextColor( RGB ( 0, 0, 255 ) );
			if ( i_pResultList->nWeight !=0 )
		    {
				i_strDispItem.Format("%d", i_pResultList->nWeight - i_pResultList->nDepth +1 );
			    pDC->TextOut( i_nDispX+20, i_nDispY-20, i_strDispItem );
			    i_strDispItem.Format("%d", i_pResultList->nWeight);
			    pDC->TextOut( i_nDispX+35, i_nDispY-20, i_strDispItem );
		    }
		    for ( i_nRowNum=0; i_nRowNum<3; i_nRowNum++ )
		    {		
			    for (i_nColNum=0; i_nColNum<3; i_nColNum++ )
			    {
				    pDC->Rectangle( i_nDispX-1, i_nDispY-1, i_nDispX+20, i_nDispY+20 );
				    if ( i_pResultList->aState[i_nRowNum][i_nColNum] !=0 )
					    i_strDispItem.Format("%d",i_pResultList->aState[i_nRowNum][i_nColNum]);
				    else
					    i_strDispItem=" ";
				    pDC->TextOut( i_nDispX+6, i_nDispY+2, i_strDispItem );
				    i_nDispX+=20;
			    } 
			    i_nDispX-=60;
			    i_nDispY+=20;
		    }
		    if ( i_pResultList->pParent )
		    {
			    pDC->MoveTo( i_nDispX+30, i_nDispY-62 );
			    i_nRowNum = i_pResultList->pParent->nBreadth;
			    i_nColNum = i_pResultList->pParent->nDepth;
			    i_nRowNum = 10 + 60;
			    i_nColNum = 20 + (i_nColNum-1) * 80 + 60;    //
			    pDC->LineTo ( i_nRowNum-30 ,i_nColNum );
		    }
		    if ( i_nDispY>i_nMaxY )
			    i_nMaxY = i_nDispY;
		}
	    i_pResultList = i_pResultList->pNext;  
	}
	//判断是否生成滚动条
	CSize i_cSize;
	i_cSize.cx = i_nMaxX;
	i_cSize.cy = i_nMaxY+20;
	return i_cSize;
}
//-----------------------------------判断当前状态是否合法------------------------------------------
bool CEightNumber::isValid(int aCurrent[3][3])
{
	bool i_bIsValid;
	int i_nEightNumber, i_nRowNum, i_nColNum;
	for ( i_nEightNumber=0; i_nEightNumber<9; i_nEightNumber++ )
	{
		i_bIsValid=false;
		for ( i_nRowNum=0; i_nRowNum <3; i_nRowNum++ )
			for ( i_nColNum=0; i_nColNum<3; i_nColNum++ )
				if ( aCurrent[i_nRowNum][i_nColNum] == i_nEightNumber )
					i_bIsValid = true;   
		if ( !i_bIsValid )
			break;
	}
	return i_bIsValid;
}

//--------------------------------判断当前状态是不是目标状态---------------------------------------
bool CEightNumber::isGoal(TEightNumberPtr pCurrent)
{
	int i_nRowNum, i_nColNum;
	for ( i_nRowNum=0; i_nRowNum<3; i_nRowNum++ )
		for ( i_nColNum=0; i_nColNum<3; i_nColNum++ )
			if ( pCurrent->aState[i_nRowNum][i_nColNum] != m_aGoal[i_nRowNum][i_nColNum] )
				return false;
	return true;
}

//-----------------------------------------新建状态------------------------------------------------
TEightNumberPtr CEightNumber::newState(TEightNumberPtr pCurrent, int nDirection)
{
    TEightNumberPtr i_pNew;
    int i_nRowNum, i_nColNum;
	TPosition i_tPosition, i_tPrevPos;
	i_tPrevPos = findBlank ( pCurrent, 0 );
	i_tPosition.x = i_tPrevPos.x + m_tDirection[nDirection].x;
    i_tPosition.y = i_tPrevPos.y + m_tDirection[nDirection].y;
	i_pNew = new TEightNumber;
	for ( i_nRowNum=0; i_nRowNum<3; i_nRowNum++ )
		for ( i_nColNum=0; i_nColNum<3; i_nColNum++ )
			i_pNew->aState[i_nRowNum][i_nColNum] = pCurrent->aState[i_nRowNum][i_nColNum];
	i_pNew->aState[i_tPrevPos.x][i_tPrevPos.y] = i_pNew->aState[i_tPosition.x][i_tPosition.y];
	i_pNew->aState[i_tPosition.x][i_tPosition.y] = 0;
	return i_pNew;
}

//-----------------------------------------新建结点------------------------------------------------
TEightNumberPtr CEightNumber::newEightNumber(TEightNumberPtr pParent, int nDirection)
{
	TEightNumberPtr i_pCurrent, i_pTemp;
	TLevelPtr i_pLevel;
	int i_nRowNum;
	i_pCurrent = newState ( pParent, nDirection );     // 初始化新结点 
	i_pCurrent->nDepth = pParent->nDepth + 1;
	if ( i_pCurrent->nDepth>m_nDepth )        // 如果深度增加
	{
		i_pCurrent->nBreadth = 1;
		i_pLevel = new TLevel;                
		i_pLevel->nNodeNumber = 1;
		i_pLevel->pNext = NULL;
		m_pLevelTail->pNext = i_pLevel;
        m_pLevelTail = i_pLevel;
		m_nDepth++;        // 深度加1
	}
	else
	{
		i_pLevel = m_pLevel;
		for ( i_nRowNum=1; i_nRowNum<m_nDepth; i_nRowNum++ )
			i_pLevel = i_pLevel->pNext;
	    i_pLevel->nNodeNumber++;
		i_pCurrent->nBreadth = i_pLevel->nNodeNumber;
	}
	i_pCurrent->nChildren = 0;
	i_pCurrent->nWeight = 0;
	i_pCurrent->nDirection = 0;
	i_pCurrent->bIsSolution = false;
	i_pCurrent->bIsVisited = false;
	i_pCurrent->pParent = pParent;
	i_pCurrent->pChildren = NULL;
	i_pCurrent->pSibling = NULL;
	i_pCurrent->pPrev = m_pTail->pNext;
	i_pCurrent->pNext = NULL;
	if ( pParent->nChildren == 0 )     // 对新结点的父结点赋值
		pParent->pChildren = i_pCurrent;
	else
	{
		i_pTemp = pParent->pChildren;
		for ( i_nRowNum=1; i_nRowNum<pParent->nChildren; i_nRowNum++ )
			i_pTemp = i_pTemp->pSibling;
		i_pTemp->pSibling = i_pCurrent;
	}
	pParent->nChildren++;
	m_pTail->pNext = i_pCurrent;        // 将新结点放入结点链表的尾部 
	m_pTail = i_pCurrent;               // 对尾指针重新赋值
    m_nTotalNum++;                      // 总结点数数量加1
	return i_pCurrent;
}

//-----------------------------------找出当前结点空格的位置---------------------------------------
TPosition CEightNumber::findBlank(TEightNumberPtr pCurrent, int nValue)
{
	TPosition  i_tPosition;
	int i_nRowNum, i_nColNum;
	for ( i_nRowNum=0; i_nRowNum<3; i_nRowNum++ )
		for ( i_nColNum=0; i_nColNum<3; i_nColNum++ )
			if ( pCurrent->aState[i_nRowNum][i_nColNum] == nValue )
			{
				i_tPosition.x = i_nRowNum;
				i_tPosition.y = i_nColNum;
			}
	return i_tPosition;
}


//-------------------------------------找出深度最大的结点-----------------------------------------
TEightNumberPtr CEightNumber::findMaxDepth(void)
{
	TEightNumberPtr i_pTemp = m_pHead, i_pReturn = NULL;
	int i_nDepth = 0;
	while ( i_pTemp )
	{
		if ( !i_pTemp->bIsVisited )
			if ( i_pTemp->nDepth > i_nDepth )
			{
				i_nDepth = i_pTemp->nDepth;
				i_pReturn = i_pTemp;
			}
		i_pTemp = i_pTemp->pNext;
	}
	if ( i_pReturn )
		i_pReturn->bIsVisited = true;
	return i_pReturn;
}

//---------------------------------找出A*算法中代价最小的结点--------------------------------------
TEightNumberPtr CEightNumber::findMinCost(void)
{
	TEightNumberPtr i_pTemp = m_pHead, i_pReturn = NULL;
	int i_nWeight = 4000;
	while ( i_pTemp )
	{
		if ( !i_pTemp->bIsVisited )
			if ( i_pTemp->nWeight < i_nWeight )
			{
				i_nWeight = i_pTemp->nWeight;
				i_pReturn = i_pTemp;
			}
		i_pTemp = i_pTemp->pNext;
	}
	if ( i_pReturn )
		i_pReturn->bIsVisited = true;
	return i_pReturn;
}

//-------------------------------间断结点的下一个位置是否合法--------------------------------------
bool CEightNumber::findNext(TEightNumberPtr pCurrent, int nDirection)
{
	TPosition i_tPosition = findBlank( pCurrent, 0 );
	i_tPosition.x += m_tDirection[nDirection].x;
	i_tPosition.y += m_tDirection[nDirection].y;
	if ( i_tPosition.x<0 || i_tPosition.x >2 || i_tPosition.y<0 || i_tPosition.y>2 )
		return false;        // 如果下一个位置的数组维数越界 则返回 false
	else                     
	{   // 判断该结点是否已经存在
		TEightNumberPtr i_pTemp, i_pNew;
		bool i_bIsExist;
		int i_nRowNum, i_nColNum;
		i_pTemp = m_pHead;
		i_pNew = newState ( pCurrent, nDirection );
		while ( i_pTemp )
		{
			i_bIsExist = true;
            for ( i_nRowNum=0; i_nRowNum<3; i_nRowNum++ )
				for ( i_nColNum=0; i_nColNum<3; i_nColNum++ )
					if ( i_pTemp->aState[i_nRowNum][i_nColNum] != i_pNew->aState[i_nRowNum][i_nColNum] )
						i_bIsExist = false;
			if ( i_bIsExist )
				break;
			i_pTemp = i_pTemp->pNext;
		}
		delete ( i_pNew );
		return !i_bIsExist;
	}
	return true;
}

//------------------------------------找到八数码问题的解-------------------------------------------
void CEightNumber::findAnswer(TEightNumberPtr pEightNumber)
{
	TEightNumberPtr i_pTemp;
	i_pTemp = pEightNumber;
	while ( i_pTemp )
	{
		i_pTemp->bIsSolution = true;
		i_pTemp = i_pTemp->pParent;
	}
}

//----------------------------------计算A*算法中结点的权值-----------------------------------------
void CEightNumber::calcWeight(TEightNumberPtr pCurrent)
{
	TPosition i_tPosition, i_tPositions[8];             
    int i_nCompNum, i_nValue = 0;
	i_tPositions[0].x = 0; i_tPositions[0].y = 0;
	i_tPositions[1].x = 0; i_tPositions[1].y = 1;
	i_tPositions[2].x = 0; i_tPositions[2].y = 2;
	i_tPositions[3].x = 1; i_tPositions[3].y = 2;
	i_tPositions[4].x = 2; i_tPositions[4].y = 2;
	i_tPositions[5].x = 2; i_tPositions[5].y = 1;
	i_tPositions[6].x = 2; i_tPositions[6].y = 0;
	i_tPositions[7].x = 1; i_tPositions[7].y = 0;
	for ( i_nCompNum=1; i_nCompNum<9; i_nCompNum++)
	{
		i_tPosition = findBlank( pCurrent, i_nCompNum );
		i_nValue=i_nValue+abs(i_tPosition.x-i_tPositions[i_nCompNum-1].x)+abs(i_tPosition.y-i_tPositions[i_nCompNum-1].y);

	}
	pCurrent->nWeight = i_nValue + pCurrent->nDepth - 1;
}

//--------------------------------重新计算A*算法中结点的位置---------------------------------------
void CEightNumber::reCalcPosition(void)
{

}