graph.cpp
来自「是数据结构实习很好的参考范本」· C++ 代码 · 共 543 行
CPP
543 行
// Graph.cpp: implementation of the CGraph class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "shixi07621.h"
#include "Graph.h"
#include"MudiDlg.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
#include"Node.h"
int luj[15][15];/* 边的值*/
int shortest[15][15];/* 两点间的最短距离*/
int path[15][15];/* 经过的景点*/
int jilu[20];
int tt=1;
CPoint loc[16];
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CGraph::CGraph()
{
for(int i=0;i<=15;i++)
for(int j=0;j<=15;j++)
luj[i][j]=10000;
luj[1][3]=luj[3][1]=14; luj[1][6]=luj[6][1]=15;
luj[2][5]=luj[5][2]=17;luj[2][6]=luj[6][2]=18;
luj[3][6]=luj[6][3]=23; luj[3][7]=luj[7][3]=25; luj[3][8]=luj[8][3]=27;
luj[4][5]=luj[5][4]=31; luj[4][11]=luj[11][4]=24; /*luj[4][12]=luj[12][4]=16; */
/*luj[4][13]=luj[13][4]=23;*/
luj[5][6]=luj[6][5]=25; luj[5][11]=luj[11][5]=19; luj[5][12]=luj[12][5]=11;
luj[6][7]=luj[7][6]=24; luj[6][11]=luj[11][6]=9;//
luj[6][12]=luj[12][6]=28;
luj[7][8]=luj[8][7]=18; luj[7][12]=luj[12][7]=33; luj[7][15]=luj[15][7]=13;
luj[8][9]=luj[9][8]=21; luj[8][15]=luj[15][8]=13;
luj[9][10]=luj[10][9]=25; luj[9][15]=luj[15][9]=16;
luj[11][12]=luj[12][11]=17; luj[11][13]=luj[13][11]=19;
luj[12][13]=luj[13][12]=18; luj[13][14]=luj[14][13]=14;
luj[14][15]=luj[15][14]=14;
loc[1].x=450;loc[1].y=30;loc[2].x=151;loc[2].y=90;loc[3].x=700;loc[3].y=72;loc[4].x=57;
loc[4].y=234;
loc[5].x=197;loc[5].y=201;loc[6].x=425;loc[6].y=180;loc[7].x=620;loc[7].y=295;
loc[8].x=730;loc[8].y=198;
loc[9].x=790;loc[9].y=325;loc[10].x=878;loc[10].y=225;loc[11].x=160;loc[11].y=374;
loc[12].x=410;loc[12].y=330;
loc[13].x=189;loc[13].y=501;loc[14].x=460;loc[14].y=560;
loc[15].x=676;loc[15].y=499;
}
CGraph::~CGraph()
{
}
void CGraph::draw(CDC *pDC)
{
CPen pen(PS_SOLID,3,RGB(0,0,255));
CPen *oldPen=(CPen *)pDC->SelectObject(&pen);
pDC->Rectangle(693,160,760,362);
pDC->Rectangle(600,30,877,102);
pDC->Ellipse(414,20,485,62);
pDC->TextOut(431,38,"北门");
pDC->Rectangle(290,140,570,170);
int x1=290;
int y1=140;
int x2=370;
int y2=170;
for(int i=0;i<3;i++)
{
pDC->Rectangle(x1,y1,x2,y2);
x1=x1+100;
x2=x2+100;
}
pDC->Rectangle(390,170,470,200);
pDC->Rectangle(595,160,663,435);
pDC->TextOut(305,150,"计通学院");
pDC->TextOut(408,150,"图书馆");
pDC->TextOut(505,150,"信控学院");
pDC->Rectangle(350,220,515,410);
pDC->TextOut(400,300,"广场");
pDC->Rectangle(600,55,680,80);
pDC->TextOut(620,62,"东教");
int c1=595;
int c2=160;
int c3=663;
int c4=185;
int d1=610;
int d2=165;
for(int j=0;j<6;j++)
{
pDC->Rectangle(c1,c2,c3,c4);
d2=d2+50;
c2=c2+50;
c4=c4+50;
}
pDC->TextOut(610,165,"学六");
pDC->TextOut(610,215,"学五");
pDC->TextOut(610,265,"学四");
pDC->TextOut(610,315,"学三");
pDC->TextOut(610,365,"学二");
pDC->TextOut(610,415,"学一");
pDC->Ellipse(415,545,500,595);
pDC->TextOut(440,570,"南门");
pDC->Ellipse(870,190,920,250);
pDC->TextOut(885,215,"东门");
pDC->Ellipse(8,205,65,255);
pDC->TextOut(17,224,"西门");
pDC->Rectangle(780,235,840,465);
int x11=780;
int y11=235;
int x22=840;
int y22=265;
for(int n=0;n<5;n++)
{
pDC->Rectangle(x11,y11,x22,y22);
y11=y11+50;
y22=y22+50;
}
pDC->Rectangle(581,452,763,558);
pDC->TextOut(790,240,"五餐");
pDC->TextOut(790,290,"学十三");
pDC->TextOut(790,340,"学十二");
pDC->TextOut(790,390,"学十一");
pDC->TextOut(790,440,"学十");
pDC->Rectangle(693,160,760,185);
pDC->TextOut(710,168,"三餐");
pDC->Rectangle(693,223,760,362);
pDC->TextOut(710,280,"综合区");
pDC->Rectangle(581,452,664,496);
pDC->TextOut(600,468,"二餐");
pDC->Rectangle(647,515,722,558);
pDC->TextOut(666,529,"一餐");
pDC->Rectangle(699,452,763,492);
pDC->TextOut(707,467,"学七");
pDC->Rectangle(105,161,285,245);
pDC->Rectangle(105,161,185,195);
pDC->TextOut(117,171,"四教");
pDC->Rectangle(105,211,185,245);
pDC->TextOut(117,221,"三教");
pDC->Rectangle(205,161,285,195);
pDC->TextOut(217,171,"一教");
pDC->Rectangle(205,211,285,245);
pDC->TextOut(217,221,"二教");
pDC->Rectangle(106,311,291,415);
pDC->TextOut(150,346,"主教学楼");
pDC->Rectangle(106,448,341,515);
pDC->TextOut(159,471,"家属住宅区");
pDC->Rectangle(124,43,297,127);
pDC->Rectangle(224,76,297,127);
pDC->TextOut(230,97,"物理学院");
pDC->Rectangle(124,43,208,77);
pDC->TextOut(141,55,"西教");
pDC->Rectangle(710,30,777,57);
pDC->TextOut(727,39,"四餐");
pDC->Rectangle(715,76,877,102);
pDC->Rectangle(715,76,782,102);
pDC->TextOut(727,82,"学八");
pDC->Rectangle(802,76,877,102);
pDC->TextOut(822,84,"学九");
//CBrush a;
pDC->TextOut(840,570,"中国石油大学（华东）");
pDC->TextOut(920,590,"2007.7.22");
pDC->TextOut(920,610,"刘兵绘制");
pDC->Ellipse(440,20,460,40);//(450,30)beimen loc1
pDC->Ellipse(141,80,161,100);//(151,90)xijiao loc2
pDC->Ellipse(690,62,710,82);//(700,72)dongjiao loc3
pDC->Ellipse(47,224,67,244);//(57,234)ximen loc4
pDC->Ellipse(187,191,207,211);//(197,201)4jiao loc5
pDC->Ellipse(415,170,435,190);//(425,180)tushuguang loc6
pDC->Ellipse(868,215,885,235);//(878,225)dongmen loc10
pDC->Ellipse(720,188,740,208);//(730,198)sancan loc8
pDC->Ellipse(400,320,420,340);//(410,330)guangchuang loc12
pDC->Ellipse(610,285,630,305);//(620,295)xue4 loc7
pDC->Ellipse(666,489,686,509);//(676,499)yican loc15
pDC->Ellipse(450,550,470,570);//(460,560)nanmen loc14
pDC->Ellipse(780,315,800,335);//(790,325)xue13 loc9
pDC->Ellipse(150,364,170,384);//(160,374)zhujiaoxuelou loc11
pDC->Ellipse(179,491,199,511);//(189,501)jiashuzhuzaiqu loc13
}
void CGraph::Createluj(CDC*pDC)
{
CBrush m_brush;
m_brush.CreateSolidBrush(RGB(255,0,0));
pDC->SetTextColor(RGB(0,0,255));
CPen pen(PS_SOLID,3,RGB(0,255,255));
CPen *oldPen=(CPen *)pDC->SelectObject(&pen);
for(int m=1;m<=15;m++)
{
for(int n=1;n<=15;n++)
{
if(luj[m][n]!=10000)
{
pDC->MoveTo(loc[m]);
pDC->LineTo(loc[n]);
char s[10];
itoa(luj[m][n],s,10);
pDC->TextOut((loc[m].x+loc[n].x)/2,(loc[m].y+loc[n].y)/2,s);
}
else
continue;
}
}
// CBrush m_brush;
// m_brush.CreateSolidBrush(RGB(255,0,0));
pDC->SetTextColor(RGB(225,0,0));
for(int g=1;g<=15;g++)
{
char f[10];
itoa(g,f,10);
pDC->TextOut(loc[g].x,loc[g].y,f);
}
}
void CGraph::floyed()
{
/*用floyed算法求两个景点的最短路径*/
/* int i,j,k;
for(i=1;i<=15;i++)
for(j=1;j<=15;j++)
{
shortest[i][j]=luj[i][j];
path[i][j]=0;
}
for(k=1;k<=15;k++)
for(i=1;i<=15;i++)
for(j=1;j<=15;j++)
if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))
{/*用path[][]记录从i到j的最短路径上点j的前驱景点的序号*/
/* shortest[i][j]=shortest[i][k]+shortest[k][j];
path[i][j]=k;
path[j][i]=k;
} */
}
void CGraph::xianshi(int i,int j,CDC*pDC)
{
/*int a,b;
a=i; b=j;
int x=350;
int y=520;
if(shortest[i][j]!=10000)
{
if(i<j)
{
char s[10];
itoa(b,s,10);
pDC->TextOut(350,500,"您要查询的最短路径是:");
pDC->TextOut(350,520,s);
x=x+20;
pDC->TextOut(x,y,"<-");
x=x+20;
while(path[i][j]!=0)
{
char d[10];
jilu[tt]=path[i][j];
tt++;
itoa(path[i][j],d,10);
pDC->TextOut(x,y,d);
x=x+20;
pDC->TextOut(x,y,"<-");
x=x+20;
if(i<j)
j=path[i][j];
else
i=path[j][i];
}
char z[10];
itoa(a,z,10);
pDC->TextOut(x,y,z);
y=y+80;
pDC->TextOut(x,y,"最短路径距离是:");
y=y+20;
x=x+20;
pDC->TextOut(x,y,"<-");
x=x+20;
char e[10];
int f=0;
f=shortest[a][b];
itoa(f,e,10);
pDC->TextOut(x,y,e);
x=x+20;
pDC->TextOut(x,y,"米");
jilu[0]=b;
jilu[tt]=a;
for(;;)
{
CPen pen(PS_SOLID,3,RGB(255,0,0));
CPen *oldPen=(CPen *)pDC->SelectObject(&pen);
if(tt==0)
break;
pDC->MoveTo(loc[jilu[tt]]);
pDC->LineTo(loc[jilu[tt-1]]);//
Sleep(1000);
tt--;
}
}
else
{
char s[10];
itoa(a,s,10);
pDC->TextOut(350,500,"您要查询的最短路径是:");
pDC->TextOut(350,520,s);
x=x+20;
pDC->TextOut(x,y,"->");
x=x+20;
while(path[i][j]!=0)
{
char d[10];
jilu[tt]=path[i][j];
tt++;
itoa(path[i][j],d,10);
pDC->TextOut(x,y,d);
x=x+20;
pDC->TextOut(x,y,"->");
x=x+20;
if(i<j)
j=path[i][j];
else
i=path[j][i];
}
char z[10];
itoa(b,z,10);
pDC->TextOut(x,y,z);
y=y+80;
pDC->TextOut(x,y,"最短路径距离是:");
y=y+20;
x=x+20;
pDC->TextOut(x,y,"->");
x=x+20;
char e[10];
int f=0;
f=shortest[a][b];
itoa(f,e,10);
pDC->TextOut(x,y,e);
x=x+20;
pDC->TextOut(x,y,"米");
}
}
else
pDC->TextOut(350,520,"输入错误不存在此路!");
jilu[0]=a;
jilu[tt]=b;
for(int d=0;d<tt;d++)
{
CPen pen(PS_SOLID,3,RGB(255,0,0));
CPen *oldPen=(CPen *)pDC->SelectObject(&pen);
// if(tt==0)
// break;
pDC->MoveTo(loc[jilu[d]]);
pDC->LineTo(loc[jilu[d+1]]);
// tt--;
Sleep(1000);
}*/
}
int CGraph::input(CDC*pDC)
{
CMudiDlg sr;
sr.DoModal();
if(sr.m_n1>15||sr.m_n1<=0||sr.m_n2<=0||sr.m_n2>15)
{
pDC->TextOut(350,500,"输入信息错误(请输入1-15)");
}
else
{
floyed();
drawpath(sr.m_n1,sr.m_n2,pDC);
}
return 1;
}
void CGraph::clear()
{
jilu[20]=0;
tt=1;
}
void CGraph::CZHao(int i,CDC*pDC)
{
if(i>0&&i<=15)
{
CPen pen(PS_SOLID,3,RGB(255,0,0));
CPen *oldPen=(CPen *)pDC->SelectObject(&pen);
pDC->Ellipse(loc[i].x-5,loc[i].y-5,loc[i].x+5,loc[i].y+5);
}
else
pDC->TextOut(350,500,"输入信息错误(请输入1-15)");
}
////////////////////////////////////////////////////////////////////////////////////////
void CGraph::ShortestPath(int n,int v)
{
for(int i=1;i<=n;i++)//初始化
{
s[i]=FALSE;
dist[i]=luj[v][i];
if((i!=v) && (dist[i]<1000))
path[i]=v;
else
path[i]=-1;
}
s[v]=TRUE;dist[v]=0;
for(i=1;i<=n-2;i++)//确定从v开始的n-1条路径
{
int u=choose(n);//选择u,使得对于所有的s[x]=FALSE,dist[u]=最小的dist[x]
s[u]=TRUE;
for(int w=1;w<=n;w++)
if(!s[w])
if(dist[u]+luj[u][w]<dist[w])
{
dist[w]=dist[u]+luj[u][w];
path[w]=u;
}
}//for(i=0;...)
}
int CGraph::choose(const int n)
{
int shortest=1000;
int u;
for(int i=1;i<=n;i++)
{
if((!s[i])&&(dist[i]<shortest))
{
u=i;
shortest=dist[i];
}
}
return u;
}
/**/
void CGraph::drawpath(int m_start, int m_end, CDC *pDC)
{
CPoint point[100];
int js=1;
if(m_start>15||m_start<1||m_end>15||m_end<1)
{
pDC->TextOut(300,300,"输入错误，请输入1-15!");
}
else
{
CPen pen;
CPen newpen3,*oldpen=NULL;
newpen3.CreatePen(PS_SOLID,3,RGB(225,0,0));
pDC->SelectObject(&newpen3);
ShortestPath(15,m_start);
int temp;
temp=path[m_end];
while(temp!=m_start)
{
point[js]=loc[m_end];
js++;
point[js]=loc[temp];
js++;
m_end=path[m_end];
temp=path[m_end];
}
point[js]=loc[m_end];
js++;
point[js]=loc[temp];
}
for(;;)
{
if(js==1)
break;
CPen pen(PS_SOLID,3,RGB(255,0,0));
CPen *oldPen=(CPen *)pDC->SelectObject(&pen);
pDC->MoveTo(point[js]);
pDC->LineTo(point[js-1]);
js--;
Sleep(1000);
}
}
void CGraph::Tianjia(int x, int y,CDC*pDC)
{
pDC->Ellipse(x-20,y-20,x+20,y+20);
}
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?