数据结构实验-图的基本操作.doc

浙江大学城市学院实验报告课程名称 数据结构 实验项目名称 实验十三/十四 图的基本操作 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 2014/06/09 一. 实验目的和要求1、掌握图的主要存储结构。2、学会对几种常见的图的存储结构进行基本操作。二. 实验内容1、 图的邻接矩阵定义及实现：建立头文件test13_AdjM.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test13.cpp（以下图为例），编译并调试程序，直到正确运行。01246532、图的邻接表的定义及实现：建立头文件test13_AdjL.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test13.cpp中调用这些函数进行验证（以下图为例）。0011223343、填写实验报告，实验报告文件取名为report13.doc。4、上传实验报告文件report13.doc到BB。注: 下载p256_GraphMatrix.cpp(邻接矩阵)和p258_GraphAdjoin.cpp(邻接表)源程序，读懂程序完成空缺部分代码。三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路）四. 实验结果与分析（包括运行结果截图、结果分析等）5. 心得体会程序比较难写，但是可以通过之前的一些程序来找到一些规律（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）【附录-源程序】256:/p-255 图的存储结构以 数组邻接矩阵 表示, 构造图的算法。#include #include #include #include typedef char VertexType; /顶点的名称为字符const int MaxVertexNum=10; /图的最大顶点数const int MaxEdgeNum=100; /边数的最大值typedef int WeightType; /权值的类型const WeightType MaxValue=32767; /权值的无穷大表示typedef VertexType VexlistMaxVertexNum; /顶点信息，定点名称typedef WeightType AdjMatrixMaxVertexNumMaxVertexNum; /邻接矩阵typedef enumDG,DN,AG,AN GraphKind; /有向图,有向网,无向图,无向网typedef struct Vexlist vexs; / 顶点数据元素AdjMatrix arcs; / 二维数组作邻接矩阵int vexnum, arcnum; / 图的当前顶点数和弧数 GraphKind kind; / 图的种类标志 MGraph;void CreateGraph(MGraph &G, GraphKind kd)/ 采用数组邻接矩阵表示法，构造图G/构造有向网G int i,j,k,q;char v, w;G.kind=kd; /图的种类printf(输入要构造的图的顶点数和弧数：n);scanf(%d,%d,&G.vexnum,&G.arcnum);getchar();/过滤回车 printf(依次输入图的顶点名称ABCD.等等：n); for (i=0; iG.vexnum; i+) scanf(%c,&G.vexsi);/构造顶点数据getchar();/过滤回车 for (i=0; iG.vexnum; i+) /邻接矩阵初始化for (j=0; j头顶点名，权值 输入数据:如A-B,23 n);elseprintf(按照： 尾顶点名-头顶点名输入数据:A-Bn); for (k=0; k%c,%d,&v,&w,&q); /输入弧的两个定点及该弧的权重elsescanf(%c-%c,&v,&w);getchar();for(i=0;iG.vexnum; i+) if(G.vexsi=v) break;/查找出v在vexs中的位置i if(i=G.vexnum) cerrvertex ERROR!;exit(1); for(j=0;jG.vexnum; j+) if(G.vexsj=w) break;/查找出v在vexs中的位置j if(j=G.vexnum) cerr头顶点名，权值 输入数据:如A-B,23a-b,5a-c,8c-b,7a-d,4d-c,3输出邻接矩阵 | 5 | 8 | 4 | | | | | | 7 | | | | | 3 | |Press any key to continue*/void PrintMGraph(MGraph &G)int i,j;switch(G.kind) case DG: for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) printf( %2.d | ,G.arcsij); printf(n); break; case DN: for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) if(G.arcsij!=MaxValue) printf( %2.d | ,G.arcsij); else printf( | ); printf(n); break; case AG: for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) printf( %2.d | ,G.arcsij); printf(n); break; case AN: /*完成构造无向网* /* 请模仿编写无向网*/ for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) if(G.arcsij!=MaxValue) printf( %2.d | ,G.arcsij); else printf( | ); printf(n); break; /*完成函数*void countdig(MGraph G) /请完成计算图的入度或初度if(G.kind=DG|G.kind=DN)/计算有向图或网的各个顶点的入度与出度int outD,inD;int i,j;for(i=0;iG.vexnum;i+)outD=inD=0;for(j=0;jG.vexnum;j+)if(G.arcsij!=0&G.arcsij!=MaxValue)outD+;for(j=0;jG.vexnum;j+)if(G.arcsji!=0&G.arcsji!=MaxValue)inD+;printf(%c：出度是%d,入度是%dn,G.vexsi,outD,inD);else/ 计算无向图或网的度int i,j;int Du;for(i=0;iG.vexnum;i+)Du=0;for(j=0;jG.vexnum;j+)if(G.arcsij!=0&G.arcsij!=MaxValue)Du+;printf(%c的度是%dn,G.vexs,Du);/*参照p265设计深度有限搜索*void DFSMatrix(MGraph G,int i,int n,bool*visited) coutG.vexsi ; visitedi=true; for(int j=0;jn;j+) if(G.arcsij!=0&G.arcsij!=MaxValue& !visitedj) DFSMatrix(G,j,n,visited);/*参照p268设计广度有限搜索*void BFSMatrix(MGraph G,int i, int n , bool*visited) const int MaxSize=30; int qMaxSize=0; int front=0,rear=0; coutG.vexsi ; visitedi=true; q+rear=i; while(front!=rear) front=(front+1)%MaxSize; int k=qfront; for(int j=0;jn;j+) if(G.arcsij!=0&G.arcsij!=MaxValue& !visitedj) coutG.vexsj ; visitedj=true; rear=(rear+1)%MaxSize; qrear=j; void main()MGraph G; int k;printf(请选择图的种类：0:有向图,1:有向网,2:无向图,3:无向网. 请选择：);scanf(%d,&k);switch(k) /DG,DN,AG,ANcase 0: printf(构造有向图n);CreateGraph(G,DG); / 采用数组邻接矩阵表示法，构造有向图break;case 1:printf(构造有向网n);CreateGraph(G,DN); / 采用数组邻接矩阵表示法，构造有向网AGGbreak;case 2:printf(构造无向图n);CreateGraph(G,AG); / 采用数组邻接矩阵表示法，构造无向图AGGbreak;case 3:printf(构造无向网n);CreateGraph(G,AN); / 采用数组邻接矩阵表示法，构造无向网AGGbreak;PrintMGraph(G); /打印图的邻接矩阵bool*visited=new boolG.vexnum;int i;cout按图的邻接矩阵得到的深度优先遍历序列endl;for(i=0;iG.vexnum;i+) visitedi=false;DFSMatrix(G,0,G.vexnum,visited);cout按图的邻接矩阵得到的广度优先遍历序列endl;for(i=0;iG.vexnum;i+) visitedi=false;BFSMatrix(G,0,G.vexnum,visited);cout度：头顶点名 输入数据:如A-Ba-ba-ca-dc-bd-c*/ #include #include #include #include typedef char VertexType; /顶点的名称为字符const int MaxVertexNum =10; /图的最大顶点数const int MaxEdgeNum =100; /边数的最大值typedef int WeightType; /权值的类型const WeightType MaxValue =32767; /权值的无穷大表示typedef VertexType Vexlist MaxVertexNum; /顶点信息，定点名称 /邻接矩阵typedef enum DG,DN,AG,AN GraphKind; /有向图,有向网,无向图,无向网struct EdgeNode /链表边结点，表示弧int adjvex; /存放与头结点顶点有关的另一个顶点在邻接表(数组)中的下标。 EdgeNode *next; /指向链表下一个结点WeightType info; / 权重值，或为该弧相关信息;typedef struct VNode /邻接表，表示顶点 VertexType data; / 顶点数据，顶点名称 EdgeNode *firstarc; / 指向边结点链表第一个结点 VNode, AdjListMaxVertexNum;typedef struct AdjList vertices;int vexnum, arcnum; / 图的当前顶点数和弧数 GraphKind kind; / 图的种类标志 ALGraph;void CreateGraph_DG(ALGraph &G)/构造有向图G EdgeNode *p; int i,j,k;char v,w; G.kind=DG; /图的种类printf(输入要构造的有向图的顶点数和弧数：n);scanf(%d,%d,&G.vexnum,&G.arcnum);getchar();/过滤回车 printf(依次输入图的顶点名称ABCD.等等：n); for (i=0; i头顶点名 输入数据:如A-B n);for (k=0; k%c,&v,&w);getchar();for(i=0;iG.vexnum; i+) if(G.verticesi.data=v) break;/查找出v在vertices中的位置i if(i=G.vexnum) cerrvertex ERROR!;exit(1); for(j=0;jG.vexnum; j+) if(G.verticesj.data=w) break;/查找出w在vertices中的位置i if(j=G.vexnum) cerradjvex=j; /置入弧尾顶点号p-info =MaxValue; /图的权值默认为无穷大 p-next=G.verticesi.firstarc; /插入链表G.verticesi.firstarc=p; /void CreateGraph_DN(ALGraph &G)/构造有向网G EdgeNode *p; int i,j,k;char v,w; WeightType q;G.kind=DN; /图的种类printf(输入要构造的有向网的顶点数和弧数：n);scanf(%d,%d,&G.vexnum,&G.arcnum);getchar();/过滤回车 printf(依次输入图的顶点名称ABCD.等等：n); for (i=0; i头顶点名,权值 输入数据:如A-B,8 n);for (k=0; k%c,%d,&v,&w,&q);getchar();for(i=0;iG.vexnum; i+) if(G.verticesi.data=v) break;/查找出v在vertices中的位置i if(i=G.vexnum) cerrvertex ERROR!;exit(1); for(j=0;jG.vexnum; j+) if(G.verticesj.data=w) break;/查找出w在vertices中的位置i if(j=G.vexnum) cerradjvex=j; /置入弧尾顶点号p-info =q; /图的权值默认为无穷大 p-next=G.verticesi.firstarc; /插入链表G.verticesi.firstarc=p; void CreateGraph_AG(ALGraph &G)/构造无向图G EdgeNode *p; int i,j,k;char v,w; G.kind=AG; /图的种类printf(输入要构造的有向图的顶点数和弧数：n);scanf(%d,%d,&G.vexnum,&G.arcnum);getchar();/过滤回车 printf(依次输入图的顶点名称ABCD.等等：n); for (i=0; i头顶点名 输入数据:如A-B n);for (k=0; k%c,&v,&w);getchar();for(i=0;iG.vexnum; i+) if(G.verticesi.data=v) break;/查找出v在vertices中的位置i if(i=G.vexnum) cerrvertex ERROR!;exit(1); for(j=0;jG.vexnum; j+) if(G.verticesj.data=w) break;/查找出w在vertices中的位置i if(j=G.vexnum) cerradjvex=j; /置入弧尾顶点号p-info =MaxValue; /图的权值默认为无穷大 p-next=G.verticesi.firstarc; /插入链表G.verticesi.firstarc=p; /无向图和网的边结点依附于i,j两个顶点,两方均应添加边 p=(EdgeNode *)malloc(sizeof(EdgeNode);/申请弧结点p-adjvex=i; /置入弧尾顶点号p-info =MaxValue; /图的权值默认为无穷大 p-next=G.verticesj.firstarc; /插入链表G.verticesj.firstarc=p; /void CreateGraph_AN(ALGraph &G)/构造无向网GEdgeNode *p; int i,j,k;char v,w; WeightType q;G.kind=AN; /图的种类printf(输入要构造的无向网的顶点数和弧数：n);scanf(%d,%d,&G.vexnum,&G.arcnum);getchar();/过滤回车 printf(依次输入图的顶点名称ABCD.等等：n); for (i=0; iG.vexnum; i+) scanf(%c,&G.verticesi.data);/构造顶点数据G.verticesi.firstarc=NULL; /初始化指向链表指针getchar();/过滤回车printf(按照： 尾顶点名-头顶点名,权值 输入数据:如A-B,8 n);for (k=0; kG.arcnum; k+) scanf(%c-%c,%d,&v,&w,&q);getchar();for(i=0;iG.vexnum; i+) if(G.verticesi.data=v) break;/查找出v在vertices中的位置i if(i=G.vexnum) cerrvertex ERROR!;exit(1); for(j=0;jG.vexnum; j+) if(G.verticesj.data=w) break;/查找出w在vertices中的位置i if(j=G.vexnum) cerradjvex=j; /置入弧尾顶点号p-info =q; /图的权值默认为无穷大 p-next=G.verticesi.firstarc; /插入链表G.verticesi.firstarc=p; /无向图和网的边结点依附于i,j两个顶点,两方均应添加边 p=(EdgeNode *)malloc(sizeof(EdgeNode);/申请弧结点p-adjvex=i; /置入弧尾顶点号p-info =q; /图的权值默认为无穷大 p-next=G.verticesj.firstarc; /插入链表G.verticesj.firstarc=p; void dfsAdjoin(ALGraph G,int i,bool *visited) /深度优先搜索p266couti:G.verticesi.data adjvex;if(visitedj=false)dfsAdjoin(G,j,visited);p=p-next ;void bfsAdjoin(ALGraph G,int i,bool *visited) /广度优先搜索p268const int MSize=30;int qMSize=0;int front=0,rear=0;coutG.verticesi.dataadjvex;if(!visitedj)coutG.verticesj.datanext;/*完成函数*void countdig(ALGraph G) /请完成计算图的入度或初度if(G.kind=DG|G.kind=DN)/计算有向图或网的个顶点的入度与初度int outD,inD;EdgeNode *p,*k;int i,j;for(i=0;inext)outD+;for(j=0;jnext)if(G.verticesk-adjvex.data=G.verticesi.data)inD+;printf(%c：出度是%d,入度是%dn,G.verticesi.data,outD,inD);else/ 计算无向图或网的度int Du;EdgeNode *p,*k;int i,j;for(i=0;inext)Du+;printf(%c：度是%dn,G.verticesi.data,Du); void PrintALGraph(ALGraph &G)/打印邻接表 EdgeNode *p;int i; for (i=0; i,i,G.verticesi.data); else printf(%d | %c ,i,G.verticesi.data); p=G.verticesi.firstarc