arithprimlistview.cpp

师兄做的算法可视化演示程序

// ArithPrimListView.cpp : implementation file
//

#include "stdafx.h"
#include "AlgorithmicDesign.h"
#include "ArithPrimListView.h"
#include "MainFrm.h"

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

/////////////////////////////////////////////////////////////////////////////
// CArithPrimListView

IMPLEMENT_DYNCREATE(CArithPrimListView, CListView)

CArithPrimListView::CArithPrimListView()
{
}

CArithPrimListView::~CArithPrimListView()
{
}


BEGIN_MESSAGE_MAP(CArithPrimListView, CListView)
	//{{AFX_MSG_MAP(CArithPrimListView)
		// NOTE - the ClassWizard will add and remove mapping macros here.
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CArithPrimListView drawing

void CArithPrimListView::OnDraw(CDC* pDC)
{
	CDocument* pDoc = GetDocument();
	// TODO: add draw code here
}

/////////////////////////////////////////////////////////////////////////////
// CArithPrimListView diagnostics

#ifdef _DEBUG
void CArithPrimListView::AssertValid() const
{
	CListView::AssertValid();
}

void CArithPrimListView::Dump(CDumpContext& dc) const
{
	CListView::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CArithPrimListView message handlers

void CArithPrimListView::OnInitialUpdate() 
{
	CListView::OnInitialUpdate();
	
	// TODO: Add your specialized code here and/or call the base class
	CListCtrl& theCtrl = GetListCtrl();	
	theCtrl.InsertColumn(0,"  算法  ",LVCFMT_CENTER,441);
	DWORD dwStype=GetWindowLong(theCtrl.GetSafeHwnd(),GWL_STYLE);
	dwStype&=~LVS_TYPEMASK;		//Remove the current stype flags
	dwStype|=LVS_REPORT;		//Add the List stype
	dwStype|=LVS_SHOWSELALWAYS;
	dwStype|=LVS_NOLABELWRAP;
	SetWindowLong(theCtrl.GetSafeHwnd(),GWL_STYLE,dwStype);	//Set it back into the list view

	DWORD dwStyle =  theCtrl.SendMessage(LVM_GETEXTENDEDLISTVIEWSTYLE,0,0);
	dwStyle |= LVS_EX_FULLROWSELECT ;//| LVS_EX_GRIDLINES | LVS_EX_HEADERDRAGDROP;
	theCtrl.SendMessage(LVM_SETEXTENDEDLISTVIEWSTYLE, 0, (LPARAM)dwStyle);

	DWORD dwEx =  theCtrl.GetExtendedStyle();
	theCtrl.SetExtendedStyle(dwEx|LVS_EX_FLATSB);
	SetRedraw(true);

	COLORREF	clrBk	=RGB(150, 175, 230);
	theCtrl.SetBkColor( clrBk);
    theCtrl.SetTextBkColor(clrBk);

    int m_Number;
	m_Number=theCtrl.GetItemCount();
	LV_ITEM lvi;
	lvi.mask =  LVIF_TEXT | LVIF_STATE ;
	lvi.iItem = m_Number;
	lvi.iSubItem = 0;
	lvi.pszText = (LPTSTR)(LPCTSTR)("void Minspantree_Prim(adjmatrix gn,vtxptr u0){");
	lvi.stateMask =LVIS_STATEIMAGEMASK;
	lvi.state =   INDEXTOSTATEIMAGEMASK(1);
	theCtrl.InsertItem(&lvi);

	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("//从u0出发构造网gn的最小生成树,按普里姆输出树上各边");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("   for(v=1;v<=vtxnum;v++) //初始化");
	theCtrl.InsertItem(&lvi);
    m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("       if(v!=u0){");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("          closedge[v].vex=u0;");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("          closedge[v].lowcost=gn[u0][v];");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("       }");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("   closedge[u0].vex=u0;");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("   closedge[u0].lowcost=0; //辅助数组初始化");
	theCtrl.InsertItem(&lvi);

	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("   for(i=1;i<=vtxnum-1;i++){");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("       k=mininum(closedge);");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("       if(k==0){");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("           showerror();return;");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("       }");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("       else{");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("           write(closedge[k].vex,k);//输出生成树的边");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("           closedge[k].lowcost=0;//顶点并入U集");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("            for(v=1;v<=vtxnum;v++)");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("               if(gn[k][v]<=closedge[v].lowcost){");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("                   closedge[v].lowcost=gn[k][v];");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("                    closedge[v].vex=k;");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("                }//在新的顶点k并入U之后，重新选择具有最小代价的边");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("             }");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("     }");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)(" }");
	theCtrl.InsertItem(&lvi);
	m_nodenumber=0;
}

