课程设计（论文）--公园导游图

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

1、课程设计（论文）学号：课程设计题目公园导游图教学院计算机学院专业计算机网络技术班级09网络技术（1）姓名指导老师冯珊、熊敬一2010年12月30日15课程设计（论文）课程设计任务书2009～2010学年第1学期学生姓名：何雪梅专业班级：09网络技术指导教师：冯姗、熊敬一工作部门：计算机学院一、课程设计题目:公园导游图二、课程设计内容给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。三、进度安排1．初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个

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

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

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

5、5课程设计（论文）１.２求最短路径给定一个带权有向图G=(V,E)，其中每条边的权是一个非负实数。另外，还给定V中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。1.2.1单源最短路径问题　　Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v到其它各顶点的最短路径全部求出为止。１.３求最小生成树对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称

6、为该树的权，记作：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)。15课程设计（论文）２.系统分析１.１系统流程本系统主要是实现图的最短路径问题图2-12.2系统相关抽象数据类型2.2.1图的邻接矩阵存储

7、结构形式说明#defineMaxVertexNuml00//最大顶点数，应由用户定义typedefcharVertexType;//顶点类型应由用户定义typedefintEdgeType;//边上的权值类型应由用户定义typedefstruct{VextexTypevexs[MaxVertexNum]//顶点表EdeTypeedges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表intn，e;//图中当前的顶点数和边数}MGragh;15课程