《公园导游图课程设计》由会员分享，可在线阅读，更多相关《公园导游图课程设计（15页珍藏版）》请在金锄头文库上搜索。
1、 课课 程程 设设 计计题目题目公 园 导 游 图专业专业网络工程班级班级1 班姓名姓名尹颖指导老师指导老师孙菁2014 年年 12 月月 28 日日课程设计（论文）1课程设计任务书课程设计任务书20142015 学年第 1 学期学生姓名：学生姓名： 尹颖吴东旭许益强葛溆李永康朱世豪尹颖吴东旭许益强葛溆李永康朱世豪 专业班级：专业班级： 1212 网络工程网络工程 指导教师：指导教师： 孙菁孙菁 一、课程设计题目一、课程设计题目: : 公园导游图二、课程设计内容二、课程设计内容给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游
2、客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。三、进度安排三、进度安排1 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2 完成最低要求：建立一个文件，包括 5 个景点情况，能完成遍历功能；3 进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。四、基本要求四、基本要求1. 界面友好，函数功能要划分好2. 总体设计应画一流程图3. 程序要加必要的注释4. 要提供程序测试方案5. 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。目目 录录摘要摘要 1 问题描述问题描述3 1.1 图、无向图3 1.1.1 图
3、的存储结构3 1.1.2 图的邻接矩阵表示法3 1.2 算最短路径4 1.3 无向图遍历4课程设计（论文）21.4 广度优先搜索42.系统分析系统分析5 2.1 系统流程图53 系统设计系统设计5 3.1 主要数据结构6 3.2 主要函数说明6 3.3 主要算法说明6 3.3.1 数组表示法6 3.3.2FLOYD算法 64 心得体会心得体会7附录一：源程序附录一：源程序8附录三：参考文献附录三：参考文献14摘摘 要要 计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调
4、整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种 运算的算法。1.问题描述课程设计（论文）3.图的存储结构图的存储方式很多，这里用的是邻接矩阵的方式。为了适合用 C 语言描述，以下假定顶点序号从 0 开始，即图 G 的顶点集的一般形式是 V(G)=v 0 ，v i ，V n-1 。1.1.11.1.1
5、图的邻接矩阵表示法图的邻接矩阵表示法（）用邻接矩阵表示顶点之间的相邻关系；（）用一个顺序表来储存顶点信息1.1.21.1.2 图的邻接矩阵图的邻接矩阵(Adacency(Adacency Matrix)Matrix)设 G=(V，E)是具有 n 个顶点的图，则 G 的邻接矩阵是具有如下性质的 n 阶方阵：若是网络，则邻接矩阵可定义为：.求最短路径给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。1.2.11.2.1 单源最短
6、路径问题单源最短路径问题Dijkstra 提出按各顶点与源点 v 间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点 v 到其它各顶点的最短路径全部求出为止。 ，其它0E(G)v,v或)v,(v或1,jijijiA课程设计（论文）4.求最小生成树对于连通的带权图(连通网)G，其生成树也是带权的。生成树 T 各边的权值总和称为该树的权，记作：Te,W(u , v)TE 表示 T 的边集w(u，v)表示边(u，v)的权。权最小的生成树称为 G 的最小生成树(Minimum Spanning Tree)。最小
7、生成树可简记为 MST。最小生成树性质：设 G=(V，E)是一个连通网络，U 是顶点集 V 的一个真子集。若(u，v)是 G 中一条“一个端点在 U 中(例如：uU)，另一个端点不在 U 中的边(例如：vV-U)，且(u，v)具有最小权值，则一定存在 G 的一棵最小生成树包括此边(u，v)。. .系统分析系统分析. .系统流程系统流程本系统主要是实现图的最短路径问题课程设计（论文）52.22.2 系统相关抽象数据类型系统相关抽象数据类型2.2.12.2.1 图的邻接矩阵存储结构形式说明图的邻接矩阵存储结构形式说明#define MaxVertexNum l00 /最大顶点数，应由用户定义typ
8、edef char VertexType; /顶点类型应由用户定义typedef int EdgeType; /边上的权值类型应由用户定义typedef structVextexType vexsMaxVertexNum /顶点表EdeType edgesMaxVertexNumMaxVertexNum;/邻接矩阵，可看作边表int n，e; /图中当前的顶点数和边数MGragh;2.2.22.2.2 建立无向网络的算法建立无向网络的算法void CreateMGraph(MGraph *G)/建立无向网的邻接矩阵表示int i，j，k，w;图 2-1课程设计（论文）6scanf(“%d%d“
9、， /输入顶点数和边数for(i=0;in;i+) /读人顶点信息，建立顶点表G-vexsi=getchar();for(i=0;in;i+)for(j=0;jn;j+)G-edgesij=0; /邻接矩阵初始化for(k=0;ke;k+)/读入 e 条边，建立邻接矩阵scanf(“%d%d%d“，/输入边(v i ,v j )上的权 wG-edgesij=w;G-edgesji=w;/CreateMGraph3.3.系统设计系统设计3.1系统功能提供无向图的生成，并保证了该无向图为一个无向网，同时也提供了计算最短距离的迪杰斯特拉算法，以及图的遍历。3.2主要函数说明本系统用了一个类来实现程序，里面包
