?? mini_treedlg.cpp
字號:
// mini_treeDlg.cpp : implementation file
//
#include "stdafx.h"
#include "mini_tree.h"
#include "mini_treeDlg.h"
#include "AppFace.h"
#include <math.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()
/////////////////////////////////////////////////////////////////////////////
// CMini_treeDlg dialog
CMini_treeDlg::CMini_treeDlg(CWnd* pParent /*=NULL*/)
: CDialog(CMini_treeDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CMini_treeDlg)
m_e1 = 0;
//}}AFX_DATA_INIT
// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}
void CMini_treeDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CMini_treeDlg)
DDX_Text(pDX, IDC_EDIT1, m_e1);
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CMini_treeDlg, CDialog)
//{{AFX_MSG_MAP(CMini_treeDlg)
ON_WM_SYSCOMMAND()
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
ON_EN_CHANGE(IDC_EDIT1, OnChangeEdit1)
ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
ON_BN_CLICKED(IDC_RADIO1, OnRadio1)
ON_BN_CLICKED(IDC_BUTTON3, Ondanbu)
ON_BN_CLICKED(IDC_RADIO2, OnRadio2)
ON_WM_CTLCOLOR()
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CMini_treeDlg message handlers
BOOL CMini_treeDlg::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
m_time=400;
return TRUE; // return TRUE unless you set the focus to a control
}
void CMini_treeDlg::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 CMini_treeDlg::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
{ CRect rect;
CPaintDC dc(this);
GetClientRect(rect);
dc.FillSolidRect(rect,RGB(230,250,250));
CDialog::OnPaint();
}
}
HBRUSH CMini_treeDlg::OnCtlColor(CDC* pDC, CWnd* pWnd, UINT nCtlColor)
{
// TODO: Change any attributes of the DC here
// TODO: Return a different brush if the default is not desired
CWnd* wnd = (CWnd*)GetDlgItem(IDC_EDIT1) ;
HBRUSH hbr = CDialog::OnCtlColor(pDC, wnd, nCtlColor);
//SetTextColor(pDC->GetSafeHdc(), RGB(255, 0, 100));
return hbr;
}
// The system calls this to obtain the cursor to display while the user drags
// the minimized window.
HCURSOR CMini_treeDlg::OnQueryDragIcon()
{
return (HCURSOR) m_hIcon;
}
/////////////////////////////////////////////////////////////////
/////////////////////////// My Code ////////////////////////////
# include <iostream.h>
# include <stdlib.h>
# include <stdio.h>
# define R 20
# define INFINITY 10000
# define MAX_VERTEX_NUM 20
# define OK 1
# define ERROR 0
# define dan 1
# define zidong 2
typedef struct ArcCell{
float adj;
int *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
int vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
struct {
int adjvex;
float lowcost;
}closedge[MAX_VERTEX_NUM];
int Tem[40];
int temp=2;
int kk[40];
int kk1=0;
Node N[11];
int e=1;
int from;
int kind=0;
int sT=0;
MGraph G;
void CMini_treeDlg::Drawline(Node N1,Node N2,float xx);
void InitMGraph(MGraph &G);
void CMini_treeDlg::OnChangeEdit1()
{
// TODO: Add your control notification handler code here
UpdateData(true);
from=m_e1;
}
void CMini_treeDlg::OnRadio1()
{
// TODO: Add your control notification handler code here
UpdateData(true);
UpdateWindow();
Invalidate();
OnButton1();
kind=dan;
}
void CMini_treeDlg::OnRadio2()
{
// TODO: Add your control notification handler code here
UpdateData(true);
UpdateWindow();
Invalidate();
OnButton1();
kind=zidong;
}
void CMini_treeDlg::DrawRect(Node N)
{
// TODO: Add your control notification handler code here
//CMini_treeDlg::Invalidate();
CMini_treeDlg::UpdateWindow();
int size,step,i;
size=20;step=10;i=1;
CDC *pDC = GetDC();
CRect rect; CString s;
rect.bottom = N.y - R;
rect.top = N.y + R;
rect.left = N.x - R;
rect.right = N.x + R;
s.Format("%d",e);
e++;
pDC->Ellipse(rect);
pDC->TextOut(N.x,N.y-i*step,s);
ReleaseDC(pDC);
}
void CMini_treeDlg::Drawline(Node N1,Node N2,float xx)
{
// TODO: Add your control notification handler code here
//CMini_treeDlg::Invalidate();
CMini_treeDlg::UpdateWindow();
CDC *pDC = GetDC();
CClientDC dc(this);
int size,step,i;
size=20;step=10;i=1;
CString s;
int x,y;
x=(int)(N1.x+N2.x)/2;
y=(int)(N1.y+N2.y)/2;
s.Format("%.1f",xx);
pDC->TextOut(x-5,y-i*step-5,s);
CPen pen;
pen.CreatePen(PS_SOLID, 2, RGB(0, 0, 0));
dc.SelectObject(pen);
dc.MoveTo(N1.x,N1.y);
dc.LineTo(N2.x,N2.y);
ReleaseDC(pDC);
}
int LocateVex(MGraph G,int u)
{ int i;
for (i=0;i<G.vexnum;i++)
{ if(u==G.vexs[i])return i;}
return 0;
}
void InitMGraph(MGraph &G)
{ int i,j;
G.vexnum=10,G.arcnum=11;
for(i=0;i<=9;i++)
{G.vexs[i]=i+1;}
for (i=0;i<10;i++)
for (j=0;j<10;j++)
G.arcs[i][j].adj=INFINITY;
G.arcs[0][2].adj=G.arcs[2][0].adj=1.0;
G.arcs[0][1].adj=G.arcs[1][0].adj=2.0;
G.arcs[0][4].adj=G.arcs[4][0].adj=3.0;
G.arcs[1][6].adj=G.arcs[6][1].adj=5.0;
G.arcs[2][3].adj=G.arcs[3][2].adj=4.0;
G.arcs[3][5].adj=G.arcs[5][3].adj=4.5;
G.arcs[5][6].adj=G.arcs[6][5].adj=8.0;
G.arcs[5][9].adj=G.arcs[9][5].adj=6.0;
G.arcs[6][8].adj=G.arcs[8][6].adj=3.5;
G.arcs[7][9].adj=G.arcs[9][7].adj=4.0;
G.arcs[8][9].adj=G.arcs[9][8].adj=2.5;
}
//求最小生成樹(Prim算法)
int MiniSpanTree_PRIM(MGraph ,int f)
{
if(f<1||f>10)
{MessageBox(NULL,"超出數據范圍!!請重新輸入!!","超出數據范圍!!請重新輸入!!",MB_OK);
return ERROR;}
else
{
int k,j,i;int u;
float minCost;
u=f;
k=LocateVex(G,u);
kk[kk1++]=k+1;
Tem[0]=k+1;
Tem[1]=closedge[k].adjvex;
for(j=0;j<G.vexnum;++j)
if (j!=k){closedge[j].adjvex=u;
closedge[j].lowcost=G.arcs[k][j].adj;}
closedge[k].lowcost=0;
for (i=1;i<G.vexnum;++i){
minCost=INFINITY;
for (j=0;j<G.vexnum;++j){
if (closedge[j].lowcost<minCost&&closedge[j].lowcost!=0){
minCost=closedge[j].lowcost;k=j;
}
}
kk[kk1++]=k+1;
Tem[temp]=k+1;Tem[temp+1]=closedge[k].adjvex;
temp+=2;
closedge[k].lowcost=0;
for (j=0;j<G.vexnum;++j)
if (G.arcs[k][j].adj<closedge[j].lowcost){
closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j].adj;}
}
return OK;
}
}
//自動執行作圖
void CMini_treeDlg::PrintTree_PRIM()
{
UpdateData(FALSE);
UpdateWindow();
CDC *pDC = GetDC();
CClientDC dc(this);
CString ss;
CPen pen;
int k1=0;
int tx=80,ty=430,tt=40;
pen.CreatePen(PS_SOLID, 2, RGB(255, 0, 0));
dc.SelectObject(pen);
int j=2;
int sTep;sTep=1;CString s;
for(int i=1;i<=9;i++)
{
pDC->SetBkColor(RGB(255,255,255));
ss.Format("%d",kk[k1++]);
pDC->TextOut(tx,ty,ss);
tx+=tt;
s.Format("%d",sTep);
pDC->SetBkColor(RGB(255,255,0));
pDC->TextOut((N[Tem[j]].x+N[Tem[j+1]].x)/2+5,(N[Tem[j]].y+N[Tem[j+1]].y)/2+5,s);
sTep++;
dc.MoveTo(N[Tem[j]].x,N[Tem[j]].y);
dc.LineTo(N[Tem[j+1]].x,N[Tem[j+1]].y);
j+=2;
Sleep(m_time);
}
pDC->SetBkColor(RGB(255,255,255));
ss.Format("%d",kk[k1++]);
pDC->TextOut(tx,ty,ss);
ReleaseDC(pDC);
}
//單步做圖
void CMini_treeDlg::PrintTree_dan()
{
//UpdateData(FALSE);
// UpdateWindow();
static int ii=1;
CDC *pDC = GetDC();
CClientDC dc(this);
CString ss;
CPen pen;
int ty=430,tt=40;
static int k1=0;static int tx=80;
static int sTep=1;static int j=2;
if(ii==11){k1=0;tx=80;sTep=1;j=2;ii=1;}
pen.CreatePen(PS_SOLID, 2, RGB(255, 0, 0));
dc.SelectObject(pen);
CString s;
pDC->SetBkColor(RGB(255,255,255));
ss.Format("%d",kk[k1++]);
pDC->TextOut(tx,ty,ss);
tx+=tt;
s.Format("%d",sTep);
pDC->SetBkColor(RGB(255,255,0));
if(sTep<10){
pDC->TextOut((N[Tem[j]].x+N[Tem[j+1]].x)/2+5,(N[Tem[j]].y+N[Tem[j+1]].y)/2+5,s);
sTep++;
}
dc.MoveTo(N[Tem[j]].x,N[Tem[j]].y);
dc.LineTo(N[Tem[j+1]].x,N[Tem[j+1]].y);
j+=2;
ii++;
ReleaseDC(pDC);
}
//原始圖
void CMini_treeDlg::OnButton1()
{
// TODO: Add your control notification handler code here
//UpdateData(FALSE);
//UpdateWindow();
Invalidate();
InitMGraph(G);
int x,y;int i;int k;
x=200;y=100;i=-1;
for(k=1;k<=10;k+=2)
{ N[k].x=x;
N[k].y=y;
x=x+i*70;i=-i;
y+=70;
}
x=400;y=100;i=1;
for(k=2;k<=10;k+=2)
{
N[k].x=x;N[k].y=y;
x=x+i*70;i=-i;
y+=70;
}
for(k=1;k<=10;k++)
DrawRect(N[k]);
Drawline(N[1],N[2],2.0);
Drawline(N[1],N[3],1.0);
Drawline(N[1],N[5],3.0);
Drawline(N[2],N[7],5.0);
Drawline(N[3],N[4],4.0);
Drawline(N[4],N[6],4.5);
Drawline(N[6],N[7],8.0);
Drawline(N[6],N[10],6.0);
Drawline(N[7],N[9],3.5);
Drawline(N[8],N[10],4.0);
Drawline(N[9],N[10],2.5);
e=1;
}
//自動演示
void CMini_treeDlg::OnButton2()
{
// TODO: Add your control notification handler code here
if(kind==zidong)
{
UpdateData(FALSE);
UpdateWindow();
Invalidate();
OnButton1();
temp=2;
kk1=0;
int ff=from;int res;
res=MiniSpanTree_PRIM(G,ff);
if(res)PrintTree_PRIM();
}
}
// 單步演示
void CMini_treeDlg::Ondanbu()
{
// TODO: Add your control notification handler code here
//UpdateData(FALSE);
if(kind==dan)
{
if(sT==-1){OnRadio1();sT=0;}
if(sT==10){UpdateData(FALSE);UpdateWindow();MessageBox("沒有下一步!!");sT=-1;}
else{
if(sT>=0&&sT<10)
{int sTep;int res;
int ff=from;sTep=2;
res=MiniSpanTree_PRIM(G,ff);
temp=2;kk1=0;
if(res){PrintTree_dan();sT+=1;}
}
}
}
}
/////////////////////////////////////////////////////////
///////////////// My CoDe end /////////////////////////
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -