primdlg.cpp

这是我用net写的一个prim算法计算最小生成树的程序

// primDlg.cpp : 实现文件
//

#include "stdafx.h"
#include "prim.h"
#include "primDlg.h"
#include ".\primdlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif


// 用于应用程序“关于”菜单项的 CAboutDlg 对话框
int value=0;
class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// 对话框数据
	enum { IDD = IDD_ABOUTBOX };

	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV 支持

// 实现
protected:
	DECLARE_MESSAGE_MAP()
public:
};

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

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

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
END_MESSAGE_MAP()


// CprimDlg 对话框



CprimDlg::CprimDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CprimDlg::IDD, pParent)
	, m_vNum(0)
	, m_eNum(0)
	, r(false)
	,num(0)
{
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CprimDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	DDX_Text(pDX, IDC_EDIT2, m_vNum);
	DDX_Text(pDX, IDC_EDIT1, m_eNum);
}

BEGIN_MESSAGE_MAP(CprimDlg, CDialog)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	//}}AFX_MSG_MAP
	ON_BN_CLICKED(IDC_GENERATE, OnBnClickedGenerate)
	ON_WM_MOUSEMOVE()
	ON_BN_CLICKED(IDC_RADIO2, OnBnClickedRadio2)
	ON_BN_CLICKED(IDC_RADIO1, OnBnClickedRadio1)
	ON_WM_LBUTTONDOWN()
	ON_WM_LBUTTONUP()
	ON_BN_CLICKED(IDC_MIN, OnBnClickedMin)
END_MESSAGE_MAP()


// CprimDlg 消息处理程序

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

	// 将\“关于...\”菜单项添加到系统菜单中。

	// IDM_ABOUTBOX 必须在系统命令范围内。
	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);
		}
	}

	// 设置此对话框的图标。当应用程序主窗口不是对话框时，框架将自动
	//  执行此操作
	SetIcon(m_hIcon, TRUE);			// 设置大图标
	SetIcon(m_hIcon, FALSE);		// 设置小图标

	// TODO: 在此添加额外的初始化代码
	((CButton*)GetDlgItem(IDC_RADIO1))->SetCheck(1);
	return TRUE;  // 除非设置了控件的焦点，否则返回 TRUE
}

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

// 如果向对话框添加最小化按钮，则需要下面的代码
//  来绘制该图标。对于使用文档/视图模型的 MFC 应用程序，
//  这将由框架自动完成。

void CprimDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // 用于绘制的设备上下文

		SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);

		// 使图标在工作矩形中居中
		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;

		// 绘制图标
		dc.DrawIcon(x, y, m_hIcon);
		
	}
	else
	{
		CPaintDC dc(this);
	    draw(&dc);
		CDialog::OnPaint();
	}
	
}

//当用户拖动最小化窗口时系统调用此函数取得光标显示。
HCURSOR CprimDlg::OnQueryDragIcon()
{
	return static_cast<HCURSOR>(m_hIcon);
}

