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

《数据实验报告书 图的应用 最短路径问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告计科111**201100814***《数据结构》实验报告书实验内容：图的应用201100814***计科111***第9页数据结构实验报告计科111**201100814***前言　　　　计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要

2、用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。　　数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。一、实验目的1、使学生可以巩固所学的有关图的基本知识。第9页数据结构实验报告计科111**201100814***2、熟练掌握图的存储结构。3、掌握如何应用图解决各种实际问题。二、实验内容本次

3、实验提供2个题目，学生可以任选一个！本人选了2个实验题目中的第2个题目如下：题目二：最短路径问题[问题描述]　　给定一个无向网，可以求得任意一对顶点之间的最短路径。[基本要求]　以邻接矩阵为存储结构，用迪杰斯特拉算法求解从某一源点到其它顶点之间的最短路径及最短路径长度。[测试数据]　　由学生依据软件工程的测试技术自己确定。三、算法设计1、程序所需头文件已经预处理宏定义如下#include#include#defineINFINITY10000#defineMAX_VERTEX_NUM20typedefstructArcCe

4、ll{intadj;int*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstructDistance{intdistance;}DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{chardata;}VertexType;typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//定义顶点类型AdjMatrixarcs;intvexnum,arcnum;}MGraph;intlocate

5、vex(MGraphG,charv){inti;for(i=0;i>G.vexnum>>G.arcnum;cout<<"请输入各个顶点:";for(i=0;i>

6、G.vexs[i].data;}for(i=0;i>v1>>v2>>weight;i=locatevex(G,v1);j=locatevex(G,v2);G.arcs[i][j].adj=weight;G.arcs

7、[j][i].adj=G.arcs[i][j].adj;}}2、最短路径的处理函数voidShortestPath_FLOYD(MGraphG,DistancMatrix&D)//最短路径处理{intu,v,w;charP[MAX_VERTEX_NUM][MAX_VERTEX_NUM];for(v=0;v