matrixchainview.cpp

这是算法程序中用求矩阵连乘问题的c++实现

// MatrixChainView.cpp : implementation of the CMatrixChainView class
//

#include "stdafx.h"
#include "MatrixChain.h"

#include "MatrixChainDoc.h"
#include "MatrixChainView.h"

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

/////////////////////////////////////////////////////////////////////////////
// CMatrixChainView

IMPLEMENT_DYNCREATE(CMatrixChainView, CFormView)

BEGIN_MESSAGE_MAP(CMatrixChainView, CFormView)
	//{{AFX_MSG_MAP(CMatrixChainView)
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CFormView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMatrixChainView construction/destruction

CMatrixChainView::CMatrixChainView()
	: CFormView(CMatrixChainView::IDD)
{
	//{{AFX_DATA_INIT(CMatrixChainView)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// TODO: add construction code here

}

CMatrixChainView::~CMatrixChainView()
{
}

void CMatrixChainView::DoDataExchange(CDataExchange* pDX)
{
	CFormView::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CMatrixChainView)
		// NOTE: the ClassWizard will add DDX and DDV calls here
	//}}AFX_DATA_MAP
}

BOOL CMatrixChainView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CFormView::PreCreateWindow(cs);
}

void CMatrixChainView::OnInitialUpdate()
{
	CFormView::OnInitialUpdate();
	GetParentFrame()->RecalcLayout();
	ResizeParentToFit();

}

/////////////////////////////////////////////////////////////////////////////
// CMatrixChainView printing

BOOL CMatrixChainView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CMatrixChainView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CMatrixChainView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

void CMatrixChainView::OnPrint(CDC* pDC, CPrintInfo* /*pInfo*/)
{
	// TODO: add customized printing code here
}

/////////////////////////////////////////////////////////////////////////////
// CMatrixChainView diagnostics

#ifdef _DEBUG
void CMatrixChainView::AssertValid() const
{
	CFormView::AssertValid();
}

void CMatrixChainView::Dump(CDumpContext& dc) const
{
	CFormView::Dump(dc);
}

CMatrixChainDoc* CMatrixChainView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CMatrixChainDoc)));
	return (CMatrixChainDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CMatrixChainView message handlers

int CMatrixChainView::GetIntArray(int a[],char * s)
{
    int i,j,State;
    BYTE c;

    j=0;
    State=0;
    for (i=0;c=s[i];i++)
    if (State==0)				// 如果等待数字
    {
	if (isdigit(c))
	{
	    a[j]=c-'0';
	    State=1;
	}
    }
    else
    {
	if (isdigit(c))
	{
	    a[j]=a[j]*10+(c-'0');
	}
	else
	{
	    j++;
	    State=0;
	}
    }
    return (State==0) ? j : j+1;;
}

int CMatrixChainView::TrackBack(int * s[],int i,int j,char * z)
{
    int k;
//    char zz1[256];
//    char zz2[256];

    if (i==j)
    {
	sprintf(z+strlen(z),"A%d",i);
	return 0;
    }
    k=s[i][j];
    if (i!=k) strcat(z,"(");
    TrackBack(s,i,k,z);
    if (i!=k) strcat(z,")");
    if (k+1!=j) strcat(z,"(");
    TrackBack(s,k+1,j,z);
    if (k+1!=j) strcat(z,")");
//    sprintf(z,"(%s)(%s)",zz1,zz2);
    return 0;
}

int CMatrixChainView::MatrixChain(int p[],int n)
{
    int * m[1024];
    int * s[1024];
    int   i,j,k,r,x;
    int * z;
    char zzz[1024];

    for (i=0;i<n+4;i++)
    {
	m[i]=0;
	s[i]=0;
    }
    z=(int *)malloc(2*sizeof(int)*(n+2)*(n+2));
    for (i=1;i<=n;i++)
    {
	m[i]=z;
	z=&z[n+1];
    }
    for (i=1;i<=n;i++)
    {
	s[i]=z;
	z=&z[n+1];
    }

    for (i=1;i<=n;i++)
    {
	m[i][i]=0;
    }

    for (r=2;r<=n;r++)				// 链长从 2 开始，到 n 为止
    {
	for (i=1;i<=n-r+1;i++)			// 链从 i 开始
	{
	    j=i+r-1;				// 链到 j 为止
	    m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
	    s[i][j]=i;
	    for (k=i+1;k<j;k++)
	    {
		x=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
		if (x<m[i][j])
		{
		    m[i][j]=x;
		    s[i][j]=k;
		}
	    }
	}
    }
    x=m[1][n];
    zzz[0]=0;
    TrackBack(s,1,n,zzz);

    CListBox * qq=(CListBox *)GetDlgItem(IDC_LIST1);
    qq->ResetContent();
    qq->AddString(zzz);
    free(m[1]);
    return 0;
}

void CMatrixChainView::OnButton1() 
{
	// TODO: Add your control notification handler code here
	char ss[256];
	int   n;
	int   a[256];

	GetDlgItemText(IDC_EDIT1,ss,sizeof(ss));
	n=GetIntArray(a,ss);
	MatrixChain(a,n-1);
}