#include<malloc.h>
#include<string.h>
#include<iomanip>
#include<stdio.h>
#define max_ver_num 50
#define OK 1
#define FALSE 0
#define Error -1
#define A 1000
#define TRUE 1
typedef struct arcnode//设置边的权值信息
{
int adj;//路径权值
}arcnode,adjarcs[max_ver_num][max_ver_num];
typedef struct verdata//设置景点信息
{
int position; //顶点个数
char name[60]; //顶点名称
char introduction[1000]; //顶点介绍
}verdata;
typedef struct mgraph //景点图
{
verdata vexs[max_ver_num]; //景点数据
adjarcs arcs; //路径信息
int vernum,arcnum;
}mgraph;
//全局变量
int visited[20];
int d[35];
mgraph g;
//校园导游图的初始化
int initgraph(mgraph& G)
{
int i,j;
G.vernum=12;
G.arcnum=20;
//初始化景点平面图
for(i=0;i<G.vernum;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[0].introduction,"体检中心体检的");
strcpy(G.vexs[1].introduction,"操场跑步的");
strcpy(G.vexs[2].introduction,"校园北口外卖进不来");
strcpy(G.vexs[3].introduction,"银杏景观都围着拍照");
strcpy(G.vexs[4].introduction,"邯郸音乐厅团委开会");
strcpy(G.vexs[5].introduction,"图书馆上自习");
strcpy(G.vexs[6].introduction,"花园景观捞鱼的？");
strcpy(G.vexs[7].introduction,"校园东口一堆人在发***");
strcpy(G.vexs[8].introduction,"人山人海");
strcpy(G.vexs[9].introduction,"没听说过");
strcpy(G.vexs[10].introduction,"上实验课");
strcpy(G.vexs[11].introduction,"离宿舍太远了");
//初始化边矩阵
for(i=0;i<G.vernum;i++)
for(j=0;j<G.vernum;j++)
G.arcs[i][j].adj=A;
G.arcs[0][1].adj=15;
G.arcs[0][2].adj=25;
G.arcs[0][3].adj=30;
G.arcs[1][4].adj=15;
G.arcs[1][7].adj=20;
G.arcs[1][9].adj=40;
G.arcs[2][5].adj=10;
G.arcs[2][8].adj=15;
G.arcs[3][6].adj=30;
G.arcs[3][8].adj=20;
G.arcs[4][7].adj=10;
G.arcs[4][9].adj=60;
G.arcs[5][8].adj=25;
G.arcs[6][8].adj=50;
G.arcs[7][9].adj=35;
G.arcs[4][5].adj=20;
G.arcs[5][6].adj=25;
G.arcs[5][7].adj=30;
G.arcs[6][7].adj=15;
G.arcs[6][9].adj=20;
G.arcs[7][8].adj=40;
G.arcs[8][9].adj=10;
G.arcs[2][9].adj=15;
G.arcs[3][9].adj=30;
G.arcs[3][4].adj=20;
G.arcs[4][8].adj=10;
G.arcs[4][5].adj=60;
G.arcs[5][9].adj=25;
G.arcs[1][8].adj=50;
G.arcs[1][7].adj=35;
for(j=0;j<G.vernum;j++)
for(i=0;i<G.vernum;i++)
G.arcs[i][j].adj=G.arcs[j][i].adj;
return 1;
}
//景点的定位
int locatevex(mgraph c,int v)//景点的定位
{
int i;
for(i=0;i<c.vernum;i++)
if(v==c.vexs[i].position)
return i;
return -1; //若无该景点则返回-1
}
//打印图的邻接矩阵；
int printmatrix(mgraph G)
{
int i,j;
printf("对应的矩阵为：\n");
for(i=0;i<G.vernum;i++)
{
for(j=0;j<G.vernum;j++)
{
if(G.arcs[i][j].adj<A){
printf("\t%d",G.arcs[i][j].adj);
}
else{
printf("\t");
printf("0");
}
}
printf("\n");
}
int x;
while(1){
printf("按1返回上一层,按0退出程序：");
scanf("%d",&x);
if( x == 1 )
return 1;
else if( x == 0 ){
exit(0);
}
else
printf("输入错误，请重新输入：\n");
}
}
//求最短路径，弗洛伊德算法
void shortestpath_Floyd(mgraph *G)
{
int v,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];//D路径
for(v=0;v<G->vernum;v++)
for(w=0;w<G->vernum;w++)
{
D[v][w]=G->arcs[v][w].adj;
for(u=0;u<G->vernum;u++)
p[v][w][u]=0;
if(D[v][w]<A)
{
p[v][w][v]=1;p[v][w][w]=1;
}
}
for(u=0;u<G->vernum;u++)
for(v=0;v<G->vernum;v++)
for(w=0;w<G->vernum;w++)
if(D[v][u]+D[u][w]<D[v][w])
{
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<G->vernum;i++)
p[v][w][i]=p[v][u][i]||p[u][w][i];
}
while(flag)
{
printf("请输入出发点编号:");
scanf("%d",&k);
printf("请输入目的地的编号:\n");
scanf("%d",&j);
if(k<0 || k>G->vernum || j<0 || j>G->vernum)
{
printf("景点编号不存在!请重新输入出发点和目的地的编号:");
printf("请输入出发点编号:");
scanf("%d",&k);
printf("请输入目的地的编号:\n");
scanf("%d",&j);
}
if(k>=0 && k<G->vernum && j>=0 && j<G->vernum)
flag=0;
}
printf("%s",G->vexs[k].name);
for(u=0;u<G->vernum;u++)
if(p[k][j][u]&&k!=u&&j!=u)
printf("-->%s",G->vexs[u].name);
printf("-->%s",G->vexs[j].name);
printf(" 总路线长%dm\n",D[k][j]);
}
//两个景点间的所有路径
void Allpath(mgraph *G)
{
int v,w,k,j,flag=1,p[10][10],D[10][10];
while(flag)
{
printf("请输入出发点和目的地的编号:\n");
printf("请输入出发点编号:");
scanf("%d",&k);
printf("请输入目的地的编号:");
scanf("%d",&j);
if(k<0||k>G->vernum||j<0||j>G->vernum)
{
printf("景点编号不存在!请重新输入出发点和目的地的编号:\n");
printf("请输入出发点编号:\n");
scanf("%d",&k);
printf("请输入目的地的编号:\n");
scanf("%d",&j);
}
if(k>=0&&k<G->vernum&&j>=0&&j<G->vernum)
flag=0;
}
for(v=0;v<G->vernum;v++)
for(w=0;w<G->vernum;w++)
{
D[v][w]=G->arcs[v][w].adj;
if(D[v][w]!=A)
{
p[v][w]=1;
p[w][v]=1;
}
}
if(p[k][j]==1)
{
printf("%s",G->vexs[k].name);
printf("-->");
printf("%s",G->vexs[j].name);
printf("总路线长%d\n",D[k][w]+D[w][j]);
}
for(w=0;w<G->vernum;w++)
if(p[k][w]==1&&p[w][j]==1)
{
printf("%s",G->vexs[k].name);
printf("-->");
printf("%s",G->vexs[w].name);
printf("-->");
printf("%s",G->vexs[j].name);
printf(" 总路线长%d\n",D[k][w]+D[w][j]);
}
for(v=0;v<G->vernum;v++)
for(w=0;w<G->vernum;w++)
if(p[k][v]==1&&p[v][w]==1&&p[w][j]==1)
{
printf("%s",G->vexs[k].name);
printf("-->");
printf("%s",G->vexs[v].name);
printf("-->");
printf("%s",G->vexs[w].name);
printf("-->");
printf("%s",G->vexs[j].name);
printf(" 总路线长%d\n",D[k][v]+D[w][j]+D[v][w]);
}
}
//显示景点信息，显示景点信息平面图
int displaycampus(mgraph G)
{
int i;
printf("景点编号\t\t景点名称\t\t景点简介\t\t\n");
printf("\n");
for(i=0;i<G.vernum;i++)
{
printf(" %d \t\t\t%s\t\t%s\t\t\n\n",G.vexs[i].position,G.vexs[i].name,G.vexs[i].introduction);
/*cout<<" "<<G.vexs[i].position<<" ";
cout<<G.vexs[i].name<<" ";
cout<<G.vexs[i].introduction<<" "<<endl;*/
}
int x;
while(1){
printf("按1返回上一层,按0退出程序：");
scanf("%d",&x);
if( x == 1 )
return 1;
else if( x == 0 ){
exit(0);
}
else
printf("输入错误，请重新输入：\n");
}
}
//构造无向图的邻接矩阵
int creatgraph(mgraph &G)
{
int i,n,m,distance,v0,v1;
printf("请输入矩阵对应的顶点数:");
scanf("%d",&G.vernum);
printf("请输入矩阵对应的边数:");
scanf("%d",&G.arcnum);
for(i=0;i<G.vernum;i++)
{
printf("请输入景点编号：");
scanf("%d",&G.vexs[i].position);
printf("请输入景点名称：");
scanf("%s",G.vexs[i].name);
printf("请输入景点简介：");
scanf("%s",G.vexs[i].introduction);
}
for(i=0;i<G.vernum;i++)
for(int j=0;j<G.vernum;j++)
G.arcs[i][j].adj=0;
for(i=0;i<G.arcnum;i++)
{
printf("输入第[%d]条边的起点编号:",i);
scanf("%d",&v0);
printf("输入第[%d]条边的终点编号:",i);
scanf("%d",&v1);
printf("输入第[%d]条边的长度编号:",i);
scanf("%d",&distance);
m=locatevex(G,v0);
n=locatevex(G,v1);
if(m>=0&&n>=0)
G.arcs[m][n].adj=G.arcs[n][m].adj=distance;
}
displaycampus(G);
printmatrix(G);
return 1;
}
//删除景点信息
int DeleteVertex(mgraph &G)
{
int i,j,v,m;
printf("请输入要删除的景点编号:");
scanf("%d",&v);
m=locatevex(G,v);
int flag=1;
while(flag)
{
if(m<0)
{
printf("无此景点，请重新输入:");
scanf("%d",&v);
}
m=locatevex(G,v);
if(m>0)
{
for(i=m;i<G.vernum ;i++)
{
strcpy(G.vexs[i].name,G.vexs [i+1].name);
strcpy(G.vexs[i].introduction,G.vexs[i+1].introduction);
}
flag=0;
}
}
for(i=m;i<G.vernum;i++)//删除行
for(j=0;j<G.vernum;j++)
G.arcs[i][j]=G.arcs[i+1][j];
for(i=m;i<G.vernum;i++)//删除列
for(j=0;j<G.vernum;j++)
G.arcs[j][i]=G.arcs[j][i+1];
G.vernum--;
displaycampus(G);
printmatrix(G);
return 1;
}
//删除图一条路径信息
int DeleteplanArc(mgraph &G)
{
int i,j,v0,v1;
int flag=1;
while(flag)
{
printf("请输入要删除的一条边对应的两个顶点编号:\n");
scanf("%d",v0);
scanf("%d",v1);
if(v0<0||v0>G.vernum||v0<0||v1>G.vernum)
{
printf("景点编号不存在!请重新输入要删除的一条边对应的两个顶点编号:");
scanf("%d",v0);
scanf("%d",v1);
}
if(v0>=0&&v0<G.vernum&&v1>=0&&v1<G.vernum)
flag=0;
}
i=locatevex(G,v0);
j=locatevex(G,v1);
G.arcs[i][j].adj=A;
G.arcs[j][i].adj=A;
G.arcnum--;
displaycampus(G);
printmatrix(G);
return 1;
}
//增加景点
int enverx(mgraph &G)
{
int i;
printf("请输入要添加的景点的信息：\n");
printf("请输入景点编号:");
scanf("%d",&G.vexs[G.vernum].position);
printf("请输入景点名称:");
scanf("%s",&G.vexs[G.vernum].name);
printf("请输入景点简介:");
scanf("%s",&G.vexs[G.vernum].introduction);
printf("\n");
G.vernum++;
for(i=0;i<G.vernum;i++)
G.arcs[i][G.vernum-1].adj=G.arcs[i][G.vernum-1].adj=A;
displaycampus(G);
printmatrix(G);
return 1;
}
//增加路径
int enarc(mgraph &G)
{
int v0,v1,distance;
printf("请输入增加路径的起始点编号:");
scanf("%d",&v0);
printf("请输入增加路径的终点编号:");
scanf("%d",&v1);
printf("请输入增加路径长度");
scanf("%s",&distance);
G.arcs[v0][v1].adj=G.arcs[v1][v0].adj=distance;
displaycampus(G);
printmatrix(G);
return 1;
}
//景点信息查询
void seaabout(mgraph G)
{
int n,flag=1;
printf("请输入要查询的景点编号：");
scanf("%d",&n);
while(flag)
{
if(n<0||n>G.vernum)
{
printf("该景点不存在，请重新输入：");
scanf("%d",&n);
}
else
{
printf("景点编号\t\t景点名称\t\t景点简介\t\t\n");
printf(" %d \t\t\t%s\t\t%s\t\t\n\n",G.vexs[n].position,G.vexs[n].name,G.vexs[n].introduction);
/*
cout<<" "<<G.vexs[n].position<<" ";
cout<<G.vexs[n].name<<" ";
cout<<G.vexs[n].introduction<<" "<<endl;
*/
flag=0;
}
}
}
//更新景点的信息
int newgraph(mgraph &G)
{
int n,m,t,i;
printf("请输入要更新的景点数：");
scanf("%d",&n);
while(n<0||n>G.vernum)
{
printf("该景点不存在，请重新输入：");
scanf("%d",&n);
}
for(i=0;i<n;i++)//修改景点信息
{
printf("输入景点的编号：");
scanf("%d",&m);
t=locatevex(G,m);
printf("输入景点的名称：");
scanf("%s",&G.vexs[t].name);
printf("输入景点的简介：");
scanf("%s",&G.vexs[t].introduction);
}
printf("请输入要更改的边数：");
scanf("%d",&n);
int distance,v0,v1;
while(n<0||n>G.arcnum)
{
printf("该路径不存在，请重新输入：");
scanf("%d",&n);
}
printf("输入更新的路径的信息：");
for(i=0;i<n;i++)//修改路径信息
{
printf("起始景点编号v0:");
scanf("%d",&v0);
printf("终点景点编号v1:");
scanf("%d",&v1);
printf("路径长度:");
scanf("%d",&distance);
m=locatevex(G,v0);
t=locatevex(G,v1);
if(m>=0&&t>=0)
G.arcs[m][t].adj=G.arcs[t][m].adj=distance;
}
displaycampus(G);
printmatrix(G);
return 1;
}
//更改图的信息
int changegraph(mgraph G)
{
int i;
printf("1、重新建图 2、删除结点 \n");
printf("3、删除边 4、增加结点 \n");
printf("5、增加边 6、更新图信息\n");
printf("7、打印邻接矩阵 8、返回程序 \n");
while(1)
{
printf("请输入要进行的操作:");
scanf("%d",&i);
switch(i)
{
case 1:
printf("重新建图:\n");
creatgraph(g);
break;
case 2:
printf("删除结点:\n");
DeleteVertex(g);
break;
case 3:
printf("删除边:\n");
DeleteplanArc(g);
break;
case 4:
printf("增加结点:\n");
enverx(g);
break;
case 5:
printf("增加边:\n");
enarc(g);
break;
case 6:
printf("更新图信息:\n");
newgraph(g);
break;
case 7:
printf("打印邻接矩阵:\n");
printmatrix(g);
break;
case 8:
printf("返回程序:\n");
return 1;
}
}
return 1;
}
int main()
{
initgraph(g);
printf("学校概况：\n");
displaycampus(g);
while(1)
{
printf("\n");
printf(" 欢迎来到HBU \n");
printf(" 1、学校景点介绍 2、打印邻接矩阵 \n");
printf(" 3、查询景点间最短路径 4、查询景点信息 \n");
printf(" 5、改变图的信息 6、查询景点间可行路径 \n");
printf(" 7、退出程序 \n");
printf("请输入你要进行的操作:");
int k;
scanf("%d",&k);
switch(k)
{
case 1:
printf("学校景点介绍:\n");
displaycampus(g);
break;
case 2:
printf("打印邻接矩阵:\n");
printmatrix(g);
break;
case 3:
printf("查询景点间最短路径:\n");
displaycampus(g);
shortestpath_Floyd(&g);
break;
case 4:
printf("查询景点信息:\n");
seaabout(g);
break;
case 5:
printf("改变图的信息:\n");
changegraph(g);
break;
case 6:
printf("查询景点间可行路径:\n");
Allpath(&g);
break;
case 7:
printf("退出程序\n");
//flag=0;
exit(0);
break;
default:
break;
}
}
}
京公网安备 11010502036488号