//具体处理时间响应，回调函数
void CALLBACK  CArithPrimListView::OnTimerExcute(HWND hWnd,UINT nMsg,UINT nIDEvent,DWORD dwTime)
{
    CMainFrame*	pMainFrame	=(CMainFrame*)::AfxGetMainWnd();
	CArithPrimListView *pWnd;
    pWnd=(CArithPrimListView*)(pMainFrame->pMintreegreedyFrame->p_AlgorithmiclistView);
    if(pWnd->m_odd)//单步执行
		pWnd->OnStop();
	CListCtrl& theCtrl = pWnd->GetListCtrl();
	int state=INDEXTOSTATEIMAGEMASK(1);;
    int mask=LVIF_TEXT | LVIF_STATE;
	//int m_line=pWnd->m_linenumber;
	if(pWnd->m_linepronumber==24)
	{
		theCtrl.SetItemState(pWnd->m_linepronumber,state, mask );
	}
	else
	{
		theCtrl.SetItemState(pWnd->m_linepronumber,state, mask );
        state = LVIS_FOCUSED|LVIS_DROPHILITED|LVIS_ACTIVATING ;
        theCtrl.SetItemState(pWnd->m_linenumber,state, mask );
	}
    pWnd->m_linepronumber=pWnd->m_linenumber; 
	switch(pWnd->m_linenumber)
	{
	case 2:
		{
			if((pWnd->v)>(pWnd->m_nodenumber))
			    pWnd->m_linenumber=7;	
			else
		        pWnd->m_linenumber=3;
            pMainFrame->pMintreegreedyFrame->p_VariablelistView->Setv(pWnd->v);
			 break;
		}
	case 3:
		{
			if((pWnd->v)==1)
				pWnd->m_linenumber=6;
			 else
			   (pWnd->m_linenumber)++;
            // pMainFrame->pPackgreedyFrame->p_VariablelistView->SetS(0);
			 break;
		}
	case 4:
		{
			(pWnd->m_linenumber)++;
            pWnd->vex[(pWnd->v)-1]=1;
            pMainFrame->pMintreegreedyFrame->p_DemolistView->SetVex((pWnd->v)-1,"1");
			break;
		}
	case 5:
		{
			(pWnd->m_linenumber)++;
			if(pWnd->gn[0][(pWnd->v)-1]>0)
                pWnd->lowcost[(pWnd->v)-1]=pWnd->gn[0][(pWnd->v)-1];
			else
                pWnd->lowcost[(pWnd->v)-1]=-1;
			CString m_str;
			if(pWnd->gn[0][(pWnd->v)-1]==0)
				m_str="*";
			else
			    m_str.Format("%.0f",pWnd->gn[0][(pWnd->v)-1]);
			pMainFrame->pMintreegreedyFrame->p_DemolistView->SetLowcost((pWnd->v)-1,m_str);
			break;
		}
	case 6:
		{
			//pMainFrame->pPackgreedyFrame->p_VariablelistView->SetI(pWnd->m_serize);
            pWnd->m_linenumber=2;
            (pWnd->v)++;
			break;
		}
	case 7:
		{
			(pWnd->m_linenumber)++;
            pWnd->vex[0]=1;
			pMainFrame->pMintreegreedyFrame->p_DemolistView->SetVex(0,"1");
			break;
		}
	case 8:
		{
			(pWnd->m_linenumber)++;
            pWnd->lowcost[0]=0;
            pWnd->v=1;
            pWnd->i=1;
			pMainFrame->pMintreegreedyFrame->p_DemolistView->SetLowcost(0,"0");
			break;
		}
	case 9:
		{
			if((pWnd->i)>(pWnd->m_nodenumber)-1)
			    pWnd->m_linenumber=24;	
			else
		        pWnd->m_linenumber=10;
            pMainFrame->pMintreegreedyFrame->p_VariablelistView->SetI(pWnd->i);
			 break;
		}
	case 10:
		{
			(pWnd->m_linenumber)++;
			double k=0;
			int kk=-1;
			for(int i=0;i<pWnd->m_nodenumber;i++)
			{
				if(k==0)
				{
					if((pWnd->lowcost[i])>0)
					{
						k=pWnd->lowcost[i];
						kk=i;
					}
				}
				else
				{
					if((pWnd->lowcost[i])<k&&(pWnd->lowcost[i])>0)
					{
						k=pWnd->lowcost[i];
						kk=i;
					}
				}
			}
            pWnd->k=k;
            pWnd->kk=kk;
            pMainFrame->pMintreegreedyFrame->p_VariablelistView->Setk(kk+1);
			break;
		}
	case 11:
		{
			if((pWnd->k)!=0)
			   pWnd->m_linenumber=13;
			else
			   pWnd->m_linenumber=12;
			break;
		}
	case 12:
		{
			pWnd->KillTimer(nIDEvent);
			pWnd->MessageBox("    此图不连通!","最小耗费生成树问题的贪心算法",MB_OK);
            pMainFrame->pMintreegreedyFrame->p_TopButtonView->m_TopbuttonDlg->OnStop();
			break;
	 
		}
	case 15:
		{
			(pWnd->m_linenumber)++;
            pMainFrame->pMintreegreedyFrame->p_DemolistView->drawArc(pWnd->kk,(pWnd->vex[pWnd->kk])-1);
			break;
		}
	case 16:
		{
			(pWnd->m_linenumber)++;
            pWnd->v=1;
            pWnd->lowcost[pWnd->kk]=0;
			pMainFrame->pMintreegreedyFrame->p_DemolistView->SetLowcost(pWnd->kk,"0");
            pMainFrame->pMintreegreedyFrame->p_DemolistView->DrawNode(pWnd->kk);
			break;
		}
	case 17:
		{
			if((pWnd->v)>(pWnd->m_nodenumber))
			    pWnd->m_linenumber=22;	
			else
		        pWnd->m_linenumber=18;
            pMainFrame->pMintreegreedyFrame->p_VariablelistView->Setv(pWnd->v);
			 break;
		}
	case 18:
		{
			if(pWnd->lowcost[(pWnd->v)-1]==-1)
			{
				if((pWnd->gn[pWnd->kk][(pWnd->v)-1])>0)
                    pWnd->m_linenumber=19;	
				else
                    pWnd->m_linenumber=21;
			}
			else if(((pWnd->gn[pWnd->kk][(pWnd->v)-1])>0)&&((pWnd->gn[pWnd->kk][(pWnd->v)-1])<(pWnd->lowcost[(pWnd->v)-1])))
			    pWnd->m_linenumber=19;	
			else
		        pWnd->m_linenumber=21;
			 break;
		}
	case 19:
		{
			pWnd->m_linenumber=20;
            pWnd->lowcost[(pWnd->v)-1]=pWnd->gn[pWnd->kk][(pWnd->v)-1];
			CString m_str;
			m_str.Format("%.0f",pWnd->lowcost[(pWnd->v)-1]);
			pMainFrame->pMintreegreedyFrame->p_DemolistView->SetLowcost((pWnd->v)-1,m_str);
			break;
		}
   case 20:
		{
			pWnd->m_linenumber=21;
            pWnd->vex[(pWnd->v)-1]=(pWnd->kk)+1;
			CString m_str;
			m_str.Format("%d",pWnd->kk+1);
			pMainFrame->pMintreegreedyFrame->p_DemolistView->SetVex((pWnd->v)-1,m_str);
			break;
		}
   case 21:
	   {
			pWnd->m_linenumber=17;
            (pWnd->v)++;
			break;
	   }
   case 23:
	   {
			pWnd->m_linenumber=9;
            (pWnd->i)++;
			break;
	   }
	default :
		{
			(pWnd->m_linenumber)++;
			break;
		}
	}
	if(pWnd->m_linepronumber==25)
	{
		pWnd->KillTimer(nIDEvent);
        pMainFrame->pMintreegreedyFrame->p_TopButtonView->m_TopbuttonDlg->OnStop();
	}
}

