aoelrdlg.cpp

采用Dijkstra算法和Floyd算法实现的简单医院选址系统

// AoelrDlg.cpp : implementation file
//

#include "stdafx.h"
#include "yyxz.h"
#include "AoelrDlg.h"

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

/////////////////////////////////////////////////////////////////////////////
// CAoelrDlg dialog


CAoelrDlg::CAoelrDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CAoelrDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CAoelrDlg)
	m_AoeA = 0;
	m_AoeB = 0;
	m_AoeSj = 0;
	m_judge=0;
	m_totaltime=0;
	m_Cs=1;
	m_AoeGjlj = _T("这里显示你输入的信息");
	m_AoeTB=_T("");
	m_AoeGJLJ=_T("");
	//}}AFX_DATA_INIT	
	for(int i=0;i<100;i++)
		Graphicmap[i]=new VexNode;
}


void CAoelrDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAoelrDlg)
	DDX_Text(pDX, IDC_EDIT_AOEA, m_AoeA);
	DDX_Text(pDX, IDC_EDIT_AOEB, m_AoeB);
	DDX_Text(pDX, IDC_EDIT_AOESJ, m_AoeSj);
	DDX_Text(pDX, IDC_STATIC_AOEGJLJ, m_AoeGjlj);
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CAoelrDlg, CDialog)
	//{{AFX_MSG_MAP(CAoelrDlg)
	ON_BN_CLICKED(IDC_BUTTON_AOEXX, OnButtonAoexx)
	ON_BN_CLICKED(IDC_BUTTON_AOEQJ, OnButtonAoeqj)
	ON_BN_CLICKED(IDC_BUTTON_AOEOK1, OnButtonAoeok1)
	ON_BN_CLICKED(IDC_BUTTON_AOECT, OnButtonAoect)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CAoelrDlg message handlers

void CAoelrDlg::OnButtonAoexx() 
{
	// TODO: Add your control notification handler code here
	CString str;
	if(GetDlgItemText(IDC_BUTTON_AOEXX,str),str=="显示信息>>")
	{
		SetDlgItemText(IDC_BUTTON_AOEXX,"隐藏信息<<");
	}
	else
	{
		SetDlgItemText(IDC_BUTTON_AOEXX,"显示信息>>");
	}

	static CRect Rectlarge;
	static CRect Rectsmall;

	if(Rectlarge.IsRectNull())
	{
		CRect Rectseprator;
		GetWindowRect(&Rectlarge);
		GetDlgItem(IDC_AOESEPRATOR)->GetWindowRect(&Rectseprator);

		Rectsmall.left=Rectlarge.left;
		Rectsmall.top=Rectlarge.top;
		Rectsmall.right=Rectseprator.right;
		Rectsmall.bottom=Rectlarge.bottom;
	}

	if(str=="隐藏信息<<")
	{
		SetWindowPos(NULL,0,0,Rectsmall.Width(),Rectsmall.Height(),SWP_NOMOVE|SWP_NOZORDER);
	}
	else
	{
		SetWindowPos(NULL,0,0,Rectlarge.Width(),Rectlarge.Height(),SWP_NOMOVE|SWP_NOZORDER);
	}
}

void CAoelrDlg::OnButtonAoeqj() 
{
	// TODO: Add your control notification handler code here
	int i;
	CString szTemp;
	i=SearchKeyPath(Graphicmap,m_projectnumber,m_activenumber,m_totaltime);
	if(i==1)
	{
		m_pJDlg=new CJgDlg;
		m_pJDlg->m_jgResult="关键路径为(V表示事件):";
		m_pJDlg->m_jgResult=m_pJDlg->m_jgResult+m_AoeGJLJ;
		m_pJDlg->m_jgResult=m_pJDlg->m_jgResult+"\n";
		szTemp.Format("%d",m_totaltime);
		m_pJDlg->m_jgResult=m_pJDlg->m_jgResult+"关键路径长度为:";
		m_pJDlg->m_jgResult=m_pJDlg->m_jgResult+szTemp;
		m_pJDlg->m_jgResult=m_pJDlg->m_jgResult+"\n";
		m_pJDlg->m_jgResult=m_pJDlg->m_jgResult+m_AoeTB;
		CDialog::OnCancel();
		m_pJDlg->DoModal();
	}
	else if(i==0)
	{
		CDialog::OnCancel();
		GetParent()->ShowWindow(SW_SHOW);
	}
}

void CAoelrDlg::CreateGraphic(VexNode *Graphicmap[], int projectnumber, int activenumber)
{    
	int begin,end,duttem; 
    EdgeNode *p; 
    
	if(m_judge==0)
	{
		for(int i=0;i<projectnumber;i++)//初始化
		{ 
			Graphicmap[i]->projectname=i; 
			Graphicmap[i]->id =0; 
			Graphicmap[i]->link =NULL;			
		}
		m_judge=1;
    } 
	//录入弧的开始结点和尾结点及权值
	   begin=m_AoeA;
	   end=m_AoeB;
	   duttem=m_AoeSj;
       p=new EdgeNode; 
       p->adjvex =end-1; 
       p->dut =duttem; 
       Graphicmap[end-1]->id ++;//尾结点入度加1 
       p->next =Graphicmap[begin-1]->link ; //将此边结点加入到头结点的链表中
       Graphicmap[begin-1]->link =p; 
}

