校园导游咨询程序.doc

1、实验三：校园导游咨询一、 设计方案简介设计一个校园导游程序，为来访的客人提供各种信息查询服务。1）设计你所在学校的校园平面图，2）为来访客人提供图中任意景点相关信息的查询。3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。二、 设计题目实现:实际需求1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息：以边表示路径，存放路径长度等相关信息。2）为来访客人提供图中任意景点相关信息的查询。3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。2）概要设计1、 校园全景一览

2、图、显示出校园的平面图。2、 提供校园中任意景点问路查询，即求任意两个景点之间的所有路径。3、提供校园图中多个景点的最佳访问路线查询，即求途径这过个景点的最佳（短）路径。1功能模块图；void Map();/校园地图void CreateGraph();/创建图void OutputPlace();/输出景点列表void SearchPlace();/查询景点信息void SearchPath();/查询最短路径void Shortpath(int i);/计算最短路径void Output(int sight1,int sight2);/输出函数2各个模块详细的功能描述。Map();/显示校

3、园整体的地图、包含学校各景点的详细位置CreateGraph();/创建图、主要用来保存各景点信息OutputPlace();/输出景点列表、供选择景点信息查询时使用SearchPlace();/查询景点信息、景点的名称及介绍SearchPath();/查询最短路径、两景点间最短距离Shortpath(int i);/计算两景点间最短路径Output(int sight1,int sight2);/输出两景点最短路径及信息四详细设计Main()1功能函数的调用关系图 CreateGraph() SearchPlace() Map() SearchPath()Outputplace()Short

4、path(i);Output(i,j);2各功能函数的数据流程图全局变量Graph G;int pathNUMNUM;int DNUM;3 重点设计及编码 重点设计：求最短路径 编码：void Shortpath(int num)/迪杰斯特拉算法最短路径 int v,w,i,t;/i、w和v为计数变量/t表示景点个数int finalNUM; /标志数组、用来存放顶点的信息int min;/记录权值、最终输出路径for(v=0;vNUM;v+)finalv=0; /假设从顶点num到顶点v没有最短路径Dv=G.arcnumv.length;/将num到其余顶点的最短路径长度初始化为权值for(

5、w=0;wNUM;w+) pathvw=0;/初始化从v到w的路径值if(DvMAX) /存在路径pathvnum=1; /存在标志置为一pathvv=1; /自身到自身Dnum=0;/初始化新路径 finalnum=1; /初始化num顶点属于final集合 /开始主循环,每一次求得num到某个顶点的最短路径，并将其加入到final集合 for(i=0;iNUM;+i) / 其余G.vexnum-1个顶点 min=MAX; /当前所知离顶点num的最近距离for(w=0;wNUM;+w)if(!finalw) /w顶点在v-s中 if(Dwmin) /w顶点离num顶点更近 v=w;min=

6、Dw; finalv=1; /离num顶点更近的v加入到s集合 for(w=0;wNUM;+w) /更新当前最短路径极其距离 if(!finalw&(min+G.arcvw.length)Dw)/不在s集合，并且比以前所找到的路径都短就更新当前路径 Dw=min+G.arcvw.length;/更新路径for(t=0;tNUM;t+)pathwt=pathvt;pathww=1;void Output(int sight1,int sight2) / 输出函数 int a,b,c,d,q=0;/a、b、c和d为计数变量/q控制计数变量、用于换行a=sight2; /将景点二赋值给a if(a!

7、=sight1) / 如果景点二不和景点一输入重合，则进行. printf(tttttt从%s到%s的最短路径是:nnttttt,G.,G.);/输出提示信息/输出sight1到sight2的最短路径长度，存放在D数组中printf(t%s,G.); /输出景点一的名称 d=sight1; /将景点一的编号赋值给dfor(c=0;cNUM;+c)gate:; /标号，可以作为goto语句跳转的位置 pathasight1=0; for(b=0;bNUM;b+) if(G.arcdb.lengt

8、h%s,G.); /输出此节点的名称 q=q+1; /计数变量加一，满8控制输出时的换行 pathab=0; d=b; /将b作为出发点进行下一次循环输出，如此反复 if(q%14=0) printf(n); goto gate; printf(nntttttt最短距离为 %dm.nnt,Da); 五测试数据及运行结果系统主界面学校平面图学校景点图最短路径信息查询异常信息三、 设计评述:设计者对本设计的评述及通过设计的收获体会1 改进方案系统还有部分漏洞未能修复、不够绝对的稳定、还需改进！求最短路径时可以采用比较简单的哈密尔顿算法。 本次课程设计仅完成了要求的基本功能、

9、由于平时掌握的不够好以及时间关系未能完成选作功能、这是一大缺陷！另外通过本次课程设计也更好的掌握了平时所学的知识、通过实践学到了许多课本上没有的知识！2 体会以后要加强动手时间能力、多与同学交流算法精髓！在编写程序中尽量做到独立完成、对于自己想要完成的问题要主动编程完成、这样自己是一个很大的提升、也能学到很多的知识、熟练编程！报告最后有两部分附录附录一：参考资料1、C语言程序设计（谭浩强版）2、数据结构（C语言版） 编著：严蔚敏、吴伟民 清华大学出版社附录二：源程序 （将所有的源程序附在最后的附录中）/ 查询景点信息.cpp : Defines the entry point for the

