数据结构——图的程序.doc

数据结构实验报告实验名称: 图的邻接矩阵存储及实现 学号： * 姓名： * 一、实验目的理解图的逻辑结构，掌握图的邻接矩阵存储方式及实现。二、实验内容用邻接矩阵存储方式建立图（无向或有向均可）。并实现以下功能：1. 求某顶点的度。2. 求某顶点的邻接点。3. 两顶点间是否存在边。三、实现思想及步骤描述用数组存储顶点信息，并定义结构体存储数据关系，将元素连接标志置为1，没有连接标志置为0，在for循环的处理过程中对数据的标志进行判断，从而判断元素的度、邻接点等，实现程序的简单操作功能。四、测试数据（画出图的结构）五、程序代码、运行结果# include # include # define maxsize 200typedef struct dataint vertexmaxsize;int arcmaxsizemaxsize;int vertexnum,arcnum;MGraph;void initGraph(MGraph *, int a, int, int);int solve_du(MGraph *,int );bool border(MGraph *,int );bool is_arc(MGraph *,int ,int);int main(void)int sel,amaxsize,n1,n2,i,bn,k,k2,k3,k4,k5;MGraph G;doprintf(n#欢迎进入图操作程序#n-1.图的建立。n-2.求某顶点的度。n-3.求某顶点的邻接点。n-4.两顶点间是否存在边。nn输入您的选择进入相关的功能。n);scanf( %d,&sel);switch(sel)case 1:printf (请输入图的顶点个数：);scanf(%d,&n1); printf (请输入图的边数：);scanf(%d,&n2);printf(请输入顶点编号（从零开始）。n); for(i=0;iarcnum=n2;l-vertexnum=n1;for(i=0;ivertexnum;i+)l-vertexi=ai;for(i=0;ivertexnum;i+)for(j=0;jvertexnum;j+)l-arcij=0;for(j=0;jarcnum;j+)printf(请输入边相接的两个顶点的编号.n);scanf(%d,&k2);scanf(%d,&k1);l-arck2k1=1;l-arck1k2=1;int solve_du(MGraph *l,int bn)int i,cou=0,j;/传入编号bnfor(i=0;ivertexnum;i+)/for(j=0;jvertexnum;j+)if(l-arcibn=1)cou+;return cou;bool border(MGraph *l,int k)int i,t=0;/求某顶点的邻接点for(i=0;ivertexnum;i+)/for(j=0;jvertexnum;j+)if(l-arcik=1)printf(%dt,i);t=1;if(t=1)return true;else return false;bool is_arc(MGraph *l,int d,int v)if(l-arcdv=1)return true;else return false;1. 程序开始界面2. 图建立3. 求某顶点的度4.5. 求某顶点的连接点6. 两顶点是否存在边六、总结与心得（1、分析图的邻接矩阵存储方式的时间性能和空间性能？它适用于那种图？2、在调试程序的过程中遇到什么问题，如何解决的？）图的邻接矩阵存储时间性能为O(n),空间性能为O(n2),适合用于网状的连接比较复杂的图，