📄 bfsearchdlg.cpp
字号:
void CBFSearchDlg::graphTraverse(CGraph *G) //要演示的程序
{
int v=0;
//////////////////////////////////////////////////////////////////////////
SetMoveValue();
SetCode(3);
if(SetValue(-1, v, -1, G->n(), -1, -1, G->first(v), -1)) return;
for (v=0; v<G->n(); v++)//////////////////////////////////////////////////
{///////////////////////////////////////////////////////////////////////////////////////////
SetMoveValue();
SetCode(4);
if(SetValue(-1, v, -1, G->n(), -1, -1, G->first(v), -1)) return;
G->setMark(v, UNVISITED); /////////////////////////////////////////////////////////////////////////
SetMoveValue();
SetCode(3);
if(SetValue(-1, v, -1, G->n(), -1, -1, G->first(v), -1)) return;
}///////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
SetMoveValue();
SetCode(5);
if(SetValue(-1, v, -1, G->n(), -1, -1, G->first(v), -1)) return;
for (v=0; v<G->n(); v++)//////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
{///////////////////////////////////////////////////////////////////////////////////////////
SetMoveValue();
SetCode(6);
if(SetValue(-1, v, -1, G->n(), -1, -1, G->first(v), -1)) return;
if (G->getMark(v) == UNVISITED) /////////////////////////////////////////////////////////////////////////
{
SetMoveValue();
SetCode(7);
if(mAuto == TRUE)
Sleep(1000);
if(SetValue(-1, v, -1, G->n(), -1, -1, G->first(v), -1)) return;
BFS(G, v, m_pQ);
}
SetMoveValue();
SetCode(5);
if(SetValue(-1, v, -1, G->n(), -1, -1, G->first(v), -1)) return;
}///////////////////////////////////////////////////////////////////////////////////////////
}
void CBFSearchDlg::SetCodeSentence()
{
m_pCodeDisplayWnd->m_Sentence[0] = "void graphTraverse(const Graph *G) ";
m_pCodeDisplayWnd->m_Sentence[1] = "{ ";
m_pCodeDisplayWnd->m_Sentence[2] = " int v; ";
m_pCodeDisplayWnd->m_Sentence[3] = " for (v=0; v<G->n( ); v++) ";
m_pCodeDisplayWnd->m_Sentence[4] = " G->setMark(v, UNVISITED); //Initialize mark bits";
m_pCodeDisplayWnd->m_Sentence[5] = " for (v=0; v<G->n( ); v++) ";
m_pCodeDisplayWnd->m_Sentence[6] = " if (G->getMark(v) == UNVISITED) ";
m_pCodeDisplayWnd->m_Sentence[7] = " DFS(G, v); ";
m_pCodeDisplayWnd->m_Sentence[8] = "} ";
m_pCodeDisplayWnd->m_Sentence[9] = "void BFS(Graph *G, int start, Queue<int> *Q) ";
m_pCodeDisplayWnd->m_Sentence[10] = "{ ";
m_pCodeDisplayWnd->m_Sentence[11] = " int v, w; ";
m_pCodeDisplayWnd->m_Sentence[12] = " Q->enqueue(start); // Initialize Q ";
m_pCodeDisplayWnd->m_Sentence[13] = " G->setMark(start, VISITED); ";
m_pCodeDisplayWnd->m_Sentence[14] = " while (Q->length( ) != 0) // Process Q ";
m_pCodeDisplayWnd->m_Sentence[15] = " { ";
m_pCodeDisplayWnd->m_Sentence[16] = " Q->dequeue(v); ";
m_pCodeDisplayWnd->m_Sentence[17] = " PreVisit(G, v); // Take action ";
m_pCodeDisplayWnd->m_Sentence[18] = " for(w=G->first(v); w<G->n( ); w=G->next(v, w)) ";
m_pCodeDisplayWnd->m_Sentence[19] = " if (G->getMark(w) == UNVISITED) ";
m_pCodeDisplayWnd->m_Sentence[20] = " { ";
m_pCodeDisplayWnd->m_Sentence[21] = " G->setMark(w, VISITED); ";
m_pCodeDisplayWnd->m_Sentence[22] = " Q->enqueue(w); ";
m_pCodeDisplayWnd->m_Sentence[23] = " } ";
m_pCodeDisplayWnd->m_Sentence[24] = " PostVisit(G, v); // Take action ";
m_pCodeDisplayWnd->m_Sentence[25] = " } ";
m_pCodeDisplayWnd->m_Sentence[26] = "} ";
m_pCodeDisplayWnd->m_Sentence_num = 27;
m_pCodeDisplayWnd->SetTextWnd();
m_ValueShow1.Empty();
m_ValueShow2.Empty();
m_ValueShow3.Empty();
}
//SetValue(int start, int v, int w, int n, int length, int markW, int firstV, int nextV)
void CBFSearchDlg::BFS(CGraph *G, int start, CQueue *Q)
{
int v=-1, w=-1;
m_lastV = start;
Q->enqueue(start);//////////////////////////////////////////////////////////
m_Queue_Str.Empty();
m_Queue_Str.Format("start=%d顶点, 即顶点%c !!!\n", start, 'A'+start);
enQueue(m_Queue_Str, start);
SetMoveValue();
SetCode(12);
if(SetValue(start, v, w, G->n(), Q->length(), G->getMark(w), G->first(v), G->next(v, w))) return;
//////////////////////////////////////////////////////////////////////////
G->setMark(start, VISITED);////////////////////////////////////////////////
SetMoveValue();
SetCode(13);
if(SetValue(start, v, w, G->n(), Q->length(), G->getMark(w), G->first(v), G->next(v, w))) return;
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
SetMoveValue();
SetCode(14);
if(SetValue(start, v, w, G->n(), Q->length(), G->getMark(w), G->first(v), G->next(v, w))) return;
///////////////////////////////////////////////////////////////////////////
while (Q->length( ) != 0) // Process Q /////////////////////////////////
{
Q->dequeue(v);///////////////////////////////////////////////////////
deQueue();
SetMoveValue();
SetCode(16);
if(SetValue(start, v, w, G->n(), Q->length(), G->getMark(w), G->first(v), G->next(v, w))) return;
//////////////////////////////////////////////////////////////////////////
//PreVisit(G, v); // Take action/////////////////////////////////////////
SetMoveValue();
SetCode(17);
if(SetValue(start, v, w, G->n(), Q->length(), G->getMark(w), G->first(v), G->next(v, w))) return;
//////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////
SetMoveValue();
SetCode(18);
if(SetValue(start, v, G->first(v), G->n(), Q->length(), G->getMark(G->first(v)), G->first(v), G->next(v, G->first(v)))) return;
for(w=G->first(v); w<G->n( ); w=G->next(v, w))/////////////////////////////
{
//////////////////////////////////////////////////////////////////////////
SetMoveValue();
SetCode(19);
if(SetValue(start, v, w, G->n(), Q->length(), G->getMark(w), G->first(v), G->next(v, w))) return;
if (G->getMark(w) == UNVISITED)/////////////////////////////////////////
{
G->setMark(w, VISITED);///////////////////////////////////////////////
SetMoveValue();
SetCode(21);
if(SetValue(start, v, w, G->n(), Q->length(), G->getMark(w), G->first(v), G->next(v, w))) return;
/////////////////////////////////////////////////////////////////////////////
Q->enqueue(w);//////////////////////////////////////////////////////////////
m_Queue_Str.Empty();
m_Queue_Str.Format("w=%d顶点, 即顶点%c!!!\n", w, 'A'+w);
enQueue(m_Queue_Str, w);
SetMoveValue();
SetCode(22);
if(SetValue(start, v, w, G->n(), Q->length(), G->getMark(w), G->first(v), G->next(v, w))) return;
/////////////////////////////////////////////////////////////////////////////
}
/////////////////////////////////////////////////////////////////////////////
SetMoveValue();
SetCode(18);
if(SetValue(start, v, G->next(v, w), G->n(), Q->length(), G->getMark(G->next(v, w)), G->first(v), G->next(v, G->next(v, w)))) return;
}
//PostVisit(G, v); // Take action///////////////////////////////////////
SetMoveValue();
SetCode(24);
if(SetValue(start, v, w, G->n(), Q->length(), G->getMark(w), G->first(v), G->next(v, w))) return;
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
SetMoveValue();
SetCode(14);
if(SetValue(start, v, w, G->n(), Q->length(), G->getMark(w), G->first(v), G->next(v, w))) return;
///////////////////////////////////////////////////////////////////////////
}
}
UINT DebugShow(LPVOID pParam)
{
CBFSearchDlg *pDialog = (CBFSearchDlg *)pParam;
pDialog->m_Break = FALSE;
pDialog->ResetCodeSentence();
pDialog->ResetQueueSentence();
pDialog->ResetMoveWnd();
pDialog->mEnd = FALSE;
pDialog->graphTraverse(pDialog->G);
if(pDialog->m_Break == FALSE)
AfxMessageBox("演示成功结束!!!");
else
AfxMessageBox("演示被终止!!!");
pDialog->mEnd = TRUE;
pDialog->mAuto = FALSE;
pDialog->mExist = FALSE;
pDialog->m_Break = FALSE;
return 0;
}
void CBFSearchDlg::OnAutoStep()
{
// TODO: Add your control notification handler code here
mAuto = TRUE;
if( mExist)
{
UpdateData(FALSE);
mStepEvent.SetEvent();
return;
}
CBFSearchDlg *pDialog = (CBFSearchDlg *)GetDlg();
if(m_pShowThread)
{
delete m_pShowThread;
m_pShowThread = NULL;
}
m_pShowThread = AfxBeginThread
(DebugShow,
pDialog,
THREAD_PRIORITY_NORMAL,
0,
CREATE_SUSPENDED);
m_pShowThread->m_bAutoDelete = FALSE;
m_pShowThread->ResumeThread();
mStepEvent.ResetEvent();
mExist = TRUE;
}
void CBFSearchDlg::OnSingleStep()
{
// TODO: Add your control notification handler code here
if( mExist)
{
UpdateData(FALSE);
mStepEvent.SetEvent();
return;
}
CBFSearchDlg *pDialog = (CBFSearchDlg *)GetDlg();
if(m_pShowThread)
{
delete m_pShowThread;
m_pShowThread = NULL;
}
m_pShowThread = AfxBeginThread
(DebugShow,
pDialog,
THREAD_PRIORITY_NORMAL,
0,
CREATE_SUSPENDED);
m_pShowThread->m_bAutoDelete = FALSE;
m_pShowThread->ResumeThread();
mStepEvent.ResetEvent();
mExist = TRUE;
}
void CBFSearchDlg::OnEndShow()
{
// TODO: Add your control notification handler code here
UpdateData(FALSE);
m_Break = TRUE;
mStepEvent.SetEvent();
}
void CBFSearchDlg::OnCancel()
{
// TODO: Add extra cleanup here
if((mAuto == FALSE)||(mEnd == TRUE))
CDialog::OnCancel();
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -