arithmeticlistview.cpp

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

// ArithmeticListView.cpp : implementation file
//

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

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

/////////////////////////////////////////////////////////////////////////////
// CArithmeticListView

IMPLEMENT_DYNCREATE(CArithmeticListView, CListView)

CArithmeticListView::CArithmeticListView()
{
	m_linenumber=4;
	m_linepronumber=4;
	m_serize=0;
	m_s=0;
	memset(m_x,0,sizeof(m_x));
	m_bstop=0;
	m_odd=0;
}

CArithmeticListView::~CArithmeticListView()
{
}


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

/////////////////////////////////////////////////////////////////////////////
// CArithmeticListView drawing

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

/////////////////////////////////////////////////////////////////////////////
// CArithmeticListView diagnostics

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

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

/////////////////////////////////////////////////////////////////////////////
// CArithmeticListView message handlers

void CArithmeticListView::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)("double knapSack(double* p, double* w, double* x ,double m, int n) {");
	lvi.stateMask =LVIS_STATEIMAGEMASK;
	lvi.state =   INDEXTOSTATEIMAGEMASK(1);
	theCtrl.InsertItem(&lvi);

	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("/* m是背包能放的物体总重量,n是物体件数,x存放解向量*/");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("/* 线性表p和w中,按p[i]/w[i]的降序分别存放物体的价格*/");
	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.state = LVIS_FOCUSED|LVIS_DROPHILITED|LVIS_ACTIVATING ;
	lvi.pszText = (LPTSTR)(LPCTSTR)("  int i = 0;");
	theCtrl.InsertItem(&lvi);	
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.state =   INDEXTOSTATEIMAGEMASK(1);
	lvi.pszText = (LPTSTR)(LPCTSTR)("	  double s = 0;");
	theCtrl.InsertItem(&lvi);	
 	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("	  for (i = 0; i < n; i++)");
	theCtrl.InsertItem(&lvi);	
 	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("        x[i] = 0;	");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("   i = 0;");
	theCtrl.InsertItem(&lvi);

	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("   while (i < n && w[i] < m) {");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("        m -= w[i];");
	theCtrl.InsertItem(&lvi);
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("        s += p[i];");
	theCtrl.InsertItem(&lvi);
 	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("        x[i] = 1;");
	theCtrl.InsertItem(&lvi);
  	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("        i++;");
	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)("    if (i < n && m > 0) {");
	theCtrl.InsertItem(&lvi); 
    m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("       s += p[i]*m/w[i];");
	theCtrl.InsertItem(&lvi);
    m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("       x[i] = m/w[i];");
	theCtrl.InsertItem(&lvi);
    m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("       i++;");
	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)("    return s;");
	theCtrl.InsertItem(&lvi);
    m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)(" }");
	theCtrl.InsertItem(&lvi);

//	OnExecute();
}

