迪杰斯特拉-景点导航问题的课程设计讲义.docx

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