第5次实验题目与报告书-计算机131-132

淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：图形数据结构实验班级：学号：姓名：评语：评语：成绩：指导教师：批阅时间：年月日《数据结构》实验报告 -PAGE1-图形数据结构实验报告要求1目的与要求:1）掌握图的邻接矩阵、邻接表、十字链表、邻接多重链表存储结构表示及其创建算法的c语言实现；2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法及C语言实现；3）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；4）认真书写实验报告,并按时提交（第12周周三前提交）。2实验内容或题目题目：图形数据结构实验——图的建立与遍历。内容：使用邻接矩阵和邻接表储表示分别实现如下给定的图1和图2所示图的物理存储结构。在1）所建立的图形存储结构上分别实现深度优先搜索遍历和广度优先搜索遍历，并给出遍历结果（序列）。图1无向图1无向图V1V2V4V5V3V7V6V8V1V1V2V4V5V3V7V6V8例2有向图3实验步骤与源程序（学生自己填写）4测试数据与实验结果（可以抓图粘贴）（学生自己填写）5结果分析与实验体会（学生自己填写）2.版面格式：（1）各级标题：黑体，小四，段前/段后：6磅（2）正文内容：宋体、五号，行间距1.25倍；（3）程序代码：宋体、五号，单倍行间距；（4）A4纸，上、下、左、右边距：2厘米注：蓝色字体部分为注释，正式报告中将其删除。举例：使用邻接矩阵创建图形结构有向网邻接矩阵存储结构及其遍历算法的实现参考程序/*头文件#include"stdlib.h"#include"stdio.h"#defineMAX_VERTEX_NUM10/*最多顶点个数*/#defineINFINITY32768/*表示极大值，即∞*/#defineTrue1#defineFalse0#defineError-1#defineOk1typedefenum{DG,DN,UDG,UDN}GraphKind;/*图的种类：DG表示有向图,DN表示有向网,UDG表示无向图,UDN表示无向网*/typedefcharVertexData;/*假设顶点数据为字符型*/typedefstructArcNode{ intadj;/*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/}ArcNode;typedefstruct{ VertexDatavexs[MAX_VERTEX_NUM];/*顶点向量*/ ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接矩阵*/ intvexnum,arcnum;/*图的顶点数和弧数*/ GraphKindkind;/*图的种类标志*/}AdjMatrix;/*(AdjacencyMatrixGraph)*/intLocateVertex(AdjMatrix*G,VertexDatav)/*求顶点位置函数*/{ intj=Error,k; for(k=0;k<G->vexnum;k++) if(G->vexs[k]==v) { j=k; break; } return(j);}头文件结束/创建程序如下intCreateDN(AdjMatrix*G)/*创建一个有向网*/{ inti,j,k,weight; VertexDatav1,v2; printf("输入图的弧数和顶点数\n"); fflush(stdin);scanf("%d,%d",&G->arcnum,&G->vexnum);/*输入图的顶点数和弧数*/for(i=0;i<G->vexnum;i++)/*初始化邻接矩阵*/ for(j=0;j<G->vexnum;j++) G->arcs[i][j].adj=INFINITY;for(i=0;i<G->vexnum;i++)//输入顶点字符循环 {printf("输入图的顶点\n"); fflush(stdin); scanf("%c",&G->vexs[i]);/*输入图的顶点*/ } for(k=0;k<G->arcnum;k++) { printf("输入一条弧的两个顶点及权值\n"); fflush(stdin); scanf("%c,%c,%d",&v1,&v2,&weight);/*输入一条弧的两个顶点及权值*/ i=LocateVertex(G,v1); j=LocateVertex(G,v2); G->arcs[i][j].adj=weight;/*建立弧*/ } return(Ok);}//深度优先搜索遍历图—邻接矩阵voidDepth1(AdjMatrixg1,intvo){ intvj; printf("%c",g1.vexs[vo]); visited[vo]=True; for(vj=0;vj<g1.vexnum1;vj++) if((!visited[vj])&&(g1.arcs[vo][vj].adj==1)) Depth1(g1,vj);}//广度优先搜索算法，注意算法中直接使用了队列数据结构voidBreadth1(AdjMatrixg1,intvo){ intvi,vj; LinkQueueQ; InitQueue(&Q); visited[vo]=True; EnterQueue(&Q,vo); while(!IsEmpty(&Q)) { DeleteQueue(&Q,&vi); printf("%c",g1.vexs[vi]); for(vj=0;vj<g1.vexnum1;vj++) if((!visited[vj])&&(g1.arcs[vi][vj].adj==1)) { visited[vj]=True; EnterQueue(&Q,vj); } }}voidTraverse1(AdjMatrixg1)//邻接矩阵存储结构的深度和广度优先搜索遍历{ intvi; for(vi=0;vi<g1.vexnum1;vi++)//深度遍历邻接矩阵 visited[vi]=False; printf("\nTheorderofG1Depth\n"); for(vi=0;vi<g1.vexnum1;vi++) { if(!visited[vi]) { Depth1(g1,vi); printf("\n"); } }//广度优先搜索遍历——邻接矩阵 for(vi=0;vi<g1.vexnum1;vi++) visited[vi]=False; printf("\nTheorderofG1Breadth\n"); for(vi=0;vi<g1.vexnum1;vi++) { if(!visited[vi]) { Breadth1(g1,vi); printf("\n"); } }}voidmain(){ AdjMatrixG; CreateDN(&G);}//邻接表存储结构与其上遍历算法的实现请参考教材先关算法邻接表创建/*邻接表存储结构的形式化说明如下-头文件：*/#defineINFINITY32768/*表示极大值，即∞*/#defineTrue1#defineFalse0#defineError-1#defineNULL0#defineOk1#defineMAX_VERTEX_NUM20/*最多顶点个数*/typedefenum{DG,DN,UDG,UDN}GraphKind;/*图的种类*/typedefcharVertexNode;typedefstructArcNode{ intadjvex;/*该弧指向顶点的位置*/ structArcNode*nextarc;/*指向下一条弧的指针*/ OtherInfoinfo;/*与该弧相关的信息*/}ArcNode;typedefstructVertexNode{ VertexDatadata;/*顶点数据*/ ArcNode*firstarc;/*指向该顶点第一条弧的指针*/}VertexNode;typedefstruct{VertexNodevertex[MAX_VERTEX_NUM];intvexnum,arcnum;/*图的顶点数和弧数*/GraphKindkind;/*图的种类标志*/}AdjList;/*基于邻接表的图(AdjacencyListGraph)*//**/typedefstructArcNode2{ intadjvex; structArcNode2*nextarc;}ArcNode2;typedefstructVertexNode{ VertexDatadata; ArcNode2*firstarc;}VertexNode;typedefstruct{ VertexNodevertex[N]; intvexnum2,arcnum2; GraphKindkind2;}AdjList;/**/typedefstructnode1{ chardata; structnode1*next;}Node1,*LinkList1;typedefstructnode2{ chardata1; chardata2; structnode2*next;}Node2,*LinkList2;//创建程序intCreateUDG2(AdjList*G2,LinkList1L,LinkList2M){ inti,j,k; //charch; Node1*m,*t; Node2*n,*s; ArcNode2*p,*r; VertexDatav1,v2; G2->vexnum2=a[0];G2->arcnum2=a[1]; for(i=0;i<G2->vexnum2;i++) { m=L->next; t=m; G2->vertex[i].data=t->data; L->next=L->next->next; free(m); G2->vertex[i].firstarc=NULL; } for(k=0;k<G2->arcnum2;k++) { s=M->next; n=s; v1=n->data1; v2=n->data2; M->next=M->next->next; free(s); i=LocateVertex2(G2,v1); j=LocateVertex2(G2,v2); if(G2->vertex[i].firstarc==NULL) { p=(ArcNode2*)malloc(sizeof(ArcNode2)); if(p==NULL) return(False); G2->vertex[i].firstarc=p; p->adjvex=j; p->nextarc=NULL; } else { r=G2->vertex[i].firstarc; while(r->nextarc!=NULL) r=r->nextarc; p=(ArcNode2*)malloc(sizeof(ArcNode2)); if(p==NULL) return(False); r->nextarc=p; p->adjvex=j; p->nextarc=NULL; } if(G2->vertex[j].firstarc==NULL) { p=(ArcNode2*)malloc(sizeof(ArcNode2)); if(p==NULL) return(Fals