淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：图形数据结构实验班级：学号：姓名：评语：成绩：指导教师：批阅时间：年月日《数据结构》实验报告-1-图形数据结构实验报告要求1目的与要求:1）掌握图的邻接矩阵、邻接表、十字链表、邻接多重链表存储结构表示及其创建算法的c语言实现；2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法及C语言实现（预习）；3）掌握AOV-网普里姆构造最小生成树算法的数据结构和算法实现（待学）；4）掌握AOE-网关路经的生成算法和实现（待学）；5）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；6）认真书写实验报告,并按时提交（第12周周一提交）。2实验内容或题目题目：一、图形数据结构实验——图的建立与遍历。内容：1）使用邻接矩阵和邻接表储表示分别实现如下给定的图1和或图2所示图的物理存储结构。2）在1）所建立的图形存储结构上分别实现深度优先搜索遍历和广度优先搜索遍历，并给出遍历结果（序列）。图1无向图V1V2V4V5V3V7V6V8《数据结构》实验报告-2-题目：二、连通网的最小生成树及其应用实验（暂不做）内容：对下图所示通信连通网，按照普里姆算法实现其最小生成树。V1V2V4V5V3V7V6V8例2有向图通信连通网（权值单位：百万元）V1v6v5v4v3V226513566425《数据结构》实验报告-3-3实验步骤与源程序邻接矩阵#include#include#defineMAX_VERTEX_NUM8#defineOK1#defineFALSE0#defineError-1#defineAdjTypeint#defineOtherInfointintvisited[MAX_VERTEX_NUM];#defineTRUE1#defineMAXSIZE6typedefstruct{intelement[MAXSIZE];intfront;intrear;}SeqQueue;typedefenum{DG,DN,UDG,UDN}GraphKind;typedefcharVertexData;typedefstructArcNode{AdjTypeadj;OtherInfoinfo;}ArcNode;typedefstruct{VertexDatavexs[MAX_VERTEX_NUM];ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intvernum,arcnum;GraphKindkind;}AdjMatrix;intLocateVertex(AdjMatrix*G,VertexDatav){intj=Error;intk;for(k=0;kvernum;k++)if(G->vexs[k]==v){j=k;break;}return(j);《数据结构》实验报告-4-}intCreatUDG(AdjMatrix*G){inti,j,k;VertexDatav1,v2;cout<<"输入无向图的顶点数和边数："<>G->vernum;cin>>G->arcnum;for(i=0;ivernum;i++)for(j=0;jvernum;j++)G->arcs[i][j].adj=0;cout<<"输入图的顶点："<vernum;i++){cin>>G->vexs[i];}for(k=0;karcnum;k++){cout<<"输入一条边的两顶点:"<>v1;cin>>v2;i=LocateVertex(G,v1);j=LocateVertex(G,v2);G->arcs[i][j].adj=1;G->arcs[j][i].adj=G->arcs[i][j].adj;}return(OK);}voidPrint(AdjMatrix*G){inti,j;for(i=0;ivernum;i++){for(j=0;jarcnum;j++)cout<arcs[i][j].adj<<"";cout<vexs[v0]<vernum;vi++){if(!visited[vi]&&G->arcs[v0][vi].adj==1)DepthFirstSearch(G,vi);《数据结构》实验报告-5-}}voidInitQueue(SeqQueue*Q){Q->front=Q->rear=0;}intEmpty(SeqQueue*Q){if(Q->front=Q->rear=0)return(TRUE);elsereturn(Error);}intEnterQueue(SeqQueue*Q,intx){if((Q->rear+1)%MAXSIZE==Q->front){cout<<"队已满。"<element[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE;return(TRUE);}intDeleteQueue(SeqQueue*Q,int*x){if(Q->front=Q->rear){cout<<"队空"<element[Q->front];Q->front=(Q->front+1)%MAXSIZE;return(*x);}intFirstAdj(AdjMatrix*G,intv){intj,p=-1;for(j=0;j<=G->vernum;j++)if(G->arcs[v][j].adj==1){p=j;break;}return(p);}《数据结构》实验报告-6-intNextAdj(AdjMatrix*G,intv,intw){intj,p=-1;for(j=w+1;jvernum;j++)if(G->arcs[v][j].adj==1){p=j;break;}return(p);}voidBreadthFirstSearch(AdjMatrix*G,intv0){SeqQueue*Q;Q=(SeqQueue*)malloc(sizeof(SeqQueue));InitQueue(Q);for(...
VIP
