数据结构实验 交通指南系统.docx
《数据结构实验 交通指南系统.docx》由会员分享，可在线阅读，更多相关《数据结构实验 交通指南系统.docx（14页珍藏版）》请在冰点文库上搜索。
数据结构实验交通指南系统
实验交通指南系统
*******
学号：
实验时间：
1.问题描述
假设以一个带权有向图表示某一区域的公交线路图，图中顶点代表一些区域中的重要站点，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一站点到达另一站点。
2.数据结构设计
（1）结点和图的存储结构
typedefstructnode
{intno;
floatwgt;
structnode*next;
}edgenode;
typedefstruct
{charvtx;
edgenode*link;
}vexnode;
typedefvexnodeGraph[n];
voidFloyd（GraphG，floatA[n][n]，intp[n][n]）
{inti，j，k;
for（i=0;ifor（j=0;j{A[i][j]=G[i][j];
P[i][j]=-1;
}
for（k=0;kfor（i=0;ifor（j=0;jif（A[i][k]+A[k][j]{p[i][j]=k;
A[i][j]=A[i][k]+A[k][j];
}
}
（2）算法提示
采用任意两点最短路径的相关算法。
3.算法设计
（1）结点类型：
structArcCell//弧
{
Intadj;//存放弧长
bool*info;//是否用过该弧
};
struct_Mgraph//站点
{
charvexs[20];//存放站点
ArcCellarcs[20][20];//
intvexnum;
intarcnum;
};
（2）类定义：
classMGraph//没用私有成员
{
public:
_MGraphmgraph;
voidDestroyGraph（）;//析构函数销毁图
intLocateVex（charu）;//返回顶点在图中的位置
boolCreateDN（）;//构造有向网
voidShortestPath_FLOYD（Path&P,Distanc&D）;
};
（3）构造有向网：
boolMGraph:
:
CreateDN（）//构造有向网
{
inti,j,w;
charv1,v2;
cout<<"请输入站点个数，直接线路的条数:
";
cin>>mgraph.vexnum>>mgraph.arcnum;
cout<<"\n请输入各站点名:
";
for（i=0;i{
cin>>mgraph.vexs[i];
}
for（i=0;i{
for（j=0;j{
if（i==j）
mgraph.arcs[i][j].adj=0;
else
mgraph.arcs[i][j].adj=20000;//infinity;
mgraph.arcs[i][j].info=false;
}
}
for（i=0;i{
cout<<"\n请输入一条线路的起点,终点,距离（公里）:
";
cin>>v1>>v2>>w;
intm=LocateVex（v1）;
intn=LocateVex（v2）;
mgraph.arcs[m][n].adj=w;//的权值
}
returntrue;
}
（4）销毁有向图：
voidMGraph:
:
DestroyGraph（）
{
for（inti=0;ifor（intj=0;j{
if（mgraph.arcs[i][j].info）
{
delete[]mgraph.arcs[i][j].info;
mgraph.arcs[i][j].info=false;
}
}
mgraph.vexnum=0;
mgraph.arcnum=0;
}
（5）定位点：
intMGraph:
:
LocateVex（charu）
{
for（inti=0;i<20;i++）
{
if（u==mgraph.vexs[i]）
{returni;}
}
return-1;
}
（6）最短路径
voidMGraph:
:
ShortestPath_FLOYD（Path&P,Distanc&D）//求每对顶点间的最短路径
//用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其带权长度D[v][w]
//若P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点。
{
intu,v,w,i;
for（v=0;v{
for（w=0;w{
D[v][w]=mgraph.arcs[v][w].adj;//顶点v到顶点w的直接距离
for（u=0;uP[v][w][u]=false;//路径矩阵初值
if（D[v][w]<20000）//从v到w有直接路径
P[v][w][v]=P[v][w][w]=true;//由v到w的路径经过v和w两点
}
}
for（u=0;u{
for（v=0;v{
for（w=0;w{
if（D[v][u]+D[u][w]//从v经u到w的一条路径更短
{
D[v][w]=D[v][u]+D[u][w];//更新最短距离
for（i=0;iP[v][w][i]=P[v][u][i]||P[u][w][i];//从v到w的路径经过从v到u和从u到w的所有路径
}
}
}
}
}
4.
运行与测试
例:
5.调试记录及收获
本实验的核心代码是用FLOYD算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其带权长度D[v][w]，其中还有邻接矩阵以及二维、三维数组的应用。
通过本次实验，我对最短路径更加熟悉，这让我在求最短路径时容易了很多。
源代码：
#include
usingnamespacestd;
structArcCell
{
intadj;//存放弧长
bool*info;//是否用过该弧
};
struct_MGraph
{
charvexs[20];//存放站点
ArcCellarcs[20][20];//
intvexnum;
intarcnum;
};
typedefintPath[20][20][20];
typedefintDistanc[20][20];
classMGraph//没用私有成员
{
public:
_MGraphmgraph;
voidDestroyGraph（）;//析构函数销毁图
intLocateVex（charu）;//返回顶点在图中的位置
boolCreateDN（）;//构造有向网
voidShortestPath_FLOYD（Path&P,Distanc&D）;
};
boolMGraph:
:
CreateDN（）//构造有向网
{
inti,j,w;
charv1,v2;
cout<<"请输入站点个数，直接线路的条数:
";
cin>>mgraph.vexnum>>mgraph.arcnum;
cout<<"\n请输入各站点名:
";
for（i=0;i{
cin>>mgraph.vexs[i];
}
for（i=0;i{
for（j=0;j{
if（i==j）
mgraph.arcs[i][j].adj=0;
else
mgraph.arcs[i][j].adj=20000;//暂时存放各个站点之间的距离为：
2000
mgraph.arcs[i][j].info=false;//初始化时，每段弧长标记没有用过
}
}
for（i=0;i{
cout<<"\n请输入一条线路的起点,终点,距离（公里）:
";
cin>>v1>>v2>>w;
intm=LocateVex（v1）;
intn=LocateVex（v2）;
mgraph.arcs[m][n].adj=w;//的权值
}
returntrue;
}
voidMGraph:
:
DestroyGraph（）
{
for（inti=0;ifor（intj=0;j{
if（mgraph.arcs[i][j].info）
{
delete[]mgraph.arcs[i][j].info;
mgraph.arcs[i][j].info=false;
}
}
mgraph.vexnum=0;
mgraph.arcnum=0;
}
intMGraph:
:
LocateVex（charu）
{
for（inti=0;i<20;i++）
{
if（u==mgraph.vexs[i]）
{
returni;
}
}
return-1;
}
voidMGraph:
:
ShortestPath_FLOYD（Path&P,Distanc&D）//求每对顶点间的最短路径
//用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其带权长度D[v][w]
//若P[v][w][u]为TRUE，则u是从v到w前求得最短路径上的顶点。
{
intu,v,w,i;
for（v=0;v{
for（w=0;w{
D[v][w]=mgraph.arcs[v][w].adj;//顶点v到顶点w的直接距离
for（u=0;uP[v][w][u]=false;//路径矩阵初值
if（D[v][w]<20000）//从v到w有直接路径
P[v][w][v]=P[v][w][w]=true;//由v到w的路径经过v和w两点
}
}
for（u=0;u{
for（v=0;v{
for（w=0;w{
if（D[v][u]+D[u][w]//从v经u到w的一条路径更短
{
D[v][w]=D[v][u]+D[u][w];//更新最短距离
for（i=0;iP[v][w][i]=P[v][u][i]||P[u][w][i];//从v到w的路径经过从v到u和从u到w的所有路径
}
}
}
}
}
voidmain（）
{
MGraphg;
Pathp;//3维数组
Distancd;//2维数组
ints,t,k;
charv1,v2;
floatsum=0;
cout<<"\n***************欢迎使用交通查询系统**************\n"<g.CreateDN（）;cout<<"\n请输入出发站、目的站：
";
cin>>v1>>v2;
s=g.LocateVex（v1）;
t=g.LocateVex（v2）;
g.ShortestPath_FLOYD（p,d）;
if（s!
=t）
{
inta=s;
cout<<"\n由"<";
for（k=0;kif（p[s][t][k]==1）
{
cout<sum=sum+g.mgraph.arcs[a][k].adj;
}
}
cout<<"最短线路总长：
"<cout<<"\n\n***************祝您旅途愉快！
*****************"<g.DestroyGraph（）;
}
升级会员 