//具体处理时间响应，回调函数
void CALLBACK  CArithmeticListView::OnTimerExcute(HWND hWnd,UINT nMsg,UINT nIDEvent,DWORD dwTime)
{
    CMainFrame*	pMainFrame	=(CMainFrame*)::AfxGetMainWnd();
	CArithmeticListView *pWnd;
    pWnd=(CArithmeticListView*)(pMainFrame->pPackgreedyFrame->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==21)
	{
		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 4:
		{
			(pWnd->m_linenumber)++;
             pMainFrame->pPackgreedyFrame->p_VariablelistView->SetI(0);
			 break;
		}
	case 5:
		{
			 (pWnd->m_linenumber)++;
             pMainFrame->pPackgreedyFrame->p_VariablelistView->SetS(0);
			 break;
		}
	case 6:
		{
			pMainFrame->pPackgreedyFrame->p_VariablelistView->SetI(pWnd->m_serize);
			if((pWnd->m_serize)<(pWnd->m_number))
			    pWnd->m_linenumber=7;
			else
			{
				pWnd->m_linenumber=8;
				pWnd->m_serize=0;
			}
			break;
		}
	case 7:
		{
			(pWnd->m_serize)++;
            pMainFrame->pPackgreedyFrame->p_VariablelistView->SetX(0,pWnd->m_serize);
            pWnd->m_linenumber=6;
			break;
		}
	case 8:
		{
			pMainFrame->pPackgreedyFrame->p_VariablelistView->SetI(pWnd->m_serize);
            (pWnd->m_linenumber)++;
		}
	case 9:
		{
			if((pWnd->m_serize)<(pWnd->m_number)&&(pWnd->m_weight[pWnd->m_serize])<(pWnd->m_totalweight))
			{
				pWnd->m_linenumber=10;
			}
            else
			{
				pWnd->m_linenumber=15;
			}
			break;
		}
	case 10:
		{
            (pWnd->m_linenumber)++;
            pWnd->m_totalweight-=pWnd->m_weight[pWnd->m_serize];
            pMainFrame->pPackgreedyFrame->p_VariablelistView->SetM(pWnd->m_totalweight);
		    pWnd->KillTimer(nIDEvent);
            pMainFrame->pPackgreedyFrame->p_DemolistView->OnExecute();
			break;
		}
	case 11:
		{
            (pWnd->m_linenumber)++;
             pWnd->m_s+=pWnd->m_price[pWnd->m_serize];
			 pMainFrame->pPackgreedyFrame->p_VariablelistView->SetS(pWnd->m_s);
			 break;
		}
	case 12:
		{
             (pWnd->m_linenumber)++;
             pWnd->m_x[pWnd->m_serize]=1;
             pMainFrame->pPackgreedyFrame->p_VariablelistView->SetX(1,pWnd->m_serize+1);
			 break;
		}
	case 13:
		{
             (pWnd->m_linenumber)++;
             pWnd->m_serize+=1;
			 pMainFrame->pPackgreedyFrame->p_VariablelistView->SetI(pWnd->m_serize);
			 break;
		}
	case 14:
		{
             pWnd->m_linenumber=9;   
			 break;
		}
	case 15:
		{
			 if((pWnd->m_serize)<(pWnd->m_number)&&(pWnd->m_totalweight)>0)
                  (pWnd->m_linenumber)++;
			 else
                  pWnd->m_linenumber=20;
			 break;
		}
	case 16:
		{
            (pWnd->m_linenumber)++;
             pWnd->m_s=pWnd->m_s+(pWnd->m_price[pWnd->m_serize])*(pWnd->m_totalweight)/(pWnd->m_weight[pWnd->m_serize]);
			 pMainFrame->pPackgreedyFrame->p_VariablelistView->SetS(pWnd->m_s);
		     pWnd->KillTimer(nIDEvent);
             pMainFrame->pPackgreedyFrame->p_DemolistView->OnExecute();			
			 break;
		}
	case 17:
		{
             (pWnd->m_linenumber)++;
             pWnd->m_x[pWnd->m_serize]=(pWnd->m_totalweight)/(pWnd->m_weight[pWnd->m_serize]);;
			 pMainFrame->pPackgreedyFrame->p_VariablelistView->SetX(pWnd->m_x[pWnd->m_serize],pWnd->m_serize+1);
			 break;
		}
	case 18:
		{
             (pWnd->m_linenumber)++;
             pWnd->m_serize+=1;
			 pMainFrame->pPackgreedyFrame->p_VariablelistView->SetI(pWnd->m_serize);
			 break;
		}
	case 20:
		{
			(pWnd->m_linenumber)++;
            pMainFrame->pPackgreedyFrame->p_VariablelistView->SetS(pWnd->m_s);
			break;
		}

	default :
		{
			(pWnd->m_linenumber)++;
			break;
		}
	}
	if(pWnd->m_linepronumber==22)
	{
		pWnd->KillTimer(nIDEvent);
        pMainFrame->pPackgreedyFrame->p_TopButtonView->m_TopbuttonDlg->OnStop();
	}
}

    
	
