heapsortdlg.cpp

此程序实现了堆排序,并且使用了MFC的图形界面,非常实用

// HeapSortDlg.cpp : implementation file
//

#include "stdafx.h"
#include "HeapSort.h"
#include "HeapSortDlg.h"
#include "Heap.h"
#include "InputDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHeapSortDlg dialog

CHeapSortDlg::CHeapSortDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CHeapSortDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CHeapSortDlg)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);

}

void CHeapSortDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CHeapSortDlg)
	DDX_Control(pDX, IDC_HEAPSORT, m_bStart);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CHeapSortDlg, CDialog)
	//{{AFX_MSG_MAP(CHeapSortDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_INPUTNUMBER, OnInputNumber)
	ON_BN_CLICKED(IDC_HEAPSORT, OnHeapsort)
	ON_WM_TIMER()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHeapSortDlg message handlers

BOOL CHeapSortDlg::OnInitDialog()
{
	CDialog::OnInitDialog();


	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}
	
	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	
//	CWnd::SetDlgItemText(IDC_OUTPUT,g_stHeapSortPoints[0]);  // 测试输出结果
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CHeapSortDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CHeapSortDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CHeapSortDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CHeapSortDlg::OnInputNumber() 
{
	m_nStep = 0;
	m_nNow  = 0;
	CInputDlg dlg;
	dlg.DoModal();
	m_nNumber[0] = dlg.m_nEdit1;
	m_nNumber[1] = dlg.m_nEdit2;
	m_nNumber[2] = dlg.m_nEdit3;
	m_nNumber[3] = dlg.m_nEdit4;
	m_nNumber[4] = dlg.m_nEdit5;
	m_nNumber[5] = dlg.m_nEdit6;
	m_nNumber[6] = dlg.m_nEdit7;
	//		TRACE("POINTS= %d",m_nNumber[0]);    //此处用来调试代码
	OnDisplayList();
	m_bStart.EnableWindow(TRUE);
}


void CHeapSortDlg::OnHeapsort() 
{
	bool flag = true;
    for (int i = 0 ; i < 6 ; i++)
		if (m_nNumber[i] > m_nNumber[i+1])
		{
			flag = false;
			break;
		}
	if (flag) NoNeedSort();
	else
	{
	   HeapSort(m_nNumber,7);    
	   m_Timer = SetTimer(1,1000,NULL);                    //启动计时器
	} 
		
	
}



void CHeapSortDlg::OnTimer(UINT nIDEvent) 
{
	// TODO: Add your message handler code here and/or call default
	OnNextStep();
	CDialog::OnTimer(nIDEvent);
}


void CHeapSortDlg::OnDisplayList()
{
CEdit *output = (CEdit *)GetDlgItem(IDC_SORTANSWER);

    CString cstemp="";
	ChangeNumberToString(cstemp,m_nNumber);
	output->SetWindowText("");                      //清屏
	output->SetSel(20000,-1);                       //将光标移至末尾 防止输出混乱
	output->ReplaceSel("初始序列为:\r\n"+cstemp);
	output->ReplaceSel("\r\n");
}

void CHeapSortDlg::ChangeNumberToString(CString &st, int list[])
{
CString csTemp;
    for (int i = 0 ; i < 7 ; i++)
	{
		csTemp = "";
		csTemp.Format(" %d",list[i]);
		st = st + csTemp ;
	}
}

void CHeapSortDlg::GetHeapTop(CString &top, CString st)
{
    top = top + st[1];
}

