某数据结构课程设计公园导游图.docx
《某数据结构课程设计公园导游图.docx》由会员分享，可在线阅读，更多相关《某数据结构课程设计公园导游图.docx（7页珍藏版）》请在冰点文库上搜索。
某数据结构课程设计公园导游图
实验四：
图（内容：
某公园导游图）
一、问题描述：
公园导游系统：
给出一张某公园的导游图，游客通过终端询问可知︰从某一景到另一景点的最短路径。
游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。
二、设计描述：
1.输入导游图的算法（存储方法）.本程序特地设计函数voidinitgraph（）用于实现键盘输入图的结构；
2.可访问导游图中任一景点的算法.为此设计了函数voidvist（GraphMatrixgraph）用于实现访问任一景点的信息；
3.最短路径从一景点到另一景点的算法。
利用floyd算法-实现每一对景点间的最短路径。
并利用voidoutgraph（）函数实现显示起始点和终点间的最短路径和其长度；
三、程序清单：
#include
usingnamespacestd;
#include
#defineMAXVEX100
#defineMAX999
typedefcharVexType;
typedeffloatAdjType;
typedefstruct//定义图结构
{
intn;/*图的顶点个数*/
VexTypevexs[MAXVEX];/*顶点信息*/
AdjTypearcs[MAXVEX][MAXVEX];/*边信息*/
}GraphMatrix;
GraphMatrixgraph;//定义一个图graph
typedefstruct//定义最短路径ShortPath结构
{
AdjTypea[MAXVEX][MAXVEX];/*关系矩阵A，存放每对顶点间最短路径长度*/
intnextvex[MAXVEX][MAXVEX];
/*nextvex[i][j]存放vi到vj最短路径上vi的后继顶点的下标值*/
}ShortPath;
ShortPathpath;//定义路径path
voidfloyd（GraphMatrix*pgraph,ShortPath*ppath）//floyd算法-用于实现每一对景点间的最短路径
{
inti,j,k;
for（i=0;in;i++）
for（j=0;jn;j++）{
if（pgraph->arcs[i][j]!
=MAX）
ppath->nextvex[i][j]=j;
elseppath->nextvex[i][j]=-1;
ppath->a[i][j]=pgraph->arcs[i][j];
}
for（k=0;kn;k++）
for（i=0;in;i++）
for（j=0;jn;j++）{
if（ppath->a[i][k]>=MAX||ppath->a[k][j]>=MAX）
continue;
if（ppath->a[i][j]>ppath->a[i][k]+ppath->a[k][j]）{
ppath->a[i][j]=ppath->a[i][k]+ppath->a[k][j];
ppath->nextvex[i][j]=ppath->nextvex[i][k];
}
}
}
voidoutgraph（）//out（）函数用于实现显示起始点和终点间的最短路径和其长度
{
intc,b,i;
cout<cout<<"请输入想查找起始点和终点:
";//输入要查找起始点和终点（本程序限于编号（int型））
cout<cin>>c;
cin>>b;
i=path.a[c][b];//通过path.a[c][b]把路径长度赋给i
cout<<"该路径总长为:
";
cout<cout<<"所得路径顺序为";
cout<c=path.nextvex[c][b];
for（;c!
=b;c=path.nextvex[c][b]）//循环顺序输出路径始点和终点之间的景点编号
cout<<","<cout<<","<cout<}
voidinitgraph（）//该函数用于实现键盘输入图的结构
{
inti,m,j;
printf（"请输入公园景点的个数：
"）;//图结点的个数赋给graph.n
scanf（"%d",&m）;
graph.n=m;
for（i=0;i{
printf（"请输入第%i个景点信息:
",i）;//为了简明起见此程序结点顶点信息限于字符型
cin>>graph.vexs[i];
}
printf（"请输入公园的邻接矩阵的信息\n"）;//循环输入图的邻接矩阵信息（也就是输入一个二维数组）
for（i=0;ifor（j=0;j{
printf（"请输入第%d行，第%d列的元素:
",i+1,j+1）;cin>>graph.arcs[i][j];
}
}
voidvist（GraphMatrixgraph）//函数用于实现访问任一景点的信息
{inti;
cout<cout<<"你想知道哪个景点的信息：
";//注意输入的是景点的编号
cin>>i;
cout<cout<<"景点信息查询结果为：
";
cout<cout<}
intjud（）//用于判断是否继续执行特定的下一步程序
{inta;
cout<<"还想继续查询?
（1&0）";
cin>>a;
returna;
}
intmain（）
{
inti,j;
initgraph（）;//initgraph（）函数来实现键盘输入图的结构
floyd（&graph,&path）;
cout<<"为了验证下面运算结果的方便，循环输出nextvex[i][j]数组";
for（i=0;i{
for（j=0;jprintf（"%d",path.nextvex[i][j]）;//nextvex[i][j]存放vi到vj最短路径上vi的后继顶点的下标值
putchar（'\n'）;
}
cout<outgraph（）;
while（jud（））
outgraph（）;//outgraph（）函数用于实现显示起始点和终点间的最短路径和其长度
vist（graph）;//函数用于实现访问任一景点的信息
cout<while（jud（））
vist（graph）;
cout<return0;
}
验四：
图（内容：
某公园导游图）
①.问题描述
给出一张某公园的导游图，游客通过终端询问可知：
（1）从某一景点到另一景点的最短路径。
（2）游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览景点，最后回到出口（出口就在入口处旁边）。
②.要求
将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值给游客 。
③.实现提示
（1）第一问实际是最短路径问题，如果有几条路径长度相同，可选择途径景点较少的路径提供给游客。
（2）第二问可采用深度优先搜索，如果有多种路径可选择，则选择带权路径最小的路线提供给游客。
④.选做内容
可以把各种路径都显示给游客，由游客自己选择游览路线。
THANKS!
!
!
致力为企业和个人提供合同协议，策划案计划书，学习课件等等
打造全网一站式需求
欢迎您的下载，资料仅供参考
升级会员 