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

《数据结构》课程实验报告（实验5——图的存储方式和应用）学生姓名

学

号班

级

指导老师实验名称

实验成绩实验报告实验目的：根据图中顶点和边的信息编制程序建立图的邻接矩阵。实验概述实

实验要求：（1）程序要有一定的通用性。（2）直接根据图中每个结点与其他结点的关联情况输入相关信息，程序能自动形成邻接矩阵。实验基本原理：（1）为保证程序的通用性，适合各种图，在建立图的邻接矩阵算法中增加两个参数k1和k2。k1为0表示无向图，否则为有向图；k2为0表示边上无权，否则为边上有权。（2）初始化邻接矩阵时，对角线元素设置为0。若图的边上有权，则其他元素值设为∞；若边上无权，则设为0。程序代码：/*实验4.1建立图的邻接矩阵*/#include<stdio.h>验内容

#defineMaxVertexNum8#defineMaxEdgeNum20#defineMaxValue1000

/*定义图的最大顶点数*//*定义图的最大边数*//*定义相当于∞的常量值*/typedefintVertexType;/*定义顶点数据类型VertexType为整型*/typedefVertexTypevexlist[MaxVertexNum];/*定义vexlist为存储顶点信息的数组类型*/typedefintadjmatrix[MaxVertexNum][MaxVertexNum];/*定义adjmatrix为存储邻接矩阵的数组类型*/voidCreateMatrix(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为有）：");scanf("%d%d",&k1,&k2);CreateMatrix(gv,ga,n,e,k1,k2);/*建立图的邻接矩阵*/printf("\n图的邻接矩阵为：\n\n");ShowMatrix(gv,ga,n);

/*输出图的邻接矩阵*/}/*输入n个顶点和e条边，建立图的邻接矩阵*/voidCreateMatrix(vexlistGV,adjmatrixGA,intn,inte,intk1,intk2){/*k1为0则无向，否则为有向；k2为0则无权，否则为有权*/inti,j,k,w;/*建立顶点数组*/printf("输入%d个顶点数据：",n);for(i=0;i<n;i++)scanf("%d",&GV[i]);/*初始化图的邻接矩阵*/for(i=0;i<n;i++)for(j=0;j<n;j++){if(i==j)GA[i][j]=0;elseif(k2!=0)GA[i][j]=MaxValue;elseGA[i][j]=0;}if(k1==0&&k2==0)

/*建立无向无权图*/{printf("输入%d条无向无权边的起点和终点序号！\n",e);for(k=1;k<=e;k++){scanf("%d%d",&i,&j);GA[i][j]=GA[j][i]=1;}}elseif(k1==0&&k2!=0)/*建立无向有权图*/{printf("输入%d条无向有权边的起点和终点序号及权值！\n",e);for(k=1;k<=e;k++){scanf("%d%d%d",&i,&j,&w);GA[i][j]=GA[j][i]=w;}}elseif(k1!=0&&k2==0)/*建立有向无权图*/{printf("输入%d条有向无权边的起点和终点序号！\n",e);for(k=1;k<=e;k++){scanf("%d%d",&i,&j);GA[i][j]=1;}}elseif(k1!=0&&k2!=0)/*建立有向有权图*/{printf("输入%d条有向有权边的起点和终点序号及权值！\n",e);for(k=1;k<=e;k++){scanf("%d%d%d",&i,&j,&w);GA[i][j]=w;}}}/*输出图的邻接矩阵*/voidShowMatrix(vexlistGV,adjmatrixGA,intn){inti,j;printf("

顶点");for(i=0;i<n;i++)printf("%6d",GV[i]);printf("\n");for(i=0;i<n;i++){printf("%6d",GV[i]);for(j=0;j<n;j++){if(GA[i][j]==MaxValue)printf("%6s","∞");elseprintf("%6d",GA[i][j]);}printf("\n");}}实验结果：测试用例1无向无权图如下图所示。程序运行结果如下：测试用例2有向有权图如下图所示。程序运行结果如下：（1）具有n个顶点的图，其邻接矩阵为