datastructex1dlg.cpp

数据结构 最小生成树 两种算法 还有代价计算啦

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

#include "stdafx.h"
#include "DataStructEx1.h"
#include "DataStructEx1Dlg.h"
#include ".\datastructex1dlg.h"

#include < time.h >

#ifdef _DEBUG
#define new DEBUG_NEW
#endif


// 用于应用程序“关于”菜单项的 CAboutDlg 对话框

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

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

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

// 实现
protected:
	DECLARE_MESSAGE_MAP()
};

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

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

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
END_MESSAGE_MAP()


// CDataStructEx1Dlg 对话框



CDataStructEx1Dlg::CDataStructEx1Dlg(CWnd* pParent /*=NULL*/)
	: CDialog(CDataStructEx1Dlg::IDD, pParent)
{
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

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

BEGIN_MESSAGE_MAP(CDataStructEx1Dlg, CDialog)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	//}}AFX_MSG_MAP
	ON_BN_CLICKED(IDC_BUTTON1, OnBnClickedButton1)
	ON_BN_CLICKED(IDC_BUTTON3, OnBnClickedButton3)
	ON_BN_CLICKED(IDC_BUTTON2, OnBnClickedButton2)
	ON_WM_TIMER()
END_MESSAGE_MAP()


// CDataStructEx1Dlg 消息处理程序

BOOL CDataStructEx1Dlg::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: 在此添加额外的初始化代码

	m_pointPos[ 0 ] = CPoint( 530, 50 );
	m_pointPos[ 1 ] = CPoint( 630, 90 );
	m_pointPos[ 2 ] = CPoint( 700, 160 );
	m_pointPos[ 3 ] = CPoint( 700, 250 );
	m_pointPos[ 4 ] = CPoint( 630, 320 );
	m_pointPos[ 5 ] = CPoint( 530, 360 ); 
	m_pointPos[ 6 ] = CPoint( 430, 320 );
	m_pointPos[ 7 ] = CPoint( 360, 250 );
	m_pointPos[ 8 ] = CPoint( 360, 160 );
	m_pointPos[ 9 ] = CPoint( 430, 90 );




	
	return TRUE;  // 除非设置了控件的焦点，否则返回 TRUE
}

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

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

void CDataStructEx1Dlg::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
	{
		CDialog::OnPaint();
	}
}

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

void CDataStructEx1Dlg::OnBnClickedButton1()
{
	srand( (unsigned)time( NULL ) );	

	
	m_nSelectedLine = 0;
	for ( int i = 0; i < 10; i ++ )
	{
		m_arrNodeColor[ i ] = 0;
		for ( int j = 0; j < 10; j ++ )
			m_arrLineColor[ i ][ j ] = 0;
	}
    
	for ( int i = 0; i < 10; i ++ )
		for ( int j = 0; j < 10; j ++ )
			m_arrMap[ i ][ j ] = MAX_DISTANCE;

	m_nLine = 20 + rand() % 10;
	for ( int i = 0; i < 10; i ++ )
	{
		int temp = rand() % 10;
		if ( temp == i && temp < 9 )
			temp ++;
		else if ( temp == i && temp == 9 )
			temp --;
		m_arrMap[ i ][ temp ] = m_arrMap[ temp ][ i ] = 1 + rand() % 99;		 	
	}
	int count = 10;
	while ( count < m_nLine )
	{
		int i = rand() % 10;
		int j = rand() % 10;
		if ( i != j && m_arrMap[ i ][ j ] == MAX_DISTANCE )
		{
			m_arrMap[ i ][ j ] = m_arrMap[ j ][ i ] = 1 + rand() % 99;
			count ++;
		}
	}

    //for ( int i = 1; i <= 10; i ++ )
	//	for ( int j = 1; j <= 10; j ++ )
	//		m_arrMap[ i ][ j ] = 99;

	CClientDC dc( this );
	CString str;

	CBrush brush( RGB( 255, 255, 255 ) );			// 画白色背景
	dc.FillRect( CRect( 18, 73, 320, 345 ), &brush );

	dc.MoveTo( 18, 73 );
	dc.LineTo( 320, 73 );
	for ( int i = 1; i <= 11; i ++ )
	{
		dc.MoveTo( 18, 70 + 25 * i );
		dc.LineTo( 320, 70 + 25 * i );
	}
	
	dc.MoveTo( 18, 73 );
	dc.LineTo( 18, 345 );
	for ( int i = 1; i <= 11; i ++ )
	{
		dc.MoveTo( 45 + 25 * i, 73 );
		dc.LineTo( 45 + 25 * i, 345 );
	}
    
	str.Format( "办公点" );
	dc.TextOut( 20, 75, str );
	
	for ( int i = 0; i < 10; i ++ )
	{
		str.Format( "%d", i );
		dc.TextOut( 77 + 25 * i, 77, str );
	}
	for ( int i = 0; i < 10; i ++ )
	{
		str.Format( "%d", i );
		dc.TextOut( 45, 100 + 25 * i, str );
	}
    
	for ( int i = 0; i < 10; i ++ )
		for ( int j = 0; j < 10; j ++ )
		{
			if ( m_arrMap[ i ][ j ] == MAX_DISTANCE )
				str.Format( " --" );
			else
				str.Format( "%d", m_arrMap[ i ][ j ] );
			dc.TextOut( 75 + 25 * i, 100 + 25 * j, str );
		}
	
	DrawGraph();




}

