dfsearchdlg.cpp

数据结构（C＋＋版）的演示程序

	m_ValueShow3.Empty();
	m_pCodeDisplayWnd->Invalidate();
}
void CDFSearchDlg::ResetStackSentence()
{
	memcpy(m_pStackDisplayWnd->m_Pos_Flag, "===>", 4);
	m_pStackDisplayWnd->m_ResetWnd = TRUE;
	m_Stack_Top = -1;
	for(int i=0; i<m_pStackDisplayWnd->m_Sentence_num; i++)
		m_pStackDisplayWnd->m_Sentence[i].Empty();
	m_pStackDisplayWnd->m_Sentence_num = 0;
	m_pStackDisplayWnd->Invalidate();
}

void CDFSearchDlg::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 DFS(Graph* G, int v)                                 ";
	m_pCodeDisplayWnd->m_Sentence[10] = "{                                                         ";
	m_pCodeDisplayWnd->m_Sentence[11] = "     PreVisit(G, v);  // Take action                      ";
	m_pCodeDisplayWnd->m_Sentence[12] = "     G->setMark(v, VISITED);                              ";
	m_pCodeDisplayWnd->m_Sentence[13] = "     for (int w=G->first(v); w<G->n( ); w=G->next(v, w))  ";
	m_pCodeDisplayWnd->m_Sentence[14] = "          if (G->getMark(w) == UNVISITED)                 ";
	m_pCodeDisplayWnd->m_Sentence[15] = "                DFS(G, w);                                ";
	m_pCodeDisplayWnd->m_Sentence[16] = "     PostVisit(G, v); // Take appropiate action           ";
	m_pCodeDisplayWnd->m_Sentence[17] = "}                                                         "; 

	m_pCodeDisplayWnd->m_Sentence_num = 18;
	m_pCodeDisplayWnd->SetTextWnd();
	m_ValueShow1.Empty();
	m_ValueShow2.Empty();
	m_ValueShow3.Empty();
}


void CDFSearchDlg::graphTraverse(CGraph *G) //要演示的程序
{
	int v=0;

	if(SetValue(-1, -1, -1, -1, -1, -1)) return;
	SetMoveValue();
	m_Stack_Str.Empty();
	m_Stack_Str.Format("Call graphTraverse( G=%d)", G);
	PushStack(m_Stack_Str);

	//////////////////////////////////////////////////////////////////////////
	if(SetValue(v, -1, G->n(), G->getMark(v), G->first(v), -1)) return;
	SetMoveValue();
	SetCode(3);
	for (v=0; v<G->n(); v++)//////////////////////////////////////////////////

	////////////////////////////////////////////////////////////////////////////////////////////
	{///////////////////////////////////////////////////////////////////////////////////////////
		if(SetValue(v, -1, G->n(), G->getMark(v), G->first(v), -1)) return;
		SetMoveValue();
		SetCode(4);
		G->setMark(v, UNVISITED); /////////////////////////////////////////////////////////////////////////
		if(SetValue(v, -1, G->n(), G->getMark(v), G->first(v), -1)) return;
		SetMoveValue();
		SetCode(3);
	}///////////////////////////////////////////////////////////////////////////////////////////

	//////////////////////////////////////////////////////////////////////////
	if(SetValue(v, -1, G->n(), -1, -1, -1)) return;
	SetMoveValue();
	SetCode(5);
	for (v=0; v<G->n(); v++)//////////////////////////////////////////////////

	////////////////////////////////////////////////////////////////////////////////////////////
	{///////////////////////////////////////////////////////////////////////////////////////////
		if(SetValue(v, -1, G->n(), G->getMark(v), G->first(v), -1)) return;
		SetMoveValue();
		SetCode(6);
		if (G->getMark(v) == UNVISITED) /////////////////////////////////////////////////////////////////////////
		{
			if(SetValue(v, -1, G->n(), G->getMark(v), G->first(v), -1)) return;
			SetMoveValue();
			SetCode(7);
			if(mAuto == TRUE)
				Sleep(1000);
			DFS(G, v, v);
		}
		if(SetValue(v, -1, G->n(), G->getMark(v), G->first(v), -1)) return;
		SetMoveValue();
		SetCode(5);

	}///////////////////////////////////////////////////////////////////////////////////////////
}