10、console application./#include stdafx.h#include stdio.h#include #include #include #include #include #define NUM 20#define MAX 100000#define FALSE 0#define TURE 1typedef struct ArcNode int length; /路径长度 ArcNode, *ArcLink; /边结点的定义typedef struct VertexNode int number; /景点的编号 char *name; /景点的名称 char *inf

11、o; /景点的简介 VertexNode; /顶点结点的定义typedef struct Graph VertexNode vertexNUM; ArcNode arcNUMNUM; int vexnum,arcnum; /图的顶点数，边数 Graph; /图的定义Graph G;int pathNUMNUM;int DNUM;void CreateGraph();/创建图void Map();/学校地图void outputplace();/输出校园景点名称void searchplace();/查询景点信息void searchpath();/查询最短路径void shortestpath

12、_DIJ(int num);/迪杰斯特拉算法最短路径void output(int sight1,int sight2);/输出函数void CreateGraph()/创建图int i,j;G.vexnum=12;G.arcnum=17;for(i=1;iNUM;i+) G.vertexi.number=i;G.=太原理工大学正门;G.=学校正门位于学校的正南方向、是进入学校前的第一道亮丽ntt的风景线!n;G.=电机馆;G.=电机馆是数学系，电子信息系，自动化，通讯等学院的学院楼!n;G.ver

13、=科学楼;G.=科学楼是我校科研机构场所，也是山西省网关所在地!n;G.=多学科楼;G.=科学楼是计算机科学与技术学院，软件学院，电子信息学院，ntt土木，建筑的学院楼，也是我校最好的学院楼!n;G.=图书馆;G.=太原理工图书馆经历了初创时期，发展时期，面向现代化的转型时期。ntt如今，她已经发展成为资源丰富，现代化，综合性，开放式的图书馆!n;G.=机械馆;G.=机械馆是我校百年高校最有力的体现!ntt是欧

14、式风格建筑，外观宏伟气派ntt为机械学院的学院楼!n;G.=篮球场;G.=篮球场全橡胶场，每天这里打球人员特多，我校篮球队ntt在历年的CUBA联赛上取得佳绩，是我们引以为豪的校队!n;G.=清泽餐厅;G.=清泽餐厅是我校最现代化的食堂，提供各种美食!n;G.=学生宿舍;G.=这里是我校学生宿舍集中所在地，包括本科生，研究生宿舍，ntt是我们在学校的家!n;G.=文体中心;G.=文体中心包括体育馆，体

15、育场，各种体育娱乐场所，供学生ntt体育锻炼的地方!n;G.=国际交流中心;G.=国际交流中心是外国留学生居住学习科研的场所!n;for(i=0;iNUM;+i)for(j=0;j0 & num=G.vexnum) /判定信息输入正确for(i=1;i11):); scanf(%d,&i); printf(tt最终景点编号(1-11):); scanf(%d,&j); getchar();if(iG.vexnum | iG.vexnum | j0 | i=j) printf(tt输入信息错误!nn); else shortestpath_DI

16、J(i);output(i,j);printf(ntt是否继续查询最短路径(y/n):);c=getchar(); getchar(); system(cls);void shortestpath_DIJ(int num)/迪杰斯特拉算法最短路径int v,w,i,t;/i、w和v为计数变量/t表示景点个数int finalNUM; /标志数组、用来存放顶点的信息int min;/记录权值、最终输出路径for(v=0;vNUM;v+)finalv=FALSE; /假设从顶点num到顶点v没有最短路径Dv=G.arcnumv.length;/将num到其余顶点的最短路径长度初始化为权值for(w

17、=0;wNUM;w+) pathvw=FALSE;/初始化从v到w的路径值if(DvMAX) /存在路径pathvnum=TURE; /存在标志置为一pathvv=TURE; /自身到自身Dnum=0;/初始化新路径 finalnum=TURE; /初始化num顶点属于final集合 /开始主循环,每一次求得num到某个顶点的最短路径，并将其加入到final集合 for(i=0;iNUM;+i) / 其余G.vexnum-1个顶点 min=MAX; /当前所知离顶点num的最近距离for(w=0;wNUM;+w)if(!finalw) /w顶点在v-s中 if(Dwmin) /w顶点离num顶

18、点更近 v=w;min=Dw; finalv=TURE; /离num顶点更近的v加入到s集合 for(w=0;wNUM;+w) /更新当前最短路径极其距离 if(!finalw&(min+G.arcvw.length)Dw)/不在s集合，并且比以前所找到的路径都短就更新当前路径 Dw=min+G.arcvw.length;/更新路径for(t=0;tNUM;t+)pathwt=pathvt;pathww=TURE;void output(int sight1,int sight2)/输出函数 int a,b,c,d,q=0;/a、b、c和d为计数变量/q控制计数变量、用于换行a=sight2;

19、 /将景点二赋值给a if(a!=sight1) / 如果景点二不和景点一输入重合，则进行. printf(tt从%s到%s的最短路径是:nntt,G.,G.);/输出提示信息/输出sight1到sight2的最短路径长度，存放在D数组中printf(%s,G.); /输出景点一的名称 d=sight1; /将景点一的编号赋值给dfor(c=0;cNUM;+c)gate:; /标号，可以作为goto语句跳转的位置 pathasight1=FALSE; for(b=0;bNUM;b+) if(G.arcdb.length%s,G.); /输出此节点的名称 q=q+1; /计数变量加一，满8控制输出时的换行 pathab=FALSE; d=b; /将b作为出发点进行下一次循环输出，如此反复 i