河南工业大学实验报告-实验二 非线性结构(二)-图

PAGEPAGE1河南工业大学实验报告实验目的掌握图的邻接矩阵和邻接链表存储结构。掌握图的建立、遍历、最小生成树等典型操作。二实验内容及要求（自选一题）归遍历操作。实验要求：C源程序须编译调试成功，独立完成。三实验过程及运行结果本次试验是采用邻接表的方法建立图，然后进行深度优先遍历具体实现结如下：//#include<stdio.h>#include<stdlib.h>#defineOK1#defineNULL0 数据结构图的邻接表存储 PAGEPAGE6#defineMAX_VERTEX_NUM20//最大顶点数typedefintStatus; //函数的类型，其值是函数结果状态代码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(ALGraphG,charv){inti;for(i=0;v!=G.vertices[i].data&&i<G.vexnum;i++);if(i>=G.vexnum)return-1;returni;}//构造邻接链表StatusCreateUDN(ALGraph&G){int j;ArcNode*s,*t;printf("输入无向图顶点数:");scanf("%d",&G.vexnum);printf("输入无向图边数:");scanf("%d",&G.arcnum);getchar();for(inti=0;i<G.vexnum;i++){printf("输入第%d个顶点信息:",i+1);scanf("%c",&G.vertices[i].data); //G.vertices[i].firstarc=NULL;getchar();}charv1,v2;for(intk=0;k<G.arcnum;k++){的位置

printf("输入第%d条边依附的顶点v1:",k+1);scanf("%c",&v1);getchar();printf("输入第%d条边依附的顶点v2:",k+1);scanf("%c",&v2);getchar();inti=LocateVex(G,v1);intj=LocateVex(G,v2); //v1,v2Gs=(ArcNode*)malloc(sizeof(ArcNode));t=(ArcNode*)malloc(sizeof(ArcNode));s->adjvex=j; //s->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=s;t->adjvex=i; //t->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=t;}returnOK;}StatusPrintAdjList(ALGraph&G){ArcNode*p;printf("%4s%6s%12s\n","编号","顶点","相邻边编号");for(inti=0;i<G.vexnum;i++){printf("%4d%6c",i,G.vertices[i].data);for(p=G.vertices[i].firstarc;p;p=p->nextarc)printf("%4d",p->adjvex);printf("\n");}returnOK;}intmain(){ALGraphG;CreateUDN(G);PrintAdjList(G);re