数据实验报告书 图的应用 最短路径问题.doc

数据结构实验报告 计科111 * 201100814*数据结构实验报告书实验内容：图的应用201100814* 计科111* 前言计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、掌握如何应用图解决各种实际问题。二、实验内容本次实验提供2个题目，学生可以任选一个！本人选了2个实验题目中的第2个题目如下：题目二：最短路径问题问题描述给定一个无向网，可以求得任意一对顶点之间的最短路径。基本要求 以邻接矩阵为存储结构，用迪杰斯特拉算法求解从某一源点到其它顶点之间的最短路径及最短路径长度。测试数据由学生依据软件工程的测试技术自己确定。3、 算法设计1、 程序所需头文件已经预处理宏定义如下#include#include#define INFINITY 10000#define MAX_VERTEX_NUM 20typedef struct ArcCellint adj;int *info;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct Distanceint distance;DistancMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char data;VertexType;typedef struct VertexType vexsMAX_VERTEX_NUM;/定义顶点类型 AdjMatrix arcs; int vexnum,arcnum;MGraph;int locatevex(MGraph G,char v)int i;for(i=0;iG.vexnum;i+)if(G.vexsi.data=v)return i;return -1;2、 生成图G的存储结构函数 void Creatgraph(MGraph &G)/生成图G的存储结构int i,j,k,weight;char v1,v2;cout请输入图的顶点数和边数G.vexnum G.arcnum; cout请输入各个顶点:;for(i=0;iG.vexsi.data;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)if(j=i)G.arcsij.adj=0;elseG.arcsij.adj=INFINITY;G.=NULL;cout请输入两顶点以及它们之间的边的权值：endl;for(k=0;kv1v2weight; i=locatevex(G,v1);j=locatevex(G,v2);G.arcsij.adj=weight; G.arcsji.adj=G.arcsij.adj; 3、 最短路径的处理函数void ShortestPath_FLOYD(MGraph G,DistancMatrix &D)/最短路径处理 int u,v,w; char PMAX_VERTEX_NUMMAX_VERTEX_NUM;for( v=0;vG.vexnum;+v)for( w=0;wG.vexnum;+w) Dvw.distance=G.arcsvw.adj; if(Dvw.distanceINFINITY ) Pvw=G.vexsv.data; else Pvw=-1;int k=0;for( u=0;uG.vexnum;+u)k+;for(v=0;vG.vexnum;+v)for(w=0;wG.vexnum;+w) if(Dvu.distance+Duw.distance)Dvw.distance) Dvw.distance=Dvu.distance+Duw.distance; Pvw=G.vexsu.data; int av, aw;coutavaw;av+;aw+;cout顶点G.vexsav.data与顶点G.vexsaw.data的最短路径长度为 Davaw.distanceendl;cout最佳路径为tG.vexsav.datat;if(Pavaw!=G.vexsav.data)coutPavawt;coutG.vexsaw.dataendl;4、 调试与测试 我们开始测试数据：输入测试数据，如图：输入两点：结果如上图所示。五、总结通过做这次实验，发现自己在数据结构这门课中还有很多不足有很多知识还没掌握，所以在写程序的时候出现了很多的错误，及还有很多的知识不以灵活运用，特别是对图的生成和处理等问题。因为以前C语言没有掌握好，所以这次做本次实验还是有点吃力，刚开始完全没有思，后来经过查找资料，在自己的努力下和同学的帮助下，终于完了本次实验。此次实验发现的自己的不足，我相信在以后的学习中，我会更加的努力。六、源代码#include#include#define INFINITY 10000#define MAX_VERTEX_NUM 20typedef struct ArcCellint adj;int *info;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct Distanceint distance;DistancMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char data;VertexType;typedef struct VertexType vexsMAX_VERTEX_NUM;/定义顶点类型 AdjMatrix arcs; int vexnum,arcnum;MGraph;int locatevex(MGraph G,char v)int i;for(i=0;iG.vexnum;i+)if(G.vexsi.data=v)return i;return -1;void Creatgraph(MGraph &G)/生成图G的存储结构int i,j,k,weight;char v1,v2;cout请输入图的顶点数和边数G.vexnum G.arcnum; cout请输入各个顶点:;for(i=0;iG.vexsi.data;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)if(j=i)G.arcsij.adj=0;elseG.arcsij.adj=INFINITY;G.=NULL;cout请输入两顶点以及它们之间的边的权值：endl;for(k=0;kv1v2weight; i=locatevex(G,v1);j=locatevex(G,v2);G.arcsij.adj=weight; G.arcsji.adj=G.arcsij.adj; void ShortestPath_FLOYD(MGraph G,DistancMatrix &D)/最短路径处理 int u,v,w; char PMAX_VERTEX_NUMMAX_VERTEX_NUM;for( v=0;vG.vexnum;+v)for( w=0;wG.vexnum;+w) Dvw.distance=G.arcsvw.adj; if(Dvw.distanceINFINITY ) Pvw=G.vexsv.data; else Pvw=-1;int k=0;for( u=0;uG.vexnum;+u)k+;for(v=0;vG.vexnum;+v)for(w=0;wG.vexnum;+w) if(Dvu.distance+Duw.distance)Dvw.distance) Dvw.distance=Dvu.distance+Duw.distance; Pvw=G.vexsu.data; int av, aw;coutavaw;av+;aw+;cout顶点G.vexsav.data与顶点G.vexsaw.data的