void CDFSearchDlg::DFS(CGraph* G, int v,  int v0) 
{
	if(SetValue(v, -1, G->n(), G->getMark(v), G->first(v), -1)) return;
	SetMoveValue();
	m_Stack_Str.Empty();
	m_Stack_Str.Format("Call DFS( G=%d, v=%d), 对第%d个顶点调用DFS", G, v, v);
	PushStack(m_Stack_Str);

	//////////////////////////////////////////////////////////////////////////
	if(SetValue(v, -1, G->n(), G->getMark(v), G->first(v), -1)) return;
	SetMoveValue();
	SetCode(11);
 // PreVisit(G, v);  // Take action////////////////////////////////////////////
	if(v0 != v)
	{
		G->SetEdge(v, v0, 2);
		G->SetEdge(v0, v, 2);
	}
	//////////////////////////////////////////////////////////////////////////

	//////////////////////////////////////////////////////////////////////////
	if(SetValue(v, -1, G->n(), G->getMark(v), G->first(v), -1)) return;
	SetMoveValue();
	SetCode(12);
	G->setMark(v, VISITED);///////////////////////////////////////////////////

	//////////////////////////////////////////////////////////////////////////
	if(SetValue(v, G->first(v), G->n(), G->getMark(v), G->first(v), G->next(v, G->first(v)))) return;
	SetMoveValue();
	SetCode(13);

	for (int w=G->first(v); w<G->n(); w = G->next(v,w))
	{
		if(SetValue(v, w, G->n(), G->getMark(v), G->first(v), G->next(v, w))) return;
		SetMoveValue();
		SetCode(14);
		if (G->getMark(w) == UNVISITED)/////////////////////////////////////////
		{
			if(SetValue(v, G->n(), G->n(), G->getMark(v), G->first(v), G->next(v, w))) return;
			SetMoveValue();
			SetCode(15);
			if(mAuto == TRUE)
				Sleep(1000);
			DFS(G, w, v);
		}
		if(SetValue(v, w, G->n(), G->getMark(v), G->first(v), G->next(v, w))) return;
		SetMoveValue();
		SetCode(13);
	}

	//////////////////////////////////////////////////////////////////////////
	if(SetValue(v, -1, G->n(), G->getMark(v), G->first(v), G->next(v, w))) return;
	SetMoveValue();
	SetCode(11);
//	PostVisit(G, v); // Take action/////////////////////////////////////////////////

	PopStack();
}

UINT DebugShow(LPVOID pParam)
{
	CDFSearchDlg *pDialog = (CDFSearchDlg *)pParam;

	pDialog->m_Break = FALSE; 
	pDialog->ResetCodeSentence();
	pDialog->ResetStackSentence();
	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 CDFSearchDlg::OnAutoStep() 
{
	// TODO: Add your control notification handler code here
	mAuto = TRUE;
	if(	mExist)
	{
		UpdateData(FALSE);
		mStepEvent.SetEvent();
		return;
	}
	CDFSearchDlg *pDialog = (CDFSearchDlg *)GetDlg();
	mStepEvent.ResetEvent();

	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();
	mExist = TRUE;
}

void CDFSearchDlg::OnSingleStep() 
{
	// TODO: Add your control notification handler code here
	if(	mExist)
	{
		UpdateData(FALSE);
		mStepEvent.SetEvent();
		return;
	}
	CDFSearchDlg *pDialog = (CDFSearchDlg *)GetDlg();
	mStepEvent.ResetEvent();

	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();
	mExist = TRUE;
}
void CDFSearchDlg::OnEndShow() 
{
	// TODO: Add your control notification handler code here
	UpdateData(FALSE);
	m_Break = TRUE;
	mStepEvent.SetEvent();
	
}


void CDFSearchDlg::OnCancel() 
{
	// TODO: Add extra cleanup here
	if((mAuto == FALSE)||(mEnd == TRUE))
	      CDialog::OnCancel();
}