校园导游系统实验报告

竭诚为您提供优质文档/双击可除

校园导游系统实验报告

篇一：校园导游图系统数据结构实验报告 一.设计目的

通过布置具有一定难度的实际程序设计项目，使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法；使学生掌握分析问题，求解问题的方法并提高学生设计编程实现的能力。 二.设计内容

用无向网表示学校的校园景点平面图，图中顶点表示主要景点，

存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。游客通过终端可询问：（1）从某一景点到另一景点的最短路径。（2）游客从公园进入，选取一

1 15

条最佳路线。

（3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。[基本要求]

（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，

边上的权值表示距离．为此图选择适当的数据结构。 （2）把各种路径都显示给游客，由游客自己选择浏览路线。（3）画出景点分布图于屏幕上。[实现提示] （1）构造一个无向图g并用邻接矩阵来存储。 （2）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组p[i][]来记录，

最短路径长度就用一维数组d[i]存放；i的范围：0～20。

（3）一维数组have[]是用来记录最短路径出现顶点的顺序。（4）根据起点和终点输出最短路径和路径长度。 三．概要设计 1．功能模块图；

2.各个模块详细的功能描述。

1.浏览校园全景：采用深度遍历遍历图进行所有景点浏览，将遍历景点信息输出

2.查看所有游览路线：用户输入一个景点，采用迪杰斯特拉算法将从该景点起所有路径查出并输出在屏幕上

2 15

3.选择出发点和目的地：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点到目的地的最短路径 4.查看景点信息：直接用编号进行单个景点查询。四．详细设计重点设计及编码

在求最短路径时采用迪杰斯特拉算法

//迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点voidshortestpath_DIJ(mgraph*g) {//迪杰斯特拉算法，求从顶点v0到其余顶点的最短路经及其带权长度d[v]//若p[v][w]为1，则w是从v0到v的最短路经上的顶点//final[v]类型用于设置访问标志intv,w,i,min,final[20],D[20],p[20][20],t=0,x,flag=1,v0;//vo为起始景点的编号while(flag){printf(\"请输入一个起始景点编

号:\");scanf(\"%d\景点编号不存在!请重新输入景点编

号:\");scanf(\"%d\al[v]=0;//初始化各顶点访问标志

D[v]=g->arcs[v0][v].adj;//v0到各顶点v的权值赋值给d[v]for(w=0;wvexnum;w++)//初始化p[][]数组，各顶点间的路径全部设置为空路径0p[v][w]=0;if(D[v] final[v0]=1;//v0的访问标志设为1，v属于s集

for(i=1;ivexnum;i++)//对其余g.vexnum-1个顶点w，依次

3 15

求v到w的最短路径

{min=InFInITY;for(w=0;wvexnum;w++)//在未被访问的顶点中，查找与v0最近的顶点

vif(!final[w])if(D[w]vexnum;w++)//修改v0到其余各顶点w的最短路径权值d[w]if(!final[w]//修改v0到w的权值d[w]for(x=0;xvexnum;x++)//所有v0到v的最短路径上的顶点x，都是v0到w的最短路径上的顶点

p[w][x]=p[v][x];p[w][w]=1;}}for(v=0;vvexnum;v++)//输出v0到其它顶点v的最短路径

