convndlg.cpp

数据结构的课程设计 图的最小生成树

// ConvNDlg.cpp : implementation file
//

#include "stdafx.h"
#include "ConvN.h"
#include "ConvNDlg.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)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CConvNDlg dialog
//G.vexnum=0;
//G.arcnum=0;
CConvNDlg::CConvNDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CConvNDlg::IDD, pParent)
{
	G.vexnum=0;
	G.arcnum=0;
	//{{AFX_DATA_INIT(CConvNDlg)
	m_arcnum = 0;
	m_vexnum = 0;
	m_vexs = _T("");
	m_1a = _T("");
	m_1b = _T("");
	m_1c = 0;
	m_out2 = _T("");
	m_ouths = _T("");
	counta=0;
	countb=0;
	m_root = _T("");
	m_srsm = _T("");
	m_smst = _T("");
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CConvNDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CConvNDlg)
	DDX_Control(pDX, IDC_BUTTONabout, m_about);
	DDX_Control(pDX, IDC_LIST2, m_minitree);
	DDX_Control(pDX, IDC_LIST1, m_listout);
	DDX_Text(pDX, IDC_EDIT2, m_arcnum);
	DDV_MinMaxInt(pDX, m_arcnum, 0, 20);
	DDX_Text(pDX, IDC_EDIT1, m_vexnum);
	DDV_MinMaxInt(pDX, m_vexnum, 1, 20);
	DDX_Text(pDX, IDC_EDIT3, m_vexs);
	DDV_MaxChars(pDX, m_vexs, 20);
	DDX_Text(pDX, IDC_EDIT1a, m_1a);
	DDV_MaxChars(pDX, m_1a, 1);
	DDX_Text(pDX, IDC_EDIT1b, m_1b);
	DDV_MaxChars(pDX, m_1b, 1);
	DDX_Text(pDX, IDC_EDIT1c, m_1c);
	DDV_MinMaxInt(pDX, m_1c, 0, 9000);
	DDX_Text(pDX, IDC_EDIT4, m_root);
	DDX_Text(pDX, IDC_EDITsrsm, m_srsm);
	DDX_Text(pDX, IDC_EDITsmst, m_smst);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CConvNDlg, CDialog)
	//{{AFX_MSG_MAP(CConvNDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BUTTON3, OnButton3)
	ON_BN_CLICKED(IDC_BUTTON5, OnButton5)
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	ON_BN_CLICKED(IDC_BUTTONclear, OnBUTTONclear)
	ON_BN_CLICKED(IDC_BUTTONhelp, OnBUTTONhelp)
	ON_BN_CLICKED(IDC_BUTTONabout, OnBUTTONabout)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CConvNDlg message handlers

BOOL CConvNDlg::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

	//m_about.GetIcon();//?????????????????????????????////

	m_bExpand=FALSE;
	CRect rcDlg,rcMarker;
	GetWindowRect(rcDlg);
	m_nExpandedWidth=rcDlg.Width();
	GetDlgItem(IDC_line)->GetWindowRect(rcMarker);
	m_nNormalWidth=(rcMarker.left-rcDlg.left);
	Display();	
	// TODO: Add extra initialization here
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CConvNDlg::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 CConvNDlg::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 CConvNDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

int CConvNDlg::LocateVex(CString v)
{
	
	for(int i=0;i<G.vexnum;i++)
	{
		if(v==G.vexs[i])
			return i;
	}
	return 10000;
}

int CConvNDlg::minimum()
{
	int i,s=0,m=INFINITY;//?????????????????????????////
	for(i=0;i<G.vexnum;i++)
	{
		if(m>closedge[i].lowcost && closedge[i].lowcost!=0)
		{
			m=closedge[i].lowcost;
			s=i;
		}

	}
	return s;
}

void CConvNDlg::OnButton3() 
{
	//提交
	int i,j;
	for(i=0;i<G.vexnum;++i)//重新初始化####
		m_minitree.DeleteString(0);
	for(i=0;i<G.vexnum;i++)
		m_listout.DeleteString(0);
	UpdateData(TRUE);	
	if(m_vexnum && m_arcnum && (m_vexs.GetLength()==m_vexnum))
	{
		G.vexnum=m_vexnum;
		G.arcnum=m_arcnum;

		strncpy(G.vexs,m_vexs,sizeof(G.vexs));
	
		for(i=0;i<G.vexnum;i++)//初始化邻接矩阵
		{
			for(j=0;j<G.vexnum;j++)
			{
				if(i==j)
					G.arcs[i][j]=0;
				else
					G.arcs[i][j]=INFINITY;
			}
		}
		counta=1;
		m_smst.Format("您共需输入%d对数据",G.arcnum);
		m_srsm.Format("请输入第1对数据");
		UpdateData(FALSE);
	}

	m_1a = _T("");
	m_1b = _T("");
	m_1c = 0;
	m_out2 = _T("");
	m_ouths = _T("");
	countb=0;
	m_root = _T("");
	UpdateData(FALSE);////重新初始化####
	//OnBUTTONclear();
}

