mini_treedlg.cpp

数据结构课程设计！MFC做的！ 其中有个是链表（单链表

// 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  /////////////////////////