数据结构大纲答案6

实验编号：6四川师大《数据结构》实验报告2015年12月25日计算机科学学院2014级1班实验名称：图及其应用姓名：陈元玲学号：2014110105指导老师：刘芳实验成绩：______一.目的要求：（1）通过完成本实验，掌握图的两种基本的存储结构（邻接矩阵、邻接表），以及图的基本算法实现（建立、遍历），并能运用图结构分析解决一些实际问题。（2）本实验训练的要点是：图的两种基本存储结构，及各种操作的算法实现（建立、遍历、图的典型应用）。二.实验内容：（1）建立无向图和有向图的邻接矩阵存储，计算顶点的度，并输出图的基本信息。//1.h#includestdio.h#includeiostream.h#includeiomanip.h#includestring.h#includemalloc.h#includeprocess.h#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineOVERFLOW-1typedefintStatus;//2.h#defineINIFINITY1000//最大值#defineMAX_VERTEX_NUM20//最大顶点数typedefenum{DG,DN,UDG,UDN}GraphKind;//图的四种类型typedefcharVertexType;typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵intvexnum,arcnum;//顶点数和弧的数目GraphKindkind;//图的种类}MGraph;//3.hintLovateVex(MGraphG,VertexTypev){for(inti=0;G.vexs[i]!=v;i++);returni;}StatusCreateUDN(MGraph&G){inti,j,k;VertexTypev1,v2;intw;coutendl输入图的顶点数和边数：;cinG.vexnumG.arcnum;coutendl输入图的顶点信息：;for(i=0;iG.vexnum;i++)cinG.vexs[i];for(i=0;iG.vexnum;i++)for(j=0;jG.vexnum;j++)G.arcs[i][j]=INIFINITY;coutendl输入边的信息v1,v2,wendl;for(k=0;kG.arcnum;k++){cinv1;cinv2;cinw;i=LovateVex(G,v1);j=LovateVex(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=G.arcs[i][j];}//forkreturnOK;}//CreateUDNStatusCreateDN(MGraph&G){inti,j,k;VertexTypev1,v2;intw;coutendl输入图的顶点数和边数：;cinG.vexnumG.arcnum;coutendl输入图的顶点信息：;for(i=0;iG.vexnum;i++)cinG.vexs[i];for(i=0;iG.vexnum;i++)for(j=0;jG.vexnum;j++)G.arcs[i][j]=INIFINITY;coutendl输入边的信息v1,v2,wendl;for(k=0;kG.arcnum;k++){cinv1;cinv2;cinw;i=LovateVex(G,v1);j=LovateVex(G,v2);G.arcs[i][j]=w;}//forkreturnOK;}//CreateDNStatusCreateUDG(MGraph&G){inti,j,k;VertexTypev1,v2;intw;coutendl输入图的顶点数和边数：;cinG.vexnumG.arcnum;coutendl输入图的顶点信息：;for(i=0;iG.vexnum;i++)cinG.vexs[i];for(i=0;iG.vexnum;i++)for(j=0;jG.vexnum;j++)G.arcs[i][j]=0;coutendl输入边的信息v1,v2endl;for(k=0;kG.arcnum;k++){cinv1;cinv2;i=LovateVex(G,v1);j=LovateVex(G,v2);G.arcs[i][j]=1;G.arcs[j][i]=G.arcs[i][j];}//forkreturnOK;}//CreateUDGStatusCreateDG(MGraph&G){inti,j,k;VertexTypev1,v2;intw;coutendl输入图的顶点数和边数：;cinG.vexnumG.arcnum;coutendl输入图的顶点信息：;for(i=0;iG.vexnum;i++)cinG.vexs[i];for(i=0;iG.vexnum;i++)for(j=0;jG.vexnum;j++)G.arcs[i][j]=0;coutendl输入边的信息v1,v2endl;for(k=0;kG.arcnum;k++){cinv1;cinv2;i=LovateVex(G,v1);j=LovateVex(G,v2);G.arcs[i][j]=1;}//forkreturnOK;}//CreateDGStatusCreateGraph(MGraph&G){intkind;coutendl输入图的类型：0-DG,1-DN,2-UDG,3-UDN:endl;cinkind;G.kind=(GraphKind)kind;switch(G.kind){caseDG:returnCreateDG(G);caseDN:returnCreateDN(G);caseUDG:returnCreateUDG(G);caseUDN:returnCreateUDN(G);default:returnERROR;}}//CreateGraphvoidPrintGraph(MGraphG){inti,j;coutendl图的顶点数和边数：;coutsetw(3)G.vexnumsetw(3)G.arcnum;coutendl图的顶点信息：endl;for(i=0;iG.vexnum;i++)coutsetw(3)G.vexs[i];coutendl图的邻接矩阵：endl;for(i=0;iG.vexnum;i++){coutendl;for(j=0;jG.vexnum;j++)if(G.arcs[i][j]==INIFINITY)coutsetw(5)∞;elsecoutsetw(5)G.arcs[i][j];}//foricoutendl;}voidGraphDegree(MGraphG){intindegree[MAX_VERTEX_NUM]={0},outdegree[MAX_VERTEX_NUM]={0};inti;switch(G.kind){caseDN:caseDG:FindIndegree(G,indegree);for(i=0;iG.vexnum;i++)coutendlG.vexs[i]的入度为indegree[i];coutendl;FindOutdegree(G,outdegree);for(i=0;iG.vexnum;i++)coutendlG.vexs[i]的出度为outdegree[i];break;caseUDN:caseUDG:FindOutdegree(G,outdegree);for(i=0;iG.vexnum;i++)coutendlG.vexs[i]的度为outdegree[i];break;}coutendl;}//GraphDegree//main.cpp#include1.h#include2.h#include3.hvoidmain(){MGraphG;CreateGraph(G);//创建图PrintGraph(G);//输出图GraphDegree(G);//计算图中顶点的度，并输出coutendl;}（2）建立有向图的邻接表存储表示，并根据存储计算顶点的出度和入度，然后输出图的基本信息。//1.h#includestdio.h#includeiostream.h#includeiomanip.h#includestring.h#includemalloc.h#includeprocess.h#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineOVERFLOW-1typedefintStatus;//2.h#defineINIFINITY1000//最大值#defineMAX_VERTEX_NUM20//最大顶点数typedefenum{DG,DN,UDG,UDN}GraphKind;//图的四种类型typedefcharVertexType;typedefintInfoType;typedefstructArcNode{intadjvex;InfoTypeweight;structArcNode*nextarc;}ArcNode;typedefstructVnode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;GraphKindkind;}ALGraph;//3.hintLovateVex(ALGraphG,VertexTypev){for(inti=0;G.vertices[i].data!=v;i++);returni;}StatusCreateUDN(ALGraph&G){inti,j,k;VertexTypev1,v2;InfoTypew;ArcNode*p,*q;coutendl输入图的顶点数和边数：;cinG.vexnumG.arcnum;coutendl输入图的顶点信息：;for(i=0;iG.vexnum;i++){cinG.vertices[i].data;G.vertices[i].firstarc=NULL;}coutendl输入边的信息v1,v2,weightendl;for(k=0;kG.arcnum;k++){cinv1;cinv2;cinw;i=LovateVex(G,v1);j=LovateVex(G,v2);p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-weight=w;p-nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;q=(ArcNode*)malloc(sizeof(ArcNode));q-adjvex=i;q-nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=q;}//forkreturnOK;}//CreateUDNStatusCreatDN(ALGragh&G){StatusCreateGraph(ALGraph&G){intkind;coutendl输入图的类型：0-DG,1