实验3 图的建立与操作

实验3图的建立与操作一、实验目的和要求在熟悉图的存储、遍历、及其应用的基础上，通过键盘输入数据，建立一个无向图的邻接表，输出该邻接表，并计算每个顶点的度。达到巩固图的存储思想及其存储实现。二、实验内容完成下图的邻接表表示，并计算每个顶点的度。附加要求：进行深度优先和广度优先遍历caebfd三、实验提示１．类型定义（邻接表存储）#defineMAX_VERTEX_NUM8//顶点最大个数typedefstructArcNode{intadjvex;structArcNode*nextarc;intweight;//边的权}ArcNode;//表结点#defineVertexTypechar//顶点元素类型typedefstructVNode{intdegree;//顶点的度，入度VertexTypedata;ArcNode*firstarc;}VNode/*头结点*/,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//顶点的实际数，边的实际数}ALGraph;2．实验步骤1）输入图中顶点信息，完成邻接表的VNode内容的初始化。2）根据图中边的信息，把各边的信息链到firstarc指针链上，同时统计degree3）输出邻接表。3.代码#includestdafx.h#includecstdlib#includeiostream#defineWeightMax100#defineUNDRIECT#defineMAXDATA100#defineMAXVEX10//#defineWEIGHTTREE//////////////////////////////////////usingnamespacestd;///////////////////////////////////////////////////////////////////////////////////////typedefcharDataType;structENode{inttailvex,headvex;intweight;structENode*tailnext,*headnext;};structVerNode{DataTypedata;ENode*firstin;ENode*firstout;};//typedefVerNodeAdjList[MAXVEX];structMGraphs{VerNodeadjList[MAXVEX];//ENode*edgeList[MAXVEX][MAXVEX];intnumNode,numEdge;};/////////////////////////////////////////////////////////////////////////intLocateVex(MGraphsG,DataTypedata){inti=0;for(i=0;iG.numNode;++i){if(G.adjList[i].data==data)returni;}return-1;}////////////////////////////////////////////////////thebuildgraph//////////////////////////////oneconstruct//////////////////////voidCreatALGraph(MGraphs&G){intweight;inti,j;DataTypevi,vj;ENode*e;coutpleaseinputthenumNodeandnumEdgeendl;cinG.numNodeG.numEdge;coutpleseinputthenodeinformationendl;for(i=0;iG.numNode;i++){cinG.adjList[i].data;G.adjList[i].firstin=NULL;G.adjList[i].firstout=NULL;}for(intk=0;kG.numEdge;k++){coutpleaseinputthethenodeofedgevi,vj,weightifithasweight;endl;cinvivj;#ifdefWEIGHTREEcinweight;#endifi=LocateVex(G,vi);j=LocateVex(G,vj);e=newENode;e-tailvex=j;e-headvex=i;e-headnext=G.adjList[j].firstin;e-tailnext=G.adjList[i].firstout;#ifdefWEIGHTREEe-weight=weight;#elsee-weight=100;#endifG.adjList[j].firstin=G.adjList[i].firstout=e;//G.edgeList[i][j]=e;}}voidFindInDegree(MGraphsG,int*a){inti=0;intDegCou=0;for(i=0;iMAXDATA;i++){a[i]=0;}for(i=0;iG.numNode;i++){DegCou=0;ENode*e=G.adjList[i].firstin;if((e==NULL))a[i]=0;else{while(!(e==NULL)){DegCou++;e=e-headnext;}e=G.adjList[i].firstout;while(!(e==NULL)){DegCou++;e=e-tailnext;}a[i]=a[i]+DegCou;}}}//////////////////////////////////////////int_tmain(intargc,_TCHAR*argv[]){MGraphsg;CreatALGraph(g);intdegree[MAXDATA]={0};FindInDegree(g,degree);for(inti=0;ig.numNode;i++)coutdegree[i]endl;system(pause);return0;}4.实验结果