国家开放大学《数据结构》课程实验报告(实验5——图的存储方式和应用)参考答案

1、数据结构课程实验报告实验5图的存储方式和应用）学生姓名学号班级指导老师实验名称实验成绩实验报告实验概述实验目的：根据图中顶点和边的信息编制程序建立图的邻接矩阵。实验要求：（1）程序要有一定的通用性。（2）直接根据图中每个结点与其他结点的关联情况输入相关信息，程序能自动形成邻接矩阵。实验基本原理：（1）为保证程序的通用性，适合各种图，在建立图的邻接矩阵算法中增加两个参数k1和k2。k1为0表示无向图，否则为有向图；k2为0表示边上无权，否则为边上有权。（2）初始化邻接矩阵时，对角线元素设置为0。若图的边上有权，则其他元素值设为a；若边上无权，则设为0。实验内容程序代码：/*实验4.1建立图的邻接

2、矩阵*/#include#defineMaxVertexNum8/*定义图的取大顶点数*/#defineMaxEdgeNum20/*定义图的取大边数*/#defineMaxValue1000/*定义相当于的常量值*/typedefintVertexType;/*定义顶点数据类型VertexType为整型*/typedefVertexTypevexlistMaxVertexNum;/*定义vexlist为存储顶点信息的数组类型*/typedefintadjmatrixMaxVertexNumMaxVertexNum;/*定义adjmatrix为存储邻接矩阵的数组类型*/voidCreateMat

3、rix(vexlistGV,adjmatrixGA,intn,inte,intk1,intk2);/*建立图的邻接矩阵*/voidShowMatrix(vexlistGV,adjmatrixGA,intn);/*输出图的邻接矩阵*/voidmain()intn,e,k1,k2;vexlistgv;/*定义保存顶点信息的数组*/adjmatrixga;/*定义保存邻接矩阵的数组*/*输入一个图的顶点数和边数*/printf(”输入待处理图的顶点数和边数：);scanf(%d%d，&n,&e);/*输入有尢向选择和有尢权选择*/printf(输入有无向选择和有无权选择(0为无，非0为有)：);sc

4、anf(”d%d”,&kl,&k2);CreateMatrix(gv,ga,n,e,kl,k2);/*建立图的邻接矩阵*/printf(n图的邻接矩阵为：nn);ShowMatrix(gv,ga,n);/*输出图的邻接矩阵*/*输入n个顶点和e条边，建立图的邻接矩阵*/voidCreateMatrix(vexlistGV,adjmatrixGA,intn,inte,intkl,intk2)/*k1为0则无向，否则为有向；k2为0则无权，否则为有权*/inti,j,k,w;/*建立顶点数组*/printf(”输入d个顶点数据：,n);for(i=0;in;i+)scanf(%d,&GVi);/*

5、初始化图的邻接矩阵*/for(i=0;in;i+)for(j=0;jn;j+)if(i=j)GAij=0;elseif(k2!=0)GAij=MaxValue;elseGAij=0;if(k1=0&k2=0)/*建立无向无权图*/printf(输入d条无向无权边的起点和终点序号！n,e);for(k=1;k=e;k+)scanf(%d%d,&i,&j);GAij=GAji=1;elseif(k1=0&k2!=0)/*建立无向有权图*/printf(输入小条无向有权边的起点和终点序号及权值！n,e);for(k=1;k=e;k+)scanf(%d%d%d,&i,&j,&w);GAij=GAji=

6、w;elseif(kl!=0&k2=0)/*建立有向无权图*/printf(输入小条有向无权边的起点和终点序号！n”,e);for(k=l;k=e;k+)scanf(”d%d”,&i,&j);GAij=l;elseif(k1!=0&k2!=0)/*建立有向有权图*/printf(输入小条有向有权边的起点和终点序号及权值！n,e);for(k=1;k=e;k+)scanf(%d%d%d,&i,&j,&w);GAij=w;/*输出图的邻接矩阵*/voidShowMatrix(vexlistGV,adjmatrixGA,intn)inti,j;printf(”顶点”)；for(i=0;in;i+)p

7、rintf(”6d”,GVi);printf(n);for(i=0;in;i+)printf(”6d”,GVi);for(j=0;jn;j+)if(GAij=MaxValue)printf(”6s”,”Q);elseprintf(”6d”,GAij);printf(n);实验结果：测试用例1无向无权图如下图所示。程序运行结果如下:z*C;kDocuscn-tsandSe-ttiogskAllUserslsy4_1Id2入特处理圈的顶点裟丁选择和有天：点議史：1冋无辗边的起点莉终点序寻!p3IR14dm1囹的邻接矩阵为,4i01topre：asanjjcontinue,11测试用例2有向有权图如下图所示。程序运行结果如下:：/*C:DocuBEiitsandSettingsXllUsersyl_1BlA?条有向育权边的起点和终点序号及衩隹!a1is027P44124Lt39p8154812642t图的邻族矩阵为1顶点123451U1&7842co&4eo003COcoUoo415coCO饰5CO266oc-8Pres-EkeytctcuntiriiLe