void CDataStructEx1Dlg::DrawGraph(void)
{
	CClientDC dc( this );

	CBrush brush( RGB( 255, 255, 255 ) );			// 画白色背景
	dc.FillRect( CRect( 333, 30, 850, 400 ), &brush );

	for ( int i = 0; i < 10; i ++ )
		for ( int j = 0; j < 10; j ++ )
		{
			if ( m_arrMap[ i ][ j ] != MAX_DISTANCE )
				DrawLine( i, j );
		}

	for ( int i = 0; i < 10; i ++ )
	{
		CString str;
		
		if ( m_arrNodeColor[ i ] == 0 )
			dc.SelectStockObject( NULL_BRUSH );
		else
			dc.SelectStockObject( LTGRAY_BRUSH );
				
		str.Format( "V%d", i );
		dc.TextOut( m_pointPos[ i ].x - 7, m_pointPos[ i ].y - 7, str );
		CRect rect( m_pointPos[ i ].x - 15, m_pointPos[ i ].y - 15, m_pointPos[ i ].x + 15, m_pointPos[ i ].y + 15 );
		dc.Ellipse( rect );		
		dc.TextOut( m_pointPos[ i ].x - 7, m_pointPos[ i ].y - 7, str );
		
	}

	
	CString str;
	str.Format( "线路      长度" );
	dc.TextOut( 750, 40, str );

	for ( int i = 0; i < m_nSelectedLine; i ++ )
	{
		CString str;
		str.Format( "V%d--->V%d:  %d", m_arrSelectedLine[ i ][ 1 ], m_arrSelectedLine[ i ][ 2 ], m_arrSelectedLine[ i ][ 0 ] );
		dc.TextOut( 750, 70 + i * 25, str );
	}

	if ( m_nSelectedLine == 9 )
	{
		int sum = 0;
		for ( int i = 0; i < m_nSelectedLine; i ++ )
			sum += m_arrSelectedLine[ i ][ 0 ];
		CString str;
		str.Format( "办公点局域网总长度为: %d", sum );
		dc.TextOut( 650, 350, str );
	}
    
}

void CDataStructEx1Dlg::DrawLine(int from, int to)
{
	CClientDC dc( this );
	CPen pen1( PS_SOLID, 1, RGB( 0, 0, 0 ) );
	CPen pen2( PS_SOLID, 2, RGB( 0, 0, 255 ) );
	if ( m_arrLineColor[ from ][ to ] == 0 )
		dc.SelectObject( &pen1 );
	else
		dc.SelectObject( &pen2 );
	dc.MoveTo( m_pointPos[ from ].x, m_pointPos[ from ].y );
	dc.LineTo( m_pointPos[ to ].x, m_pointPos[ to ].y );

}


