数据结构校园导航程序设计.doc

一、设计题目： 实验题目： 设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。校园导航 本课题实现校园多个场所（至少10个）的最短路径求解。 （1） 输入的形式和输入值的范围：本系统主要数据类型为字符型和整形，字符型主要包括地点编号，地点名称，地点简介，功能编号；输入功能编号与单位编号进行操作。 (2) 输出的形式：输出则通过已有的信息数据，通过相关的操作输出相应信息。 (3) 程序所能达到的功能：可以为学生或旅客了解我校大概地点位置以及路径， 主要功能：1.浏览校园地点及简介； 2.查看所有游览路线； 3.选择出发点和目的地求出最佳路径； 4.查看某一单位信息。 （4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 a.首先看到的是校园导航 b．查看浏览路线等待输入起始地点： C．选择出发点与目的地等待输入起始地点与目的地编号（中间用空格隔开）： d．参看地点信息等待输入地点编号： 三、概要设计 本系统包含菜单（menu），显示信息（show），弗洛伊德算法(floyd)，迪杰斯特拉算法(shotpath_dj)，查找地点信息等程序段(search)。主程序为整系统的入口处，菜单主要实现显示系统功能，显示信息主要实现显示地点信息，弗洛伊德算法主要实现求两地点之间最短路径，迪杰斯特拉算法实现找两地点之间所有路径，查找地点信息主要实现显示某一地点信息。 系统首先通过主程序调用void main( );进入系统主菜单函数，根据用户的选择可分别进入：1.浏览各地点及简介； 2.查看所有游览路径； 3.选择出发点和目的地求出最短路径； 4.查看地点信息； 5.退出系统。 选择“1”项，显示十个地点的有关信息，包括地点编号，地点名称，地点简介。 选择“2”项，会进入输入起始地点编号的界面，输入正确编号后会显示起始地点到其余九个地点的所有路径。 选择“3”项，会进入输入起始地点与目的地点的界面，输入起始地 点与目的地点，并有空格隔开就得到两地点之间的最短路径。 选择“4”项，会进入输入要查看的地点的界面，输入地点编号后会显示该地点的有关信息。 选择“5”项，就会退出程序。 下图为程序总框架图，表示函数之间的函数关系： 系统详细设计 （1）十个校园地点图： 0：正大门 1：南三栋 2：西区篮球场 3：食堂 4：教三栋 5：图书馆 6：北区食堂 7：医务室 8：软件楼 9：北门 （2）主程序流程图： （3）迪结斯特拉算法实现的顶点V1到其他顶点的最短路径： void ShortPath_Dj(MGraph * G) { int v,w,i,min,t=0,x,flag=1,v0; int final[20], D[20], p[20][20]; cout编号 地点名称 简介 endl; for(v=0;vG-vexnum;v++) coutG-vexs[v].numG-vexs[v].name G-vexs[v].introductionendl; while(flag) { cout请输入一个起始地点编号:; cinv0; if(v00||v0G-vexnum) { cout地点编号不存在!请重新输入地点编号:; cinv0; } if(v0=0v0G-vexnum) flag=0; } for(v=0;vG-vexnum;v++) { final[v]=0; D[v]=G-arcs[v0][v].adj; for(w=0;wG-vexnum;w++) p[v][w]=0; if(D[v]infinity) { p[v][v0]=1;p[v][v]=1; } } D[v0]=0;final[v0]=1; for(i=1;iG-vexnum;i++) { min=infinity; for(w=0;wG-vexnum;w++) if(!final[w]) if(D[w]min){v=w;min=D[w];} final[v]=1; for(w=0;wG-vexnum;w++) if(!final[w](min+G-arcs[v][w].adjD[w])) { D[w]=min+G-arcs[v][w].adj; for(x=0;xG-vexnum;x++)