数据结构图及其应用C程序及实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
(CFree测试通过)
课程名称 数据结构试验
实验项目名称 图及其应用
(一)实验目的和要求;
了解最短路径的概念,掌握求最短路径的方法
(二)实验主要内容;
建立一个包含6个结点的有向图,并求顶点v到其它的最短路径。 0
(三)主要仪器设备
计算机,VC++高级程序语言
(四)实验原理
图是由结点的有穷集合V和边的集合E组成
求最短路径用迪杰斯特拉算法:
1) 适用条件&范围:
a) 单源最短路径(从源点s到其它所有顶点v);
b) 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图) c) 所有边权非负(任取(i,j)?E都有W?0); ij
2) 算法描述:
a) 初始化:dis[v]=maxint(v?V,v?s); dis[s]=0; pre[s]=s; S={s};
b) For i:=1 to n
1.取V-S中的一顶点u使得dis[u]=min{dis[v]|v?V-S} 2.S=S+{u}
3.For V-S中每个顶点v do Relax(u,v,W) u,v
c) 算法结束:dis[i]为s到i的最短距离;pre[i]为i的前驱节点 (五)实验步骤及调试分析;
首先根据图的基本操作建立图,然后根据迪杰斯特拉算法写出求最短路径算法,最后写出主程序,运行找出错误。在运行过程中,由于建立及求最短路径
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
上可以找到,还是在主程序上有些问题,某些方面感觉无法下手。但是最后还是在汇编程序及同学帮助下得出了正确程序。
(六)实验结果及分析;
试验中以3
顶点代替6
顶点进行试
验 不影响
程序的正确
性,实验结
果如下所示
(七)附
录:源程序
include
#define INFINITY 32767
#define max_vertex_num 20
#define max_name 9
#define FALSE 0
#define TURE 1
typedef int status;
typedef int vrtype;
typedef status pathmatrix[max_vertex_num][max_vertex_num];
typedef vrtype shortpathtable[max_vertex_num];
struct vertextype
{
char name[max_name];
};
enum graphkind{DG,DN,UDG,UDN}; typedef struct arccell
{
vrtype adj;
}arccell,adjmatrix[max_vertex_num][max_vertex_num];
struct mgraph
{
vertextype vexs[max_vertex_num]; adjmatrix arcs;
int vexnum,arcnum;
graphkind kind;
};
int locatevex(mgraph G,vertextype U) {
int i;
for(i=0;i
本文档为【数据结构图及其应用C程序及实验报告(CFree测试通过)】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。