校园导游实验报告——数据结构_校园导游实验报告
校园导游实验报告——数据结构由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“校园导游实验报告”。
数据结构实验报告
——实验六 简单校园导游程序的设计与实现
本实验的目的是通过对校园导游程序的设计与实现来熟练掌握图型结构在实际问题中的应用。
一、【问题描述】
当人们到一个陌生的地方去旅游的时候可能会找一个导游为自己在游玩的过程中提供方便。导游可以提供很多服务，比如介绍参观景点的历史背景等相关信息，推荐到下一个景点的最佳路径，以及解答旅游者所提出的关于旅游经典的相关问询等等。对于新生刚刚来到校园，对校园环境不熟悉的情况也如此，一般都是高年级的学生充当了“校园导游员”的角色，如果能够提供一个程序让新生或来访的客人自主的通过与机器的“对话”来获得相关的信息的话，将会节省大量的人力和时间。而且所提供的信息也能够做到尽可能的准确、详尽。一个成功的校园导游程序可以替代现实生活中这些“校园导游员”，更方便了大家查询校园相关的信息。
本次实验需要开发一个简单的校园导游程序，程序的主体功能为：
1、显示校园平面图，方便用户直观的看到校园的全景示意图，并确定自己的位置。
2、为用户提供对平面图中任意场所的相关信息的查询。
3、为用户提供对平面图中任意场所的问路查询。
二、【数据结构设计】
由于各个场所通过校园中的道路相连，各个场所和连接它们的道路构成了整个校园的地理环境，所以使用图这种数据结构对他们去进行描述。以图中的顶点表示校园内各个场所，应包含场所名称、代号、简介等信息；以边表示连接各个场所的道路，应包含道路的代号、路径的长度等信息。顶点和边均使用结构体定义，整个图的数据结构可以采用教材中介绍的各种表示方法，例如带权的邻接矩阵。
三、【功能（函数）设计】
1、显示校园平面图的功能模块。
通过读文件的方式将各个地点的信息读入程序中.平面图中应醒目的标识出场所的准确名称以备用户查询。河北大学校园导游的基本地点信息。
***************欢迎进入河北大学校园导游系统!**************-----------------------景点名称---------------------------
主楼 多功能馆 毓秀园 图书馆
操场
留学生楼
七教 八教
九教 成教 南大门 北大门
一教 逸夫楼 博物馆 物理楼
电信楼 化学楼 生科楼 建工楼
北院食堂
南院食堂
竹园 梅园
桂园 菊园 易百超市 北院生活园区
---------------------------地点的存储
typedef struct Vertex//顶点结构体 { int No;//地点编号
char name[20];//地点名称
char info[1000];//地点简介 }Vertex;typedef struct //无向图结构体 { Vertex view[Max_Vertex];int edges[Max_Vertex][Max_Vertex];//边的邻接矩阵
int vnum,anum;//顶点和边的个数 }Graph;
2、查询任意场所的相关信息查询的功能模块。
此模块接收用户所输入的场所名称，并将场所的简介信息反馈给用户。查找出查询的场所将其信息输出,信息通过文本文件读入 函数void introduction(Graph &G)实现
先通过strcpy进行查找，再讲找到顶点v1 G.view[v1].info输出
3、任意场所的问路查询的功能模块。
void shortpath(Graph &G,int v0,int v1)；此函数运用克鲁斯卡尔算法计算两点间最短路径。
void dispath(Graph &G)//查询最短路径 { „shortpath(G, v0, v1)； } 此模块接收用户所输入的场所名称，并在调用shortpath(G, v0, v1)；计算出最短路径相关项的信息反馈给用户。
4、求单源点到其他各点的最短路径的功能模块。
此模块计算并记录从校园门口到各个场所的最短路径。for(i=0;i
四、【界面设计】
本程序为方便用户所设计，由于使用的最终用户大多对校园的情况并不熟悉，所以在图中给出的任何提示信息一定要准确，尽量的避免歧义。
五、【编码实现】 #include #include #include #include #include #define Max_Vertex 100 #define Maxnum 1000 typedef struct Vertex//顶点结构体 { int No;//地点编号
char name[20];//地点名称
char info[1000];//地点简介 }Vertex;typedef struct //无向图结构体 { Vertex view[Max_Vertex];
int edges[Max_Vertex][Max_Vertex];//边的邻接矩阵
int vnum,anum;//顶点和边的个数 }Graph;void Creat(Graph &G){ ifstream infile(“view.txt”,ios::in);
if(!infile)
{
cout
abort();
}
int i,j,k,w;
infile>>G.vnum;
infile>>G.anum;
//cout
for(i=0;i
{
infile>>G.view[i].No>>G.view[i].name>>G.view[i].info;
}
for(i=0;i
{
for(j=0;j
G.edges[i][j]=Maxnum;
}
ifstream weight_file(“weight.txt”,ios::in);
if(!weight_file)
{
cout
abort();
}
for(k=0;k
{
weight_file>>i>>j>>w;
i--;
j--;
G.edges[i][j]=w;
G.edges[j][i]=G.edges[i][j];
} } void introduction(Graph &G){ char temp[20];cout>temp;int v1,i,count=0;for(i=0;i
if(strcmp(G.view[i].name,temp)==0)
{
v1=i;
count++;
} } if(count!=1){
cout
return;} else {
cout
cout
return;} } void shortpath(Graph &G,int v0,int v1){
int P[100];float D[100];int i,j,w;int v,pre;float min;
int final[Max_Vertex];for(v=0;v
{
final[v]=0;
D[v]=G.edges[v0][v];
if(D[v]
P[v]=v0;
if(D[v]==Maxnum)
P[v]=-2;
} D[v0]=0;final[v0]=1;P[v0]=-1;
for(i=1;i
min=Maxnum;
//min为当前所知离源点的最近距离
for(w=0;w
if(!final[w])
if(D[w]
{
j=w;
//记忆此点
min=D[w];
}
final[j]=1;
//离源点最近的j加入S集合 for(w=0;w
//更新其它点地当前最短路径
if(!final[w] &&(min+G.edges[j][w]
{
D[w]=min+G.edges[j][w];
P[w]=j;
//将w的前驱结点改为j
} }
if(P[v1]==-2)
cout
else
{
pre=P[v1];
cout
cout
cout
while(pre>0)
{
cout
pre=P[pre];
}
if(v0==0)
cout
else
cout
cout
}
}
void dispath(Graph &G)//查询最短路径 { int v1,v0,i;int count=0;char temp1[20],temp2[20];cout>temp1>>temp2;
for(i=0;i
if(strcmp(G.view[i].name,temp1)==0)
{
v0=i;
count++;
}
if(strcmp(G.view[i].name,temp2)==0)
{
v1=i;
count++;
} } if(count!=2){
cout
return;} else {
shortpath(G,v0,v1);
return;} } void main(){ Graph G;Creat(G);int i;char ch1;
cout
cout
for(i=0;i
{
if(i%4==0)
{
cout
cout
}
else
{
cout
}
}
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
cin>>ch1;
while(!(ch1='0'))
{
cout
cin>>ch1;
}
switch(ch1)
{
case '1': introduction(G);break;
case '2' :
for(i=0;i
shortpath(G,10,i);
break;
case '3' : dispath(G);
break;
}
}while(ch1!=0);}
六、【运行与测试】
***************欢迎进入河北大学校园导游系统!**************
-----------------------景点名称---------------------------
主楼
多功能馆
毓秀园
图书馆
操场
留学生楼
七教
八教
九教
成教
南大门
北大门
一教
逸夫楼
博物馆
物理楼
电信楼
化学楼
生科楼
建工楼
北院食堂
南院食堂
竹园
梅园
桂园
菊园
易百超市
北院生活园区
---------------------------
__________________________________________________________
请选择要进行的操作
1.查询景点信息
2:显示大门到各个地点的最短路径
3:查询两个景点之间的最短路径
0:退出
__________________________________________________________ 请选择(0~2):1 请输入要查询的景点名称 主楼
该景点简介为
是河北大学本部标志性建筑，这H型高大的建筑，正对着河北大学校本部南院黑
校门，此楼于2001年建成。主要为教学、科研、办公服务。
__________________________________________________________
请选择要进行的操作
1.查询景点信息
2:显示大门到各个地点的最短路径
3:查询两个景点之间的最短路径
0:退出
__________________________________________________________ 请选择(0~2):1 请输入要查询的景点名称 哈哈
输入的名称不存在__________________________________________________________
请选择要进行的操作
1.查询景点信息
2:显示大门到各个地点的最短路径
3:查询两个景点之间的最短路径
0:退出
__________________________________________________________ 请选择(0~2):2 南大门到主楼最短路径为50米 主楼←南大门
南大门到多功能馆最短路径为60米 多功能馆←南大门
南大门到毓秀园最短路径为60米 毓秀园←图书馆←南大门
南大门到图书馆最短路径为40米 图书馆←南大门
南大门到操场最短路径为160米 操场←毓秀园←图书馆←南大门 南大门到留学生楼最短路径为180米
留学生楼←操场←毓秀园←图书馆←南大门
南大门到七教最短路径为115米
七教←桂园←毓秀园←图书馆←南大门
南大门到八教最短路径为65米 八教←图书馆←南大门
南大门到九教最短路径为70米 九教←图书馆←南大门
南大门到成教最短路径为75米 成教←八教←图书馆←南大门
南大门到南大门最短路径为0米 南大门
南大门到北大门最短路径为25米 北大门←南大门
南大门到一教最短路径为35米 一教←北大门←南大门
南大门到逸夫楼最短路径为60米
逸夫楼←博物馆←物理楼←北大门←南大门
南大门到博物馆最短路径为45米 博物馆←物理楼←北大门←南大门
南大门到物理楼最短路径为35米 物理楼←北大门←南大门
南大门到电信楼最短路径为60米 电信楼←一教←北大门←南大门
南大门到化学楼最短路径为50米 化学楼←物理楼←北大门←南大门
南大门到生科楼最短路径为145米
生科楼←建工楼←化学楼←物理楼←北大门←南大门
南大门到建工楼最短路径为100米
建工楼←化学楼←物理楼←北大门←南大门
南大门到北院食堂最短路径为115米
北院食堂←化学楼←物理楼←北大门←南大门
南大门到南院食堂最短路径为80米 南院食堂←八教←图书馆←南大门
南大门到竹园最短路径为135米
竹园←七教←桂园←毓秀园←图书馆←南大门
南大门到梅园最短路径为145米
梅园←七教←桂园←毓秀园←图书馆←南大门
南大门到桂园最短路径为95米 桂园←毓秀园←图书馆←南大门
南大门到菊园最短路径为125米 菊园←八教←图书馆←南大门
南大门到易百超市最短路径为145米
易百超市←七教←桂园←毓秀园←图书馆←南大门
南大门到北院生活园区最短路径为159米
北院生活园区←北院食堂←化学楼←物理楼←北大门←南大门
__________________________________________________________
请选择要进行的操作
1.查询景点信息
2:显示大门到各个地点的最短路径
3:查询两个景点之间的最短路径
0:退出
__________________________________________________________ 请选择(0~2): 请输入要查询的两个景点名称 主楼 七教
主楼到七教最短路径为75米 七教←桂园←毓秀园←主楼
__________________________________________________________
请选择要进行的操作
1.查询景点信息
2:显示大门到各个地点的最短路径
3:查询两个景点之间的最短路径
0:退出
__________________________________________________________ 请选择(0~2):3 请输入要查询的两个景点名称 桌喽 菊园
输入的名称不存在__________________________________________________________
请选择要进行的操作
1.查询景点信息
2:显示大门到各个地点的最短路径
3:查询两个景点之间的最短路径
0:退出
__________________________________________________________
请选择(0~2):
