某数据结构课程设计公园导游图.doc

该【某数据结构课程设计公园导游图 】是由【雨林书屋】上传分享，文档一共【7】页，该文档可以免费在线阅读，需要了解更多关于【某数据结构课程设计公园导游图 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构实验报告班级:06软件工程姓名:周邓雄学号:06517037实验
四:图(内容:某公园导游图)
一、问题描述:
公园导游系统:给出一张某公园的导游图,旅客经过终端咨询可知︰从某一景到另一景点的最短路径。旅客从公园大门进入,选一条最正确路线,使旅客可以不重复地旅游各景点,最后回到出口(出口就在进口旁边)。
二、设计描述:
(储存方法).本程序特意设计函数voidinitgraph()用于实现键盘输入图的结构;
(GraphMatrixgraph)用于实现接见任一景点的信息;
。利用floyd算法-实现每一对景点间的最短路径。
并利用voidoutgraph()函数实现显示初步点和终点间的最短路径和其长度;
三、程序清单:
#include<iostream>
usingnamespacestd;
#include<>
#defineMAXVEX100
#defineMAX999
typedefcharVexType;
数据结构实验报告班级:06软件工程姓名:周邓雄学号:06517037typedeffloatAdjType;
1/7
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;i<pgraph->n;i++)
for(j=0;j<pgraph->n;j++){
if(pgraph->arcs[i][j]!=MAX)
ppath->nextvex[i][j]=j;
数据结构实验报告班级:06软件工程姓名:周邓雄学号:06517037elseppath->nextvex[i][j]=-1;
ppath->a[i][j]=pgraph->arcs[i][j];
2/7
}
for(k=0;k<pgraph->n;k++)
for(i=0;i<pgraph->n;i++)
for(j=0;j<pgraph->n;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<<endl;
cout<<"请输入想查找初步点和终点:";//输入要查找初步点和终点(本程序限于编号(int型))cout<<endl;
cin>>c;
cin>>b;
i=[c][b];//[c][b]把路径长度赋给i数据结构实验报告班级:
06软件工程姓名:周邓雄学号:06517037cout<<"该路径总长为:";
3/7
cout<<i<<endl;//输出路径长度
cout<<"所得路径序次为";
cout<<c;//此处输出路径的第一个编号c=[c][b];
for(;c!=b;c=[c][b])//循环序次输出路径始点和终点之间的景点编
cout<<","<<c;
cout<<","<<b;//再输出路径的最后一个编号cout<<endl;
}
voidinitgraph()//该函数用于实现键盘输入图的结构
{
inti,m,j;
printf("请输入公园景点的个数:");//
scanf("%d",&m);
=m;
for(i=0;i<;i++)//循环输入结点极点信息
{
printf("请输入第%i个景点信息:",i);//为了简短起见此程序结点极点信息限于字符型cin>>[i];
}
printf("请输入公园的毗邻矩阵的信息\n");//循环输入图的毗邻矩阵信息(也就是输入一个二维数组)for(i=0;i<;i++)
数据结构实验报告班级:06软件工程姓名:周邓雄学号:
06517037for(j=0;j<;j++)
4/7
{
printf("请输入第%d行,第%d列的元素:",i+1,j+1);cin>>[i][j];}
}
voidvist(GraphMatrixgraph)//函数用于实现接见任一景点的信息{inti;
cout<<endl;
cout<<"你想知道哪个景点的信息:";//注意输入的是景点的编号
cin>>i;
cout<<endl;
cout<<"景点信息盘问结果为:";
cout<<[i];//输出景点信息
cout<<endl;
}
intjud()//用于判断能否连续执行特定的下一步程序{inta;
cout<<"还想连续盘问?(1&0)";
cin>>a;
returna;
}
intmain()
数据结构实验报告班级:06软件工程姓名:周邓雄学号:06517037{
inti,j;
initgraph();//initgraph()函数来实现键盘输入图的结构floyd(&graph,&path);
5/7
cout<<"为了考据下边运算结果的方便,循环输出nextvex[i][j]数组";
for(i=0;i<;i++)
{
for(j=0;j<;j++)//为了考据下边运算结果的方便,循环输出nextvex[i][j]数组printf("%d",[i][j]);//nextvex[i][j]存放vi到vj最短路径上vi的后继极点的下标值putchar('\n');
}
cout<<endl;
outgraph();
while(jud())
outgraph();//outgraph()函数用于实现显示初步点和终点间的最短路径和其长度vist(graph);//函数用于实现接见任一景点的信息cout<<endl;
while(jud())
vist(graph);
cout<<endl;
return0;
}
数据结构实验报告班级:06软件工程姓名:周邓雄学号:06517037验四:
图(内容:某公园导游图)
.问题描述
①
给出一张某公园的导游图,旅客经过终端咨询可知:
6/7
1)从某一景点到另一景点的最短路径。
2)旅客从公园大门进入,选一条最正确路线,使旅客可以不重复地旅游景点,最后回到出口(出口就在进口处旁边)。
.要求
②
将导游图看作一张带权无向图,极点表示公园的各个景点,边表示各景点之间的道路,边上的权值给旅客。
.实现提示
③
1)第一问实质是最短路径问题,假如有几条路径长度同样,可选择门路景点较少的路径供应给旅客。
2)第二问可采纳深度优先找寻,假如有多种路径可选择,则选择带权路径最小的路线供应给旅客。
.选做内容
④
可以把各种路径都显示给旅客,由旅客自己选择旅游路线。数据结构实验报告班级:06软件工程姓名:周邓雄学号:06517037
7/7