《数据结构】图的存储和遍历实验实训报告 .doc》由会员分享，可在线阅读，更多相关《数据结构】图的存储和遍历实验实训报告 .doc（12页珍藏版）》请在金锄头文库上搜索。
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 dataQueueS
2、ize;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 De
3、Queue(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请
4、输入第%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);visited
5、i=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 DFSTrave
6、rseM(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已建立一个有向
7、图的邻接矩阵存储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);getcha
8、r();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（）循环语
9、句中的控制条件：p-next!=NULL出了问题。将其改成p!=NULL后，邻接表便可顺利输出。下面就是经修改后以有向图G1和无向图G2为例的程序运行结果（2） 经验和体会：必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的科学态度。我想这不仅是对于程序设计，做任何事都应如此。4. 测试结果采用测试数据，列出实际的输入、输出结果。平时考试注意事项一 以平常心态考试会发挥得更好。紧张时，闭眼，静一静。二 考前不给自己定科目考试分数目标会考得更好。三 审题要
10、仔细要审完关键字要标识能减少失误四 遇到3-4分钟没思路的题可暂时放弃，演算很复杂的题可等容易简单的题做完后再做，切不可在一道题上消耗过多的宝贵时间。五 解题时只专心在本题上会大大提高正确率，一心二用易失误。六 以中等速度解题争取做一题对一题，做对比做完重要一万倍。七 会的题要保证全对，中档题要争取全对，不会的题争取不交白卷。低档题和中档题全做对就能考上一本！八 力争一次做对，不要指望有时间检查和修改。九 整洁清爽的卷面，正确的书写，会赢得改卷老师的欢喜。十 解题时要由易到难，尤其是理综卷可看成是一门课。容易的题先做，拿到了基本分，心踏实了，反而会发挥得更好。十一 解题推演要一步一步地推，跳步
11、骤可能导致失误丢分。十二 草稿纸演算标题号，书写要整齐，以便查错方便。十三 考过的科目不要再去想它，一门心思准备后面的考试。十四 晚上要早点休息，保证以最佳状态参加考试。十五 考试要带的东西要头天晚上准备好，以免遗漏，并放在最瞩目的地方。十六 考试前一天晚上把考试格言认真读一遍。高考和平时考试并无二样，所不同的只是高考内容广泛且综合，囊括了小学，初中，高中所学知识。高考主要考核每个考生十二年来所学知识的全面性，灵活性和解题能力。统计过去历次高考情况，试题难易程度分配率大致排比为3:5:2，即一般难度的大约三成，中等难度的大约占五成，难度大点的所谓提高题约占二成。由此可见，只要能把中等难度以前的
12、分数全都拿到，总分应该稳得600分。如果提高题再能拿到30%应有的分数，那总分就可得640650分了。所以一定要有信心和决心，不要被高考所吓倒。当然对待每道具体试题，还一定要认真细心，不能有丝毫马虎大意才行。接到试卷后不要急着答题，先简略的浏览下卷间的篇幅及夹层面或背面有无试题（防止答漏题）以及试卷的说明和要求（或注意事项）。还要留意答案的相应位置。审题和解题应是同步进行的，每道题在解题前都必须用几秒到几十秒的时间先认真思考一下试题的意义和要解答的问题以及如何去解答。审题要注意试题里关键词和字的意义，特制一些棱模两可的词和字一定要区分清楚。有时一遍弄不懂的就要两遍三遍，知道弄懂题意后再动笔作答。审题要集中思想，专心致志，不要一心挂两头，瞻前顾后，分散精力，打乱思维。思考到那一题就好像全张试卷就只有这么一题。其他试卷题全都不存在似地。总之，思考试题时精力一定要高度集中，千万不可以思考了这一题又惦记着那一题。也不要怕审题耽误时间，常言道磨刀不误砍柴工。题审好答案明朗了，下笔要流利些，顺当些，时间省在里面不说，更重要的是避免了不必要的失分。解题次序应自第一题起向后依次逐题解答。这一题解答结束了才能解答下一题，不能跳（挑）题或选题等乱解一通。这样容易出现答乱题或者在解这一题时大脑还同时想着那一题的混乱现象，最容易出差错。所以
