实验三：校园导游咨询实验三：校园导游咨询 一、 设计方案简介一、 设计方案简介 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 1）设计你所在学校的校园平面图， 2）为来访客人提供图中任意景点相关信息的查询。 3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的 简单路径。 二、设计题目实现二、设计题目实现: 实际需求 1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景 点，存放景点名称、代号、简介等信息：以边表示路径，存放路径长度等相关信息。 2）为来访客人提供图中任意景点相关信息的查询。 3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的 简单路径。 2）概要设计）概要设计 1、校园全景一览图、显示出校园的平面图。 2、提供校园中任意景点问路查询，即求任意两个景点之间的所有路径。 3、提供校园图中多个景点的最佳访问路线查询，即求途径这过个景点的最佳（短）路径。 1功能模块图；1功能模块图； void Map();/校园地图 void CreateGraph();/创建图 void OutputPlace();/输出景点列表 太原理工大学计算机科学与技术学院太原理工大学计算机科学与技术学院 2012年年 01 月月 void SearchPlace();/查询景点信息 void SearchPath();/查询最短路径 void Shortpath(int i);/计算最短路径 void Output(int sight1,int sight2);/输出函数 2各个模块详细的功能描述。2各个模块详细的功能描述。 Map();/显示校园整体的地图、包含学校各景点的详细位置 CreateGraph();/创建图、主要用来保存各景点信息 OutputPlace();/输出景点列表、供选择景点信息查询时使用 SearchPlace();/查询景点信息、景点的名称及介绍 SearchPath();/查询最短路径、两景点间最短距离 Shortpath(int i);/计算两景点间最短路径 Output(int sight1,int sight2);/输出两景点最短路径及信息 四详细设计四详细设计 1功能函数的调用关系图1功能函数的调用关系图 Main() CreateGraph() 太原理工大学计算机科学与技术学院太原理工大学计算机科学与技术学院 2012年年 01 月月 2各功能函数的数据流程图各功能函数的数据流程图 全局变量全局变量 Graph G; int pathNUMNUM; int DNUM; 3重点设计及编码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(w=0;wNUM;w+) pathvw=0;/初始化从 v 到 w 的路径值 if(DvMAX) /存在路径 pathvnum=1; /存在标志置为一 pathvv=1; /自身到自身 Map() SearchPlace() SearchPath() Outputplace() Shortpath(i); Output(i,j); 太原理工大学计算机科学与技术学院太原理工大学计算机科学与技术学院 2012年年 01 月月 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=Dw; finalv=1; /离 num 顶点更近的 v 加入到 s 集合 for(w=0;wNUM;+w) /更新当前最短路径极其距离 if(!finalw/更新路径 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!=sight1) / 如果景点二不和景点一输入重合，则进行. printf(tttttt 从%s 到%s 的最短路径 是:nnttttt,G.vertexsight1.name,G.vertexsight2.name);/输出提示信息 /输出 sight1 到 sight2 的最短路径长度，存放在 D数组中 printf(t%s,G.vertexsight1.name); /输出景点一的名称 d=sight1; /将景点一的编号赋值给 d for(c=0;cNUM;+c) 太原理工大学计算机科学与技术学院太原理工大学计算机科学与技术学院 2012年年 01 月月 gate:; /标号，可以作为 goto 语句跳转的位置 pathasight1=0; for(b=0;bNUM;b+) if(G.arcdb.length%s,G.vertexb.name); /输出此节点的名称 q=q+1; /计数变量加一，满 8 控制输出时的换行 pathab=0; d=b; /将 b 作为出发点进行下一次循环输出，如此反复 if(q%14=0) printf(n); goto gate; printf(nntttttt 最短距离为 %dm.nnt,Da); 五测试数据及运行结果五测试数据及运行结果 系统主界面 太原理工大学计算机科学与技术学院太原理工大学计算机科学与技术学院 2012年年 01 月月 学校平面图 太原理工大学计算机科学与技术学院太原理工大学计算机科学与技术学院 2012年年 01 月月 学校景点图 太原理工大学计算机科学与技术学院太原理工大学计算机科学与技术学院 2012年年 01 月月 太原理工大学计算机科学与技术学院太原理工大学计算机科学与技术学院 2012年年 01 月月 最短路径信息查询 太原理工大学计算机科学与技术学院太原理工大学计算机科学与技术学院 2012年年 01 月月 异常信息 太原理工大学计算机科学与技术学院太原理工大学计算机科学与技术学院 2012年年 01 月月 三、 设计评述三、 设计评述:设计者对本设计的评述及通过设计的收获 体会 设计者对本设计的评述及通过设计的收获 体会 1改进方案1改进方案 系统还有部分漏洞未能修复、不够绝对的稳定、还需改进！ 求最短路径时可以采用比较简单的哈密尔顿算法。 本次课程设计仅完成了要求的基本功能、由于平时掌握的不够好以及时间关系未能完 成选作功能、这是一大缺陷！另外通过本次课程设计也更好的掌握了平时所学的知识、通 过实践学到了许多课本上没有的知识！ 2体会2体会 以后要加强动手时间能力、多与同学交流算法精髓！ 在编写程序中尽量做到独立完成、对于自己想要完成的问题要主动编程完成、这样自 己是一个很大的提升、也能学到很多的知识、熟练编程！ 报告最后有两部分附录报告最后有两部分附录 附录一：参考资料附录一：参考资料 1、C 语言程序设计（谭浩强版）语言程序设计（谭浩强版） 2、数据结构（、数据结构（C 语言版）语言版） 编著：严蔚敏、 吴伟民 编著：严蔚敏、 吴伟民 清华大学出版社清华大学出版社 附录二：源程序附录二：源程序 （将所有的源程序附在最后的附录中）（将所有的源程序附在最后的附录中） / 查询景点信息.cpp : Defines the entry point for the console application. / 太原理工大学计算机科学与技术学院太原理工大学计算机科学与技术学院 2012年年 01 月月 #include stdafx.h #include stdio.h #include #include #include #include #include #define NUM 20 #define MAX 100000 #define FALSE 0 #define TURE 1 typedef struct ArcNode int length; /路径长度 ArcNode, *ArcLink; /边结点的定义 typedef struct VertexNode int number; /景点的编号 char *name; /景点的名称 char *info; /景点的简介 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_DIJ(int num);/迪杰斯特拉算法最短路径 void output(int sight1,int sight2);/输出函数 void CreateGraph()/创建图 太原理工大学计算机科学与技术学院太原理工大学计算机科学与技术学院 2012年年 01 月月 int i,j; G.vexnum=12; G.arcnum=17; for(i=1;iNUM;i+) G.vertexi.number=i; G.vertex1.name=太原理工大学正门; G.vertex1.info=学校正门位于学校的正南方向、 是进入学校前的第一道亮丽ntt 的风 景线!n; G.vertex2.name=电机馆; G.vertex2.info=电机馆是数学系，电子信息系，自动化，通讯等学院的学院楼!n; G.vertex3.name=科学楼; G.vertex3.info=科学楼是我校科研机构场所，也是山西省网关所在地!n; G.vertex4.name=多学科楼; G.vertex4.info=科学楼是计算机科学与技术学院，软件学院，电子信息学院，ntt 土 木，建筑的学院楼，也是我校最好的学院楼!n; G.vertex5.name=图书馆; G.vertex5.info=太原理工图书馆经历了初创时期， 发展时期， 面向现代化的转型时期。 ntt 如今，她已经发展成为资源丰富，现代化，综合性，开放式的图书馆!n; G.vertex6.name=机械馆; G.vertex6.info=机械馆是我校百年高校最有力的体现!ntt 是欧式风格建筑，外观宏 伟气派ntt