公园导游图课程设计.doc

课 程 设 计
题目
公 园 导 游 图
专业
网络工程
班级
1班
姓名
尹颖
指导老师
孙菁
2014
年
12
月
28
日

课程设计任务书
2014～2015学年第 1学期
学生姓名： 尹颖吴东旭许益强葛溆李永康朱世豪
专业班级： 12网络工程
指导教师： 孙菁
一、课程设计题目: 公园导游图
二、课程设计内容
给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。
三、进度安排
1． 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；
2． 完成最低要求：建立一个文件，包括5个景点情况，能完成遍历功能；
3． 进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。四、基本要求
1. 界面友好，函数功能要划分好
2. 总体设计应画一流程图
3. 程序要加必要的注释
4. 要提供程序测试方案
5. 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
目 录
摘要
1 问题描述 3
、无向图 3
3
图的邻接矩阵表示法 3
4
4
4
5
5
3 系统设计 5
6
主要函数说明 6
6
6
6
4 心得体会 7
附录一：源程序 8
附录三：参考文献 14
摘 要

　　 计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种 运算的算法。


　图的存储方式很多，这里用的是邻接矩阵的方式。为了适合用C语言描述，以下假定顶点序号从0开始，即图G的顶点集的一般形式是V(G)={v 0 ，v i ，…，V n-1 }。
图的邻接矩阵表示法
（１）用邻接矩阵表示顶点之间的相邻关系；
（２）用一个顺序表来储存顶点信息
　图的邻接矩阵(Adacency Matrix)
设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：
若Ｇ是网络，则邻接矩阵可定义为：
　　　

给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

　　Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。
３求最小生成树
对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作：
Te,W(u , v)
　　TE表示T的边集
　　w(u，v)表示边(u，v)的权。
　　权最小的生成树称为G的最小生成树(Minimum Spanning Tree)。最小生成树可简记为MST。
最小生成树性质：
设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中一条“一个端点在U