我做的校园导游程序,,
是用Floyd算法求最短路径的, 不想改了...
就这样了..
#include<string.h>
#include<iostream>
#define MaxVertexNum 100
#define INFITY 200
using namespace std;
typedef int EdgeType;
typedef char VertexType;
typedef int pathMatrix;
typedef int distancMatrix;
typedef struct{
VertexType vexs[MaxVertexNum];
EdgeType edges[MaxVertexNum][MaxVertexNum];
int n,e;
}MGraph;
typedef struct{
char data;
char name[20];
int number;
char introduce[60];
} vertex;
void shortest_path(MGraph *G,pathMatrix p[MaxVertexNum][MaxVertexNum],distancMatrix D[MaxVertexNum][MaxVertexNum])
{ int v,w,u,i,j;
for(v=0;v<G->n;++v)
for(w=0;w<G->n;++w)
{D[v][w]=G->edges[v][w]; /* 把边权值的邻接矩阵赋给D数组*/
if(D[v][w]<INFITY&&D[v][w]!=0)
p[v][w]=v;
else if(v!=w) p[v][w]=-2;
if(v==w) p[v][w]=-1; /*初始化P数组*/
}
for(u=0;u<G->n;++u)
for(v=0;v<G->n;++v)
for(w=0;w<G->n;++w)
if(D[v][u]+D[u][w]<D[v][w])
{D[v][w]=D[v][u]+D[u][w]; /*当v w之间有一点u使用vu的长度加上uw的长度小于 vw的长度, 把相应的P改变,同时改变D数组*/
p[v][w]=u;
}
cout<<"please input you choice between i and j:\n";
cin>>i;
cin>>j;
if(i>=6||j>=6) cout<<"对不起.您输入的景点不存在, 请重新输入.\n"; /*本题我只定义了六个结点*/
else {cout<<"you choice is between "<<G->vexs[i]<<"---and---"<<G->vexs[j]; cout<<endl;
if(p[i][j]>=0)
{w=j; /*输出部分*/
cout<<"您所选择的两景点间的长度为:"; cout<<D[i][j]; cout<<endl; cout<<"您所选择的景点的代号为:"; cout<<G->vexs[j];
cout<<"<--";
while(p[i][w]!=i)
{
cout<<G->vexs[p[i][w]];
w=p[i][w];
cout<<"<--";
}
cout<<G->vexs[i]<<endl;
}
else cout<<"sorry,you choice is not exist.plese try again.\n";
}
}
void start()
{ cout<<"********************************************\n";
cout<<" 校园导游图 \n";
cout<<" 福建工程学院 j0303 41号 周谅友\n";
cout<<"*********************************************\n";
cout<<"请选择操作:\n";
cout<<"0.退出\n";
cout<<"1.任意两个景点间的最短路径\n";
cout<<"2.各个景点的讯息\n";
cout<<"3.用户手册\n";
}
void Readme()
{
cout<<"**********用户手册***************************\n";
cout<<"****查询任意两个景点间的最短路径****\n";
cout<<"请注意:共有六个景点可供选择,数字:0-5\n";
cout<<"输入您要查询的两个景点的数字, 例如0回车5\n";
cout<<"**********各个景点的讯息*************\n";
cout<<"1.请输入您要查询的景点的编号\n";
cout<<"2.例如.. 001 002--006\n";
cout<<"**********感谢你的使用!^_^****************\n";
cout<<endl;
}
main()
{MGraph *G;
int i,j,k,w,m,number_2,l;
vertex t[2];
G=(MGraph *)malloc(sizeof(MGraph));
G->n=6; /*初始化关于G图的各个讯息*/
G->e=8; /*初始化边数跟顶点数*/
G->vexs[0]='a';G->vexs[1]='b'; G->vexs[2]='c'; G->vexs[3]='d'; G->vexs[4]='e'; G->vexs[5]='f'; /* 建立顶点讯息*/
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
{if(i==j) G->edges[i][j]=0;
else G->edges[i][j]=INFITY;
}
G->edges[0][2]=10;G->edges[0][4]=30;G->edges[0][5]=100;
G->edges[1][2]=5; G->edges[2][3]=50;G->edges[3][5]=10;
G->edges[4][3]=20;G->edges[4][5]=60;/*建立图中所有的连接点跟权值*/
pathMatrix p[MaxVertexNum][MaxVertexNum];
distancMatrix D[MaxVertexNum][MaxVertexNum];
l=-1;
t[0].data='a';
strcpy(t[0].name,"class");t[0].number=001;
strcpy(t[0].introduce,"all of the lesson are held at here!!");
t[1].data='b';
strcpy(t[1].name,"lab");t[1].number=002;
strcpy(t[1].introduce,"we do very experience at here!!");
t[2].data='c';
strcpy(t[2].name,"garden");t[2].number=003;
strcpy(t[2].introduce,"we can wander after dinner at here ohch!!");
t[3].data='d';
strcpy(t[3].name,"playground");t[3].number=004;
strcpy(t[3].introduce,"it is a field to play togerther!!");
t[4].data='e';
strcpy(t[4].name,"privacy");t[4].number=005;
strcpy(t[4].introduce,"it is a good place for lover!!");
t[5].data='f';
strcpy(t[5].name,"lake");t[5].number=006;
strcpy(t[5].introduce,"you can see lots of fishes is siwiming there!"); /*建立结点的各个讯息*/
start();
while(l!=0)
{
cin>>l;
switch(l)
{
case 0:
return;
case 1:
cout<<"您选择的是得知任意两个景点间的最短路径\n";
shortest_path(G,p,D);
l=-1;
start();
break;
case 2:
cout<<"您选择的是各个景点的讯息"<<endl;
cout<<"please input your choice:\n";
cin>>number_2;
if(number_2>=007) cout<<"对不起.您输入的景点不存在, 请重新输入.\n";
else{
for(i=0;i<6;i++)
{
if(t[i].number==number_2)
{k=i;
cout<<"the data is:"<<t[k].data<<endl;
cout<<"the name is:"<<t[k].name<<endl;
cout<<"the introduction:"<<t[k].introduce<<endl;
}
}
}
l=-1;
start();
break;
case 3:
cout<<"您选择的是用户手册\n";
cout<<endl;
Readme();
l=-1;
start();
break;
default:
cout<<"输入有误!请重新选择操作!\n";
start();
}
}
}