数据结构与算法实验3

任课教师：《数据结构与算法》（2011-2012学年第2学期）实验报告学号：姓名：班级：实验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）输出邻接表。四、程序源码：#includeiostreamusingnamespacestd;#includestdio.h#includestdlib.h#defineOK1#defineNULL0#defineMAX_VERTEX_NUM20//最大顶点数typedefcharVertexType;typedefintVRType;typedefintInforType;typedefstructArcNode{intadjvex;//该边所指的顶点的位置structArcNode*nextarc;//指向下一条边的指针intweight;//边的权}ArcNode;//表的结点typedefstructVNode{VertexTypedata;//顶点信息（如数据等）ArcNode*firstarc;//指向第一条依附该顶点的边的弧指针}VNode,AdjList[MAX_VERTEX_NUM];//头结点typedefstructALGraph{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;//返回顶点v在顶点向量中的位置intLocateVex(ALGraph&G,charv){inti;for(i=0;v!=G.vertices[i].data&&iG.vexnum;i++);if(i=G.vexnum)return-1;returni;}//增加节点voidadd_vex(ALGraph&G){cout输入无向图顶点数:endl;cinG.vexnum;//getchar();//吃回车cout输入顶点信息:endl;for(inti=0;iG.vexnum;i++){cinG.vertices[i].data;//构造顶点向量G.vertices[i].firstarc=NULL;//getchar();}}//增加边voidadd_arc(ALGraph&G){ArcNode*s,*t;cout输入无向图边数:endl;cinG.arcnum;charv1,v2;cout输入边信息:endl;for(intk=0;kG.arcnum;k++){cinv1v2;inti=LocateVex(G,v1);intj=LocateVex(G,v2);//确定v1,v2在G中的位置s=(ArcNode*)malloc(sizeof(ArcNode));t=(ArcNode*)malloc(sizeof(ArcNode));s-adjvex=j;//该边所指向的顶点的位置为js-nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=s;t-adjvex=i;//该边所指向的顶点的位置为jt-nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=t;}}//构造邻接链表voidCreateUDN(ALGraph&G){add_vex(G);//增加节点add_arc(G);//增加边}voidPrintAdjList(ALGraph&G){inti;ArcNode*p;cout编号顶点邻点编号endl;for(i=0;iG.vexnum;i++){coutiG.vertices[i].data;for(p=G.vertices[i].firstarc;p;p=p-nextarc)coutp-adjvex;coutendl;}}intmain(){ALGraphG;CreateUDN(G);PrintAdjList(G);return0;}五、运行结果与测试分析：六、实验心得与体会：