公园导游图课程设计

《公园导游图课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计（论文）课程设计题目公园导游图专业网络工程班级1班姓名尹颖指导老师孙菁2014年12月28日14课程设计（论文）课程设计任务书2014～2015学年第1学期学生姓名：尹颖吴东旭许益强葛溆李永康朱世豪专业班级：12网络工程指导教师：孙菁一、课程设计题目:公园导游图二、课程设计内容给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。三、进度安排1．初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2．完成最低

2、要求：建立一个文件，包括5个景点情况，能完成遍历功能；3．进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。四、基本要求1.界面友好，函数功能要划分好2.总体设计应画一流程图3.程序要加必要的注释4.要提供程序测试方案5.程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。目录摘要1问题描述31.1图、无向图31.1.1图的存储结构31.1.2图的邻接矩阵表示法31.2算最短路径41.3无向图遍历414课程设计（论文）1.4广度优先搜索42.系统分析52.1系统流程图53系统设计53.1主要

3、数据结构63.2主要函数说明63.3主要算法说明63.3.1数组表示法63.3.2Floyd算法64心得体会7附录一：源程序8附录三：参考文献14摘要　　计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效

4、率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。1.问题描述14课程设计（论文）１.１图的存储结构　图的存储方式很多，这里用的是邻接矩阵的方式。为了适合用C语言描述，以下假定顶点序号从0开始，即图G的顶点集的一般形式是V(G)={v0，vi，…，Vn-1}。1.1.1图的邻接矩阵表示法（１）用邻接矩阵表示顶点之间的相邻关系；（２）用一个顺序表来储存顶点信息1.1.2　图的邻接矩阵(AdacencyMatrix)设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如

5、下性质的n阶方阵：若Ｇ是网络，则邻接矩阵可定义为：　　　１.２求最短路径给定一个带权有向图G=(V,E)，其中每条边的权是一个非负实数。另外，还给定V中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。1.2.1单源最短路径问题　　Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v到其它各顶点的最短路径全部求出为止。１.３求最小生成树14

6、课程设计（论文）对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作：Te,W(u,v)　　TE表示T的边集　　w(u，v)表示边(u，v)的权。　　权最小的生成树称为G的最小生成树(MinimumSpanningTree)。最小生成树可简记为MST。最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中一条“一个端点在U中(例如：u∈U)，另一个端点不在U中的边(例如：v∈V-U)，且(u，v)具有最小权值，则一定存在G的一棵最小生成树包括此边(u，v)。２.系统分析１.

7、１系统流程本系统主要是实现图的最短路径问题14课程设计（论文）图2-12.2系统相关抽象数据类型2.2.1图的邻接矩阵存储结构形式说明#defineMaxVertexNuml00//最大顶点数，应由用户定义typedefcharVertexType;//顶点类型应由用户定义typedefintEdgeType;//边上的权值类型应由用户定义typedefstruct{VextexTypevexs[MaxVertexNum]//顶点表EdeTypeedges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表intn，e

8、;//图中当前的顶点数和边数}MGragh;2.2.2建立无向网络的算法voidCreateMGraph(MGraph*G