北理珠校园导游咨询与最短路径

北京理工大学珠海学院课程设计说明书_2014_—_2015_学年第_1_学期题目:北理珠校园导游咨询与最短路径学院：计算机学院专业班级：学号：学生姓名：指导教师：王琳成绩：时间：2014年12月30日2014年12月30日设计任务书2014～2015学年第1学期学生姓名：专业班级：指导教师：王琳工作部门：计算机学院一、课程设计题目北理珠校园导游咨询与最短路径二、课程设计内容（含技术指标）【问题描述】从北京理工大学珠海学院的平面图中选取有代表性景点（10-15个），抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地之间距离。本程序的目的是为用户提供路径咨询。根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息。【任务要求】从北京理工大学珠海学院的平面图中选取有代表性景点（10-15个），抽象成一个无向带权图。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。区分汽车线路与步行线路。【测试数据】北理珠校园导游图（距离可估计）。三、进度安排1．初步设计：写出初步设计思路，进行修改完善，并进行初步设计。2．详细设计：根据确定的设计思想，进一步完善初步设计内容，按要求编写出数据结构类型定义、各算法程序、主函数。编译分析调试错误。3．测试分析：设计几组数据进行测试分析，查找存在的设计缺陷，完善程序。4．报告撰写：根据上面设计过程和结果，按照要求写出设计报告。5．答辩考核验收：教师按组（人）检查验收，并提出相关问题，以便检验设计完成情况。四、基本要求1．在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。2．在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。3．设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，报告格式严格按照模板要求撰写，排版及图、表要清楚、工整。从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便；程序的整体结构及局部结构要合理；设计报告要符合规范。课程负责人签名：年月日课程设计分工安排姓名课程设计负责工作备注成绩评定表姓名成绩评定权重总分总成绩（五分制）平时成绩20报告成绩50答辩成绩30摘要通过数据结构“图”构成抽象数据类型，该系统运用了数组表示法（领结矩阵）初始化图，分别存储数据元素（景点）和数据元素（路段）之间的关系，迪杰斯特拉算法来描述各景点所有游览路径，佛洛依德算法设计景点之间的最短路径，结合上述算法设计了一个校园导航与最短路径系统，供来访北理珠的客人使用，为其提供方便。关键词：概要设计详细设计软件测试I目录课程设计说明书..............................................................................................1设计任务书...............................................................................................................................2成绩评定表...............................................................................................................................6摘要.......................................................................................................................................7目录...........................................................................................................................................81.前言...............................................................................................................................91.1问题的描述................................................................................................................91.2算法输入....................................................................................................................91.3算法输出....................................................................................................................92.概要设计.........................................................................................................................112.1要点描述..................................................................................................................112.2模块分解..................................................................................................................113.详细设计.........................................................................................................................123.1算法程序流程图......................................................................................................123.2界面设计..................................................................................................................134.软件测试..........................................................................................................................175.参考文献..........................................................................................................................196.心得体会............................................................................................错误!未定义书签。答辩记录表.............................................................................................................................281.前言1.1问题的描述从北京理工大学珠海学院的平面图中选取有代表性景点（10-15个），抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地之间距离。本程序的目的是为用户提供路径咨询。根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息1.2算法输入MGraphCreatGraph(void)//初始化{MGraphG;inti,j;G.vexnum=10;//14个顶点G.arcnum=16;//14条弧for(i=0;iG.vexnum;i++)G.vexs[i].num=i;//第i个景点的编号为istrcpy_s(G.vexs[0].name,北理图书馆);……1.3算法输出voidcmd(void);MGraphCreatGraph(void);//初始化图voidMenu(void);//主界面voidBrowser(MGraph*G);//浏览全部景点voidShortestPath_DIJ(MGraph*G);//该点到其它全部路径voidFloyd(MGraph*G);//两景点最短路径voidSearch(MGraph*G);//查看景点信息voidprintMatrix(MGraph*G);//输出领结矩阵2.概要设计2.1要点描述用图的算法进行构造，用邻接表建立图，图的每一个顶点代表相应的景点。然后再用深度优先遍历进行搜索，查找所需的路径。再用迪杰特斯拉算法求出一个景点到其他景点之间的最佳路径。然后再用弗洛伊德算法求出要查询的出发点到目的地的最短路径。2.2模块分解（1）主菜单（Menu）：存放着所有的选择供用户查询。用户可通过输入编号来查询自己想要获得的信息（2）浏览校园全景（Browser）：采用深度遍历图进行所有景点浏览，将遍历景点信息输出。（3）查看各景点游览路线（ShortestPath_DIJ）：用户输入一个景点，采用迪杰斯特拉算法将从该景点起所有路径查出并输出在屏幕上。（4）选择出发点和目的地(Floyd)：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点到目的地的最短路径。（5）查看景点信息(Search)：直接输入编号进行单个景点查询。（6）显示图的邻接矩阵(print)（7）退出系统(exit)3.详细设计3.1算法程序流程图3.2界面设计主菜单（Menu）:voidMenu()//定义主菜单{printf(\n北京理工大学珠海学院导游图\n);printf(\n);printf(1.浏览校园全景\n);printf(2.查看各景点所有游览路线\n);printf(3.选择出发点和目的地\n);printf(4.查看景点信息\n);printf(5.显示此图的邻接矩阵\n);printf(6.退出系统\n);printf(\n);printf(选项-:);}浏览校园全景（Browser）:voidBrowser(MGraph*G){intv;printf(编号景点名称简介\n);for(v=0;vG-vexnum;v++)printf(┃%-4d┃%-16s┃%-56s┃\n,G-vexs[v].num,