图的实验报告.doc

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

1、《数据结构》实验报告题目：图一、实现图的邻接矩阵和邻接表存储（一）需求分析对于下图所示的有向图G，编写一个程序完成如下功能：1．建立G的邻接矩阵并输出之2．由G的邻接矩阵产生邻接表并输出之3．再由2的邻接表产生对应的邻接矩阵并输出之（二）系统设计1、本程序中用到的所有抽象数据类型的定义；typedefstruct{intno;InfoTypeinfo;}VertexType;//顶点类型typedefstruct//图的定义{intedges[MAXV][MAXV];intvexnum,arcnum;VertexTypevexs[MAXV];}MG

2、raph;//图的邻接矩阵类型typedefstructANode//弧的结点结构类型{intadjvex;structANode*nextarc;InfoTypeinfo;}ArcNode;typedefintVertex;typedefstructVnode//邻接表头结点的类型{Vertexdata;ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[MAXV];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;}ALGraph;

3、//图的邻接表类型1、主程序的流程以及各程序模块之间的层次调用关系，函数的调用关系图：Main()DispAdj(G);输出邻接表GDispMat(g);输出邻接矩阵gMatToList(g,G);将邻接矩阵g转换成邻接表G2、列出各个功能模块的主要功能及输入输出参数voidMatToList(MGraphg,ALGraph*&G)将邻接矩阵g转换成邻接表GvoidDispMat(MGraphg)输出邻接矩阵gvoidDispAdj(ALGraph*G)输出邻接表GintOutDegree(ALGraph*G,intv)求图中每个顶点的出度（三）调

4、试分析调试过程中还是出现了一些拼写错误，经检查后都能及时修正。有些是语法设计上的小错误，比如一些参变量的初始值设置错误，使得程序调试出错。在小组讨论分析后纠正了这些结果，并尽量改进了算法的性能，减小时间复杂度。将邻接矩阵g转换成邻接表G，输出邻接矩阵g，输出邻接表G的算法时间复杂度都是O(n^2)。通过这次实验，对图的存储方法有了更深刻的印象。（四）测试结果测试结果：（1）有向图G的邻接矩阵为0104009235800060（2）图G的邻接矩阵转换成的邻接表为：0:131:232:0123:2（五）用户手册不需要输入参数（五）附录源程序#inclu

5、de#include#defineMAXV100//最大顶点个数#defineINF32767//INF表示∞typedefintInfoType;typedefstruct{intno;//顶点编号InfoTypeinfo;//顶点其他信息}VertexType;//顶点类型typedefstruct//图的定义{intedges[MAXV][MAXV];//邻接矩阵intvexnum,arcnum;//顶点数，弧数VertexTypevexs[MAXV];//存放顶点信息}MGraph;//图的邻接矩阵类型

6、typedefstructANode//弧的结点结构类型{intadjvex;//该弧的终点位置structANode*nextarc;//指向下一条弧的指针InfoTypeinfo;//该弧的相关信息,这里用于存放权值}ArcNode;typedefintVertex;typedefstructVnode//邻接表头结点的类型{Vertexdata;//顶点信息ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[MAXV];//AdjList是邻接表类型typedefstruct{AdjList

7、adjlist;//邻接表intn,e;//图中顶点数n和边数e}ALGraph;//图的邻接表类型voidMatToList(MGraphg,ALGraph*&G)//将邻接矩阵g转换成邻接表G{inti,j,n=g.vexnum;//n为顶点数ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;iadjlist[i].firstarc=NULL;for(i=0;i=0;

8、j--)if(g.edges[i][j]!=0)//邻接矩阵的当前元素不为0{p=(ArcNode*)malloc(siz