{if(v0!=v)printf(\"%s\输出景点v0的景点名for(w=0;wvexnum;w++)//对图中每个顶点w，试探w是否是v0到v的最短路径上的顶点{if(p[v][w]t++;}if(t>g->vexnum-1}}

五．测试数据及运行结果1．正常测试数据和运行结果 1.浏览校园全部景点信息： 2.查看景点信息：

3.输出两个景点间的最短路径 :

2．异常测试数据及运行结果

1.当输出错误编号时程序没有反映，继续输入直到输入正确：

2.当查询两景点编号相同时的最短路径时，结果如下：

4 15

篇二：校园导游实验报告[1] 校园导游实验报告 学号：20XX30457018 姓名：熊博 班级：09计科1班 完成日期：20XX-12-21 1、问题描述

制作陶瓷学院的校园导游图，游客通过终端可询问： （1）从某一景点到另一景点的最短路径。

（2）游客从公园进入，选取一条最佳路线3，使游客可以不重复地游览各景点，最后回到出口（出口就在入口处旁边） 2、要求

（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离。为此图选择适当的数据结构。

（2）把各种路径都显示给游客，由游客自己选择游览路线。

（3）画出景点分布图于屏幕上。 3、实现提示

（1）第一实际是最短路径问题，如果有几条路径长度相同，可选择途径景点较少的路径提供给游客。

5 15

（2）第二问可采用深度优先搜索，如果有多种路径可选择，则选择带权路径最小的路线提供给游客。 2.概要设计： typedefstructArcell {

intadj;//路径长度

}Arcell,Adjmatrix[mAx_VeRTex_num][mAx_VeRTex_num];

typedefstruct//图中顶点表示主要景点，存放景点的信息 {

charname[30]; intnum; intx; inty;

charintroduction[500];//简介 }infotype; typedefstruct {

infotypevexs[mAx_VeRTex_num]; Adjmatrixarcs; intvexnum,arcnum;

6 15

}mgraph; mgraphb;

voiddij(mgraph*);计算出起点到其他各个顶点之间的最短路径

voidfloyd(mgraph*);计算任意两个景点之间的最短路径

voidsearch(mgraph*g);查看景点信息 voidjdbrowser();查看主要景点布局图 3.详细设计： main函数： voidmain() { intk;

system(\"colorcf\");

system(\"modecon:cols=140lines=130\"); b=Initgraph(); system(\"cls\");

printf(\"欢迎您进入景德镇陶瓷学院学校园导游咨询系统\\n\");

printf(\"\\\\n\"); sleep(1000); do

7 15

{ while(1) {

printf(\"\\n\");

printf(\"主要景点列表\\n\"); printf(\"\\n\"); printf(\"操场游 泳馆\\n\"); printf(\"3教体 育馆\\n\");

printf(\"2教1教\\n\"); printf(\"图书馆2实 验楼\\n\");

printf(\"9实验楼医 院\\n\");

printf(\"东西办9# 宿舍楼\\n\"); printf(\"综合食堂二 三食堂\\n\"); printf(\"80广场大 门\\n\"); printf(\"\\n\");

8 15

printf(\"\\\\n\");

printf(\"┏━━━━━━━━━━━━━━━━ ━━━━━━━┓\\n\");

printf(\"┃1.查看主要景点布局图┃\\n\"); printf(\"┃2.查看景点信息┃\\n\"); printf(\"┃3.查看某一景点到其他景点的最 短路径┃\\n\");

printf(\"┃4.查看任意两个景点之间的最短 路径┃\\n\");

printf(\"┃0.退出系统┃\\n\");

printf(\"┗━━━━━━━━━━━━━━━━ ━━━━━━━┛\\n\");

printf(\"请输入您的选择选择，按回车键结束:\"); scanf(\"%d\ if(k5) {

printf(\"输入有误请重新输入，按回车键结束!\\n\"); scanf(\"%d\ }

elsebreak; }

switch(k)

9 15

{

case1:jdbrowser();system(\"cls\");break; case2:search(system(\"cls\");break; case3:dij(system(\"cls\");break; case4:floyd(system(\"cls\");break; case0:exit(0); }

}while(1); }

图形初始化函数： mgraphInitgraph() { mgraphg; inti,j; g.vexnum=17; g.arcnum=19;

for(i=0;i g.vexs[i].num=i; strcpy(g.vexs[1].name,\"操场\");

strcpy(g.vexs[1].introduction,\"足球场，现代化塑胶跑道,人造草坪,锻炼身体的场所\");strcpy(g.vexs[2].name,\"游泳馆\");

strcpy(g.vexs[2].introduction,\"一般只是暑假期间

10 15

开放，水不是很干净\");

strcpy(g.vexs[3].name,\"3教\");

strcpy(g.vexs[3].introduction,\"多媒体教学场所,设施先进,环境良好\");

strcpy(g.vexs[4].name,\"体育馆\");

strcpy(g.vexs[4].introduction,\"里面有篮球场还有羽毛球场，平时用作羽毛球场地\");strcpy(g.vexs[5].name,\"2教\");

strcpy(g.vexs[5].introduction,\"学院第二大教学楼,环境较差\");

strcpy(g.vexs[6].name,\"1教\");

strcpy(g.vexs[6].introduction,\"学院最大的教学楼,共5层，环形建筑,适宜学习\");strcpy(g.vexs[7].name,\"图书馆\");

strcpy(g.vexs[7].introduction,\"藏书60万册,设施良好，2楼为电子阅览室，环境幽雅\"); strcpy(g.vexs[8].name,\"2实验楼\");

strcpy(g.vexs[8].introduction,\"信息科学与技术学院所在地\");

strcpy(g.vexs[9].name,\"9实验楼\");

strcpy(g.vexs[9].introduction,\"学校机房所在地\"); strcpy(g.vexs[10].name,\"医院\");

11 15

strcpy(g.vexs[10].introduction,\"校医院,设施不是很齐全，收费较贵\");

strcpy(g.vexs[11].name,\"春晖楼\");

strcpy(g.vexs[11].introduction,\"全体教师办公场所，楼高12层，各种设施齐全

\");strcpy(g.vexs[12].name,\"9#宿舍楼\");

strcpy(g.vexs[12].introduction,\"装饰古朴，设施还算齐全，就是挤了点\");strcpy(g.vexs[13].name,\"综合食堂\");

strcpy(g.vexs[13].introduction,\"新建标准化食堂，食物种类多，但是价格比较贵。

\");strcpy(g.vexs[14].name,\"二三食堂\");

strcpy(g.vexs[14].introduction,\"收费比较便宜的食堂，二楼的套餐还可以，主要是便宜，不过菜有点难吃\"); strcpy(g.vexs[15].name,\"80广场\");

strcpy(g.vexs[15].introduction,\"新建的广场，据说由80界校友捐赠。\");

strcpy(g.vexs[16].name,\"大门\"); 篇三：校园导游实验报告 简单校园导游系统的设计与实现

本实验的目的是通过对“校园导游”程序的设计与实现来熟练掌握图形结构在实际问题中的应用。一.问题描述

12 15

当人们到一个陌生的地方去旅游时，可能找到一个导游为自己在游玩的过程中提供帮助。导游可以提供多种服务，如介绍参观景点的历史背景等相关信息，推荐到下一个景点的最佳路径，解答旅游者所提出的关于旅游景点的相关查询等。对于刚刚来到校园的新生，对校园环境不熟悉的情况也是如此，一般都是高年级的学生充当“校园导游”的角色。如果能够提供一个程序让新生或来访的客人自主地通过与机器的“对话”来获得相关信息的话，将会节省大量的人力和时间，并且所提供的信息应做到尽可能的准确、详尽。一个成功的校园导游程序可以替代现实生活中的这些“校园导游”，更方便大家查询校园相关的信息。

本次实验需要开发一个简单的校园导游程序，程序的主体功能如下：

①显示校园平面图，方便用户直观地看到校园的全景示意图，并确定自己的位置。

②为用户提供对平面图中任意场所相关信息的查询。③为用户提供对平面图中任意场所的问路查询。二.数据结构设计

由于各个场所通过校园中的道路相连，各个场所和连接它们的道路构成了整个校园的地理环境，所以使用图这种数据结构对它们进行描述。以图中的顶点表示校园内各个场所，应包含场所、名称、代号、简介等信息；以边表示连接各个

13 15

场所的道路，应包含道路的代号、路径的长度等信息。顶点和边都使用结构体定义，整个图的数据结构使用带权的邻接矩阵。如下：typedefstruct{ char*name;intnum;char*instr;

}Vertextype;//定义顶点结构类型typedefstruct{ intnum;intlength;

}edgetype;//定义边结构类型typedefstruct{ Vertextypevexs[maxvernum];

edgetypeedges[maxvernum][maxvernum]; intvnumber;intenumber;

}graph;//以邻接矩阵存储的图的类型三、功能函数设计1、图中包含信息的初始化 函数原型为voidget(graph

g.vexs[2].name=newchar(strlen(\"逸夫楼\")+1);strcpy(g.vexs[2].name,\"逸夫楼\"); n=g.vexs[2].instr=n; 对路径1进行初始化：

g.edges[0][1].length=200;g.edges[0][1].num=1;2、主函数

3、求单源点到其他各个场所的最短路径的功能模块 函数原型为

voidshortestpath(graphg,intv0,int*p,int*D)

14 15

本模块使用迪杰斯特拉（Dijkstra）算

法，该算法的基本思想是：设置两个顶点的集合s和T（T=V-s），集合s中存放已找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。初始状态时，集合s中只包含单源点v,然后不断从集合T中选取到顶点v的路径长度最短的顶点u加入到集合s中，集合s中每加入一个新的顶点u，都要修改顶点V到集合T中剩余顶点的最短路径值，集合T中各个顶点的新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径加上u到该顶点的路径长度中的较小值。此过程不断重复，直到集合T中的顶点全部都加入到s中为止。

15 15