void CAoelrDlg::OnButtonAoeok1() 
{
	// TODO: Add your control notification handler code here
	UpdateData(TRUE);
	CString  szTemp;	
	if(m_Cs<=m_activenumber)
	{
		if(m_AoeA==0||m_AoeB==0)
		{
			MessageBox("输入不能为空,请输入");
		}
		else if(m_AoeSj==0)
		{
			MessageBox("时间不能为空");
		}
		else if(m_AoeA==m_AoeB)
		{
			MessageBox("您输入了相同事件,请输入不同事件");
		}
		else
		{
			szTemp.Format("%d",m_Cs);//数字转换为字符	
			m_AoeGjlj="第"+szTemp;
			m_AoeGjlj=m_AoeGjlj+"组数据:\n";
			m_AoeGjlj=m_AoeGjlj+"事件";
			szTemp.Format("%d",m_AoeA);
			m_AoeGjlj=m_AoeGjlj+szTemp;
			m_AoeGjlj=m_AoeGjlj+"到";
			m_AoeGjlj=m_AoeGjlj+"事件";
			szTemp.Format("%d",m_AoeB);
			m_AoeGjlj=m_AoeGjlj+szTemp;
			m_AoeGjlj=m_AoeGjlj+"所需时间为";	   
			szTemp.Format("%d",m_AoeSj);  
			m_AoeGjlj=m_AoeGjlj+szTemp;
			CreateGraphic(Graphicmap,m_projectnumber,m_activenumber);//建立邻接表
			m_AoeA=0;
			m_AoeB=0;
			m_AoeSj=0;
			++m_Cs;
		}
	}
	else
	{
		MessageBox("信息已输入完毕!");
	}
	UpdateData(FALSE);//更新对话框显示
}

void CAoelrDlg::OnButtonAoect() 
{
	// TODO: Add your control notification handler code here
	GetParent()->ShowWindow(SW_SHOW);
	CDialog::OnCancel();
}