void CDataStructEx1Dlg::OnBnClickedButton2()
{
	CButton* button;
	button = ( CButton* ) GetDlgItem( IDC_BUTTON1 );
	button->EnableWindow( 0 );
	button = ( CButton* ) GetDlgItem( IDC_BUTTON2 );
	button->EnableWindow( 0 );
	button = ( CButton* ) GetDlgItem( IDC_BUTTON3 );
	button->EnableWindow( 0 );

	for ( int i = 0; i < 10; i ++ )
	{
		m_arrNodeColor[ i ] = 0;
		m_arrLowCost[ i ] = m_arrMap[ 0 ][ i ];
		m_arrClosest[ i ] = 0;
		for ( int j = 0; j < 10; j ++ )
			m_arrLineColor[ i ][ j ] = 0;
	}

	//DrawGraph();
	m_nSelectedLine = 0;
	m_nReached = 1;
	m_arrNodeColor[ 0 ] = 1;
	m_arrLowCost[ 0 ] = 0;
	m_nStep = 1;
	//DrawGraph();
    SetTimer( 1, 1000, 0 );


}

void CDataStructEx1Dlg::OnBnClickedButton3()
{
	CButton* button;
	button = ( CButton* ) GetDlgItem( IDC_BUTTON1 );
	button->EnableWindow( 0 );
	button = ( CButton* ) GetDlgItem( IDC_BUTTON2 );
	button->EnableWindow( 0 );
	button = ( CButton* ) GetDlgItem( IDC_BUTTON3 );
	button->EnableWindow( 0 );

	for ( int i = 0; i < 10; i ++ )
	{
		m_arrNodeColor[ i ] = 0;
		m_arrLowCost[ i ] = m_arrMap[ 0 ][ i ];
		m_arrClosest[ i ] = 0;
		for ( int j = 0; j < 10; j ++ )
			m_arrLineColor[ i ][ j ] = 0;
	}

	int k = 0;
	for ( int i = 0; i < 10; i ++ )
		for ( int j = 0; j < i; j ++ )
		{
			if ( m_arrMap[ i ][ j ] != MAX_DISTANCE )
			{
				m_arrSortLine[ k ][ 0 ] = m_arrMap[ i ][ j ];
				m_arrSortLine[ k ][ 1 ] = i;
				m_arrSortLine[ k ][ 2 ] = j;
				k ++;
			}
		}
	for ( int i = 0; i < k ; i ++ )
		for ( int j = 0; j < k - 1; j ++ )
		{
			if ( m_arrSortLine[ j ][ 0 ] > m_arrSortLine[ j + 1 ][ 0 ] )
			{
				int temp[ 3 ];
				for ( int t = 0; t < 3; t ++ )
				{
					temp[ t ] = m_arrSortLine[ j ][ t ];
					m_arrSortLine[ j ][ t ] = m_arrSortLine[ j + 1 ][ t ];
					m_arrSortLine[ j + 1 ][ t ] = temp[ t ];
				}
			}
		}
	for ( int i = 0; i < 10; i ++ )
		m_Stack[ i ] = i;

	//DrawGraph();
	m_nSelectedLine = 0;
	m_nCount = 0;
	//m_arrNodeColor[ 0 ] = 1;
	//m_arrLowCost[ 0 ] = 0;
	m_nStep = 1;
	//DrawGraph();
    SetTimer( 2, 1000, 0 );	

	


}



