yblm.cpp

数据结构中有关FLOYD算法的VC++程序

// YBLM.cpp : implementation file
//

#include "stdafx.h"
#include "Ex_FDYangBoLiMan.h"
#include "YBLM.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// YBLM dialog
int a[4][4];
int path[4][4];
int Edge[4][4]={{0,1,100,4},{100,0,9,2},{3,5,0,8},{100,100,6,0}};

YBLM::YBLM(CWnd* pParent /*=NULL*/)
	: CDialog(YBLM::IDD, pParent)
{
	//{{AFX_DATA_INIT(YBLM)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
}


void YBLM::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(YBLM)
	DDX_Control(pDX, IDC_MSFLEXGRID1, m_grid1);
	DDX_Control(pDX, IDC_MSFLEXGRID10, m_grid10);
	DDX_Control(pDX, IDC_MSFLEXGRID2, m_grid2);
	DDX_Control(pDX, IDC_MSFLEXGRID3, m_grid3);
	DDX_Control(pDX, IDC_MSFLEXGRID4, m_grid4);
	DDX_Control(pDX, IDC_MSFLEXGRID5, m_grid5);
	DDX_Control(pDX, IDC_MSFLEXGRID6, m_grid6);
	DDX_Control(pDX, IDC_MSFLEXGRID7, m_grid7);
	DDX_Control(pDX, IDC_MSFLEXGRID8, m_grid8);
	DDX_Control(pDX, IDC_MSFLEXGRID9, m_grid9);
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(YBLM, CDialog)
	//{{AFX_MSG_MAP(YBLM)
	ON_BN_CLICKED(IDC_BUTTON_FLOYD, OnButtonFloyd)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// YBLM message handlers

BOOL YBLM::OnInitDialog() 
{
	CDialog::OnInitDialog();
	
	// TODO: Add extra initialization here
	m_grid1.SetRow(0);
	m_grid1.SetCol(0);
    m_grid1.SetText("矩阵1");
	DispMatrix(m_grid1);
	return TRUE;  // return TRUE unless you set the focus to a control
	              // EXCEPTION: OCX Property Pages should return FALSE
}

void YBLM::OnButtonFloyd() 
{
	// TODO: Add your control notification handler code here
	AllLengths(4);
	DispMatrix(m_grid2);
		AllLengths(4);
	DispMatrix(m_grid3);
		AllLengths(4);
	DispMatrix(m_grid4);
		AllLengths(4);
	DispMatrix(m_grid5);
		AllLengths(4);
	DispMatrix(m_grid6);
		AllLengths(4);
	DispMatrix(m_grid7);
		AllLengths(4);
	DispMatrix(m_grid8);
		AllLengths(4);
	DispMatrix(m_grid9);
		AllLengths(4);
	DispMatrix(m_grid10);
}

void YBLM::DispMatrix(CMSFlexGrid &m_grid1)
{
	int i,j;
  CString str;
  for (i=1;i<=4;i++)
  { str.Format("第%d列",i);
     m_grid1.SetRow(0);
     m_grid1.SetCol(i);
     m_grid1.SetText(str);
  }
  for (j=1;j<=4;j++)
  {  str.Format("第%d行",j);
     m_grid1.SetRow(j);
     m_grid1.SetCol(0);
     m_grid1.SetText(str);
  }
 for (i=1;i<=4;i++)
 {  
	 for (j=1;j<=4;j++)
	   {    
			m_grid1.SetRow(i);
			m_grid1.SetCol(j);
			str.Format("%d",Edge[i-1][j-1]);
            m_grid1.SetText(str);

       }

}
}

void YBLM::AllLengths(int n)
{
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			a[i][j]=Edge[i][j];
			if(i!=j && a[i][j]<100)
				path[i][j]=i;
			else
				path[i][j]=0;
		}
	}
	for(int k=0;k<4;k++)
		for(int i=0;i<4;i++)
			for(int j=0;j<n;j++)
				if(a[i][k]+a[k][j]<a[i][j])
				{
					a[i][j]=a[i][k]+a[k][j];
					path[i][j]=path[k][j];
				}
}