校园导游咨询程序

实验三：校园导游咨询一、设计方案简介设计一个校园导游程序，为来访的客人提供各种信息查询服务。1）设计你所在学校的校园平面图，2）为来访客人提供图中任意景点相关信息的查询。3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。二、设计题目实现:实际需求1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息：以边表示路径，存放路径长度等相关信息。2）为来访客人提供图中任意景点相关信息的查询。3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。2）概要设计1、校园全景一览图、显示出校园的平面图。2、提供校园中任意景点问路查询，即求任意两个景点之间的所有路径。3、提供校园图中多个景点的最佳访问路线查询，即求途径这过个景点的最佳（短）路径。1．功能模块图；voidMap();//校园地图voidCreateGraph();//创建图voidOutputPlace();//输出景点列表太原理工大学计算机科学与技术学院2012年01月voidSearchPlace();//查询景点信息voidSearchPath();//查询最短路径voidShortpath(inti);//计算最短路径voidOutput(intsight1,intsight2);//输出函数2．各个模块详细的功能描述。Map();//显示校园整体的地图、包含学校各景点的详细位置CreateGraph();//创建图、主要用来保存各景点信息OutputPlace();//输出景点列表、供选择景点信息查询时使用SearchPlace();//查询景点信息、景点的名称及介绍SearchPath();//查询最短路径、两景点间最短距离Shortpath(inti);//计算两景点间最短路径Output(intsight1,intsight2);//输出两景点最短路径及信息四．详细设计1．功能函数的调用关系图Main()CreateGraph()太原理工大学计算机科学与技术学院2012年01月2．各功能函数的数据流程图全局变量GraphG;intpath[NUM][NUM];intD[NUM];3．重点设计及编码重点设计：求最短路径编码：voidShortpath(intnum)//迪杰斯特拉算法最短路径{intv,w,i,t;//i、w和v为计数变量//t表示景点个数intfinal[NUM];//标志数组、用来存放顶点的信息intmin;//记录权值、最终输出路径for(v=0;vNUM;v++){final[v]=0;//假设从顶点num到顶点v没有最短路径D[v]=G.arc[num][v].length;//将num到其余顶点的最短路径长度初始化为权值for(w=0;wNUM;w++)path[v][w]=0;//初始化从v到w的路径值if(D[v]MAX)//存在路径{path[v][num]=1;//存在标志置为一path[v][v]=1;//自身到自身}}Map()SearchPlace()SearchPath()Outputplace()Shortpath(i);Output(i,j);太原理工大学计算机科学与技术学院2012年01月D[num]=0;//初始化新路径final[num]=1;//初始化num顶点属于final集合//开始主循环,每一次求得num到某个顶点的最短路径，并将其加入到final集合for(i=0;iNUM;++i)//其余G.vexnum-1个顶点{min=MAX;//当前所知离顶点num的最近距离for(w=0;wNUM;++w)if(!final[w])//w顶点在v-s中if(D[w]min)//w顶点离num顶点更近{v=w;min=D[w];}final[v]=1;//离num顶点更近的v加入到s集合for(w=0;wNUM;++w)//更新当前最短路径极其距离if(!final[w]&&((min+G.arc[v][w].length)D[w]))//不在s集合，并且比以前所找到的路径都短就更新当前路径{D[w]=min+G.arc[v][w].length;//更新路径for(t=0;tNUM;t++)path[w][t]=path[v][t];path[w][w]=1;}}}voidOutput(intsight1,intsight2)//输出函数{inta,b,c,d,q=0;//a、b、c和d为计数变量//q控制计数变量、用于换行a=sight2;//将景点二赋值给aif(a!=sight1)//如果景点二不和景点一输入重合，则进行...{printf(\t\t\t\t\t\t从%s到%s的最短路径是:\n\n\t\t\t\t\t,G.vertex[sight1].name,G.vertex[sight2].name);//输出提示信息//输出sight1到sight2的最短路径长度，存放在D[]数组中printf(\t%s,G.vertex[sight1].name);//输出景点一的名称d=sight1;//将景点一的编号赋值给dfor(c=0;cNUM;++c){太原理工大学计算机科学与技术学院2012年01月gate:;//标号，可以作为goto语句跳转的位置path[a][sight1]=0;for(b=0;bNUM;b++){if(G.arc[d][b].lengthMAX&&path[a][b])//如果景点一和它的一个临界点之间存在路径且最短路径{printf(---%s,G.vertex[b].name);//输出此节点的名称q=q+1;//计数变量加一，满8控制输出时的换行path[a][b]=0;d=b;//将b作为出发点进行下一次循环输出，如此反复if(q%14==0)printf(\n);gotogate;}}}printf(\n\n\t\t\t\t\t\t最短距离为%dm.\n\n\t,D[a]);}}五．测试数据及运行结果系统主界面太原理工大学计算机科学与技术学院2012年01月学校平面图太原理工大学计算机科学与技术学院2012年01月学校景点图太原理工大学计算机科学与技术学院2012年01月太原理工大学计算机科学与技术学院2012年01月最短路径信息查询太原理工大学计算机科学与技术学院2012年01月异常信息太原理工大学计算机科学与技术学院2012年01月三、设计评述:设计者对本设计的评述及通过设计的收获体会1．改进方案系统还有部分漏洞未能修复、不够绝对的稳定、还需改进！求最短路径时可以采用比较简单的哈密尔顿算法。本次课程设计仅完成了要求的基本功能、由于平时掌握的不够好以及时间关系未能完成选作功能、这是一大缺陷！另外通过本次课程设计也更好的掌握了平时所学的知识、通过实践学到了许多课本上没有的知识！2．体会以后要加强动手时间能力、多与同学交流算法精髓！在编写程序中尽量做到独立完成、对于自己想要完成的问题要主动编程完成、这样自己是一个很大的提升、也能学到很多的知识、熟练编程！报告最后有两部分附录附录一：参考资料1、C语言程序设计（谭浩强版）2、数据结构（C语言版）编著：严蔚敏、吴伟民清华大学出版社附录二：源程序（将所有的源程序附在最后的附录中）//查询景点信息.cpp:Definestheentrypointfortheconsoleapplication.//太原理工大学计算机科学与技术学院2012年01月#includestdafx.h#includestdio.h#includestring.h#includestdio.h#includemalloc.h#includestdlib.h#includeconio.h#defineNUM20#defineMAX100000#defineFALSE0#defineTURE1typedefstructArcNode{intlength;//路径长度}ArcNode,*ArcLink;//边结点的定义typedefstructVertexNode{intnumber;//景点的编号char*name;//景点的名称char*info;//景点的简介}VertexNode;//顶点结点的定义typedefstructGraph{VertexNodevertex[NUM];ArcNodearc[NUM][NUM];intvexnum,arcnum;//图的顶点数，边数}Graph;//图的定义GraphG;intpath[NUM][NUM];intD[NUM];voidCreateGraph();//创建图voidMap();//学校地图voidoutputplace();//输出校园景点名称voidsearchplace();//查询景点信息voidsearchpath();//查询最短路径voidshortestpath_DIJ(intnum);//迪杰斯特拉算法最短路径voidoutput(intsight1,intsight2);//输出函数voidCreateGraph()//创建图太原理工大学计算机科学与技术学院2012年01月{inti,j;G.vexnum=12;G.arcnum=17;for(i=1;iNUM;i++)G.vertex[i].number=i;G.vertex[1].name=太原理工大学正门;G.vertex[1].info=学校正门位于学校的正南方向、是进入学校前的第一道亮丽\n\t\t的风景线!\n;G.vertex[2].name=电机馆;G.vertex[2].info=电机馆是数学系，电子信息系，自动化，通讯等学院的学院楼!\n;G.vertex[3].name=科学楼;G.vertex[3].info=科学楼是我校科研机构场所，也是山西省网关所在地!\n;G.vertex[4].name=多学科楼;G.vertex[4].info=科学楼是计算机科学与技术学院，软件学院，电子信息学院，\n\t\t土木，建筑的学院楼，也是我校最好的学院楼!\n;G.vertex[5].name=图书馆;G.vertex[5].info=太原理工图书馆经历了初创时期，发展时期，面向现代化的转型时期。\n\t\t如今，她已经发展成为资源丰富，现代化，综合性，开放式的图书馆!\n;G.vertex[6].name=机械馆;G.vertex[6].info=机械馆是我校百年高校最有力的体现!\n\t\t是欧式风格建筑，外观宏伟气派\n\t\t为机械学院的学院楼!\n;G.vertex[7].name=篮球场;G.vertex[7].info=篮球场全橡胶场，每天这里打球人员特多，我校篮球队\n\t\t在历年的CUBA联赛上取得佳绩，是我们引以为豪的校队!\n;G.vertex[8].name=清泽餐厅;G.vertex[8].info=清泽餐厅是我校最现代化的食堂，提供各种美食!\n;G.vertex[9].name=学生宿舍;G.vertex[9].info=这里是我校学生宿舍集中所在地，包括本科生，研究生宿舍，\n\t\t是我们在学校的家!\n;G.vertex[10].name=文体中心;G.vertex[10].info=文体中心包括体育馆，体育场，各种体育娱乐场所，供学生\n\t\t体育锻炼的地方!\n;G.vertex[11].name=国际交流中心;G.vertex[11].info=国际交流中心是外国留学生居住学习科研的场所!\n;for(i=0;iNUM;++i)for(j=0;jNUM;++j)G.arc[i][j].length=MAX;G.arc[1][2].length=G.arc[2][1].length=60;G.arc[1][3].length=G.arc[3][1].length=30;G.ar