void CDataStructEx1Dlg::OnTimer(UINT nIDEvent)
{
	if ( nIDEvent == 1 )
	{
        if ( m_nStep == 1 )
		{
			int i, k;
			int min = 9999;
			DrawGraph();

			if ( m_nReached == 10 )
			{
				KillTimer( 1 );
				CButton* button;
				button = ( CButton* ) GetDlgItem( IDC_BUTTON1 );
				button->EnableWindow( 1 );
				button = ( CButton* ) GetDlgItem( IDC_BUTTON2 );
				button->EnableWindow( 1 );
				button = ( CButton* ) GetDlgItem( IDC_BUTTON3 );
				button->EnableWindow( 1 );
				return;
			}
            
			for ( int i = 0; i < 10; i ++ )
			{
				if ( m_arrLowCost[ i ] != 0 &&  m_arrLowCost[ i ] < min )
				{
					min = m_arrLowCost[ i ];  k = i;
				}
						
			}
			m_nReached ++;
			m_arrLowCost[ k ] = 0;
			m_arrNodeColor[ k ] = 1;
			m_arrLineColor[ m_arrClosest[ k ] ][ k ] = 1;
			m_arrLineColor[ k ][ m_arrClosest[ k ] ] = 1;
			int from = m_arrClosest[ k ], to = k;
			m_arrSelectedLine[ m_nSelectedLine ][ 0 ] = m_arrMap[ from ][ to ];
			m_arrSelectedLine[ m_nSelectedLine ][ 1 ] = from;
			m_arrSelectedLine[ m_nSelectedLine ][ 2 ] = to;
			m_nSelectedLine ++;			

			for  ( int i = 0; i < 10; i ++ )
			{
				if ( m_arrMap[ k ][ i ] != -1 && m_arrMap[ k ][ i ] < m_arrLowCost[ i ] )
				{
					m_arrLowCost[ i ] = m_arrMap[ k ][ i ];
					m_arrClosest[ i ] = k;
				}
			}
			//m_nStep == 2;
		}
		else if ( m_nStep == 2 )
		{

			DrawGraph();
			m_nStep = 1;
		}
                
	}






	else if ( nIDEvent == 2 )
	{
		if ( m_nStep == 1 )
		{
			DrawGraph();
			int flag = 0;
			for ( int i = 0; i < 9; i ++ )
			{
				if ( m_Stack[ i ] != m_Stack[ i + 1 ] )
				{
					flag = 1;
					break;
				}
			}

			if ( flag == 0 )
			{
				KillTimer( 2 );
				CButton* button;
				button = ( CButton* ) GetDlgItem( IDC_BUTTON1 );
				button->EnableWindow( 1 );
				button = ( CButton* ) GetDlgItem( IDC_BUTTON2 );
				button->EnableWindow( 1 );
				button = ( CButton* ) GetDlgItem( IDC_BUTTON3 );
				button->EnableWindow( 1 );
				return;
			}


			int m1 = m_arrSortLine[ m_nCount ][ 1 ], m2 = m_arrSortLine[ m_nCount ][ 2 ];
			int sn1 = m_Stack[ m1 ], sn2 = m_Stack[ m2 ];	
			m_nCount ++;
			while ( sn1 == sn2 )
			{
				m1 = m_arrSortLine[ m_nCount ][ 1 ];	m2 = m_arrSortLine[ m_nCount ][ 2 ];
				sn1 = m_Stack[ m1 ];	sn2 = m_Stack[ m2 ];	
				m_nCount ++;
			}
			for ( int i = 0; i < 10; i ++ )
			{
				if ( m_Stack[ i ] == sn2 )
					m_Stack[ i ] = sn1;
			}
            m_arrNodeColor[ m1 ] = 1;	m_arrNodeColor[ m2 ] = 1;
			m_arrLineColor[ m1 ][ m2 ] = 1;	m_arrLineColor[ m2 ][ m1 ] = 1;

			int from = m1, to = m2;
			if ( from > to )
			{
				int t = from;	from = to;	to = t;
			}
            m_arrSelectedLine[ m_nSelectedLine ][ 0 ] = m_arrMap[ from ][ to ];
			m_arrSelectedLine[ m_nSelectedLine ][ 1 ] = from;
			m_arrSelectedLine[ m_nSelectedLine ][ 2 ] = to;
			m_nSelectedLine ++;
			
			//m_nStep = 2;

		}


	}

	CDialog::OnTimer(nIDEvent);
}