数据结构实验---图的储存与遍历

数据结构课程实验报告学号：姓名：实验日期：2016.1.7实验名称：图的存贮与遍历一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。二、实验内容与实验步骤题目1：对以邻接矩阵为存储结构的图进行DFS和BFS遍历问题描述：以邻接矩阵为图的存储结构，实现图的DFS和BFS遍历。基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS和BFS序列。测试数据：如图所示题目2：对以邻接表为存储结构的图进行DFS和BFS遍历问题描述：以邻接表为图的存储结构，实现图的DFS和BFS遍历。基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS和BFS序列。测试数据：如图所示V0V1V2V3V4三、附录：在此贴上调试好的程序。#includestdio.h#includemalloc.h#includestring.hV0V1V4V3V20100000001010101000100010A1∧∧∧010∧3∧3∧4∧#defineM100typedefstructnode{charvex[M][2];intedge[M][M];intn,e;}Graph;intvisited[M];Graph*Create_Graph(){Graph*GA;inti,j,k,w;GA=(Graph*)malloc(sizeof(Graph));printf(请输入矩阵的顶点数和边数(用逗号隔开)：\n);scanf(%d,%d,&GA-n,&GA-e);printf(请输入矩阵顶点信息：\n);for(i=0;iGA-n;i++)scanf(%s,&(GA-vex[i][0]),&(GA-vex[i][1]));for(i=0;iGA-n;i++)for(j=0;jGA-n;j++)GA-edge[i][j]=0;for(k=0;kGA-e;k++){printf(请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开)：,k+1);scanf(%d,%d,%d,&i,&j,&w);GA-edge[i][j]=w;}return(GA);}voiddfs(Graph*GA,intv){inti;printf(%c%c\n,GA-vex[v][0],GA-vex[v][1]);visited[v]=1;for(i=0;iGA-n;i++)if(GA-edge[v][i]==1&&visited[i]==0)dfs(GA,i);}voidtraver(Graph*GA){inti;for(i=0;iGA-n;i++)visited[i]=0;for(i=0;iGA-n;i++)if(visited[i]==0)dfs(GA,i);}voidbfs(Graph*GA,intv){intj,k,front=-1,rear=-1;intQ[M];printf(%c%c\n,GA-vex[v][0],GA-vex[v][1]);visited[v]=1;rear=rear+1;Q[rear]=v;while(front!=rear){front=front+1;k=Q[front];for(j=0;jGA-n;j++)if(GA-edge[k][j]==1&&visited[j]==0){printf(%c%c\n,GA-vex[j][0],GA-vex[j][1]);visited[j]=1;rear=rear+1;Q[rear]=j;}}}voidtraver1(Graph*GA){inti;for(i=0;iGA-n;i++)visited[i]=0;for(i=0;iGA-n;i++)if(visited[i]==0)bfs(GA,i);}typedefstructNODE{intadjvex;structNODE*next;}ENode;typedefstructNODE1{charvex[2];ENode*first;}VexNode;typedefstructFS1{VexNodeGL[M];intbian,top;}FS;FS*CreateGL(){FS*kk=(FS*)malloc(sizeof(FS));inti,j,k;ENode*s;printf(请输入顶点数和边数(用逗号隔开)：\n);scanf(%d,%d,&kk-top,&kk-bian);printf(请输入顶点信息：\n);for(i=0;ikk-top;i++){scanf(%s,kk-GL[i].vex);kk-GL[i].first=NULL;}printf(请输入边的信息(i,j)：\n);for(k=0;kkk-bian;k++){scanf(\n%d,%d,&i,&j);s=(ENode*)malloc(sizeof(ENode));s-adjvex=j;s-next=kk-GL[i].first;kk-GL[i].first=s;}returnkk;}voidDFS(FS*kk,intv){ENode*w;inti;printf(%s\n,kk-GL[v].vex);visited[v]=1;w=kk-GL[v].first;while(w!=NULL){i=w-adjvex;if(visited[i]==0)DFS(kk,i);w=w-next;}}voidTRAVER(FS*kk){inti;for(i=0;ikk-top;i++)visited[i]=0;for(i=0;ikk-top;i++)if(visited[i]==0)DFS(kk,i);}voidBFS(FS*kk,intv){intQ[M],front=-1,rear=-1;ENode*w;inti,k;printf(%s\n,kk-GL[v].vex);visited[v]=1;rear=rear+1;Q[rear]=v;while(front!=rear){front=front+1;k=Q[front];w=kk-GL[k].first;while(w!=NULL){i=w-adjvex;if(visited[i]==0){visited[i]=1;printf(%s,kk-GL[i].vex);rear=rear+1;Q[rear]=i;}w=w-next;}}}voidTRAVER1(FS*kk){inti;for(i=0;ikk-top;i++)visited[i]=0;for(i=0;ikk-top;i++)if(visited[i]==0)BFS(kk,i);}intmain(){inti=0;Graph*p;FS*q;while(i=1){/*建立菜单*/charjz[30]={1.创建邻接矩阵};charjd[30]={2.邻接矩阵DFS遍历};charjb[30]={3.邻接矩阵BFS遍历};charbg[30]={4.创建邻接表};charbd[30]={5.邻接表DFS遍历};charbb[30]={6.邻接表BFS遍历};chartc[30]={7.退出};charmn[30]={菜单};intl=strlen(jd);into=strlen(mn);intm,n;printf(\n);for(m=0;m=(2*l-o)/2;m++)printf();printf(%s,mn);for(m=0;m=(2*l-o)/2;m++)printf();printf(\n);for(m=0;m=2*l;m++)printf(*);printf(\n);printf(*%s*\n*%s*\n*%s*\n*%s*\n*%s*\n*%s*\n*%s*\n,jz,jd,jb,bg,bd,bb,tc);for(m=0;m=2*l;m++)printf(*);printf(\n);/*选择功能*/printf(请输入所需功能序号：);scanf(%d,&n);switch(n){case1:p=Create_Graph();break;case2:traver(p);break;case3:traver1(p);break;case4:q=CreateGL();break;case5:TRAVER(q);break;case6:TRAVER1(q);break;case7:return0;default:printf(输入功能序号有误！\n);}}return0;}四、运行结果：在此把运行结果从屏幕上拷下来贴在此五、心得体会：测试数据要注意现实中矩阵是从1开始，而数组里是从0开始。