void CprimDlg::OnBnClickedGenerate()
{
	UpdateData(1);
	//rndBnd=new CRoundButton*[m_vNum];
	//rndBnd=new CRoundButton();
	//rndBnd->Create(_T("hello!!"),WS_CHILD|BS_PUSHBUTTON, CRect(200,200,400,400),this, 1);
	//rndBnd->ShowWindow(1);
	//for(int i=0;i<m_vNum;i++)
		//rndBnd[0].Create(_T("1"),WS_CHILD|WS_VISIBLE|BS_PUSHBUTTON, 
			//CRect(10,10,100,30),(CWnd*)m_hWnd, 1);
	//m_ctl=new CButton();
	//m_ctl->Create(_T("1"),WS_CHILD|WS_VISIBLE|BS_PUSHBUTTON, CRect(10,10,100,30),this, 1);
	//CRgn rgn;
	//rgn.CreateRoundRectRgn( 50, 50, 150, 150, 30, 30 );
	//m_ctr.SetWindowRgn((HRGN)rgn,1);
	CClientDC dc(this);
	//dc.Ellipse(CRect(20,20,45,45));
	rect=new CRect[m_vNum];
	line=new int*[m_vNum];
	line1=new int*[m_vNum];
	for(int i=0;i<m_vNum;i++)
		line[i]=new int[m_vNum];
	for(int i=0;i<m_vNum;i++)
		for(int j=0;j<m_vNum;j++)
			line[i][j]=10000;
	for(int i=0;i<m_vNum;i++)
		line1[i]=new int[m_vNum];
	for(int i=0;i<m_vNum;i++)
		for(int j=0;j<m_vNum;j++)
			line1[i][j]=0;
	CString str;
	for(int i=0;i<m_vNum;i++)
	{
		rect[i].left=25*(i%20+1);
		rect[i].top=40+25*(i/20);
		rect[i].right=25*(i%20+2);
		rect[i].bottom=65+25*(i/20);
		Invalidate();
		draw(&dc);
	}
	

}
void CprimDlg::draw(CDC* pDC)
{
	CString str;
	CBrush* pOldBrush;
	CBrush* pBrush=new CBrush(RGB(0,255,0));
	pOldBrush=pDC->SelectObject(pBrush);
	for(int i=0;i<m_vNum;i++)
	{
		str.Format("%d",i+1);
		CSize size;
		size=pDC->GetTextExtent(str);
		pDC->Ellipse(&rect[i]);
		double x=(rect[i].right-rect[i].left)/2+rect[i].left;
		double y=(rect[i].bottom-rect[i].top)/2+rect[i].top;
		CRect rect1(x-size.cx/2,y-size.cy/2,x+size.cx/2,y+size.cy/2);
		pDC->SetBkMode(TRANSPARENT);
		pDC->DrawText(str,&rect1,0);
		
	}
	CPen *pOldPen,*pen,*pen1;
	pen=new CPen(PS_SOLID, 2, RGB(0,0,255));
	pen1=new CPen(PS_SOLID, 2, RGB(255,0,0));
	for(int i=0;i<m_vNum;i++)
	{
		for(int j=0;j<i;j++)
		{
			if(line[i][j]<10000)
			{
				if(line1[i][j])
				{
					pOldPen=pDC->SelectObject(pen1);
					CPoint p1,p2;
					p1=Center(rect[i]);
					p2=Center(rect[j]);
					pDC->MoveTo(p1);
					pDC->LineTo(p2);
					str.Format("%d",line[i][j]);
					pDC->TextOut((p1.x+p2.x)/2,(p1.y+p2.y)/2,str);
					pDC->SelectObject(pOldPen);	
				}
				else
				{
					pOldPen=pDC->SelectObject(pen);
					CPoint p1,p2;
					p1=Center(rect[i]);
					p2=Center(rect[j]);
					pDC->MoveTo(p1);
					pDC->LineTo(p2);
					str.Format("%d",line[i][j]);
					pDC->TextOut((p1.x+p2.x)/2,(p1.y+p2.y)/2,str);
					pDC->SelectObject(pOldPen);	
				}
			}

		}
	}
	
	pDC->SelectObject(pOldBrush);

}

void CprimDlg::OnMouseMove(UINT nFlags, CPoint point)
{
	if(isInRect(point))
		SetCursor(::LoadCursor(NULL,(LPCTSTR)IDC_CROSS));
	else SetCursor(::LoadCursor(NULL,(LPCTSTR)IDC_ARROW));
	CDialog::OnMouseMove(nFlags, point);
}

int CprimDlg::isInRect(CPoint point)
{
	for(int i=0;i<m_vNum;i++)
	{
		if(point.x<rect[i].right&&point.x>rect[i].left&&point.y>rect[i].top&&point.y<rect[i].bottom)
		return i+1;
	}
	return false;
}

void CprimDlg::OnBnClickedRadio2()
{
	r=1;
}


void CprimDlg::OnBnClickedRadio1()
{
	r=0;
}

void CprimDlg::OnLButtonDown(UINT nFlags, CPoint point)
{
	num=isInRect(point);
	CDialog::OnLButtonDown(nFlags, point);
}

void CprimDlg::OnLButtonUp(UINT nFlags, CPoint point)
{
	CPoint point1(point.x-12.5,point.y-12.5);
	if(num&&!r)
	{
	    rect[num-1].MoveToXY(point1);
		Invalidate();
		num=0;
	}
	int num1=isInRect(point);
	if(num&&r&&num1&&num1!=num)
	{
		CDlg dlg;
		if(IDOK==dlg.DoModal())
			line[num-1][num1-1]=line[num1-1][num-1]=value;
		Invalidate(1);
	}
	num=0;
	CDialog::OnLButtonUp(nFlags, point);
}

CPoint CprimDlg::Center(CRect rect)
{
	CPoint point;
	point.x=(rect.right-rect.left)/2+rect.left;
	point.y=(rect.bottom-rect.top)/2+rect.top;
	return point;
}

void CprimDlg::OnBnClickedMin()
{
	Prim(m_vNum,line);
	Invalidate();
}

void CprimDlg::Prim(int n, int** c)
{
	int *lowcost=new int[n];  
	int *closest=new int[n];  
	bool *s=new bool[n];  

	s[0]=true;  
	for(int i=1;i<=n;i++)  
	{
		lowcost[i]=c[0][i];
		closest[i]=0;
		s[i]=false;
	}

	for(i=1;i<n;i++)  
	{
		int min=10000;  
		int j=1;  
		for(int k=1;k<n;k++)  
			if((lowcost[k]<min) && (!s[k]))
			{
				min=lowcost[k];
				j=k;
			}
		
		//cout<<"  "<<closest[j]+1<<"-------"<<j+1<<endl;
		line1[closest[j]][j]=line1[j][closest[j]]=1;
		s[j]=true;  
		for(k=1;k<n;k++) 
			if((c[j][k]<lowcost[k]) && (!s[k]))
			{
				lowcost[k]=c[j][k];
				closest[k]=j;
			}
	}
}