数据结构图及其应用实验报告+代码

1、 顶点为：a,b,顶点为：a,b,c,d,e弧及其权值为:a,b,2a,c,3b,d,4b,e,2d,e,1结果如下:1图的创建，先输入顶点个数与边数，如图4.1.1,接着输入各顶点的值，如图4.1.2,最后输入三条边依附的顶点以及权值，当输入的顶点不在图中时，会提示重新输入，如图4.1.3图4.1.1图4.1.2图4.1.32图的矩阵输出，如图4.2图的邻接矩阵输出如下；a.bcdeaoo23cocob2coCO42G3cocococodco4CQCQ1eQO2CO1co图4.23深度优先遍历图，输出序列，如图4.3图4.34广度优先遍历图，输出序列，如图4.4图4.4六、总结与体会图，是一

2、种较线性表和树更为复杂的数据结构将其用深度遍历后，可以变成一棵树，或者一个森林。和树的遍历相类似，都利用了递归的方法，逐个搜索输出。用邻接矩阵表示图，形象地体现出顶点与顶点之间的紧密关系。七、程序清单（包含注释）#includestdio.h#includelimits.hINT_MAX头文件#includewindows.h/boolean头文件#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20#defineOVERFLOW-1#defineOK1#defineERROR0typedefintStatus;typedefenumDG,DN,UDG,UD

3、NGraphKind;typedefintVRType;typedefcharVertexType;typedefchar*InfoType;typedefintQElemType;/边信息typedefstructArcCellVRTypeadj;/1或0表示是否邻接,对带权图，则为权值类型InfoType*info;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/图结构typedefstruct/邻接矩阵，为一二维数组/邻接矩阵，为一二维数组/图的当前顶点数和弧数/图的种类标志AdjMatrixarcs;intvexnum,arcnum;Gra

4、phKindkind;MGraph;/辅助队列typedefstructQNodeQElemTypedata;/数值域structQNode*next;/指针域QNode,*QueuePtr;typedefstructQueuePtrfront;/队头QueuePtrrear;/队尾LinkQueue;/初始化队列StatusInitQueue(LinkQueue&Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)printf(内存分配失败!)；exit(OVERFLOW);Q.front-next=NULL；returnO

5、K；/插入元素到队尾StatusEnQueue(LinkQueue&Q,QElemTypee)QueuePtrp=(QueuePtr)malloc(sizeof(QNode)；if(!p)printf(n内存分配失败!)；exit(OVERFLOW)；p-data=e；p-next=NULL；Q.rear-next=p;Q.rear=p;returnOK;/队列判空StatusQueueEmpty(LinkQueueQ)returnQ.front=Q.rear;/销毁队列StatusDestroyQueue(LinkQueue&Q)while(Q.front)Q.rear=Q.front-ne

6、xt;free(Q.front);Q.front=Q.rear;returnOK;/删除队头元素StatusDeQueue(LinkQueue&Q,QElemType&e)if(QueueEmpty(Q)printf(n队列为空！);returnERROR;QueuePtrp=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);returnOK;对顶点V定位，返回该顶点在数组的下标索引，若找不到则返回-1intLocateVex(MGraphG,charv)for(inti=0;iMAX_VE

7、RTEX_NUM)printf(最大顶点为20,重新输入(如：4,3):);scanf(%d,%d,&G.vexnum,&G.arcnum);printf(n依次输入顶点向量值n);inti;for(i=0;iG.vexnum;i+)/清空缓冲区fflush(stdin);printf(第d(:,i+1);scanf(%c,&G.vexsi);/初始化邻接矩阵for(i=0;iG.vexnum;i+)for(intj=0;jG.vexnum;j+)G.arcsij.adj=INFINITY;G.=NULL;charfront,rear;intvalues;printf(n

8、输入依附两个顶点的边及其权值n);for(i=0;iG.arcnum;i+)printf(第4条：,i+1);/清空缓冲区fflush(stdin);scanf(%c,%c,%d,&rear,&front,&values);intm,n;定位两顶点在vexs数组中的索引m=LocateVex(G,rear);n=LocateVex(G,front);if(m=-1|n=-1)printf(输入顶点或不在此图中，请重新输入！n);i-;continue;/赋予对应矩阵位置的权值，以及对称弧的权值G.arcsmn.adj=values;G.arcsnm.adj=values;returnOK;/C

9、reateUDG/矩阵输出voidprintArcs(MGraphG)inti;printf();/输出第一行的顶点向量for(i=0;iG.vexnum;i+)printf(%c,G.vexsi);for(i=0;iG.vexnum;i+)printf(nn%c,G.vexsi);for(intj=0;jG.vexnum;j+)if(G.arcsij.adj=INFINITY)printf(”);elseprintf(%d,G.arcsij.adj);printf(n);/访问顶点v输出StatusprintAdjVex(MGraphG,intv)printf(%c,G.vexsv);ret

10、urnOK;/查找v顶点的第一个邻接点StatusFirstAdjVex(MGraphG,intv)查找与顶点v的第一个邻接点，找到后立即返回其索引，若找不到，则返回-1for(inti=1;iG.vexnum;i+)if(G.arcsvi.adj!=INFINITY)returni;return-1;查找基于V顶点的w邻接点的下一个邻接点StatusNextAdjVex(MGraphG,intv,intw)/查找基于顶点v的w邻接点的下一个邻接点，找到之后立即返回其索引，若找不到，则返回-1for(inti=w+1;i=0;w=NextAdjVex(G,v,w)if(!visitedw)DF

11、S(G,w);/深度优先遍历voidDFSTraverse(MGraphG,Status(*Visit)(MGraphG,intv)将函数复制给全局的函数指针变量，待调用DFS时使用VisitFunc=Visit;intv;/将访问标记初始化为falsefor(v=0;vG.vexnum;v+)visitedv=false;for(v=0;vG.vexnum;v+)/对尚未访问即访问标记为false的顶点调用DFSif(!visitedv)DFS(G,v);/广度优先遍历voidBFSTraverse(MGraphG,Status(*Visit)(MGraphG,intv)按广度优先非递归遍历图G，使用辅助队列Q和访问标志数组Visitedintv;intu;将访问标记数组初始化为falsefor(v=0;vG.vexnum;v+)visitedv=FALSE;/创建辅助队列QLinkQueueQ;InitQueue(Q);for(v=0;v=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;Visit(G,w);EnQueue(Q,w);/销毁队列DestroyQueue(Q);voidmain()printf(“=图的创建及其应用=n);/创建一个图MGraph