void CArithmeticListView::OnExecute()
{
 /*   m_linenumber=4;
	m_linepronumber=4;
	CListCtrl& theCtrl = GetListCtrl();
	int state = LVIS_FOCUSED|LVIS_DROPHILITED|LVIS_ACTIVATING ;
	int mask =  LVIF_TEXT | LVIF_STATE;
	theCtrl.SetItemState(m_linenumber, state, mask  );
    m_linenumber++;
	m_serize=0;
	m_s=0;*/
	SetTimer(1,1000,OnTimerExcute);
	m_bstop=0;
	m_odd=0;
    //KillTimer(1);

/*	LV_ITEM  lvi;
	char buffer[256];
	lvi.iItem = 10;
	lvi.iSubItem = 0;
	lvi.pszText=buffer;
	lvi.mask =  LVIF_TEXT;
	lvi.cchTextMax=256;
    int ret= theCtrl.GetItem(&lvi);*/

}


void CArithmeticListView::AddDemoData(int n, double m, char *p, char *w)
{
	 memset(m_price,0,sizeof(m_price));
	 memset(m_weight,0,sizeof(m_weight));
     int i,flag = 1;
	 double temp;
	 char *pdest;
	 int ch=',';
	 int k=0;
	 for(i=0;i<n-1;i++)
	 {
		 pdest = strchr(p, ch);
		 if( pdest != NULL )
		 {
			 *pdest='\0';
			 m_price[k]=atof(p);
			 k++;
			 strcpy(p,pdest+1);
		 }
	 }
	 m_price[k]=atof(p);
	 if((k+1)!=n)
	 {
		MessageBox("    有物体没有价格!","0/1背包问题的贪心算法",MB_OK);
		return;
	 }
	 k=0;
	 for(i=0;i<n-1;i++)
	 {
		 pdest = strchr(w, ch);
		 if( pdest != NULL )
		 {
			 *pdest='\0';
			 m_weight[k]=atof(w);
			 k++;
			 strcpy(w,pdest+1);
		 }
	 }
	 m_weight[k]=atof(w);
	 if((k+1)!=n)
	 {
		MessageBox("    有物体没有重量!","0/1背包问题的贪心算法",MB_OK);
		return;
	 }
    //排序,初始化
	 while (flag != 0) {
        flag = 0;
        for (i = 0; i < n-1; i++) {
            if (m_price[i]/m_weight[i] < m_price[i+1]/m_weight[i+1]) 	{
                temp = m_price[i];
                m_price[i] = m_price[i+1];
                m_price[i+1] = temp;
                temp = m_weight[i];
                m_weight[i] = m_weight[i+1];
                m_weight[i+1] = temp;
                flag = 1;
            }
        }
    }

   m_number=n;
   m_totalweight=m;
   CMainFrame*	pMainFrame	=(CMainFrame*)::AfxGetMainWnd();
   pMainFrame->pPackgreedyFrame->p_DemolistView->AddDemoData(m_number,m_totalweight,m_price,m_weight);
   pMainFrame->pPackgreedyFrame->p_VariablelistView->SetVarianlemnpw(m_number,m_totalweight,m_price,m_weight);
   m_linenumber=4;
   m_linepronumber=4;
   CListCtrl& theCtrl = GetListCtrl();
   int state = LVIS_FOCUSED|LVIS_DROPHILITED|LVIS_ACTIVATING ;
   int mask =  LVIF_TEXT | LVIF_STATE;
   theCtrl.SetItemState(m_linenumber, state, mask );
   m_linenumber++;
   m_serize=0;
   m_s=0;
   m_bstop=0;
   m_odd=0;
}

void CArithmeticListView::SetArithmeticTimer()
{
   if(!m_bstop)
      SetTimer(1,1000,OnTimerExcute);
  // else
  //   KillTimer(1);
   m_bstop=0;
}

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

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