校园导游咨询程序.doc

实验三：校园导游咨询 设计方案简介 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 1）设计你所在学校的校园平面图， 2）为来访客人提供图中任意景点相关信息的查询。 3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 设计题目实现: 实际需求 1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息：以边表示路径，存放路径长度等相关信息。 2）为来访客人提供图中任意景点相关信息的查询。 3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 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();//显示校园整体的地图、包含学校各景点的详细位置 CreateGraph();//创建图、主要用来保存各景点信息 OutputPlace();//输出景点列表、供选择景点信息查询时使用 SearchPlace();//查询景点信息、景点的名称及介绍 SearchPath();//查询最短路径、两景点间最短距离 Shortpath(int i);//计算两景点间最短路径 Output(int sight1,int sight2);//输出两景点最短路径及信息 四．详细设计 1．功能函数的调用关系图 2．各功能函数的数据流程图 全局变量 Graph G; int path[NUM][NUM]; int D[NUM]; 重点设计及编码 重点设计：求最短路径 编码： void Shortpath(int num)//迪杰斯特拉算法最短路径 { int v,w,i,t;//i、w和v为计数变量//t表示景点个数 int final[NUM]; //标志数组、用来存放顶点的信息 int min;//记录权值、最终输出路径 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; //自身到自身 } } 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; } } } void Output(int sight1,int sight2) // 输出函数 { int a,b,c,d