实验七实验报告模版

实验报告课程数据结构实验名称实验七图结构学号08073216姓名顾香兰实验日期：2010-12-13实验七图结构实验目的：1.熟悉图的邻接矩阵（或邻接表）表示；2.掌握建立图的邻接矩阵（或邻接表）存储结构的算法；3.熟悉对图的邻接矩阵（或邻接表）进行深度优先和广度优先搜索算法；4.熟练图的典型著名算法，如图的最小生成树、最短距离等。实验原理：图的邻接矩阵储结构下的基本算法；图的邻接表存储结构下的基本算法；图的典型著名算法，如图的最小生成树、最短距离等。实验内容：8-14、邻接表存储结构图的程序设计。要求：（1）以图8-17为例，设计一个测试8.3.2节讨论的邻接表存储结构下图的操作函数的主函数，并给程序运行的输出结果。（2）设计邻接表存储结构下图的深度优先搜索遍历函数和广度优先遍历搜索函数，并以图8-17为例，编写主函数测试这些函数。（3）编写删除图G中结点v的函数（提示:删除一个结点时要删除所有与该结点有关联的边），并测试该函数的正确性。实验步骤:1）.以图8-17为例，设计一个测试8.3.2节讨论的邻接表存储结构下图的操作函数的主函数，并给程序运行的输出结果。(注：以下程序都基于将书上头文件中GetNextVex操作中的语句:if(v10||v1=G-numOfVerts||v20||v2=G-numOfVerts){printf(参数v1或v2越界出错！);exit(0);}作如下修改实现的:if(v10||v1=G.numOfVerts||v20||v2=G.numOfVerts){return-1;}）#includestdio.h#includestdlib.htypedefcharDataType;#defineMaxSize100#defineMaxVertices100#defineMaxEdges100#includeAdjLG.hintmain(void){AdjLGraphg;DataTypea[6]={'A','B','C','D','E','F'};RowColrc[]={{0,1},{1,3},{1,5},{2,1},{2,5},{3,2},{3,4},{3,5},{4,0},{5,0},{5,4}};intn=6,e=11;inti,j;CreatGraph(&g,a,n,rc,e);for(i=0;ig.numOfVerts;i++){printf(%c,g.a[i].data);printf(%3d%3d%3d,GetFirstVex(g,i),GetNextVex(g,i,GetFirstVex(g,i)),GetNextVex(g,i,GetNextVex(g,i,GetFirstVex(g,i))));printf(\n);printf(\n);}}#includestdio.h#includestdlib.h#includemalloc.h#includestring.htypedefcharDataType;#defineMaxQueueSize100#defineMaxVertices10#includeAdjLG.h#includeDFSBFS.hvoidVisit(DataTypeitem){printf(%c,item);}intmain(void){AdjLGraphg;DataTypea[6]={'A','B','C','D','E','F'};RowColrc[]={{0,1},{1,3},{1,5},{2,1},{2,5},{3,2},{3,4},{3,5},{4,0},{5,0},{5,4}};intn=6,e=11;inti,j;CreatGraph(&g,a,n,rc,e);printf(Thedeepsearcharrayis：);DepthFirstSearch(g,Visit);printf(\nThewidthsearcharrayis：);BroadFirstSearch(g,Visit);}#includestdio.h#includestdlib.htypedefcharDataType;#defineMaxVertices100#includeAdjLG.hvoidDeleteVertex(AdjLGraph*G,intv){inti;Edge*pre,*curr;for(i=0;iG-numOfVerts;i++){if(i==v){curr=G-a[i].adj;while(curr!=NULL){pre=curr-next;free(curr);G-numOfEdges--;curr=pre;}}if(i!=v){pre=NULL;curr=G-a[i].adj;while(curr!=NULL&&curr-dest!=v){pre=curr;curr=curr-next;}if(curr!=NULL&&curr-dest==v&&pre==NULL){G-a[i].adj=curr-next;free(curr);G-numOfEdges--;}elseif(curr!=NULL&&curr-dest==v&&pre!=NULL){pre-next=curr-next;free(curr);G-numOfEdges--;}}for(i=v;iMaxVertices;i++){G-a[i].data=G-a[i+1].data;G-a[i].adj=G-a[i+1].adj;}}}intmain(void){AdjLGraphg;DataTyped;DataTypea[6]={'A','B','C','D','E','F'};RowColrc[]={{0,1},{1,3},{1,5},{2,1},{2,5},{3,2},{3,4},{3,5},{4,0},{5,0},{5,4}};intn=6,e=11;inti,j;CreatGraph(&g,a,n,rc,e);DeleteVertex(&g,2);for(i=0;ig.numOfVerts-1;i++){printf(%c,g.a[i].data);printf(%3d%3d%3d,GetNextVex(g,i,GetNextVex(g,i,GetFirstVex(g,i))),GetNextVex(g,i,GetFirstVex(g,i)),GetFirstVex(g,i));printf(\n);}}实验结果：总结与思考