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

数据结构B实验报告系 计算机与电子 专业 级 01 _班 姓名学号2010年1 0月 9日1. 上机题目： 图的存储和遍历2. 详细设计#include#define GRAPHMAX 10#define FALSE 0#define TRUE 1#define error printf#define QueueSize 30typedef structchar vexsGRAPHMAX;int edgesGRAPHMAXGRAPHMAX;int n,e;MGraph;int visited10;typedef structint front,rear,count;int dataQueueSize;CirQueue;void InitQueue(CirQueue *Q)Q-front=Q-rear=0;Q-count=0;int QueueEmpty(CirQueue *Q)return Q-count=QueueSize;int QueueFull(CirQueue *Q)return Q-count=QueueSize;void EnQueue(CirQueue *Q,int x)if(QueueFull(Q)error(Queue overflow);elseQ-count+;Q-dataQ-rear=x;Q-rear=(Q-rear+1)%QueueSize;int DeQueue(CirQueue *Q)int temp;if(QueueEmpty(Q)error(Queue underflow);return NULL;elsetemp=Q-dataQ-front; Q-count-;Q-front=(Q-front+1)%QueueSize;return temp;void CreateMGraph(MGraph *G)int i,j,k;char ch1,ch2;printf(ntt请输入定点数，边数并按回车（格式如：3，4）：);scanf(%d,%d,&(G-n),&(G-e);for(i=0;in;i+)getchar();printf(ntt请输入第%d个定点数并按回车：,i+1);scanf(%c,&(G-vexsi);for(i=0;in;i+)for(j=0;jn;j+)G-edgesij=0;for(k=0;ke;k+)getchar();printf(ntt请输入第%d条边的顶点序号（格式如：i,j）：,k+1);scanf(%c,%c,&ch1,&ch2);for(i=0;ch1!=G-vexsi;i+);for(j=0;ch2!=G-vexsj;j+);G-edgesij=1;void DFSM(MGraph *G,int i)int j;printf(ntt深度优先遍历序列： %cn,G-vexsi);visitedi=TRUE;for(j=0;jn;j+)if(G-edgesij=1 & visitedj!=1) /DFSM(G,j);void BFSM(MGraph *G,int k)int i,j;CirQueue Q;InitQueue(&Q);printf(ntt广度优先遍历序列：%cn,G-vexsk);visitedk=TRUE;EnQueue(&Q,k);while(!QueueEmpty(&Q)i=DeQueue(&Q);for(j=0;jn;j+)if(G-edgesij=1 & visitedj!=1)visitedj=TRUE;EnQueue(&Q,j);void DFSTraverseM(MGraph *G) int i;for(i=0;in;i+)visitedi=FALSE;for(i=0;in;i+)if(!visitedi) DFSM(G,i);void BFSTraverseM(MGraph *G) int i;for(i=0;in;i+)visitedi=FALSE;for(i=0;in;i+)if(!visitedi) BFSM(G,i);void main()MGraph *G,a;char ch1;int i,j,ch2;G=&a;printf(ntt建立一个有向图的邻接矩阵表示n);CreateMGraph(G);printf(ntt已建立一个有向图的邻接矩阵存储n);for(i=0;in;i+)printf(ntt);for(j=0;jn;j+)printf(%5d,G-edgesij);getchar();ch1=y;while(ch1=y|ch1=Y)printf(n);printf(ntt 图的存储与遍历);printf(ntt*);printf(ntt* 1-更新邻接矩阵 *);printf(ntt* 2-深度优先遍历 *);printf(ntt* 3-广度优先遍历 *);printf(ntt* 0-退 出 *);printf(ntt*);printf(ntt请选择菜单号（0-3）);scanf(%d,&ch2);getchar();switch(ch2)case 1:CreateMGraph(G);printf(ntt图的邻接矩阵存储建立完成n);break;case 2:DFSTraverseM(G);break;case 3:BFSTraverseM(G);break;case 0:ch1=n;break;default:printf(ntt输出错误！清重新输入！);3. 调试分析（1） 调试过程中主要遇到哪些问题？是如何解决的？ 由于实习之初对邻接表的存储结构了解不是很清楚，所以在运行出了一个小错误，即在输出邻接表时，每个结点都少了一个邻接点。通过仔细分析，发现是输出邻接表的语句不对，其中的for（）循环语句中的控制条件：p-next!=NULL出了问题。将其改成p!=NULL后，邻接表便可顺利输出。下面就是经修改后以有向图G1和无向图G2为例的程序运行结果（2） 经验和体会：必须培养严谨的科学态度。自己在编程时经