mergesortshowdlg.cpp

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

	m_pCodeDisplayWnd->m_Sentence[6]  = "      }                                              ";
	m_pCodeDisplayWnd->m_Sentence[7]  = "      int i, j, k, mid = (left+right)/2;             ";
	m_pCodeDisplayWnd->m_Sentence[8]  = "      if (left == right)                             ";
	m_pCodeDisplayWnd->m_Sentence[9]  = "            return;                                  ";
	m_pCodeDisplayWnd->m_Sentence[10] = "      mergesort(A, temp, left, mid);                 ";
	m_pCodeDisplayWnd->m_Sentence[11] = "      mergesort(A, temp, mid+1, right);              ";
	m_pCodeDisplayWnd->m_Sentence[12] = "      for (i=mid; i>=left; i--)                      ";
	m_pCodeDisplayWnd->m_Sentence[13] = "            temp[i] = A[i];                          ";
	m_pCodeDisplayWnd->m_Sentence[14] = "      for (j=1; j<=right-mid; j++)                   ";
	m_pCodeDisplayWnd->m_Sentence[15] = "            temp[right-j+1] = A[j+mid];              ";
	m_pCodeDisplayWnd->m_Sentence[16] = "      for (i=left,j=right,k=left; k<=right; k++)     ";
	m_pCodeDisplayWnd->m_Sentence[17] = "            if (temp[i] < temp[j])                   ";
	m_pCodeDisplayWnd->m_Sentence[18] = "                  A[k] = temp[i++];                  ";
	m_pCodeDisplayWnd->m_Sentence[19] = "            else                                     ";
	m_pCodeDisplayWnd->m_Sentence[20] = "                  A[k] = temp[j--];                  "; 
	m_pCodeDisplayWnd->m_Sentence[21] = "}                                                    "; 

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


void CMergeSortShowDlg::inssort(int A[], int n)
{
	int temp;
	for(int i=1; i<n; i++)
		for(int j=i; ((j>0)&&(A[j]<A[j-1])); j--)
		{
			temp = A[j];
			A[j] = A[j-1];
			A[j-1] = temp;
		}
}


