1605120107-胡志豪-实验报告07-图的应用一

计算机科学与工程学院《算法与数据结构》实验报告(七)专业班级20XX级计算机XX班实验地点J419机房学生学号指导教师张俊学生姓名实验时间2018-5-22实验项目图的应用一实验类别基础性（）设计性（√）综合性（）其它（）实验目的及要求（1）熟练掌握图的基本存储方法；（2）熟练掌握图的深度优先和广度优先搜索方法；（3）应用DFS和BFS的思想解决常见问题。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明：评阅教师：张俊日期：2018年5月22日计算机科学与工程学院《算法与数据结构》实验报告2实验内容实验内容：图的两种遍历方法及对应的生成树。自己编写源程序，把图的深度优先遍历、广度优先遍历改为输出深度优先生成树、广度优先生成树。实验说明：（1）读懂教师给定的程序或课本的程序；（2）输入图；（3）把显示遍历序列改为显示深度优先、广度优先生成树。#ifndefDIGRPH_H#defineDIGRPH_H#includestdio.h#includemalloc.h#defineMAXV100#defineINF32767typedefcharInfoType;typedefstructANode{intadjvex;structANode*nextarc;intweight;}ArcNode;typedefstructVnode{InfoTypeinfo;ArcNode*firstarc;}VNode;计算机科学与工程学院《算法与数据结构》实验报告3typedefstruct{VNodeadjlist[MAXV];intn,e;}AdjGraph;voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte){inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;in;i++)G-adjlist[i].firstarc=NULL;for(i=0;in;i++)for(j=n-1;j=0;j--)if(A[i][j]!=0&&A[i][j]!=INF){p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-weight=A[i][j];p-nextarc=G-adjlist[i].firstarc;G-adjlist[i].firstarc=p;}计算机科学与工程学院《算法与数据结构》实验报告4G-n=n;G-e=e;}voidDispAdj(AdjGraph*G){inti;ArcNode*p;for(i=0;iG-n;i++){p=G-adjlist[i].firstarc;printf(%3d:,i);while(p!=NULL){printf(%3d[%d]→,p-adjvex,p-weight);p=p-nextarc;}printf(∧\n);}}voidDestroyAdj(AdjGraph*&G){inti;ArcNode*pre,*p;for(i=0;iG-n;i++){计算机科学与工程学院《算法与数据结构》实验报告5pre=G-adjlist[i].firstarc;if(pre!=NULL){p=pre-nextarc;while(p!=NULL){free(pre);pre=p;p=p-nextarc;}free(pre);}}free(G);}voidDFS(AdjGraph*G,intv){ArcNode*p;intw;visited[v]=1;printf(%d,v);p=G-adjlist[v].firstarc;while(p!=NULL)计算机科学与工程学院《算法与数据结构》实验报告6{w=p-adjvex;if(visited[w]==0)DFS(G,w);p=p-nextarc;}}#endif#ifndefSQ_QUEUE#defineSQ_QUEUE#defineMaxSize100typedefstruct{ElemTypedata[MaxSize];intfront,rear;//队首和队尾指针}SqQueue;voidInitQueue(SqQueue*&q){q=(SqQueue*)malloc(sizeof(SqQueue));计算机科学与工程学院《算法与数据结构》实验报告7q-front=q-rear=0;}voidDestroyQueue(SqQueue*&q){free(q);}boolQueueEmpty(SqQueue*q){return(q-front==q-rear);}boolenQueue(SqQueue*&q,ElemTypee){if((q-rear+1)%MaxSize==q-front)//队满上溢出returnfalse;q-rear=(q-rear+1)%MaxSize;q-data[q-rear]=e;returntrue;}booldeQueue(SqQueue*&q,ElemType&e){if(q-front==q-rear)//队空下溢出returnfalse;计算机科学与工程学院《算法与数据结构》实验报告8q-front=(q-front+1)%MaxSize;e=q-data[q-front];returntrue;}#endif//SQ_QUEUE#includedigraph.hintmain(){intA[6][MAXV]={{0,5,0,7,0,0},{0,0,4,0,0,0},{8,0,0,0,0,9},{0,0,5,0,0,6},{3,0,0,0,1,0}};AdjGraph*G;CreateAdj(G,A,6,10);DispAdj(G);DestroyAdj(G);}实验内容计算机科学与工程学院《算法与数据结构》实验报告9实验内容计算机科学与工程学院《算法与数据结构》实验报告10实验总结