数据结构实验三图的创建与访问算法的设计

1、实验室名称：信息工程学院机房内蒙古工业大学信息工程学院实验报告课程名称实验名称实验类型数据结构与算法图的创建与访问算法的设计验证性口综合性口设计性内蒙古工业大学信息工程学院实验三图的创建与访问算法的设计一、目的本实验的目的是通过理解图的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。二、题目图的创建与访问算法的设计三、实验类型设计性。本实验设计了图的创建与访问算法。四、要求及提示说明：以下4个题中，任意选作一题。2、【问题描述】设有六个比赛项目，规定每个选手至多可参加四个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。姓名项目1项目2项目

2、3项目4张一跳咼100米200米跳远王二铅球跳咼200米李三标枪跳远马四100米200米跳咼董六铅球标枪【基本要求】实现以下基本操作：（1）建立图。（2）输出比赛日程表。（3）对所建的图进行广度优先遍历，输出广度优先遍历序列解法分析：（1）设用如下六个不同的代号代表不同的项目：跳咼跳远标枪铅球100米200米ABCDEF姓名项目1项目2项目3项目4张一AEFB王二DAF李三CB马四EFA董六DC2）用顶点代表比赛项目，不能同时进行比赛的项目之间连上一条边。3）某选手比赛的项目必定有边相连（不能同时比赛）。作如下无向图：V6E5E9E6E2V5E8ElE3E4比赛时间第一种第二种第三种单位时间1

3、ACDEDF单位时间2BDCFCE单位时间3EAB单位时间4FBAV4D找到图中未邻接的点为一组从上表可以看出：只需安排四个单位时间进行比赛（各组项目顺序可交换）。源代码：#include#include#defineM40/表结点typedefstructArcNodeintadjvex;structArcNode*next;ArcNode;/*表结点结构*/*存放与头结点相邻接的顶点在数组中的序号*/*指向与头结点相邻接的下一个顶点的表结点*/头结点typedefstructVerNodecharvertexM;charv;structVerNode*link;点*/VerNode;/*存

4、放图中顶点的具体信息*/*存放图中顶点的信息字母代表*/*指针指向对应的单链表中的表结点，即指向顶点的第一个邻接typedefstructVerNodeadjlistM;/*邻接链表表头数组,adjlist0不用*/intvexnum,arcnum;intkind;ALGraph;/*顶点数和边数*/*图的类型*/ALGraphadjg;voidcreate_ALGraph()ArcNode*p;inti,v,v1,e,v2;adjg.kind=2;/*无向图*/printf(nt输入顶点数:)scanf(%d,&v);printf(t输入边数:)；scanf(%d,&e);fflush(st

5、din);adjg.vexnum=v;adjg.arcnum=e;printf(nn);/头结点赋值为各顶点值for(i=1;i=v;i+)/*存放顶点数在adjg.vexnum中*/*存放边点数在adjg.arcnum中*/*i从1开始，adjlist0不用*/printf(输入顶点%d的值(字母，比赛项目)：，i)；scanf(%c,%s,&adjg.adjlisti.v,adjg.adjlisti.vertex);/*输入顶点的信息*/fflush(stdin);adjg.adjlisti.link=NULL;printf(nn);/链接各个表结点for(i=1;i=adjg.arcnu

6、m;i+)printf(输入第%d条边的起始点和终止点(x,x):,i);scanf(%d,%d,&v1,&v2);/*输入边的起始顶点和终止顶点在数组中的编号*/fflush(stdin);while(v1adjg.vexnum|v2adjg.vexnum)printf(输入错误，重新输入：)；scanf(%d,%d,&v1,&v2);fflush(stdin);p=malloc(sizeof(ArcNode);/*建立一个和边相关的结点*/p-adjvex=v2;p-next=adjg.adjlistv1.link;/*头插法挂到对应的单链表上*/adjg.adjlistv1.link=p

7、;p=malloc(sizeof(ArcNode);/*建立另一个和边相关的结点*/p-adjvex=v1;p-next=adjg.adjlistv2.link;/*头插法挂到对应的单链表上*/adjg.adjlistv2.link=p;return;/广度遍历voidtraver(intn)inti;staticintvisitedM;/标志数组for(i=1;i=n;i+)visitedi=0;for(i=1;i=n;i+)if(visitedi=0)bfs(i,visited);voidbfs(intv,intvisited)intquM,f=0,r=0;ArcNode*p;printf

8、(%s,adjg.adjlistv.vertex);visitedv=1;qu0=v;r+;/入队while(fadjvex;if(visitedv=0)visitedv=1;printf(%s,adjg.adjlistv.vertex);qu+r=v;p=p-next;printf(nn);广度遍历：AEFDBC/比赛时间安排voidtimetable()ArcNode*p;inti,j,k=0,FM;for(i=1;i=adjgvexnum;i+)Fi=0;/0表示该点未使用过for(j=1;j=adjgvexnum;j+)for(i=j+1;i=adjgvexnum;i+)p=adjga

9、djlistjlink;while(p!=NULL)if(i=p-adjvex)/第j个顶点与第i个顶点邻接k=0;break;/标志k=0,跳出while循环elsek=i;/第j个顶点与第i个顶点不邻接p=p-next;if(k!=0)break;/j与第i个顶点不邻接跳出for循环if(j=adjgvexnum&Fj=0)printf(t%sn,adjgadjlistjvertex);break;if(Fj=0)if(k!=0)printf(t%s,%sn,adjg.adjlistj.vertex,adjg.adjlistk.vertex);Fk=1;k=0;elseprintf(t%s

10、n,adjg.adjlistj.vertex);return;intmain()printf(t创建邻接表n);create_ALGraph();/*建立连通图的邻接链表*/printf(nn广度遍历序列：n);traver(adjg.vexnum);/*连通图的广度遍历算法*/printf(nn);printf(比赛时间分四段：n);timetable();return0;运行结果iijCU&ersAiTibitionXDesktop图.ex巳ftBcDE,F.SSSm项项项项项项UIIIIL.-IL.-I母母母母母母ixxnJ.nJ.nJ.nJ&u&u123456顶顶顶顶顶顶入入入入入入.

11、3刖3刖3刖3即j即!244365656113211522ccccccccc占苦苦苦苦苦苦苦苦心止止止止止止止止止终终终终终终终终终nununununununununufc771-7fa7fa7fa7faT,LTLT-1.-1.-1.-1.-1.-1.-1.-1.-1.占苦苦苦苦苦苦苦苦小4口4口4口4口4口4口4口4口4口-F:!-!.-F:!-!.-FX-FX-FX-FX-R.-R.-R.-B-B-B-己-己-己-己-己-己-_1_1二匕二匕二匕二匕二匕二匕二匕.Jlttlttlttlttlttltt边边边边边边边边边.1-1.1-1.1-1.I-1.I-1.I-1.I-1.1-1.1-1.tilBS12345678?第第第第第第第第第JA-