课程设计报告

《课程设计报告》由会员分享，可在线阅读，更多相关《课程设计报告（16页珍藏版）》请在金锄头文库上搜索。

1、课程设计报告课程设计题目：校园导航学生姓名 ：良谱专业：计算机科学与技术班级：学号：指导教师：艾菊梅2012 年 6 月 21 日目 录一、需求分析说明 . 3 二、开发环境 . . 3 三、总设计体 . . .3 四、详细设计 . . 5 五、实现部分 . . 6 六、程序测试 . 14 七、总结 . 16 一、需求分析：设计你的学校的平面图，至少包括10 个以上的景点（场所），每两个景点间可以有不同的路，且路长也可能不同，找出从任意景点到达另一景点的最佳路径（最短路径）。要求：（1）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。（2）为来

2、访客人提供图中任意景点相关信息的查询。（3） 为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。（4）修改景点信息。二、开发环境本文所采用的开发环境主要是基于c+的 visual stadio c+。它是一个系统的集成开发环境。很适合CC+程序的开发。我们日常的学习和生活中大多就用这个开发环境进行学习和编程。三、总体设计：1.数据结构：用图（无向网）来描述学校n 个景点之间的关系，顶点为单位代号，权值为两景点的距离。本系统基于东华理工大学校园平面图为基准而设计，先将校园内15 个具有代表性的顶点列出，然后绘制出其平面图，标出任意两顶点间是否有直达的边，同时在图上有直达边的

3、两顶点边的权值，本系统中设计的东华理工大学校园平面图如下（景点前面所对应的代号为系统中无向网的顶点号）：东华理工大学学校平面图2.系统功能图：指定两景点之间的最短距离任 意 景 点 到 其 他景 点 的 所 有 最 短校园基础设施介绍退出程序输入要查询相应的选项号输 入 相 应 的 景 点所对应的顶点号输 入 终 点输 入 起 点东华理工大学校园导航系统15 南小门6 北区食堂5 女生公寓3 体育馆1 北门2 软件楼4 北区超14 南区宿舍7 图书馆9 3教学楼10西区食堂11 西区超市12 西区宿舍13 篮球场8 学校正门四、详细设计：一、按所设想的功能，把程序化分为7 个模块，各模块的名称

4、和其数据类型如下表所示：源文件函数名或其他成分功能校园导航 .cpp Main（）主函数Menu （）主菜单函数Create （）建立邻接矩阵shortest_path（）单点到其他点所有最短路径Pointpath（）任意两点间最短路径Chaxun（）查询学校基础设施概况Exit() 跳出程序各模块的说明如下：1. 类模块：本系统中只涉及了一个Graph（无向网类）类，其数据成员为无向网的相关信息， 例如图的邻接矩阵 ( 程序中用数组 arcsn+1n+1存放有关邻接矩阵的相关信息 ) 、原点到各定点的相关信息 （存放在 distn+1数组中 ） 、最短路径上该顶点的前一顶点相关信息（存放在p

5、athn+1 数组中） 、以求得到的最短路径上的顶点的顶点号（存放在sn+1 数组中） ，同时将求最小路径的实现函shortest_path（）定义为其成员函数。2. 具体函数模块：（1）Main 主函数调用各函数，实现课程设计的目标。本系统主函数设计非常简洁，就是反复调用菜单函数 menu()，具体的函数调用代码都设计在菜单函数当中，这样使整个系统函数看起来简单明了。（2）Create （）函数此函数用于建立一个以东华理工大学平面图为蓝本的邻接矩阵，用于对全校各景点间路径信息以及任意两点间路径权值的初始化，为稍后求最小路径工作做铺垫。在此函数当中，各个景点间的相关信息（有无直达的边，边的权值

6、）已经写在函数体中。（3）shortest_path（） 该函数核心代码为迪杰斯特拉算法，用以求任意两景点之间最短路径。具体 思想为设置并逐步扩充集合S，存放以求出的最短路劲的顶点，尚未确定最短路 径的顶点放置在另一集合V 中，按最短路径长度的递增顺序将V 中的顶点加到 S中，直到 S 中包含所有顶点。实现过程中引入了一个辅助数组dist，它的每一 个分量 disti 表示当前找到的从原点到终点的最短路径的长度。 （4）Pointpath （） 该函数在以迪杰斯特拉为原型的基础上稍加改变，在采用迪杰斯特拉算法时 新增一个终点参数， 在输出最小路径时不需要使用for 循环将所有原点与其他顶 点的

