📄 eightnumber.cpp
字号:
//-------------------------------------------------------------------------------------------------
//-------八数码问题的实现文件 作者：申徐洲 日期：2004年5月6日 AllRightsReserve
//-------------------------------------------------------------------------------------------------
#include "StdAfx.h"
#include ".\EightNumber.h"
//-------------------------------------------构造函数----------------------------------------------
CEightNumber::CEightNumber(void)
{
int i_nRowNum, i_nColNum;
for ( i_nRowNum=0; i_nRowNum<4; i_nRowNum++ )
m_tDirection[i_nRowNum].x = g_aHorizon[i_nRowNum]; // 初始化搜索方向的水平分量
for ( i_nColNum=0; i_nColNum<4; i_nColNum++ )
m_tDirection[i_nColNum].y = g_aVertical[i_nColNum]; // 初始化搜索方向的垂直分量
for ( i_nRowNum=0; i_nRowNum<3; i_nRowNum++ )
for ( i_nColNum=0; i_nColNum<3; i_nColNum++ )
m_aGoal[i_nRowNum][i_nColNum] = g_aGoal[i_nRowNum][i_nColNum]; // 初始化目标状态
m_pHead = NULL; // 初始化头指针
m_pTail = NULL; // 初始化尾指针
m_pLevel = NULL; // 初始化第N层结点数量的头指针
m_pLevelTail = NULL; // 初始化第N层结点数量的头指针
m_nTotalNum = 0; // 初始化总结点数
m_nDepth = 0; // 初始化深度
}
//----------------------------------------虚拟析构函数---------------------------------------------
CEightNumber::~CEightNumber(void)
{
while( m_pHead ) // 删除八数码问题的状态内存空间
{
m_pTail = m_pHead;
m_pHead = m_pHead->pNext;
delete( m_pTail );
}
while( m_pLevel ) // 删除八数码问题的第N层结点数量的内存空间
{
m_pLevelTail = m_pLevel;
m_pLevel = m_pLevel->pNext;
delete( m_pLevelTail );
}
}
//--------------------------------------初始化八数码问题-------------------------------------------
bool CEightNumber::initEightNumber(int aCurrent[3][3])
{
if( isValid ( aCurrent ) )
{
while( m_pHead ) // 删除八数码问题的状态内存空间
{
m_pTail = m_pHead;
m_pHead = m_pHead->pNext;
delete( m_pTail );
}
m_pHead = new TEightNumber; // 头指针指向源结点
int i_nRowNum, i_nColNum;
for ( i_nRowNum=0; i_nRowNum<3; i_nRowNum++ )
for ( i_nColNum=0; i_nColNum<3; i_nColNum++ )
m_pHead->aState[i_nRowNum][i_nColNum] = aCurrent[i_nRowNum][i_nColNum];
m_pHead->nDepth = 1;
m_pHead->nBreadth = 1;
m_pHead->nChildren = 0;
m_pHead->nWeight = 0;
m_pHead->nDirection = 0;
m_pHead->bIsSolution = false;
m_pHead->bIsVisited = false;
m_pHead->pParent = NULL;
m_pHead->pChildren = NULL;
m_pHead->pSibling = NULL;
m_pHead->pPrev = NULL;
m_pHead->pNext = NULL;
m_pTail = m_pHead; // 尾指针指向源结点
m_pLevel = new TLevel; // 第一层结点数是1
m_pLevel->nNodeNumber = 1;
m_pLevel->pNext = NULL;
m_pLevelTail = m_pLevel;
m_nTotalNum = 1; // 总结点数量是1
m_nDepth = 1; // 深度是1
return true;
}
else
return false;
}
//------------------------------------A*算法搜索八数码问题-------------------------------------------
bool CEightNumber::searchByAlgorithm(void)
{
calcWeight( m_pHead );
TEightNumberPtr i_pTemp = m_pHead,i_pNew;
int i_nDirection;
while ( i_pTemp ) // 如果仍有路径可寻
{
i_pTemp = findMinCost();
if ( !i_pTemp )
return false; // 如果结点总数大于1000 则认为该问题无解
if ( isGoal( i_pTemp) )
{
findAnswer( i_pTemp );
return true;
}
for ( i_nDirection = 0; i_nDirection<4; i_nDirection++ )
if ( findNext( i_pTemp, i_nDirection ) ) // 按东南西北的顺序判判断下一状态是否合法
{
i_pNew = newEightNumber ( i_pTemp ,i_nDirection ) ;
calcWeight( i_pNew );
}
if ( m_nTotalNum>4000 )
return false; // 如果结点总数大于1000 则认为该问题无解
}
AfxMessageBox("该问题无解 只显示前50步！");
return false; // 如果所以路径走完仍没找到 则返回 fasle
}
//----------------------------------广度优先搜索八数码问题-----------------------------------------
bool CEightNumber::searchByBreadth(void)
{
if ( isGoal ( m_pHead ) ) // 如果源状态等于目标状态 则返回 true
{
findAnswer( m_pHead );
AfxMessageBox("恭喜你！算法成功");
return true;
}
TEightNumberPtr i_pTemp = m_pHead;
int i_nDirection;
while ( i_pTemp ) // 如果仍有路径可寻
{
for ( i_nDirection=0; i_nDirection<4; i_nDirection++ )
if ( findNext ( i_pTemp, i_nDirection ) ) // 按东南西北的顺序判判断下一状态是否合法
if( isGoal ( newEightNumber ( i_pTemp ,i_nDirection ) ) ) // 如果下一状态是目标状态
{
findAnswer( m_pTail ); // 找出八数码问题的正解
AfxMessageBox("恭喜你！算法成功");
return true;
}
if ( m_nTotalNum>4000 )
{
AfxMessageBox("算法失败 只显示前50步！");
return false; // 如果结点总数大于1000 则认为该问题无解
}
i_pTemp = i_pTemp->pNext; // 指向下一个状态
}
AfxMessageBox("该问题无解 只显示前50步！");
return false; // 如果所以路径走完仍没找到 则返回 fasle
}
//----------------------------------深度优先搜索八数码问题-----------------------------------------
bool CEightNumber::searchByDepth(void)
{
if ( isGoal ( m_pHead ) ) // 如果源状态等于目标状态 则返回 true
{
findAnswer( m_pHead );
AfxMessageBox("恭喜你！算法成功");
return true;
}
TEightNumberPtr i_pTemp = m_pHead;
int i_nDirection;
while ( i_pTemp ) // 如果仍有路径可寻
{
i_pTemp = findMaxDepth();
if ( !i_pTemp )
{
AfxMessageBox("算法失败 只显示前50步！");
return false; // 如果结点总数大于1000 则认为该问题无解
}
for ( i_nDirection = 0; i_nDirection<4; i_nDirection++ )
if ( findNext( i_pTemp, i_nDirection ) ) // 按东南西北的顺序判判断下一状态是否合法
if( isGoal ( newEightNumber ( i_pTemp ,i_nDirection ) ) ) // 如果下一状态是目标状态
{
findAnswer( m_pTail ); // 找出八数码问题的正解
AfxMessageBox("恭喜你！算法成功");
return true;
}
if ( m_nTotalNum>4000 )
{
AfxMessageBox("算法失败 只显示前50步！");
return false; // 如果结点总数大于1000 则认为该问题无解
}
}
AfxMessageBox("该问题无解 只显示前50步！");
return false; // 如果所以路径走完仍没找到 则返回 fasle
}
//-------------------------------------------获取结果链表----------------------------------------
TEightNumberPtr CEightNumber::getResultList(void)
{
return m_pHead;
}
//----------------------------------------获取结果总结点数量-------------------------------------
int CEightNumber::getResultNum(void)
{
return m_nTotalNum;
}
//-------------------------------------------获取结果深度----------------------------------------
int CEightNumber::getResultDepth(void)
{
return m_nDepth;
}
//---------------------------------------显示全部结点----------------------------------------------
CSize CEightNumber::showAll(CDC* pDC, TEightNumberPtr pResultList, int nResultNum)
{
TEightNumberPtr i_pResultList = pResultList;
int i_nResultNum = nResultNum;
int i_nRowNum, i_nColNum, i_nTempNum;
int i_nDispX, i_nDispY, i_nMaxX = 100 , i_nMaxY = 100;
CString i_strDispItem;
for ( i_nTempNum=0; i_nTempNum<i_nResultNum; i_nTempNum++ )
{
i_nDispY = i_pResultList->nDepth;
i_nDispX = i_pResultList->nBreadth;
i_nDispX = 10 + ( i_nDispX -1 ) * 70;
i_nDispY = 20 + ( i_nDispY -1 ) * 130;
if ( i_pResultList->bIsSolution )
pDC->SetTextColor( RGB ( 0, 0, 255 ) );
else
pDC->SetTextColor( RGB ( 0, 0, 0 ) );
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 + (i_nRowNum-1) * 70 + 60;
i_nColNum = 20 + (i_nColNum-1) * 130 + 60;
pDC->LineTo ( i_nRowNum-30 ,i_nColNum );
}
if ( i_nDispX + 60 > i_nMaxX )
i_nMaxX = i_nDispX+60;
if ( i_nDispY > i_nMaxY )
i_nMaxY = i_nDispY;
i_pResultList = i_pResultList->pNext;
}
//判断是否生成滚动条
CSize i_cSize;
i_cSize.cx = i_nMaxX+20;
i_cSize.cy = i_nMaxY+20;
return i_cSize;
}
//----------------------------------------只显示结果-----------------------------------------------
CSize CEightNumber::showResult(CDC* pDC, TEightNumberPtr pResultList, int nResultNum)
{
TEightNumberPtr i_pResultList = pResultList;
int i_nResultNum = nResultNum;
int i_nRowNum, i_nColNum, i_nTempNum;
int i_nDispX = 100, i_nDispY= 100; int i_nMaxX = 100, i_nMaxY = 100;
CString i_strDispItem;
for ( i_nTempNum=0; i_nTempNum<i_nResultNum; i_nTempNum++ )
{
i_nDispY = i_pResultList->nDepth;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -