2012《数据结构》上机实验报告 .doc

《2012《数据结构》上机实验报告 .doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、西华数学与计算机学院上机实践报告课程名称：数据结构年级：2011上机实践成绩：指导教师：唐剑梅姓名：蒋俊上机实践名称：图学号：1118上机实践日期：2012-12-4上机实践编号：3上机实践时间：8:00-9:30一、实验目的1．熟悉图的两种常用的存储结构，以及在这两种存储结构上的两种遍历图的方法，即深度优先遍历和广度优先遍历。进一步掌握递归算法的设计方法。2．关于各种典型著名的复杂算法，在上机实验方面不做基本要求。更适合于安排大型课程设计。二、实验内容1.设计一个程序，建立有向图的邻接矩阵，进行深度优

2、先遍历，并利用广度优先遍历算法判断有向图中是否存在顶点vi到顶点vj的路径（i≠j）。2.设计一个程序，建立无向图的邻接链表，进行广度优先遍历，并利用深度优先遍历算法判断无向图中是否存在顶点vi到顶点vj的路径（i≠j）。三、实验环境硬件:微型计算机P4软件:WindowsXP+MicrosoftVisualC++6.0四、程序源码及调试过程第一题源代码：1.cpp#include#include#include"3.h"#include"2.h"const

3、intMaxVertices=10;constintMaxWeight=10000;structMinSpanTree//带权边的三个参数{intbegin,end;//边的起点与终点intlength;//边的权值};classAdjMWGraph{private:intVertices[10];//顶点信息的数组intEdge[MaxVertices][MaxVertices];//边的权信息的矩阵intnumE;//当前的边数intnumV;//当前的顶点数public:AdjMWGraph();

4、//构造函数voidCreatG(intn,inte);//建立一个图的邻接矩阵voidDepthF();voidBoradF();voidPrintOut();private:voidBorad(intv,intvisited[]);//广度优先遍历voidDepth(intv,intvisited[]);//深度优先遍历};AdjMWGraph::AdjMWGraph()//构造函数{for(inti=0;i

5、{if(i==j)Edge[i][j]=0;elseEdge[i][j]=MaxWeight;//MaxWeight表示无穷大}numE=0;//当前边个数初始为0numV=0;}voidAdjMWGraph::CreatG(intn,inte){intvi,vj,w,i;numE=e;numV=n;cout<<"输入顶点的信息（整型）：";for(i=0;i>Vertices[i];}for(i=0;i

6、out<<"输入边的信息（vi,vj,W）：";cin>>vi>>vj>>w;Edge[vi-1][vj-1]=w;}}voidAdjMWGraph::Depth(intv,intvisited[])//深度优先遍历{cout<<"顶点"<

7、

8、Edge[v][col]==MaxWeight)continue;if(!visited

9、[col])Depth(col,visited);}}voidAdjMWGraph::DepthF(){intvisit[MaxVertices];for(inti=0;iq;c

10、out<0&&Edge[vi][col]