7、路径信息输出，只需输出起点和终点两点间的最短距离即可。 （5）liangdian() 此函数为一辅助函数，该函数体中调用了shortest_path（） ，实际上该函 数的功能就是求出一点到其他所有点的最小路径，只不过为了更好在函数调用过 程中理清各函数间的关系同时也是为了使界面设计过程中避免各基础函数代码 冗余，从而引进该函数做辅助用。 (6)dandian() 此函数作用跟上一函数一样也是做辅助用。该函数体中调用了Pointpath （） 函数，实际上该函数的功能就是求出指定两点间的最小路径，只不过为了更好的 在函数调用的过程中理清各函数间的关系同时也是为了使界面设计过程中避免 各函数代码

8、出现冗余，从而引进该函数最辅助之用。 （7）此函数用于为用户提供相关信息的查询服务，本系统为用户提供东华理工 大学相关基础设施的查询服务。 用户只需输入相关的代号就能查询到相关的东华 理工大学基础设施的相关信息。 （8）Menu （） 主菜单函数，负责本系统中个函数的调用工作。因为在设计系统界面时， 主函数通过此函数调用其他函数。五、实现部分(一)、类的定义：先定义一个无向网类，名为Graph，其数据成员包括 int 型数组 arcsn+1n+1(存放图的邻接矩阵相关信息)、int 型数组 distn+1(存放原点到个 点的最小路径 )、int 型数组sn+1(存放最短路径上顶点的顶点号)，成

9、员函数 shortest_path(Graph /图的邻接矩阵 int distn+1; /存放从源点到各顶点的最短路径 int pathn+1; /存放在最短路径上该顶点的前一顶点号bool sn+1; /已求得在最短路径上的顶点的顶点号,为 bool 类型 void shortest_path(Graph /单点到所有其他点的最小路径 void pointpath(Graph (二)、图邻接矩阵的建立：事先指定单点到其自身的距离为0，如两点间没有路 径，则其权值为 max(实现指定的一个很大的数)，然后将设计的学校平面图中个 定点间的相关信息事先定义在该函数中，例如两点间是否有路径， 路径

10、的权值等 实现录入到函数体中。具体实现如下： void create(Graph for(i=1;ichoose; /输入选项号switch(choose) case 1: /如果用户选择1，执 行此处语句coutchoose1; switch(choose1) case 1:chaxun();break; case 2:menu();break; case 3:exit(0); case 2: /如果用户选择 2，执行此处语 句 coutchoose2; switch(choose2) case 1: chaxun();break; case 2:menu();break; case 3:e

11、xit(0); case 3: /如果用户选择 3，执行此处语 句 coutchoose3; switch(choose3) case 1:chaxun();break; case 2:menu();break; case 3:exit(0); case 4: /如果用户选择4，执行此处 语句 coutchoose4; switch(choose4) case 1: chaxun();break; case 2:menu();break; case 3:exit(0); default:coutk; Graph g; g.shortest_path (g,k); coutchoose1; /输

12、入选项号switch(choose1) case 1:menu();break; case 2:exit(0); default:couti; coutj; Graph g; g.pointpath (g, i, j); coutchoose1; /输入选项号switch(choose1) case 1:menu();break; case 2:exit(0); default:coutchoice; /输入选项号switch(choice) case 1:liangdian();break; /两点间最小路径查询 case 2:dandian();break; /单点到其他所有顶点最 短路径

13、查询 case 3:chaxun();break; /查询学校基础设施信息 case 4:exit(0); /退出程序 default:cout“选择错误，请重新输入 !“endl; menu(); break; （七）主函数：通过调用菜单menu 。 void main() cout“ 欢迎 光临 东华 理工大 学， 祝你 旅途 愉快！ “endl; cout“ 东华 理工 大学 校园导 航系 统为 您服 务！ n “endl; cout“ 导航景点 :“endl; cout“ 1北门 2软件楼 3体育馆 4北去超市 “endl; cout“ 5女生公寓 6北去食堂 7图书馆 8正大门 “endl; cout“ 9三栋教学楼 10西区食堂 11西区超市 12 西区宿舍 “endl; cout“ 13篮球场 14南区宿舍 15 南区小门 n“endl; void menu(); menu(); 六、程序测试（一）登入界面设计：（二）两点间最短距离导航：（三）任一景点到其他所有景点间的最短距离导航：选择选项2，依照提示输入起点的序号：（四）查询东华理工大学相关的基础设施情况：选择选项3，依照提示输入想要了解的基础设施所对应的选好，获取相应的信息。具体操作如下：七、总结经过这一个星期的紧张而又充实的课程设计，是我对数据结构这一门课程的相关知识有了全