📄 lrxxdlg.cpp
字号:
// LrxxDlg.cpp : implementation file
//
#include "stdafx.h"
#include "yyxz.h"
#include "LrxxDlg.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CLrxxDlg dialog
CLrxxDlg::CLrxxDlg(CWnd* pParent /*=NULL*/)
: CDialog(CLrxxDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CLrxxDlg)
m_lrxxCza = _T("");
m_lrxxCzb = _T("");
m_lJjz = _T("");
m_lrxxLczj = 0;
m_Cs=1;
m_k=0;
m_j=0;
m_i=0;
m_lrxxXx = _T("这里显示你输入的信息");
m_xXXx = _T("");
//}}AFX_DATA_INIT
for(int i=0;i<30;i++)
GRA.vexs[i]=new CString;
}
void CLrxxDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CLrxxDlg)
DDX_Text(pDX, IDC_EDIT_CZA, m_lrxxCza);
DDX_Text(pDX, IDC_EDIT_CZB, m_lrxxCzb);
DDX_Text(pDX, IDC_EDIT_LCZJ, m_lrxxLczj);
DDX_Text(pDX, IDC_STATIC_XX, m_lrxxXx);
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CLrxxDlg, CDialog)
//{{AFX_MSG_MAP(CLrxxDlg)
ON_BN_CLICKED(IDC_BUTTON_LRXXQD, OnButtonLrxxqd)
ON_BN_CLICKED(IDC_BUTTON_KSXZ, OnButtonKsxz)
ON_BN_CLICKED(IDC_BUTTON_LRXXOK, OnButtonLrxxok)
ON_BN_CLICKED(IDC_BUTTON_CT, OnButtonCt)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CLrxxDlg message handlers
void CLrxxDlg::OnButtonLrxxqd()
{
// TODO: Add your control notification handler code here
CString str;
if(GetDlgItemText(IDC_BUTTON_LRXXQD,str),str=="显示信息>>")
{
SetDlgItemText(IDC_BUTTON_LRXXQD,"隐藏信息<<");
}
else
{
SetDlgItemText(IDC_BUTTON_LRXXQD,"显示信息>>");
}
static CRect largeRect;
static CRect smallRect;
if(largeRect.IsRectNull())
{
CRect sepratorRect;
GetWindowRect(&largeRect);
GetDlgItem(IDC_SEPRATOR)->GetWindowRect(&sepratorRect);
smallRect.left=largeRect.left;
smallRect.top=largeRect.top;
smallRect.right=sepratorRect.right;
smallRect.bottom=largeRect.bottom;
}
if(str=="隐藏信息<<")
{
SetWindowPos(NULL,0,0,smallRect.Width(),smallRect.Height(),SWP_NOMOVE|SWP_NOZORDER);
}
else
{
SetWindowPos(NULL,0,0,largeRect.Width(),largeRect.Height(),SWP_NOMOVE|SWP_NOZORDER);
}
}
void CLrxxDlg::OnButtonKsxz()
{
// TODO: Add your control notification handler code here
m_pJgDlg=new CJgDlg;
if((m_Cs-1)<GRA.arcnum)//判断道路数输入是否足够
{
MessageBox("输入的信息不完全，道路数不够");
}
else
{
if(m_jSFsxzCzdl==0)
{
FloydGetResult(GRA);//求解结果
}
else if(m_jSFsxzCzdl==1)
{
DjikstraGetResult(GRA);
}
//显示结果
m_pJgDlg->m_jgResult="医院最好建在村庄"+*m_result;
m_pJgDlg->m_jgResult=m_pJgDlg->m_jgResult+"\n\n";
m_pJgDlg->m_jgResult=m_pJgDlg->m_jgResult+"邻接矩阵为:\n";
m_pJgDlg->m_jgResult=m_pJgDlg->m_jgResult+m_lJjz;
m_pJgDlg->m_jgResult=m_pJgDlg->m_jgResult+"\n";
m_pJgDlg->m_jgResult=m_pJgDlg->m_jgResult+m_xXXx;
CDialog::OnCancel();
m_pJgDlg->DoModal();
}
}
void CLrxxDlg::OnButtonLrxxok()
{
// TODO: Add your control notification handler code here
UpdateData(TRUE);
CString szTemp;
if(m_Cs<=GRA.arcnum)
{
if(m_lrxxCza==""||m_lrxxCzb=="")
{
MessageBox("输入不能为空,请输入");
}
else if(m_lrxxCza==m_lrxxCzb)
{
MessageBox("您输入了相同的村庄,请输入不同的村庄");
}
else
{
szTemp.Format("%d",m_Cs);//数字转换为字符
m_lrxxXx="第"+szTemp;
m_lrxxXx=m_lrxxXx+"组数据:\n";
m_lrxxXx=m_lrxxXx+"村庄";
m_lrxxXx=m_lrxxXx+m_lrxxCza;
m_lrxxXx=m_lrxxXx+"到";
m_lrxxXx=m_lrxxXx+"村庄";
m_lrxxXx=m_lrxxXx+m_lrxxCzb;
m_lrxxXx=m_lrxxXx+"的距离为";
szTemp.Format("%d",m_lrxxLczj);
m_lrxxXx=m_lrxxXx+szTemp;
CreateWXW(GRA);
m_k++;
m_i++;
m_lrxxCza="";
m_lrxxCzb="";
m_lrxxLczj=0;
++m_Cs;
}
}
else
{
MessageBox("信息已输入完毕!");
}
UpdateData(FALSE);//更新对话框显示
}
void CLrxxDlg::OnButtonCt()
{
// TODO: Add your control notification handler code here
CString szTemp;
if(m_Cs!=1)
szTemp.Format("%d",m_Cs-1);
else if(m_Cs==1)
{
szTemp.Format("%d",m_Cs);
m_Cs--;
}
m_lrxxXx="请重新输入第"+szTemp;
m_lrxxXx=m_lrxxXx+"组数据";
m_lrxxCza="";
m_lrxxCzb="";
m_lrxxLczj=0;
if(m_Cs>1)
m_Cs--;
if(m_i>=2)
{
m_k-=2;
m_i-=2;
}
UpdateData(FALSE);
}
int CLrxxDlg::LocateVex(VAGraph G, CString *v)
{ //返回顶点v在图G中的位置,不存在则重新输入此顶点
int vfind=-1;//顶点在图中找到与否的标志
for(int i=0;i<G.vexnum;i++)
{
if(*G.vexs[i]==*v)
{
vfind=i;//顶点找到，s赋i，退出循环
break;
}
}
return vfind;//返回顶点位置
}
//采用数组表示法，构造无向网
void CLrxxDlg::CreateWXW(VAGraph &GRA)
{ //采用数组表示法，构造无向网GRA
int i,j,w;//定义循环变量
lab[m_k]=m_lrxxCza;
lab[++m_k]=m_lrxxCzb;
if(m_j==0)//判断数组中是否已有元素
{
GRA.vexs[m_i]=&lab[--m_k]; //村庄a
//初始化邻接矩阵
for(j=0;j<GRA.vexnum;++j)
{
if(m_i!=j)
GRA.arcs[m_i][j]=LARGEST;
else
GRA.arcs[m_i][j]=0;//一个点到它自身的距离是0
}
GRA.vexs[++m_i]=&lab[++m_k];//村庄b
for(j=0;j<GRA.vexnum;++j)
{
if(m_i!=j)
GRA.arcs[m_i][j]=LARGEST;//初始两村之距最大
else
GRA.arcs[m_i][j]=0;//一个点到它自身的距离是0
}
m_j=1;
}
else
{ --m_k;
if(LocateVex(GRA,&lab[m_k])==-1)
{
GRA.vexs[m_i]=&lab[m_k];
for(j=0;j<GRA.vexnum;++j)
{
if(m_i!=j)
GRA.arcs[m_i][j]=LARGEST;
else
GRA.arcs[m_i][j]=0;//一个点到它自身的距离是0
}
}
else
m_i--;
++m_k;
if(LocateVex(GRA,&lab[m_k])==-1)
{
GRA.vexs[++m_i]=&lab[m_k];
for(j=0;j<GRA.vexnum;++j)
{
if(m_i!=j)
GRA.arcs[m_i][j]=LARGEST;
else
GRA.arcs[m_i][j]=0;//一个点到它自身的距离是0
}
}
else
m_i--;
}
//构造邻接矩阵
CString *v1;
CString *v2;//矩阵行和列
v1=&lab[--m_k];
v2=&lab[++m_k];
w=m_lrxxLczj;
//输入顶点v1、v2的名称,边v1v2的权值w
i=LocateVex(GRA,v1);
j=LocateVex(GRA,v2);
GRA.arcs[i][j]=w;//边<v1,v2>的权值
GRA.arcs[j][i]=GRA.arcs[i][j];//此矩阵是对称矩阵
}
//求最短路径长度
void CLrxxDlg::FloydGetResult(VAGraph GRA)//使用Floyd算法
{ //用Floyed算法求有向网G中个对顶点的最短路径长度D[v][w]
int D[MAX_VEXNUM][MAX_VEXNUM];//最短路径的带权长度矩阵
static int P[MAX_VEXNUM];//各顶点到最远点的距离P[]
int v,u,w;
for(v=0;v<GRA.vexnum;++v)//各对节点之间初始已知距离
{
for(w=0;w<GRA.vexnum;++w)
{
D[v][w]=GRA.arcs[v][w];//给矩阵赋值
}
}
for(u=0;u<GRA.vexnum;++u)//求各对顶点的最短路径，如果直接的路径不是最短就找合路径
{
for(v=0;v<GRA.vexnum;++v)
{
for(w=0;w<GRA.vexnum;++w)
{
if(D[v][u]+D[u][w]<D[v][w])//从v经u到w的一条路径更短
{
D[v][w]=D[v][u]+D[u][w];//路径之和，舍弃直接的路径
}
}
}
}
//输出结果矩阵
CString szTemp;
for(u=0;u<GRA.vexnum;++u)
{
for(v=0;v<GRA.vexnum;++v)
{ //输出最短路径长度矩阵D[v][w]，并求P[u]
szTemp.Format("%d",D[u][v]);
m_lJjz=m_lJjz+szTemp;
m_lJjz=m_lJjz+"\t";
if(P[u]<D[u][v]) //求出每个顶点到其它顶点的距离最大值存于P[u]中
{
P[u]=D[u][v];
}
}
m_lJjz=m_lJjz+"\n";
}
//求P[u]的最小值,并输出其对应的顶点信息
int i,temp=LARGEST;
for(u=0;u<GRA.vexnum;++u)//求P[u]的最小值，并记录它的位置
{
if(temp>P[u])
{
temp=P[u];
i=u;//所选村庄顶点为P[u]对应的顶点
}
}
m_result=GRA.vexs[i];//医院最好的选址
for(u=0;u<GRA.vexnum;++u)//输出所选顶点到其它顶点的最短距离
{
if(u!=i)
{
szTemp.Format("%d",D[i][u]);
m_xXXx=m_xXXx+"村庄";
m_xXXx=m_xXXx+*m_result;
m_xXXx=m_xXXx+"到";
m_xXXx=m_xXXx+*GRA.vexs[u];
m_xXXx=m_xXXx+"的距离为:";
m_xXXx=m_xXXx+szTemp;
m_xXXx=m_xXXx+"\n";
}
}
}
void CLrxxDlg::DjikstraGetResult(VAGraph GRA)//使用Djikstra算法
{
int DD[MAX_VEXNUM][MAX_VEXNUM];//最短路径的带权长度矩阵
int final[MAX_VEXNUM];//是否加入S集中
static int P[MAX_VEXNUM];//到最远点的距离
int D[MAX_VEXNUM];//源点到其它顶点的距离
int i,j,v,u,w,min;
for(i=0;i<GRA.vexnum;i++)
{
for(v=0;v<GRA.vexnum;v++)
{
final[v]=0;
D[v]=GRA.arcs[i][v];
}//for
D[i]=0;final[i]=1;
//开始主循环，每次求得v0到某个顶点v的最短路径，并将v加入到s集
for(j=0;j<GRA.vexnum;j++)
{
min=LARGEST;
for(w=0;w<GRA.vexnum;w++)
{
if(!final[w])
if(D[w]<min)
{
v=w;//保存离v0最近的顶点的信息
min=D[w];//w离v0最近
}
}
final[v]=1;//离v0最近的v加入到s集
for(w=0;w<GRA.vexnum;w++)//更新当前最短路径及距离
if(!final[w]&&(min+GRA.arcs[v][w]<D[w]))//修改D[w]
{
D[w]=min+GRA.arcs[v][w];
}//if
}//for
for(j=0;j<GRA.vexnum;j++)
{
DD[i][j]=D[j];
}
}//for
//求出每个顶点到其它顶点的距离最大值存于P[u]中
CString szTemp;
for(u=0;u<GRA.vexnum;++u)
{
for(v=0;v<GRA.vexnum;++v)
{ //输出最短路径长度矩阵D[v][w]，并求P[u]
szTemp.Format("%d",DD[u][v]);
m_lJjz=m_lJjz+szTemp;
m_lJjz=m_lJjz+"\t";
if(P[u]<DD[u][v])
{
P[u]=DD[u][v];
}
}
m_lJjz=m_lJjz+"\n";
}
//求P[u]的最小值,并输出其对应的顶点信息
int temp=LARGEST;
for(u=0;u<GRA.vexnum;++u)//求P[u]的最小值，并记录它的位置
{
if(temp>P[u])
{
temp=P[u];
i=u;//所选村庄顶点为P[u]对应的顶点
}
}
m_result=GRA.vexs[i];//医院最佳选址
for(u=0;u<GRA.vexnum;++u)//输出所选顶点到其它顶点的最短距离
{
if(u!=i)
{
szTemp.Format("%d",DD[i][u]);
m_xXXx=m_xXXx+"村庄";
m_xXXx=m_xXXx+*m_result;
m_xXXx=m_xXXx+"到";
m_xXXx=m_xXXx+*GRA.vexs[u];
m_xXXx=m_xXXx+"的距离为:";
m_xXXx=m_xXXx+szTemp;
m_xXXx=m_xXXx+"\n";
}
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -