公园导游图课程设计.doc

学号:

课程设计
题目
公园导游图
教学院
计算机学院
专业
计算机网络技术
班级
09网络技术(1)
姓名
指导老师
冯珊、熊敬一
2010
年
12
月
30
日

课程设计任务书
2009~2010学年第 1学期
学生姓名: 何雪梅专业班级: 09网络技术
指导教师: 冯姗、熊敬一工作部门: 计算机学院
一、课程设计题目: 公园导游图
二、课程设计内容
给出一张某公园的导游图,游客通过终端询问可知:从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。
三、进度安排
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 }。
图的邻接矩阵表示法
(1)用邻接矩阵表示顶点之间的相邻关系;
(2)用一个顺序表来储存顶点信息
图的邻接矩阵(Adacency Matrix)
设G=(V,E)是具有n个顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵:
若G是网络,则邻接矩阵可定义为:


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

Dijkstra提出按各顶点与源点v间的路径长度的递增次序,生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v 到其它各顶点的最短路径全部求出为止。
3求最小生成树
对于连通的带权图(连通网)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中(例如:u∈U),另一个端点不在U中的边(例如:v∈V-U),且(u,v)具有最小权值,则一定存在G的一棵最小生成树包括此边(u,v)。

1系统流程
本系统主要是实现图的最短路径问题
图2-1


#define MaxVertexNum l00 //最大顶点数,应由用户定义
typedef char VertexType;