void CMergeSortShowDlg::mergesort(int A[], int temp[], int left, int right) //要演示的程序
{
	// TODO: Add extra validation here
	int i, j, k, mid;

	if(SetValue(i, j, k, mid, A, temp, left, right)) return;
	SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
	m_Stack_Str.Empty();
	m_Stack_Str.Format("Call mergesort(A=%d, temp=%d, left=%d, right=%d)", A, temp, left, right);
	PushStack(m_Stack_Str);

	CString str;
	///////////////////////////////////////////////////////////////////////////////////////////
	if(SetValue(i, j, k, mid, A, temp, left, right)) return;
	SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
	SetCode(2);
	if ((right-left) <= 2)  ////////////////////////////////////////////////////////////////////THRESHOLD=2

	///////////////////////////////////////////////////////////////////////////////////////////
    {//////////////////////////////////////////////////////////////////////////////////////////
		if(SetValue(i, j, k, mid, A, temp, left, right)) return;
		SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
		SetCode(4);
		inssort(&A[left],right-left+1);/////////////////////////////////////////////////////////

	////////////////////////////////////////////////////////////////////////////////////////////
		if(SetValue(i, j, k, mid, A, temp, left, right)) return;
		SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
		SetCode(5);
		PopStack();
	    return;/////////////////////////////////////////////////////////////////////////////////
	}///////////////////////////////////////////////////////////////////////////////////////////

	////////////////////////////////////////////////////////////////////////////////////////////
	if(SetValue(i, j, k, mid, A, temp, left, right)) return;
	SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
	SetCode(7);
    mid = (left+right)/2;//////////////////////////////////////////////////////////

	////////////////////////////////////////////////////////////////////////////////////////////
	if(SetValue(i, j, k, mid, A, temp, left, right)) return;
	SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
	SetCode(8);
	if (left == right)//////////////////////////////////////////////////////////////////////////

	////////////////////////////////////////////////////////////////////////////////////////////
	{
		if(SetValue(i, j, k, mid, A, temp, left, right)) return;
		SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
		SetCode(9);
		PopStack();
		return;/////////////////////////////////////////////////////////////////////////////////
	}///////////////////////////////////////////////////////////////////////////////////////////

	////////////////////////////////////////////////////////////////////////////////////////////
	if(SetValue(i, j, k, mid, A, temp, left, right)) return;
	SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
	SetCode(10);
	mergesort(A, temp, left, mid);//////////////////////////////////////////////////////////////

	////////////////////////////////////////////////////////////////////////////////////////////
	if(SetValue(i, j, k, mid, A, temp, left, right)) return;
	SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
	SetCode(11);
	mergesort(A, temp, mid+1, right);///////////////////////////////////////////////////////////

	////////////////////////////////////////////////////////////////////////////////////////////
	if(SetValue(i, j, k, mid, A, temp, left, right)) return;
	SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
	SetCode(12);
	for (i=mid; i>=left; i--)///////////////////////////////////////////////////////////////////

	////////////////////////////////////////////////////////////////////////////////////////////
	{///////////////////////////////////////////////////////////////////////////////////////////
		if(SetValue(i, j, k, mid, A, temp, left, right)) return;
		SetMoveValue(TRUE, TRUE, FALSE, i, i, A, temp);
		SetCode(13);
		temp[i] = A[i];/////////////////////////////////////////////////////////////////////////
		if(SetValue(i, j, k, mid, A, temp, left, right)) return;
		SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
		SetCode(12);
	}///////////////////////////////////////////////////////////////////////////////////////////

	////////////////////////////////////////////////////////////////////////////////////////////
	if(SetValue(i, j, k, mid, A, temp, left, right)) return;
	SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
	SetCode(14);
    for (j=1; j<=right-mid; j++)////////////////////////////////////////////////////////////////

	////////////////////////////////////////////////////////////////////////////////////////////
	{///////////////////////////////////////////////////////////////////////////////////////////
		if(SetValue(i, j, k, mid, A, temp, left, right)) return;
		SetMoveValue(TRUE, TRUE, FALSE, j+mid, right-j+1, A, temp);
		SetCode(15);
		temp[right-j+1] = A[j+mid];//////////////////////////////////////////////////////////////
		if(SetValue(i, j, k, mid, A, temp, left, right)) return;
		SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
		SetCode(14);
	}///////////////////////////////////////////////////////////////////////////////////////////

	/////////////////////////////////////////////////////////////////////////////////////////////
	if(SetValue(i, j, k, mid, A, temp, left, right)) return;
	SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
	SetCode(16);
	for (i=left,j=right,k=left; k<=right; k++)//////////////////////////////

	////////////////////////////////////////////////////////////////////////////////////////////
	{///////////////////////////////////////////////////////////////////////////////////////////
		if(SetValue(i, j, k, mid, A, temp, left, right)) return;
		SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
		SetCode(17);
		if (temp[i] < temp[j])///////////////////////////////////////////////////////////

	//////////////////////////////////////////////////////////////////////////////
		{/////////////////////////////////////////////////////////////////////////
			if(SetValue(i, j, k, mid, A, temp, left, right)) return;
			SetMoveValue(TRUE, FALSE, TRUE, i, k, A, temp);
			SetCode(18);
			A[k] = temp[i++];/////////////////////////////////////////////////////
		}/////////////////////////////////////////////////////////////////////////

	///////////////////////////////////////////////////////////////////////////////
       else////////////////////////////////////////////////////////////////////////
	   {///////////////////////////////////////////////////////////////////////////
   			if(SetValue(i, j, k, mid, A, temp, left, right)) return;
			SetMoveValue(TRUE, FALSE, TRUE, j, k, A, temp);
			SetCode(20);
			A[k] = temp[j--];////////////////////////////////////////////////////////
			if(SetValue(i, j, k, mid, A, temp, left, right)) return;
			SetMoveValue(FALSE, FALSE, FALSE, 0, 0, A, temp);
			SetCode(16);
	   }/////////////////////////////////////////////////////////////////////////////
	}////////////////////////////////////////////////////////////////////////////////
	PopStack();
}

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

	pDialog->m_step = 0; 
	pDialog->ResetCodeSentence();
	pDialog->ResetStackSentence();
	pDialog->ResetMoveWnd();
	pDialog->mEnd = FALSE;
	pDialog->mergesort(pDialog->m_A, pDialog->m_temp, 0, 7);
	if(pDialog->m_step >= 0)
		AfxMessageBox("演示成功结束!!!");
	else
		AfxMessageBox("演示被终止!!!");
	pDialog->mEnd = TRUE;
	pDialog->mAuto = FALSE;
	pDialog->mExist = FALSE;
	return 0;
}	


void CMergeSortShowDlg::OnSingleStep() 
{
	// TODO: Add your control notification handler code here
	if(	mExist)
	{
		UpdateData(FALSE);
		if(m_step==0)
		{
			m_step++; 
			mStepEvent.SetEvent();
		}
		return;
	}
	CMergeSortShowDlg *pDialog = (CMergeSortShowDlg *)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 CMergeSortShowDlg::OnCancel() 
{
	// TODO: Add extra cleanup here
	if((mAuto == FALSE)||(mEnd == TRUE))
	      CDialog::OnCancel();
}

void CMergeSortShowDlg::OnEndShow() 
{
	// TODO: Add your control notification handler code here
	UpdateData(FALSE);
	if(m_step==0)
	{
		m_step = -1; 
		mStepEvent.SetEvent();
	}
	
}

void CMergeSortShowDlg::OnAutoStep() 
{
	// TODO: Add your control notification handler code here
	mAuto = TRUE;
	if(	mExist)
	{
		UpdateData(FALSE);
		if(m_step==0)
		{
			m_step++; 
			mStepEvent.SetEvent();
		}
		return;
	}
	CMergeSortShowDlg *pDialog = (CMergeSortShowDlg *)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;
}