数据结构实验报告12

宜宾学院实验报告课程名称数据结构实验名称图院系计算机学院班级16级5班 专业 软件工程学号161105024姓名子墨实验日期第17、18周周五34节实验教室计算机基础实验室五810指导教师阳万安评阅意见一、 实验目的和要求（本次实验所涉及并要求掌握的知识点）掌握图的存储思想及其存储实现；掌握图的深度、广度优先遍历算法思想及其程序实现；掌握图的常见应用算法的思想及其程序实现；理解有向无环图、最短路径等算法。二、 实验内容（本次实验计划安排的实验内容）实现图的矩阵表示和邻接表表示；实现图的矩阵表示和邻接表表示相互转换；实现图的遍历算法；在主函数中输入一组数据，测试算法的正确性。三、 实验环境（本次实验所需要的平台和相关软件）。VC++6.0。四、 实验步骤（针对本次实验计划安排的实验内容写具体实现步骤）打开VC++6.0，新建一个空的Win32控制台工程；添加一个C++资源文件，命名为：expl2.cpp;写入以下代码：/*无向图的邻接矩阵表示法*/#include<stdio.h>#defineINT_MAX1000000#defineINFINITYINT_MAX//最大值无穷#defineMAX_VERTEX_NUM20//最大顶点个数#defineVRTypebool//顶点关系类型bool只取01#defineInfoTypechar#defineVerTexTypechar#defineStatusbool#defineOK1//图的类型定义typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向图，无向网}//弧信息的定义typedefstruetArcCell{VRTypeadj;//顶点关系类型对无权图用1或0表示相邻否；对有权图，则为权值类型InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//图的邻接矩阵的定义typedefstruet{VerTexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和边数GraphKindkind;//图的种类标志}MGraph;//创建无向图StatusCreateUDN(MGraph&G){//采用邻接矩阵表示法，构造无向图printf("请输入图的边数和顶点数\n");scanf("%d%d"，&G.vexnum，&G.arcnum);getchar();//构造顶点向量for(inti=0;i<G.vexnum;++i){printf("请输入第％小个顶点\n",i+1);scanf("%c"，&G.vexs[i]);getchar();}//初始化邻接矩阵for(i=0;i<G.vexnum;++i){for(intj=0;j<G.vexnum;++j){G.arcs[i][j].adj=0;G.arcs[i][j].info二NULL;}}//构造邻接矩阵for(intk=O;k<G.arcnum;++k){intp,q;//输入一条边依附的顶点及权值printf("请输入第%小条边依附的两个顶点，格式如v1v2\n",k+l);scanf("%d%d",&p,&q);G.arcs[p-l][q-l].adj=l;G.arcs[p-l][q-l].info二NULL;G.arcs[q-l][p-l]=G.arcs[p-l][qT];}returnOK;}//输出图的邻接矩阵voidOutput(MGraphG){printf("图的邻接矩阵如下：\n");for(inti=O;i<G.vexnum;++i){for(intj=O;j<G.vexnum;++j){printf("%d",G.arcs[i][j].adj);}printf("\n");}}//主函数测试intmain(void){MGraphG;CreateUDN(G);Output(G);return1;}编译运行测试程序。另建一个新工程，命名为expl2_2;在工程上新建一个c++资源文件，命名为：expl2_2.cpp;写入以下代码：/*无向图的邻接表表示法*/#include<stdio.h>#include<stdlib.h>#defineVexTypechar//顶点数据的类型#defineMAX_VERTEX_NUM100//图的最大顶点数//图的类型typedefenum{DM,DN,UDM,UDN}GraphKind;//边结点类型typedefstruetArcNode{intadjvex;//该边的另一个顶点的位置struetAreNode*nextare;//扌旨向下一条边}ArcNode;//顶点结点类型typedefstruetVNode{VexTypedata;//顶点的值AreNode*firstare;//指向第一条依附该顶点的边的指针}VNode,AdjList[MAX_VERTEX_NUM];//图的存储结构typedefstruet{AdjListvertices;//顶点数组intvexnum,arenum;//图的顶点数和边数GraphKindkind;//图的类型}ALGraph;//定位函数intLoeateVex(ALGraphG,VexTypev){for(inti=0;i<G.vexnum;i++){if(v==G.vertiees[i].data)returni;}return-1;}//创建无向图voidCreateUDG(ALGraph&G){AreNode*p,*q;inti,j,k;VexTypev1,v2;printf("输入顶点个数和边数：\n");seanf("%d%d"，&G.vexnum，&G.arenum);printf("输入各个顶点值(char):\n");getchar();for(i=0;i<G.vexnum;i++){printf("请输入第%小个结点的值\n",i+1);scanf("%c"，&G.vertices[i].data);G.vertices[i].firstare二NULL;//初始化getchar();}printf("输入各条边的两个顶点，格式如：v1v2\n");for(k=0;k<G.arcnum;k++){printf("请输入第%小条边依附的两个顶点\n",k+1);scanf("%c%c",&vl,&v2);getchar();i=LocateVex(G,vl);//定位j=LocateVex(G,v2);//定位//新分配一个结点p=(ArcNode*)malloc(sizeof(ArcNode));//初始化p->adjvex=j;p->nextare二NULL;//连接结点p->nextare二G.vertices[i].firstare;G.vertices[i].firstare二p;//新分配结点q=(ArcNode*)malloc(sizeof(ArcNode));//初始化q->adjvex=i;q->nextare二NULL;//连接结点q->nextare二G.vertices[j].firstare;G.vertices[j].firstare二q;}}//输出邻接表voidOutput(ALGraphG){inti,j;for(i=0;i<G.vexnum;i++){printf("%d:",i);ArcNode*p;p二G.vertices[i].firstare;while(p!=NULL){printf(“->%d",p->adjvex);p=p->nextare;}printf(〃\n〃);}}intmain(void){ALGraphG;CreateUDG(G);Output(G);return1;}编译运行测试程序；另建一个新工程，命名为expl2_3;在其中新建一个C++资源文件，命名为expl2_3.cpp;在expl2.cpp的基础上，添加部分代码如下：宏定义中添加：#defineMAX20新定义一个全局数组：boolvisited[MAX];新加入以下函数(声明在主函数之前)：//在邻接矩阵中获取到第一个邻接点的位置intFirstAdjVex(MGraphG,intv){for(inti=O;i<G.vexnum;v++){if(G.arcs[v][i].adj!=O){returni;}}return-1;}//在邻接矩阵中获取到w后第一个邻接点的位置intNextAdjVex(MGraphG,intv,intw){for(inti二w+1;i<G.vexnum;v++){if(G.arcs[v][i].adj!=O){returni;}}return-1;}//从第v个顶点出发，递归深度优先遍历图GvoidDFS(MGraphG,intv){visited[v]=l;printf("v%d\n",v+l);for(intw二FirstAdjVex(G,v);w>=O;w二NextAdjVex(G,v,w)){if(!visited[w])DFS(G,w);}}//深度优先搜索voidDFSTraverse(MGraphG,intv){for(v=0;v<G.vexnum;v++){visited[v]=0;}for(v=0;v<G.vexnum;v++){if(!visited[v])DFS(G,v);}}主函数中，加入深度优先遍历函数调用语句(return语句之前)：DFSTraverse(G,O);编译运行，测试程序结果的正确性。五、实验过程和结果 (记录实验过程和结果、以及所出现的问题和解决方法)实验结果如下图：邻接矩阵存储：

储结构的特点以及它们之间的差别和相同之处，通过对比，深入理解了什么时候应该使用邻接表存储无向图和什么时候应该用邻接矩阵存储无向图。在实现图的深度优先遍历算法时，没有按照老师所给的范例来完成，而是自己写算法，根据自己对图这种数据结构的理解，去完成的算法，收获颇多。B■D:\161105<i24