void CArithPrimListView::OnExecute()
{
	m_bstop=0;
	m_odd=0;
	u0=1;
	v=1;
	i=1;
	for(int i=0;i<50;i++)
	{
		vex[i]=0;
		lowcost[i]=0;
	}
	m_linenumber=2;
    m_linepronumber=2;
    CListCtrl& theCtrl = GetListCtrl();
    int state = LVIS_FOCUSED|LVIS_DROPHILITED|LVIS_ACTIVATING ;
    int mask =  LVIF_TEXT | LVIF_STATE;
    theCtrl.SetItemState(m_linenumber, state, mask );
	CMainFrame*	pMainFrame	=(CMainFrame*)::AfxGetMainWnd();
    pMainFrame->pMintreegreedyFrame->p_VariablelistView->SetU0(1);
    pMainFrame->pMintreegreedyFrame->p_DemolistView->DrawNode(0);
	SetTimer(1,1000,OnTimerExcute);
}

void CArithPrimListView::OnOdd()
{
     m_odd=1;
	 SetTimer(1,1000,OnTimerExcute);
	 m_bstop=0;
}


void CArithPrimListView::OnStop()
{
   KillTimer(1);
   m_bstop=1;
}

void CArithPrimListView::OnContinue()
{
	SetTimer(1,1000,OnTimerExcute);
	m_bstop=0;
	m_odd=0;
}