dsview.cpp

该程序是作者编写的程序

// dsView.cpp : implementation of the CDsView class
//

#include "stdafx.h"
#include "ds.h"
#include "city.h"
#include "DLAG1.h"
#include "dsDoc.h"
#include "dsView.h"

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

/////////////////////////////////////////////////////////////////////////////
// CDsView

IMPLEMENT_DYNCREATE(CDsView, CView)

BEGIN_MESSAGE_MAP(CDsView, CView)
	//{{AFX_MSG_MAP(CDsView)
	ON_COMMAND(IDM_READ_DATA, OnReadData)
	ON_COMMAND(IDM_SHOW_LINK, OnShowLink)
	ON_COMMAND(IDM_SHOW_COST, OnShowCost)
	ON_COMMAND(IDM_SORT_POPULATION, OnSortPopulation)
	ON_COMMAND(IDM_SORT_LENGTH, OnSortLength)
	ON_COMMAND(IDM_MINCOST_TREE, OnMincostTree)
	ON_COMMAND(IDM_KRUSKA, OnKruska)
	ON_COMMAND(IDM_ALLROUTE, OnAllroute)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDsView construction/destruction

CDsView::CDsView()
{
	// TODO: add construction code here
	num = 0;
	indication = 0;
}

CDsView::~CDsView()
{
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CDsView drawing

void CDsView::OnDraw(CDC* pDC)
{
	CDsDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
	switch( indication )
	{
	case IDM_READ_DATA:
	case IDM_SORT_POPULATION:
		showbaseinfo(pDC);
		break;
	case IDM_SHOW_LINK:
		showlinkinfo(pDC);
		break;
	case IDM_SHOW_COST:
		showcostinfo(pDC);
		break;
	case IDM_SORT_LENGTH:
		showcitycity(pDC);
		break;
    case IDM_MINCOST_TREE:
		showmincosttree(pDC);
		break;
	case IDM_KRUSKA:
		showmincosttree_kruska(pDC);
		break;
    case IDM_ALLROUTE:
		showallroute(pDC);
        break;
	}
}

/////////////////////////////////////////////////////////////////////////////
// CDsView printing

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CDsView diagnostics

#ifdef _DEBUG
void CDsView::AssertValid() const
{
	CView::AssertValid();
}

void CDsView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

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

/////////////////////////////////////////////////////////////////////////////
// CDsView message handlers

void CDsView::OnReadData() 
{
	// TODO: Add your command handler code here
	FILE *fp;
    if( ( fp = fopen("base.txt", "rt" ) ) != NULL )
	{  // 读出城市的基本信息
		int i = 0;
		while( !feof( fp ) )
		{
			fscanf( fp, "%d", &city[i].id );
			fscanf( fp, "%s", city[i].name );
			fscanf( fp, "%f", &city[i].population );
			fscanf( fp, "%f", &city[i].area );
			i++;
			if( i == N ) break;
		}
		num = i;
		fclose( fp );
	}
    if( ( fp = fopen("link.txt", "rt" ) ) != NULL )
	{  // 读出城市间的距离和代价
		int i, j;
		while( !feof( fp ) )
		{
			fscanf( fp, "%d%d", &i, &j );
			ASSERT( i < num && i >= 0 );
			ASSERT( j < num && j >= 0 );
			fscanf( fp, "%f", &link[i][j] );
			link[j][i] = link[i][j];
			fscanf( fp, "%f", &cost[i][j] );
			cost[j][i] = cost[i][j];
		}
		fclose( fp );
	}
	indication = IDM_READ_DATA;
	Invalidate();
}

void CDsView::OnShowLink() 
{
	// TODO: Add your command handler code here
	indication = IDM_SHOW_LINK;
	Invalidate();
}

void CDsView::OnShowCost() 
{
	// TODO: Add your command handler code here
	indication = IDM_SHOW_COST;
	Invalidate();
}

void CDsView::showlinkinfo(CDC *pDC)
{
	for( int i = 0; i < num; i++ )
	{
		CString str;
		str.Format( "%5.1f", link[i][0] );
		for( int j = 1; j < num; j++ )
		{
			CString buf;
			buf.Format( " %5.1f", link[i][j] );
			str += buf;
		}
		pDC->TextOut( 50, i * 20, str );
	}
}

void CDsView::showcostinfo( CDC *pDC )
{
	for( int i = 0; i < num; i++ )
	{
		CString str;
		str.Format( "%5.1f", cost[i][0] );
		for( int j = 1; j < num; j++ )
		{
			CString buf;
			buf.Format( " %5.1f", cost[i][j] );
			str += buf;
		}
		pDC->TextOut( 50, i * 20, str );
	}
}

void CDsView::showbaseinfo(CDC *pDC)
{
	for( int i = 0; i < num; i++ )
	{
		CString str;
		str.Format( "%3d %10s %7.2f %7.2f", city[i].id,
			city[i].name, city[i].population, city[i].area );
		pDC->TextOut( 50, i * 20, str );
	}
}

void CDsView::SortByPopulation()
{
	for( int i = 0; i < num; i++ )
	{  // select sort
		int loc = i;
		for( int j = i+1; j < num; j++ )
			if( city[j].population < city[loc].population ) loc = j;
		if( loc != i )
		{  // exchange data
			city_info t;
			t = city[i]; city[i] = city[loc]; city[loc] = t;
		}
	}
}

void CDsView::OnSortPopulation() 
{
	// TODO: Add your command handler code here
	SortByPopulation();
	indication = IDM_SORT_POPULATION;
	Invalidate();
}

int CDsView::dumpcityinfo()
{
	int k = 0;
	for( int i = 1; i < num; i++ )
	{
		for( int j = 0; j < i; j++ )
			if( link[i][j] ) 
			{
				citylen[k].from = i;
				citylen[k].end  = j;
				citylen[k].length = link[i][j];
				k++;
			}
	}
	return k;
}

void CDsView::OnSortLength() 
{
	// TODO: Add your command handler code here
	nn = dumpcityinfo();
	Sortbylength();
	indication = IDM_SORT_LENGTH;
	Invalidate();
}

void CDsView::showcitycity(CDC *pDC)
{
	for( int i = 0; i < nn; i++ )
	{
		CString str;
		str.Format( "%10s %10s %7.2f", city[citylen[i].from].name, 
			city[citylen[i].end].name, citylen[i].length );
		pDC->TextOut( 50, i * 20, str );
	}
}

void CDsView::Sortbylength()
{
	for( int i = 0; i < nn; i++ )
	{  // select sort
		int loc = i;
		for( int j = i+1; j < nn; j++ )
			if( citylen[j].length < citylen[loc].length ) loc = j;
		if( loc != i )
		{  // exchange data
			city_city t;
			t = citylen[i]; citylen[i] = citylen[loc]; citylen[loc] = t;
		}
	}
}

void CDsView::OnMincostTree() 
{
	// TODO: Add your command handler code here
    indication = IDM_MINCOST_TREE;
	Invalidate();

	
}

void CDsView::showmincosttree(CDC *pDC)
{   // prim 算法 
    // 从0顶点开始
	int k;  float min;
	float lowcost[N];
	int closest[N];
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			if(cost[i][j]==0&&i!=j) cost[i][j]=32767;
//
  /* for(  i = 0; i < num; i++ )
	{
		CString str;
		str.Format( "%5.1f", cost[i][0] );
		for( int j = 1; j < num; j++ )
		{
			CString buf;
			buf.Format( " %5.1f", cost[i][j] );
			str += buf;
		}
		pDC->TextOut( 50, i * 20, str );
	} */
//
 
   for( i=1 ;i<=N-1;i++)
	{ lowcost[i]=cost[0][i];
	  closest[i]=0;
	//}
   //
      //CString str;
	 // str.Format( "%.1f   %d", lowcost[i],closest[i]);
	// pDC->TextOut( 50, i * 20, str );  
   }
   //
 	for(i=1;i<=N-1;i++)
	{ min=lowcost[i];
	  k=i;
	  for(int j=1; j<=N-1;j++)
		   if( lowcost[j]<min)
		   { min=lowcost[j];
		     k=j;
           }
	  CString str;
	  str.Format( "%d   %d", k,closest[k]);
	  pDC->TextOut( 50, i * 20, str );  
      lowcost[k]=32767;
	  for(j=1;j<=N-1;j++)
		  if(cost[k][j]<lowcost[j]&&lowcost[j]<32767)
		  { lowcost[j]=cost[k][j];
		    closest[j]=k;
		  }
	}

  }











void CDsView::OnKruska() 
{
	// TODO: Add your command handler code here
	 indication = IDM_KRUSKA;
	Invalidate();
}

void CDsView::showmincosttree_kruska(CDC *pDC)
{ // kruska 算法  
   // 按费用由小到大将权值排序  
    int mm;
	mm=dumpcitycost();
    for( int i = 0; i <mm; i++ )
	{  // select sort
		int loc = i;
		for( int j = i+1; j < mm; j++ )
			if( citycost[j].cost  < citycost[loc].cost ) loc = j;
		if( loc != i )
		{  // exchange data
			city_city_cost  t;
			t = citycost[i]; citycost[i] = citycost[loc]; citycost[loc] = t;
		}
	}
   //kruska
    int j;  city_city_cost  c[N];
	int s[N+1][N+1];   // s为一个集合，一行元素表示一个集合，s[i][t]=1表示顶点t属于该集合
	for(i=0;i<=N-1;i++)
		for(j=0;j<=N-1;j++)
			if(i==j) s[i][j]=1;
			else s[i][j]=0;
    int k=1;    // 统计生成树的边数
	int d=0; //  表示待扫描边的下标位置
	int m1,m2;   // 记录一条边的两个顶点所在集合的序号
	while(k<N)
	{ for(i=0;i<=N-1;i++)
	   for(j=0;j<=N-1;j++)
	   {if((citycost[d].from==j)&&(s[i][j]==1))
	       m1=i;
	    if((citycost[d].end==j)&&(s[i][j]==1))
           m2=i;
	   }
	   if(m1!=m2)
	   {c[k]=citycost[d];
	    k++;
		for(j=0;j<=N-1;j++)
		{ s[m1][j]=s[m1][j]||s[m2][j]; // 求出一条边后，合并两个集合
		  s[m2][j]=0;    // 另一个集合置为空
        }
	   }
	   d++;
	}
   // 输出	
  for(i=1; i<N;i++)
  {    CString str;
	  str.Format( "%d   %d   %.1f", c[i].from ,c[i].end ,c[i].cost );
	  pDC->TextOut( 50, i * 20, str );  
  }

}




int CDsView::dumpcitycost()
{ int k = 0;
	for( int i = 0; i < num; i++ )
	{
		for( int j = 0; j < i; j++ )
			if( cost[i][j] ) 
			{
				citycost[k].from = i;
				citycost[k].end  = j;
				citycost[k].cost = cost[i][j];
				k++;
			}
	}
	return k;
    
}

void CDsView::OnAllroute() 
{
	// TODO: Add your command handler code here
    
	indication = IDM_ALLROUTE;
	Invalidate();

}

void CDsView::showallroute(CDC *pDC)
{   //  寻找两个城市的所有路径
    DLAG1  dlg;
	dlg.DoModal();
	CString str1,str2;
    str1=dlg.m_vx;
	str2=dlg.m_vy;
    /*str1.Format( "%d   ", dlg.m_vx );
	  pDC->TextOut( 50, 20, str1 );  
    str2.Format( "%d   ", dlg.m_vy );
	  pDC->TextOut( 50, 50, str2 );
     */
	int m=0;
    for(int i=0;i<N;i++)
		s0[i]=d0[i]=-1;
	s0[0]=dlg.m_vx;
	dest=dlg.m_vy;
	find_all_path(s0,link,dest,pDC,m);
    

}

void CDsView::find_all_path(int s0[],float link[][N],int dest,CDC *pDC,int m)
{ int k=0;
  while(s0[k]!=-1)
   k++;
  int last=s0[k-1];
  //m++;
  if(last==dest)
  {   m++;
	  for(int i=0;i<k;i++)
  {   CString str;
	  str.Format( "%d", s0[i]);
	  pDC->TextOut( 50+m*20, i * 20, str );  
  }
  return;
  }
  int length=0;
  for(int i=0;i<N;i++)
	  if(link[last][i])
	  {for(int j=0;j<k;j++)
	    if(s0[j]==i)break;
		if(j>=k) {d0[length]=i; length++;}
      }
  
  for(int I=0;I<=length-1;I++)  //
  {s0[k]=d0[I]; m++;
    find_all_path(s0,link,dest,pDC,m);   //  
  }
}