int CAoelrDlg::SearchKeyPath(VexNode *Graphicmap[], int projectnumber, int activenumber, int &totaltime)
{
	int i,j,k,m=0; 
    int front=-1,rear=-1;//初始化队列
    int* topologystack=new int[projectnumber];//用来保存拓扑排列 
    int* vl=new int[projectnumber];//用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间 
    int* ve=new int[projectnumber];//用来表示Vj最早发生时间 
 	int* keypath=new int[projectnumber];//用来表示此事件已加入关键路径
    int* l=new int[activenumber];//用来表示活动Ai最迟完成开始时间 
    int* e=new int[activenumber];//表示活动最早开始时间
 	EdgeNode *p;//边结点 
     totaltime=0; 
     for(i=0;i<projectnumber;i++)//初始化
 	{
 		ve[i]=0; 
 		keypath[i]=0;
 	}
     for(i=0;i<projectnumber;i++) 
     { 
        if(Graphicmap[i]->id==0) 
        { 
            topologystack[++rear]=i; 
            m++;//队中元素个数
        } 
     }
     while(front!=rear)//求事件最早开始时间
     { 
        front++; 
        j=topologystack[front];//队头元素出队 
        m++; 
        p=Graphicmap[j]->link; 
        while(p) 
        { 
            k=p->adjvex; 
            Graphicmap[k]->id--; 
            if(ve[j]+p->dut>ve[k]) 
               ve[k]=ve[j]+p->dut; 
            if(Graphicmap[k]->id==0) 
               topologystack[++rear]=k; 
            p=p->next; 
        } 
     } 
     if(m<projectnumber) //拓扑排序的结点数小于总的结点数，含回路
     { 
        MessageBox("\n本程序所建立的图有回路不可计算出关键路径,请重新输入!\n");  
        return 0; 
     } 
     totaltime=ve[projectnumber-1]; //关键路径长度
	 m_totaltime=totaltime;
     for(i=0;i<projectnumber;i++) //初始化
        vl[i]=totaltime; 
     for(i=projectnumber-2;i>=0;i--) //求事件最迟开始时间
     { 
        j=topologystack[i]; 
        p=Graphicmap[j]->link; 
        while(p)
        { 
	        k=p->adjvex ; 
            if((vl[k]-p->dut)<vl[j]) 
               vl[j]=vl[k]-p->dut ; 
            p=p->next ; 
        } 
     } 
     i=0; 
 	CString szTemp;
 	CString temp="";//暂存事件分支的"关键路径"
 	int iAoe,jAoe=0,kAoe,mAoe;//jAoe标识事件有分支，iAoe标识第k个事件，mAoe标识事件分支的第k个事件，kAoe防止事件重复
     m_AoeTB="| 起点 | 终点 |  最早开始时间  |  最迟开始时间  | 差值 |  关键活动  |\n";
     for(j=0;j<projectnumber;j++) 
    { 
        p=Graphicmap[j]->link; 
        while(p) 
        { 
            k=p->adjvex ; 
            e[++i]=ve[j]; 
            l[i]=vl[k]-p->dut; 
 		   //保存列表
 		   szTemp.Format("%d",Graphicmap[j]->projectname +1);
 		   m_AoeTB=m_AoeTB+szTemp;//起点
 		   m_AoeTB=m_AoeTB+"\t";
 		   szTemp.Format("%d",Graphicmap[k]->projectname +1);
 		   m_AoeTB=m_AoeTB+szTemp;//终点
 		   m_AoeTB=m_AoeTB+"\t\t";
 		   szTemp.Format("%d",e[i]);
 		   m_AoeTB=m_AoeTB+szTemp;//最早开始时间
 		   m_AoeTB=m_AoeTB+"\t\t";
 		   szTemp.Format("%d",l[i]);
 		   m_AoeTB=m_AoeTB+szTemp;//最迟完成时间
 		   m_AoeTB=m_AoeTB+"\t";
 		   szTemp.Format("%d",(l[i]-e[i]));
		   m_AoeTB=m_AoeTB+szTemp;//差值
 		   m_AoeTB=m_AoeTB+"\t";
           if(l[i]==e[i]) 
 		   {
 			   m_AoeTB=m_AoeTB+"是 |";
 			   //保存关键路径
 			   if(jAoe==1&&j==mAoe)//如果有分支，求分支的关键路径
 			   {
			   if(mAoe!=j&&keypath[j]!=1)//消除关键路径中重复的事件
 				   {
 					   szTemp.Format("%d",(j+1));
 					   temp=temp+"V";
 					   temp=temp+szTemp;
 					   temp=temp+"->";
 					   keypath[j]=1;//加入关键路径					   
 				   }
 			   
 				   if((k+1)!=projectnumber)
 				   {	
 					   szTemp.Format("%d",(k+1));
 					   temp=temp+"V";
 					   temp=temp+szTemp;
 					   temp=temp+"->";
 					   keypath[k]=1;
 				   }
 				   if((k+1)==projectnumber)
 				   {			   
 					   szTemp.Format("%d",(k+1));
 					   temp=temp+"V";
 					   temp=temp+szTemp;
				   temp=temp+")";
 					   iAoe=NULL;
 					  	
 				   }
 				   iAoe=k;
 				   jAoe=0;
 			   }
 			   else//没有分支
 			   {
 			   if(kAoe!=j)//控制一个事件的多个分支
 			   {
 					kAoe=j;
 				   if(iAoe!=j&&keypath[j]!=1)//消除关键路径中重复的事件
 				   {
 					   szTemp.Format("%d",(j+1));
 					   m_AoeGJLJ=m_AoeGJLJ+"V";
 					   m_AoeGJLJ=m_AoeGJLJ+szTemp;
 					   m_AoeGJLJ=m_AoeGJLJ+"->";
 					   keypath[j]=1;					   
 				   }
 			   
 				   if((k+1)!=projectnumber)
 				   {	
 					   szTemp.Format("%d",(k+1));
 					   m_AoeGJLJ=m_AoeGJLJ+"V";
 					   m_AoeGJLJ=m_AoeGJLJ+szTemp;
 					   m_AoeGJLJ=m_AoeGJLJ+"->";
 					   keypath[k]=1;
 				   }
 				   if((k+1)==projectnumber)//整个过程结束
 				   {			   
 					   szTemp.Format("%d",(k+1));
 					   m_AoeGJLJ=m_AoeGJLJ+"V";
 					   m_AoeGJLJ=m_AoeGJLJ+szTemp;
 					   m_AoeGJLJ=m_AoeGJLJ+temp;
 					   iAoe=NULL;
 					  	
 				   }
 				   iAoe=k;//保存最后一个事件
 			   }
 			   else//有分支
 			   {
 				   temp=temp+"(或";
 				   if(iAoe!=j)
				   {
				   szTemp.Format("%d",(j+1));
				   temp=temp+"V";
				   temp=temp+szTemp;
				   temp=temp+"->";
				   }			   
 				   if((k+1)!=projectnumber)
 				   {	
 					   szTemp.Format("%d",(k+1));
 					   temp=temp+"V";
 					   temp=temp+szTemp;
 					   temp=temp+"->";
 				   }
				   if((k+1)==projectnumber)
 				   {			   
 					   szTemp.Format("%d",(k+1));
 					   temp=temp+"V";
 					   temp=temp+szTemp;
 					   iAoe=NULL;
 				   }
 				   mAoe=k; 
 				   jAoe=1;
 			   }
 			   }
 		   }
 		   else
		   {
			   m_AoeTB=m_AoeTB+"否 |";
 		   }
           //保存关键路径 
 		   m_AoeTB=m_AoeTB+"\n";
           p=p->next ;
        } 
     } 
     return 1;
}