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

《【数据结构】图的存储和遍历实验报告》由会员分享，可在线阅读，更多相关《【数据结构】图的存储和遍历实验报告（8页珍藏版）》请在金锄头文库上搜索。

1、数据结构 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 data

2、QueueSize;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);else Q-count+;Q-dataQ-rear=x;Q-rear=(Q-rear+1)%QueueSize

3、;int DeQueue(CirQueue *Q)int temp;if(QueueEmpty(Q) error(Queue underflow);return NULL;else temp=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,for(i=0;in;i+) getchar();printf(ntt 请输入

4、第 %d 个定点数并按回车：,i+1);scanf(%c,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,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

5、;j+)if(G-edgesij=1 & visitedj!=1) /DFSM(G,j);void BFSM(MGraph *G,int k) int i,j;CirQueue Q;InitQueue(printf(ntt 广度优先遍历序列： %cn,G-vexsk);visitedk=TRUE;EnQueue(while(!QueueEmpty(&Q) i=DeQueue(for(j=0;jn;j+)if(G-edgesij=1 & visitedj!=1) visitedj=TRUE;EnQueue(void DFSTraverseM(MGraph *G) int i;for(i=0;in

6、;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=printf(ntt 建立一个有向图的邻接矩阵表示 n);CreateMGraph(G);printf(ntt 已建立一个有向图的邻接矩阵存储 n);for(i=0;in;i+) print

7、f(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,getchar();switch(ch2)case 1:CreateMGra

8、ph(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） 经验和体会：必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的科学态度。我想这不仅是对于程序设计，做任何事都应如此。4. 测试结果采用测试数据，列出实际的输入、输出结果。