void CHeapSortDlg::OnNextStep()
{
    CEdit* output = (CEdit *)GetDlgItem(IDC_SORTANSWER);
    CString csTemp = "";

	output->SetSel(20000,-1);	//将光标移至末尾，避免文字混乱
	csTemp = "";
    csTemp.Format("%d",m_nNow);
	if (m_nNow == 0) output->ReplaceSel("初始堆:\r\n");
	 else output->ReplaceSel("第"+csTemp+"次调整后\r\n");
	output->ReplaceSel(m_spShow[m_nNow]);
	output->ReplaceSel(" 堆顶元素为:");
	csTemp = "";
	GetHeapTop(csTemp,m_spShow[m_nNow]);
    output->ReplaceSel(csTemp);
	output->ReplaceSel("\r\n");
	                                         //在右框中输出排序过程
   
    CClientDC dc(this);
	CPoint p1,p2;
	CBrush brush(RGB(255,255,255));


	dc.SetViewportOrg(140,100);
	p1.x = -110;  p1.y = -20;  p2.x = 140 ;  p2.y = 200;

	CRect rect(p1,p2);
	CBrush *pOldBrush = dc.SelectObject(&brush);
	dc.FillRect(&rect,&brush);
    dc.SelectObject(pOldBrush);
    
	CHeap heap;
	heap.root = heap.CreateHeap(m_nList[m_nNow],1,m_nNow);
	heap.DrawHeap(&dc,heap.root,0,0,0);      //左框中输出堆
  
	m_nNow++;
	if (m_nNow == m_nStep) SortEnd();
}

void CHeapSortDlg::Swap(int *a, int *b)
{
    int temp;
	temp = *a;
    *a   = *b;
    *b   = temp;
}

// 调整堆数组
// array是待调整的堆数组,i是待调整的数组元素的位置,length是数组的长度
void CHeapSortDlg::HeapAdjust(int array[], int i, int length)
{
	int child, temp;
	
    for (temp = array[i]; 2 * i + 1 < length; i = child)
    {
        child = 2 * i + 1;
		
        // 得到子结点中较小的结点
        if (child != length - 1 && array[child + 1] > array[child])
            ++child;
		
        // 如果较小的子结点大于父结点那么把较小的子结点往上移动,替换它的父结点
        if (temp < array[child])
        {
            array[i] = array[child];
        }
        else    // 否则退出循环
        {
            break;
        }
    }
	
    // 最后把需要调整的元素值放到合适的位置
    array[i] = temp;
}

void CHeapSortDlg::HeapSort(int array[], int length)
{
	CString csTemp;
// 调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素
    for (int i = length / 2 - 1; i >= 0; --i)
    {
        HeapAdjust(array, i, length);
    }
	csTemp = "";
    ChangeNumberToString(csTemp,array);
   	m_spShow[m_nStep] = csTemp;
	for (i = 0 ; i < 7 ; i++) m_nList[m_nStep][i] = array[i];
	
	m_nStep ++;
	

    // 从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素
    for (i = length - 1; i > 0; --i)
    {
        // 把第一个元素和当前的最后一个元素交换,
        // 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
        Swap(&array[0], &array[i]);

        // 对当前的序列进行调整,调整完之后保证第一个元素是当前序列的最大值
        HeapAdjust(array, 0, i);
	    csTemp = "";
		for (int j = 0 ; j < 7 ; j++) m_nList[m_nStep][j] = array[j];
		ChangeNumberToString(csTemp,array);
   	    m_spShow[m_nStep] = csTemp;
        m_nStep ++;
	}
}

void CHeapSortDlg::SortEnd()
{
	CEdit *output = (CEdit *)GetDlgItem(IDC_SORTANSWER);
	if (m_Timer != 0 ) 
	{
		KillTimer(m_Timer);
		m_Timer = 0;
	}
	output->SetSel(20000,-1);	//将光标移至末尾，避免文字混乱
	output->ReplaceSel("排序结束!  ");
	output->ReplaceSel("\r\n");

	m_bStart.EnableWindow(FALSE);  //排序结束之后,将开始'排序按钮"置灰

}



void CHeapSortDlg::NoNeedSort()
{
   	CEdit *output = (CEdit *)GetDlgItem(IDC_SORTANSWER);
    output->SetSel(20000,-1);
	output->ReplaceSel("该序列已经是有序序列!\r\n");
}