void CConvNDlg::OnButton5() 
{
	int i,j;
	UpdateData(TRUE);
	i=LocateVex(m_1a);
	j=LocateVex(m_1b);
	if(counta && (m_1a!=("")) && (m_1b!=("")) && m_1c>0 && m_1c<9000 && i!=10000 && j!=10000)
	{	
		
		G.arcs[i][j]=m_1c;
		G.arcs[j][i]=G.arcs[i][j];
		if(counta==G.arcnum)
		{				//输入所有的边时打印出图的邻接矩阵
			for(int k=0;k<G.vexnum;k++)
			{
				for(int h=0;h<G.vexnum;h++)
				{
					if(G.arcs[k][h]==INFINITY)
						m_out2.Format("   ∞");
					else
					{
						m_out2.Format("%5d",G.arcs[k][h]);
					}
					m_ouths=m_ouths+m_out2;//把一行的每一列相加,也就是所有字符串连接起来
				}
				m_listout.AddString(m_ouths);
				m_ouths="";//每输出一行后m_ouths字符串重新初始化
			}
			m_srsm.Format("您已输完%d对数据",G.arcnum);
			counta=-1;
			countb=1;
		}
		else
		{
			m_srsm.Format("请输入第%d对数据",counta+1);		
		}
		counta++;
		m_1a = _T("");
		m_1b = _T("");
		m_1c = 0;
		UpdateData(FALSE);
	}
}


void CConvNDlg::OnButton1() 
{
	UpdateData(TRUE);
	int k,j,sum=0;
	k=LocateVex(m_root);
	if(m_root!=("") && countb && k!=10000)
	{	
		for(j=0;j<G.vexnum;++j)//辅助数组初始化
		{
			if(j!=k)
			{
				closedge[j].adjvex=m_root[0];
				closedge[j].lowcost=G.arcs[k][j];
			}
			else
			{
				closedge[j].adjvex=G.vexs[j];
				closedge[j].lowcost=0;
			}
		}
		for(j=G.vexnum;j<MAX_VERTEX_NUM;j++)
		{
			closedge[j].adjvex=0;
			closedge[j].lowcost=INFINITY;
		}
		closedge[k].lowcost=0;
		
		for(int i=1;i<G.vexnum;++i)
		{//输出最小生成树的各边
			k=minimum();
			m_ouths.Format("%c   %c",closedge[k].adjvex,G.vexs[k]);
			m_minitree.AddString(m_ouths);
			sum=sum+closedge[k].lowcost;
			closedge[k].lowcost=0;
			for(j=0;j<G.vexnum;++j)
			{
				if(G.arcs[k][j]<closedge[j].lowcost)
				{
					closedge[j].adjvex=G.vexs[k];
					closedge[j].lowcost=G.arcs[k][j];
				}
			}
		}
		m_ouths.Format("所有边权值和为%d",sum);
		m_minitree.AddString(m_ouths);//输出所有边权值和
		countb=0;
	}
}


void CConvNDlg::OnBUTTONclear() //全部清除
{
	for(int i=0;i<G.vexnum;++i)
		m_minitree.DeleteString(0);
	for(i=0;i<G.vexnum;i++)
		m_listout.DeleteString(0);
	m_arcnum = 0;
	m_vexnum = 0;
	m_vexs = _T("");
	m_1a = _T("");
	m_1b = _T("");
	m_1c = 0;
	m_out2 = _T("");
	m_ouths = _T("");
	counta=0;
	countb=0;
	m_root = _T("");
	m_srsm=("");
	m_smst.Format("");
	UpdateData(FALSE);		
	
}


void CConvNDlg::OnBUTTONhelp() 
{
	Display();
}
void CConvNDlg::Display()
{
	CRect rcDlg;
	GetWindowRect(rcDlg);
	if(m_bExpand)
	{
		rcDlg.SetRect(rcDlg.left,rcDlg.top,rcDlg.left+m_nExpandedWidth,rcDlg.top+rcDlg.Height());
		m_bExpand=0;
		
	}
	else
	{
		rcDlg.SetRect(rcDlg.left,rcDlg.top,rcDlg.left+m_nNormalWidth,rcDlg.top+rcDlg.Height());
		m_bExpand=1;
	}
	MoveWindow(rcDlg,TRUE);
}

void CConvNDlg::OnBUTTONabout() 
{
	CAboutDlg aboutDlg;
	aboutDlg.DoModal();
	//m_about.();
}