迪杰斯特拉景点导航问题的课程设计

课程设计报告实验名称：数据结构与算法课程设计题目：景点导航问题院系：计算机工程学院班级：软件学号：学生姓名：指导教师：设计周数：1 周成绩：日期： 2016 年 7 月 4 日1目录一、 课程设计的目的与要求 .21. 目的： .22. 要求： .2二、 课程设计题目 .2三、 需求分析 .2四、 概要设计 .3五、 详细设计 .4六、 调试分析 .61. 界面及其选择功能测试 .62. 创建景点平面图功能的调试 .73. 景点相关信息查询功能的调试 .74. 景点路径信息查询功能的调试 .8七、 使用说明 .9八、 测试结果 .10九、 总结 .111 已完成的工作 .112 未完成的工作 .113 需做的改进 .12附录 .12参考文献 .12景点平面图 .12源程序 .132一、 课程设计的目的与要求1. 目的：应用数据结构和算法来设计相应的程序，培养学生问题求解模块的框架设计和详细设计、相关程序实现和调试能力，完成创新能力和实践能力的训练。2. 要求：用高级程序设计语言 C 编码，用 VC+开发平台调试。二、 课程设计题目景点导航问题：设计某一景点的平面图，至少包括 10 个以上的场所，每两个场所可以有不同的路径，并且路径长度可能不同，找出从任意场所到达另一场所的最佳路径。三、 需求分析本演示程序基于 VC+6.0 编写，完成景点布局的建立、查询，以及各个景点之间的路径查询。1) 设计景点的平面图，在该景点选取 10 个左右的子景点。以图中顶点表示该景点内的各景点，存放子景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2) 为来访客人提供图中任意景点相关信息的查询。3) 为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。4) 为来访客人提供将所查询到的信息保存到指定文件中去的功能。5) 测试数据：A. 创建景点平面图的操作中依次输入 11（景点个数） 、14（相邻景点边数） 、 “枇杷园” （各个景点的名称） 、 “枇杷园是” （各个景点的简介） 、（1 2） （相邻景点的代号） 、13（相邻景点的距离） ，生成一个景点平面图。3B. 查询景点相关信息操作中，输入 1、2、3屏幕终端分别显示 1号景点、2 号景点、3 号景点的名称、简介，以及其相邻的景点。C. 查询景点路径的操作中，输入景点代号，如代号 1，屏幕终端显示1 号景点与其他所有景点的最短路程及所经过的路径。四、 概要设计1) 为了实现上述程序功能，需要定义景点平面图的抽象数据类型：Mgraph数据对象：D1=vex|vexvexsvnum，i=0,1,2，n0D2=arc|arc IntegerSet，i=0,1,2，n0数据关系：R=（ai,ai+1）=arci|ai,ai+1 D1，arciD2基本操作：函数原型 初始条件 操作结果Voidcreatgraph(Mgraph *G,char *name,char *intro) 无初始条件创建一个景点平面图的邻接矩阵和两个字符数组，存放有景点名称、简介等相关信息Voiddijkstra(MgraphG,intv,char *name);景点平面图 G、景点名称数组name 已经存在查询到任意一景点代号 v 到其他景点的最短路程和路径Void dijkstra_file(MgraphG,intv,char *name);景点平面图 G、景点名称数组name 已经存在查询到任意一景点代号 v 到其他景点的最短路程和路径并保存到指定文件中Void asked(MgraphG,intv,char *intro,char*name);景点平面图 G、景点名称数组name、景点简介数组 intro 已经存在查询到任意一景点 v 的名称、简介以及相邻景点Void asked_file(MgraphG,intv,char *intro,char *name);景点平面图 G、景点名称数组name、景点简介数组 intro 已经存在查询到任意一景点 v 的名称、简介以及相邻景点并保存到指定文件中Void menu_one(); 在屏幕终端输入 1实现任意一景点的相关查询；在屏幕上显示操作菜单4Void menu_two();在屏幕终端输入 2、景点平面图 G、景点名称数组 name 已经存在在屏幕上显示操作菜单实现景点平面图中任意一景点相关信息的查询2) 本程序包含 8 个函数 主函数 main() 创建景点平面图函数 creatgraph() 显示操作菜单函数一 menu_one() 显示操作菜单函数二 menu_two() 最短路径查询函数 dijkstra() 最短路径结果储存函数 dijkstra_file() 景点名称查询函数 asked() 景点名称结果储存函数 asked_file()各函数间关系如下：五、 详细设计为了实现概要设计中定义的所有的数据类型，对每个操作写出 C 语言算法；对主程序和其他模块也都需要写出 C 语言算法；画出系统结构图1) 景点平面图的数据类型5typedef char Velemtype;typedefstructVelemtypevexsvnum;int arcsvnumvnum;intvex,arc;Mgraph;2) 景点平面图的基本操作如下void creatgraph(Mgraph *G,char *name,char *intro);void dijkstra(MgraphG,intv,char *name);void dijkstra_file(MgraphG,intv,char *name);void asked(MgraphG,intv,char *intro,char *name);void asked_file(MgraphG,intv,char *intro,char *name);void menu_one();void menu_two();voidmain();其说明见前。其中 Menu_two 为自行设计的景点平面图，即景点平面图已初始化成功。该景点平面图有 11 个景点、14 条景点间的接边。该景点平面图设计如下：6六、 调试分析1. 界面及其选择功能测试检查界面布局是否合理、正确，选择不同功能后是否可以正确显示。 主菜单 1(Menu_one)的界面如下： 主菜单 2(menu_two)的界面如下：72. 创建景点平面图功能的调试3. 景点相关信息查询功能的调试 Menu_one 中查询功能的调试分别为输入数据有误和无误时的情况，并可选择是否将结果储存到文件中：8 Menu_two 中查询功能的调试1. 输入正确时：