数据结构实验图.docx
《数据结构实验图.docx》由会员分享，可在线阅读，更多相关《数据结构实验图.docx（17页珍藏版）》请在冰点文库上搜索。
数据结构实验图
一、实验目的
图是应用极为广泛的数据结构，也是这门课程的重点，继续使学生更了解数据结构加操作的程序设计观点。
二、问题描述
给出一张某公园的导游图，游客通过终端询问可知：
a）从某一景点到另一个景点的最短路径。
b）游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回到出口。
三、实验要求
1、将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构。
2、为游客提供图中任意景点相关信息的查询；
1、为游客提供任意两个景点之间的一条最短的简单路径。
2、为游客选择最佳游览路径。
四、实验环境
PC微机
DOS操作系统或Windows操作系统
TurboC程序集成环境或VisualC++程序集成环境
五、实验步骤
1、设计公园平面图，图中顶点表示公园的各个景点，存放名称、代号、简介等信息；边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构；
2、设计图的最短路径算法，如果有几条路径长度相同，选择途径景点较少的路径给游客；
3、设计图的深度优先搜索算法，如果有多种路径可选，则选带权路径最短的路线给游客；
4、选择适当语言实现算法；
3、调试程序。
六、测试数据
可根据实际情况指定。
测试数据见南昌大学平面示意图。
七、实验报告要求
1、问题描述；
该程序包扩以下内容：
（1）设计学校的校园平面图，所含景点为9个。
（2）以图中顶点表示校内各景点，存放景点名称、代号、间介等信息；以边表示路径，存放路径长度等相关信息。
（3）为来访客人提供图中任意景点相关信息的查询。
（4）提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径。
（5）提供途中任意景点问路查询，即求任意两个景点间的所有路径。
（6）提供校园图中多个景点的最佳访问路线查询，即求途经这多个景点的最佳（短）路径。
设计思路：
对系统功能抽象，分析问题描述。
首先，平面图用输出模拟；存储景点信息采用结构体；对各景点用字母代替，字母组成图，通过对图的操作，狄克斯特拉算法求出指定最短路径及一点到其它所有点的最短路径，递归进行图的遍历求两点所有路径。
由此可实现以上所有功能。
2、图的建立
图的建立：
这是一个无向带权图，实际上无向带权图与有向带权图相似，采用邻接矩阵存储比较方便。
邻接矩阵的结点结构体如下：
其赋值如下：
3、图的最短路径算法
算法思想：
设置两个结点集合S和T，集合S中存放已找到的最短路径的结点，集合T中存放当前还没找到的最短路径的结点。
初始状态时，集合S中只包含源点，没为v0，然后不断的从集合T中选择到源点v0的路径长度最短的结点u加入到集合S中，集合S中每加入一新的结点u，都要修改源点v0到集合T中剩余结点的当前最短路径长度值，集合T中各点的新的当前最短路径长度值为原来的当前最短路径长度值，与结点u的最短路径长度值加上结点u到该结点的路径长度值（即为从源点结点u到达该结点的路径长度）中的较小者。
此过程不断重复，直到集合T中的对号点全部加到集合S中为止。
算法实现如下：
voidDijkstra（MGraphg,intv,intto）
"<<<<"\n简介：
"<<<}
voidbrowse（）览学校景点2.查找单个景点信息│"<cout<<"│3.学校地图平面示意图4.路线推荐│"<cout<<"│5.景点最短线路6.两景点所有路径│"<cout<<"│7.退出系统│"<cout<<"└────────────────────────────────┘"<}
voidFunMenue2（）学校大门B.和平女神像"<cout<<"C.体育馆D.游泳馆"<cout<<"E.商业街F.教学主楼"<cout<<"G.正气广场H.图书馆"<cout<<"I.天健园"<}
SightC_IN2（）//字母转换为景点
{
charkey;
cin>>key;
switch（key）
{
case'A':
returnA;break;
case'B':
returnB;break;
case'C':
returnC;break;
case'D':
returnD;break;
case'E':
returnE;break;
case'F':
returnF;break;
case'G':
returnG;break;
case'H':
returnH;break;
case'I':
returnI;break;
default:
cout<<"您的输入有误！
请选择A～I！
\n";system（"pause"）;system（"cls"）;FunMenue2（）;C_IN2（）;
}
}
intSprint（charitem）//对字母表示的景点输出
{
switch（item）
{
case'A':
cout<<<<;break;
case'B':
cout<<<<;break;
case'C':
cout<<<<;break;
case'D':
cout<<<<;break;
case'E':
cout<<<<;break;
case'F':
cout<<<<;break;
case'G':
cout<<<<;break;
case'H':
cout<<<<;break;
case'I':
cout<<<<;break;
default:
cout<<"无此景点\n";return1;break;
}
return0;
}
#endif
//构造图及图的相关操作，由狄克斯拉算法改成。
#include""
#defineMAXV100
#defineINF32767
typedefintInfoType;
//邻接矩阵存储方法
typedefstruct
{
intedges[MAXV][MAXV];
intn;
}MGraph;
//狄克斯特拉算法
voidPpath（intpath[],inti,intv）
{
intk;
k=path[i];
if（k==v）return;
Ppath（path,k,v）;
Sprint（k+'A'）;
cout<";
}
voidDispath（intdist[],intpath[],ints[],intn,intv,inti）//对最短路径输出
{
if（s[i]==1）
{
cout<<"";
Sprint（v+'A'）;
cout<Sprint（i+'A'）;
cout<"<";
Sprint（v+'A'）;
cout<";
Ppath（path,i,v）;
Sprint（i+'A'）;
cout<}
else
cout<<"从"<cout<<"────────────────────────────────────";
}
voidDijkstra（MGraphg,intv,intto）//Dijkstrag图中v为起点求出到所有点的最短路径
{
intdist[MAXV],path[MAXV];//dist存路径path存顶点
ints[MAXV];//标记
intmindis,i,j,u;
for（i=0;i<;i++）
{
dist[i]=[v][i];
s[i]=0;
if[v][i]elsepath[i]=-1;
}
s[v]=1;path[v]=0;
for（i=0;i<;i++）
{
mindis=INF;
for（j=0;j<;j++）
{
if（s[j]==0&&dist[j]{
u=j;
mindis=dist[j];
}
}
s[u]=1;
for（j=0;j<;j++）
{
if（s[j]==0）
{
if[u][j]{
dist[j]=dist[u]+[u][j];
path[j]=u;
}
}
}
}
Dispath（dist,path,s,,v,to）;
}
voidDijkstra（MGraphg,intv）//重载，当只有一点求最短路径时，用到
{
intto;
for（to=0;to<;to++）
{
if（to==v）continue;
Dijkstra（g,v,to）;
}
}
//////////////////////////////////////////////////////////////////////////////
intpath[10];
intpathF[10]={0};
intBPsize=0;
intEofV（MGraphg,intstart）
{
intcon=0;
for（intj=0;j<;j++）
if[start][j]!
=0&&[start][j]con++;
returncon;
}
intNest（MGraphg,intstart,inti）
{
intcon=0;
for（intj=0;j<;j++）
{
if[start][j]!
=0&&[start][j]con++;
if（con==i）
returnj;
}
return0;
}
voidPrint（MGraphg）//打印找到路径
{
intTVal=0;
for（intj=0;j{
TVal=TVal+[path[j]][path[j+1]];
Sprint（path[j]+'A'）;
cout<<"---->";
}
Sprint（path[j]+'A'）;
cout<<"\n总长：
"<}
voidFindAllWay（MGraphg,intstart,intend,intn）//寻找所有路径
{
inti;
if（start==end）
{
path[n]=start;
BPsize=n+1;
Print（g）;
return;
}
intnum=EofV（g,start）;
path[n]=start;
for（i=1;i<=num;i++）
{
if（pathF[Nest（g,start,i）]!
=1）
{
pathF[start]=1;
FindAllWay（g,Nest（g,start,i）,end,n+1）;
pathF[start]=0;
}
}
}
//////////////////////////////
//Shortest函数
intShortest（intchoice）//最短路径函数
{
charfrom,to;
inti,j,n;
MGraphg;n=9;//图信息
for（i=0;ifor（j=0;jif（i!
=j）
[i][j]=32767;
else
[i][j]=0;
[0][1]=[1][0]=100;
[0][2]=[2][0]=500;
[0][6]=[6][0]=200;
[0][7]=[7][0]=350;
[2][3]=[3][2]=150;
[3][5]=[5][3]=250;
[4][5]=[5][4]=200;
[4][8]=[8][4]=800;
[5][7]=[7][5]=600;
[6][7]=[7][6]=400;
[7][8]=[8][7]=300;
=n;
if（choice==5）
{
cout<<"请输入起点和终点：
"<cin>>from>>to;
cout<<"+++++++++++++++++++++++++++++竭诚为您提供最短路径+++++++++++++++++++++++++++++++";
i=from-'A';j=to-'A';
Dijkstra（g,i,j）;
cout<}
if（choice==4）
{
cout<<"请输入起点：
"<cin>>from;
system（"cls"）;
cout<<"++++++++++++++++++++++我为您提供这里到学校其它景点最好选择++++++++++++++++++++++";
cout<<"您选择了";
if（Sprint（from）==1）return0;
cout<<"为起点\n";
i=from-'A';
Dijkstra（g,i）;
cout<}
if（choice==6）
{
cout<<"请输入起点和终点：
"<charfrom,to;
cin>>from>>to;
intf,t;
f=from-'A';
t=to-'A';
FindAllWay（g,f,t,0）;
}
return0;
}
#include""
#include""
voidexc（）;
voidC_IN（void）//对主选单操作
{
charkey;
cin>>key;
switch（key）
{
case'1':
browse（）;break;
case'2':
FunMenue2（）;S_print（C_IN2（））;system（"pause"）;system（"cls"）;break;
case'3':
Gprint（）;break;
case'4':
FunMenue2（）;Shortest（4）;system（"pause"）;system（"cls"）;break;
case'5':
FunMenue2（）;Shortest（5）;system（"pause"）;system（"cls"）;break;
case'6':
FunMenue2（）;Shortest（6）;system（"pause"）;system（"cls"）;break;
case'7':
cout<<"\n\n－－－－－－欢迎您的到来，谢谢您的使用！
－－－－－－－－－\n";
cout<<"学校主页：
";
exc（）;
default:
cout<<"您的输入有误！
请选择1～4！
\n";system（"pause"）;system（"cls"）;FunMenue（）;C_IN（）;
}
}
voidexc（）
{
cout<<"确认退出（Y/N）：
";
charkey;
cin>>key;
while（key!
='Y'&&key!
='N'）
cin>>key;
if（key=='Y'）
exit
（1）;
if（key=='N'）
{system（"cls"）;FunMenue（）;C_IN（）;}
}
intmain（）//主函数
{
while
（1）
{
FunMenue（）;
C_IN（）;
}
return0;
}
升级会员 