中国石油大学数据结构上机实验7

1《数据结构》实验报告学号2015011512姓名胡明禹专业数学与应用数学时间2018.5.22一、实验题目:实验七图的遍历二、实验目的1.掌握图的逻辑结构与基本存储方法；2.掌握有关图的操作算法并用高级语言实现；3.熟练掌握图的两种搜索路径遍历方法。三、算法设计分析实验由8个函数共同组成。其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能voidmain()（2）返回顶点下标函数intLocateVex(MGraph&G,VertexTypech){//返回顶点在G中顶点向量中的下标值inti;for(i=0;G.vexnum;i++)if(ch==G.vexs[i])returni;return-1;}（3）返回第一个未被访问的相邻节点下标函数intFirstAdjVex(MGraph&G,intv){//得到第一个未被访问的相邻节点下标，若无，则返回-1inti;for(i=0;iG.vexnum;i++){if(!visited[i]&&G.arcs[v][i].adj0&&G.arcs[v][i].adjINFINITY)returni;}return-1;}（4）返回v的（相对于w）下一个邻接顶点函数2intNextAdjVex(MGraph&G,intv,intw){//返回v的（相对于w）下一个邻接顶点，若w是v的最后一个邻接顶点，返回空inti;for(i=w;iG.vexnum;i++){if(!visited[i]&&G.arcs[v][i].adj0&&G.arcs[v][i].adjINFINITY)returni;}return-1;}（5）创建有向图的邻接矩阵函数StatusCreateDG(MGraph&G){//创建有向图的邻接矩阵inti,j,k,w;charv1,v2;printf(请输入顶点数和边数：);scanf(%d%d,&G.vexnum,&G.arcnum);visited=(int*)malloc(G.vexnum*sizeof(int));for(i=0;iG.vexnum;i++)visited[i]=0;printf(\n请按次序输入%d个顶点字母标号(如ABCD等)：,G.vexnum);getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键for(i=0;iG.vexnum;i++)scanf(%c,&G.vexs[i]);getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键for(i=0;iG.vexnum;++i)//初始化邻接矩阵for(j=0;jG.vexnum;++j){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}printf(\n输入边的顶点和权值(如AB1):\n);//构造邻接矩阵for(k=0;kG.arcnum;k++){scanf(%c%c%d,&v1,&v2,&w);//输入一条有向边的起点终点和权值i=LocateVex(G,v1);//确定顶点在G中的位置j=LocateVex(G,v2);G.arcs[i][j].adj=w;getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键}returnOK;}3（6）输出邻接矩阵函数StatusPrintArcs(MGraph&G){//输出邻接矩阵inti;intj;printf(邻接矩阵\n);//按行序依次输出for(i=0;iG.vexnum;i++){for(j=0;jG.vexnum;j++){if(INFINITY==G.arcs[i][j].adj)printf(%6s%,INF);elseprintf(%6d,G.arcs[i][j]);}printf(\n);}returnOK;}（7）从某点开始进行深度优先遍历函数StatusDFS(MGraph&G,intv){//从某点开始进行深度优先遍历intw;printf(\n);visited[v]=TRUE;//访问第v个顶点printf(%-4c,G.vexs[v]);for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);//对v尚未访问的邻接顶点w调用递归DFSreturnOK;}（8）菜单函数voidmainmenu()//输出菜单,供用户进行操作选择{printf(\n菜单);printf(\n********************************************\n\n);printf(*1.创建有向图邻接矩阵*\n);printf(*2.输出邻接矩阵*\n);printf(*3.从某点开始的深度优先遍历*\n);printf(*0.退出*\n);printf(\n********************************************\n);4}四、实验测试结果及结果分析（一）测试结果（此处给出程序运行截图）5四、实验程序代码(该部分请加注释)#includestdio.h#includestdlib.h#includemalloc.h#includelimits.h#defineOK1#defineTRUE1#defineINFINITYINT_MAX//最大值无穷#defineMAX_VERTEX_NUM20//最大顶点个数typedefintInfoType;typedefintVRType;typedefcharVertexType;6typedefintStatus;int*visited;//记录顶点是否被访问typedefstructArcCell{VRTypeadj;InfoType*info;//该边相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的顶点数和有向边数}MGraph;intLocateVex(MGraph&G,VertexTypech){//返回顶点在G中顶点向量中的下标值inti;for(i=0;G.vexnum;i++)if(ch==G.vexs[i])returni;return-1;}intFirstAdjVex(MGraph&G,intv){//得到第一个未被访问的相邻节点下标，若无，则返回-1inti;for(i=0;iG.vexnum;i++){if(!visited[i]&&G.arcs[v][i].adj0&&G.arcs[v][i].adjINFINITY)returni;}return-1;}intNextAdjVex(MGraph&G,intv,intw){//返回v的（相对于w）下一个邻接顶点，若w是v的最后一个邻接顶点，返回空7inti;for(i=w;iG.vexnum;i++){if(!visited[i]&&G.arcs[v][i].adj0&&G.arcs[v][i].adjINFINITY)returni;}return-1;}StatusCreateDG(MGraph&G){//创建有向图的邻接矩阵inti,j,k,w;charv1,v2;printf(请输入顶点数和边数：);scanf(%d%d,&G.vexnum,&G.arcnum);visited=(int*)malloc(G.vexnum*sizeof(int));for(i=0;iG.vexnum;i++)visited[i]=0;printf(\n请按次序输入%d个顶点字母标号(如ABCD等)：,G.vexnum);getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键for(i=0;iG.vexnum;i++)scanf(%c,&G.vexs[i]);getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键for(i=0;iG.vexnum;++i)//初始化邻接矩阵for(j=0;jG.vexnum;++j){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}printf(\n输入边的顶点和权值(如AB1):\n);//构造邻接矩阵for(k=0;kG.arcnum;k++){scanf(%c%c%d,&v1,&v2,&w);//输入一条有向边的起点终点和权值i=LocateVex(G,v1);//确定顶点在G中的位置j=LocateVex(G,v2);G.arcs[i][j].adj=w;getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键}8returnOK;}StatusPrintArcs(MGraph&G){//输出邻接矩阵inti;intj;printf(邻接矩阵\n);//按行序依次输出for(i=0;iG.vexnum;i++){for(j=0;jG.vexnum;j++){if(INFINITY==G.arcs[i][j].adj)printf(%6s%,INF);elseprintf(%6d,G.arcs[i][j]);}printf(\n);}returnOK;}StatusDFS(MGraph&G,intv){//从某点开始进行深度优先遍历intw;printf(\n);visited[v]=TRUE;//访问第v个顶点printf(%-4c,G.vexs[v]);for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);//对v尚未访问的邻接顶点w调用递归DFSreturnOK;}voidmainmenu()//输出菜单,供用户进行操作选择{printf(\n菜单);printf(\n********************************************\n\n);printf(*1.创建有向图邻接矩阵*\n);printf(*2.输出邻接矩阵*\n);printf(*3.从某点开始的深度优先遍历*\n);printf(*0.退出*\n);9printf(\n********************************************\n);}voidmain()//主函数{MGraphG;intchoose;intv;while(1){mainmenu();printf(\n请输入你的选择：);scanf(%d,&choose);switch(choose){case1://在此插入创建有向图邻接矩阵函数system(cls);CreateDG(G);system(PAUSE);system(cls);break;case2://在此插入输出邻接矩阵函数system(cls);PrintArcs(G);printf(\n);system(PAUSE);system(cls);break;case3://在此调用从某点开始深度优先遍历函数system(cls);printf(请输入开始结点：);scanf(%d,&v);DFS(G,v);system(PAUSE);system(cls);break;case0://退出exit(0);break;default:10//输入非法，提示用户重新输入printf(\n输入错误，重新输入！\n);}}}