山西师范大学校园导航
#include
using namespace std;
#define MAXVEX 30 //最大顶点个数
#define MAX 100000 //边的最大值
typedef struct arcweight //设置边的权值信息
{
int weight; //路径权值
}arcweight,arcs[MAXVEX][MAXVEX];
typedef struct verinfo //设置景点信息
{
int position; //顶点位置
char name[60]; //顶点名称
char info[1000]; //顶点信息
}verinfo;
typedef struct graph // 无向图
{
verinfo vexs[MAXVEX];
arcs arcs;
int vernum,arcnum;
}graph;
//全局变量
graph g;
int initgraph(graph &G) //图的初始化
{
int i,j;
G.vernum=20;
G.arcnum=29;
//初始化景点
for(i=0;i
G.vexs[i].position=i; //设置景点编号值
//设置景点名称
strcpy(G.vexs[0].name,"巨人广场");
strcpy( G.vexs[1].name,"一号教学楼");
strcpy(G.vexs[2].name,"二号教学楼");
strcpy( G.vexs[3].name,"三号教学楼");
strcpy(G.vexs[4].name,"四号教学楼");
strcpy(G.vexs[5].name,"五号教学楼");
strcpy(G.vexs[6].name,"六号教学楼");
strcpy(G.vexs[7].name,"田家炳教育书院");
strcpy(G.vexs[8].name,"科学会堂");
strcpy(G.vexs[9].name,"莳英园");
strcpy(G.vexs[10].name,"图书馆");
strcpy(G.vexs[11].name,"操场");
strcpy(G.vexs[12].name,"篮球场");
strcpy(G.vexs[13] .name,"食堂");
strcpy(G.vexs[14].name,"校医院");
strcpy(G.vexs[15].name,"北门");
strcpy(G.vexs[16].name,"南门");
strcpy(G.vexs[17].name,"西门");
strcpy(G.vexs[18].name,"东门");
strcpy(G.vexs[19].name,"西平房");
//设置景点简介
strcpy(G.vexs[0].info, "巨人广场，主要用于健身，活动，娱乐。");
strcpy(G.vexs[1].info, "一号楼，政法学院和历史学院的所在地。");
strcpy(G.vexs[2].info, "二号教学楼，为工程学院所在地。");
strcpy(G.vexs[3].info, "三号教学楼，为生命科学学院所在地。");
strcpy(G.vexs[4].info, "四号教学楼，为物信学院和城环学院所在地。");
strcpy(G.vexs[5].info, "五号教学楼，楼内教室全部为阶梯教室。");
strcpy(G.vexs[6].info, "六号教学楼，为化材学院所在地。");
strcpy(G.vexs[7].info, "七号教学楼，也叫“田家炳教育书院”。");
strcpy(G.vexs[8].info, "八号教学楼，即“科学会堂”，学校标志性建筑。");
strcpy(G.vexs[9].info, "莳英园环境优美，有人工湖，小桥，楼阁。");
strcpy(G.vexs[10].info, "学校最早建筑之一，馆内有大量藏书。");
strcpy(G.vexs[11].info, "一圈四百米的标准操场，有草坪和塑胶跑道，还有观看台。");
strcpy(G.vexs[12].info, "活动场所，有16个篮球架。");
strcpy(G.vexs[13].info, "食堂菜品丰富，可供2000人进餐。");
strcpy(G.vexs[14].info, "校医院属于学校直属单位，方便学生和教职工看病体检。");
strcpy(G.vexs[15].info, "即山西师范大学的北大门，仿效北大大门。");
strcpy(G.vexs[16].info, "师范大学南门，可通往华盛宿舍楼。");
strcpy(G.vexs[17].info, "山西师范大学的西大门，通往宿舍楼。");
strcpy(G.vexs[18].info, "山西师范大学东大门，也是正门仿清华大门。");
strcpy(G.vexs[19].info, "山西师范大学校学生会所在地。");
//初始化边
for(i=0;i
for(j=0;j
G.arcs[i][j].weight=MAX;
G.arcs[i][i].weight=G.arcs[j][j].weight=0;
//设置路径权值
G.arcs[0][4].weight = G.arcs[4][0].weight = 52;
G.arcs[0][6].weight = G.arcs[6][0].weight = 64;
G.arcs[0][8].weight = G.arcs[8][0].weight = 55;
G.arcs[0][10].weight = G.arcs[10][0].weight = 61;
G.arcs[1][2].weight = G.arcs[2][1].weight = 33;
G.arcs[1][3].weight = G.arcs[3][1].weight = 34;
G.arcs[1][4].weight = G.arcs[4][1].weight = 62;
G.arcs[1][13].weight =G.arcs[1][13].weight = 123;
G.arcs[2][3].weight = G.arcs[3][2].weight = 51;
G.arcs[2][4].weight = G.arcs[4][2].weight = 44;
G.arcs[2][8].weight = G.arcs[8][2].weight = 62;
G.arcs[2][14].weight = G.arcs[1][13].weight = 81;
G.arcs[3][5].weight = G.arcs[5][3].weight = 53;
G.arcs[3][4].weight = G.arcs[4][3].weight = 34;
G.arcs[4][5].weight = G.arcs[5][4].weight = 28;
G.arcs[4][8].weight = G.arcs[8][4].weight = 51;
G.arcs[5][6].weight = G.arcs[6][5].weight = 33;
G.arcs[6][7].weight = G.arcs[7][6].weight = 56;
G.arcs[7][10].weight = G.arcs[7][10].weight= 68;
G.arcs[7][18].weight = G.arcs[18][7].weight= 48;
G.arcs[8][9].weight = G.arcs[9][8].weight = 445;
G.arcs[8][19].weight = G.arcs[19][8].weight = 234;
G.arcs[9][10].weight = G.arcs[10][9].weight = 432;
G.arcs[9][19].weight = G.arcs[19][9].weight = 512;
G.arcs[9][15].weight = G.arcs[15][9].weight = 68;
G.arcs[11][12].weight = G.arcs[12][11].weight =55;
G.arcs[11][16].weight = G.arcs[16][11].weight =111;
G.arcs[12][13].weight = G.arcs[13][12].weight =67;
G.arcs[12][17].weight = G.arcs[17][12].weight =79;
G.arcs[13][14].weight = G.arcs[14][13].weight =58;
G.arcs[14][19].weight = G.arcs[19][14].weight =156;
return 1;
}
int locatevex(graph G,int v) //查找顶点的位置
{
int i;
for(i=0;i
if(v==G.vexs[i].position)
return i;
return -1;
}
//(0)预览地图
void Map()
{
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
//(1)显示景点信息，显示景点信息平面图；
void showinfo(graph G)
{
int i;
cout
for(i=0;i
{
cout
cout
cout
}
}
//(2)景点信息查询
void inquire(graph G)
{
int n,m,flag=1;
cout
cin>>n;
m=locatevex(G,n);
while(flag)
{
if(m
{
cout
cin>>n;
}
m=locatevex(G,n);
if(m>0)
{
cout
cout
flag=0;
}
}
}
//(3)求最短路径，弗洛伊德算法
void shortestpath_Floyd(graph *G)
{
int a,b,c,d,m,n,flag=1,P[20][20][20],D[20][20]; //D路径 景点简介"
do{
do{
cout
cin>>m;
if(m=G->vernum)
cout=0&&mvernum)
flag=0;
}while(m=G->vernum);
do{
cout
cin>>n;
if(n=G->vernum||n==m)
cout=0&&nvernum)
flag=0;
}while(n=G->vernum||n==m);
}while(flag);
for(a=0;avernum;a++) //初始化数组
for(b=0;bvernum;b++)
{
D[a][b]=G->arcs[a][b].weight;
for(c=0;cvernum;c++)
P[a][b][c]=0;
if(D[a][b]
P[a][b][a]=P[a][b][b]=1; }
for(a=0;avernum;a++)
for(b=0;bvernum;b++)
for(c=0;cvernum;c++)
if(D[a][c]+D[b][c]
{
D[a][b]=D[a][c]+D[b][c];
for(d=0;dvernum;d++)
P[a][b][d]=P[a][c][d]||P[b][c][d]; }
coutvexs[m].name;
for(c=0;cvernum;c++)
if(P[m][n][c]&&m!=c&&n!=c)
{
cout"vexs[c].name; }
cout"vexs[n].name;
cout
}
//(4)两个景点间的所有路径
void Allpaths(graph *G)
{
int a,b,c,m,n,flag=1,p[20][20],D[20][20];
do{
do{
cout
cin>>m;
if(m=G->vernum)
cout
if(m>=0&&mvernum)
flag=0;
}while(m=G->vernum);
do{
cout
cin>>n;
if(n=G->vernum||n==m)
cout
if(n>=0&&nvernum)
flag=0;
}while(n=G->vernum||n==m);
}while(flag);
for(a=0;avernum;a++)
for(b=0;bvernum;b++)
{
D[a][b]=G->arcs[a][b].weight=G->arcs[b][a].weight;
if(D[a][b]!=MAX)
p[a][b]=p[b][a]=1;
}
if(p[m][n]==1)
{
coutvexs[m].name;
cout"vexs[n].name;
cout
}
for(a=0;avernum;a++)
if(p[m][a]==1&&p[a][n]==1&&a!=m&&a!=n)
{
coutvexs[m].name;
cout"vexs[a].name;
cout"vexs[n].name;
cout
}
for(a=0;avernum;a++)
for(b=0;bvernum;b++)
if(p[m][a]==1&&p[a][b]==1&&p[b][n]==1&&a!=m&&a!=n&&b!=m&&b!=n)
{
coutvexs[m].name;
cout"vexs[a].name;
cout"vexs[b].name;
cout"vexs[n].name;
cout
}
for(a=0;avernum;a++)
for(b=0;bvernum;b++)
for(c=0;cvernum;c++)
if(p[m][a]==1&&p[a][b]==1&&p[b][c]==1&&p[c][n]==1&&a!=m&&a!=n&&b!=m&&b!=n&&c!=m&&c!=n) {
coutvexs[m].name;
cout"vexs[a].name;
cout"vexs[b].name;
cout"vexs[c].name;
cout"vexs[n].name;
cout
}
}
//(5)更改图的信息
// 1.删除景点信息
int Deletesight(graph &G)
{
int i,v,m,flag=1;
cout
cin>>v;
m=locatevex(G,v);
while(flag)
{
if(m
{
cout
cin>>v;
}
if(m>0)
{
for(i=m;i
{
strcpy(G.vexs[i].name,G.vexs [i+1].name);
strcpy(G.vexs[i].info,G.vexs[i+1].info);
}
flag=0;
}
}
G.vernum--;
showinfo(G);
return 1;
}
// 2.删除图一条边信息
int Deletepath(graph &G)
{
int i,j,v0,v1, flag=1;
while(flag)
{
cout
cin>>v0>>v1;
if(v0G.vernum||v0G.vernum)
{
cout>v0>>v1;
}
if(v0>=0&&v0=0&&v1
flag=0;
}
i=locatevex(G,v0);
j=locatevex(G,v1);
G.arcs[i][j].weight=G.arcs[j][i].weight=MAX;
G.arcnum--;
showinfo(G);
return 1;
}
// 3.增加景点
int Addsight(graph &G)
{
cout
cout>G.vexs[G.vernum].position;
while(G.vexs[G.vernum].position>G.vexs[G.vernum].position;}
cout
cin>>G.vexs[G.vernum].name;
cout
cin>>G.vexs[G.vernum].info;
cout
G.vernum++;
showinfo(G);
return 1;
}
// 4.增加路径
int Addpath(graph &G)
{
int v0,v1,distance;
cout
cin>>v0;
cout
cin>>v1;
cout
cin>>distance;
G.arcs[v0][v1].weight=G.arcs[v1][v0].weight=distance; showinfo(G);
return 1;
}
// 5.更新景点的信息
int newgraph(graph &G)
{
int n,m,t,i; //修改景点信息
cout
cin>>n;
while(nG.vernum)
{
cout
cin>>n;
}
for( i=0;i
{
cout
cin>>m;
cout
cin>>G.vexs[m].name ;
cout
cin>>G.vexs[m].info ;
}
int distance,v0,v1; //修改边的信息
cout
cin>>n;
while(nG.arcnum)
{
cout
cin>>n;
}
cout
for(i=0;i
{
cout
cin>>v0;
cout
cin>>v1;
cout
cin>>distance;
m=locatevex(G,v0);
t=locatevex(G,v1);
if(m>=0&&t>=0)
G.arcs[m][t].weight=G.arcs[t][m].weight=distance; }
showinfo(G);
return 1;
}
//(5)更改图的信息
int changegraph(graph G)
{
int i,flag=1;
cout
cout
{
cout
cin>>i;
switch(i)
{
case 1:
cout
Deletesight(g);break;
case 2:
cout
Deletepath(g);break;
case 3:
cout
Addsight(g);break;
case 4:
cout
Addpath(g);break;
case 5:
cout
newgraph(g);break;
case 6:
cout
return 1;
}
cout
cout
return 1;
}
//主函数
void main()
{
initgraph(g);
cout
cout
cout
cout
cout
cout
cout
{
cout
int i;
cin>>i;
switch(i)
{
case 0:
cout
Map();break;
case 1:
cout
showinfo(g);break;
case 2:
cout
inquire(g);break;
case 3:
cout
shortestpath_Floyd(&g);break;
case 4:
cout
Allpaths(&g);break;
case 5:
cout
changegraph(g);break;
case 6:
cout
flag=0;exit(0);break;
}
cout
cout
cout
cout
cout
cout
cout
cout
cout
}