【数据结构】图的存储和遍历实验报告

《数据结构B》实验报告系计算机与电子专业级01__班姓名学号2010年10月9日1.上机题目：图的存储和遍历2.详细设计#includestdio.h#defineGRAPHMAX10#defineFALSE0#defineTRUE1#defineerrorprintf#defineQueueSize30typedefstruct{charvexs[GRAPHMAX];intedges[GRAPHMAX][GRAPHMAX];intn,e;}MGraph;intvisited[10];typedefstruct{intfront,rear,count;intdata[QueueSize];}CirQueue;voidInitQueue(CirQueue*Q){Q-front=Q-rear=0;Q-count=0;}intQueueEmpty(CirQueue*Q){returnQ-count=QueueSize;}intQueueFull(CirQueue*Q){returnQ-count==QueueSize;}voidEnQueue(CirQueue*Q,intx){if(QueueFull(Q))error(Queueoverflow);else{Q-count++;Q-data[Q-rear]=x;Q-rear=(Q-rear+1)%QueueSize;}}intDeQueue(CirQueue*Q){inttemp;if(QueueEmpty(Q)){error(Queueunderflow);returnNULL;}else{temp=Q-data[Q-front];Q-count--;Q-front=(Q-front+1)%QueueSize;returntemp;}}voidCreateMGraph(MGraph*G){inti,j,k;charch1,ch2;printf(\n\t\t请输入定点数，边数并按回车（格式如：3，4）：);scanf(%d,%d,&(G-n),&(G-e));for(i=0;iG-n;i++){getchar();printf(\n\t\t请输入第%d个定点数并按回车：,i+1);scanf(%c,&(G-vexs[i]));}for(i=0;iG-n;i++)for(j=0;jG-n;j++)G-edges[i][j]=0;for(k=0;kG-e;k++){getchar();printf(\n\t\t请输入第%d条边的顶点序号（格式如：i,j）：,k+1);scanf(%c,%c,&ch1,&ch2);for(i=0;ch1!=G-vexs[i];i++);for(j=0;ch2!=G-vexs[j];j++);G-edges[i][j]=1;}}voidDFSM(MGraph*G,inti){intj;printf(\n\t\t深度优先遍历序列：%c\n,G-vexs[i]);visited[i]=TRUE;for(j=0;jG-n;j++)if(G-edges[i][j]==1&&visited[j]!=1)////////////////DFSM(G,j);}voidBFSM(MGraph*G,intk){inti,j;CirQueueQ;InitQueue(&Q);printf(\n\t\t广度优先遍历序列：%c\n,G-vexs[k]);visited[k]=TRUE;EnQueue(&Q,k);while(!QueueEmpty(&Q)){i=DeQueue(&Q);for(j=0;jG-n;j++)if(G-edges[i][j]==1&&visited[j]!=1){visited[j]=TRUE;EnQueue(&Q,j);}}}voidDFSTraverseM(MGraph*G){inti;for(i=0;iG-n;i++)visited[i]=FALSE;for(i=0;iG-n;i++)if(!visited[i])DFSM(G,i);}voidBFSTraverseM(MGraph*G){inti;for(i=0;iG-n;i++)visited[i]=FALSE;for(i=0;iG-n;i++)if(!visited[i])BFSM(G,i);}voidmain(){MGraph*G,a;charch1;inti,j,ch2;G=&a;printf(\n\t\t建立一个有向图的邻接矩阵表示\n);CreateMGraph(G);printf(\n\t\t已建立一个有向图的邻接矩阵存储\n);for(i=0;iG-n;i++){printf(\n\t\t);for(j=0;jG-n;j++)printf(%5d,G-edges[i][j]);}getchar();ch1='y';while(ch1=='y'||ch1=='Y'){printf(\n);printf(\n\t\t图的存储与遍历);printf(\n\t\t********************************);printf(\n\t\t*1-----更新邻接矩阵*);printf(\n\t\t*2-----深度优先遍历*);printf(\n\t\t*3-----广度优先遍历*);printf(\n\t\t*0-----退出*);printf(\n\t\t********************************);printf(\n\t\t请选择菜单号（0----3）);scanf(%d,&ch2);getchar();switch(ch2){case1:CreateMGraph(G);printf(\n\t\t图的邻接矩阵存储建立完成\n);break;case2:DFSTraverseM(G);break;case3:BFSTraverseM(G);break;case0:ch1='n';break;default:printf(\n\t\t输出错误！清重新输入！);}}}3.调试分析（1）调试过程中主要遇到哪些问题？是如何解决的？由于实习之初对邻接表的存储结构了解不是很清楚，所以在运行出了一个小错误，即在输出邻接表时，每个结点都少了一个邻接点。通过仔细分析，发现是输出邻接表的语句不对，其中的for（）循环语句中的控制条件：p-next!=NULL出了问题。将其改成p!=NULL后，邻接表便可顺利输出。下面就是经修改后以有向图G1和无向图G2为例的程序运行结果（2）经验和体会：必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的科学态度。我想这不仅是对于程序设计，做任何事都应如此。4.测试结果采用测试数据，列出实际的输入、输出结果。