田径运动会赛程安排.doc

题目：在一个田径运动会上，已知有m个选手参加比赛，运动项目共有n个，这包括若干个诸如100m之类的以个人形式参加的单项和4100m之类的多人参加的集体项目。另外，每位选手最多可参加3个单项，集体项目则不限制。为使选手能正常比赛，需要对赛程作合理安排。请构造出有关模型和数据结构，设计出合理安排赛程的算法和程序，以使每位选手都能正常地参加比赛，并要求比赛时间尽可能短。一问题分析和任务定义1问题分析：首先怎样考虑选手报名情况，我们可以规定有m个选手报名参加了这次田径运动会项目，并给他们从1到m编号他们。由于实际情况我们规定有n个田径比赛项目，分别为个人形式参加的单项项目有100米等。多人参加的集体项目有4*100米等项目。由于题目规定每位选手最多可参加3个单项，集体项目不限制。所以我们假设每人参加的项目就用1表示，没参加用0表示。可以用列表来表示相关模型，模型见数据结构的定义。 由于选手参加的条件不能超过3个单人项目，所以在参加之前先判断是否符合条件，若不符合则将选手排除。2任务定义：合理赛程安排考虑以下三方面：2.1 某些比赛项目不能同时进行。设比赛场地为有8道400米长的跑道，那么400米和800米比赛不能同时进行，4*200米和8*100米不能同时进行等赛场冲突。2.2 某一选手参加的交叉项目不能同时进行。如一选手既参加了100米又参加了200米则为了每个选手都能正常进行100米和200米比赛不能同时进行等时间冲突。2.3 在满足上面（1）、(2)条件下，尽可能在最短时间内完成比赛。3功能：编号1到100个选手参加7个项目分别是跳高、跳远、铅球、跨栏、100米单人项目和4*100米，8*100米等多人项目。确定每个项目参加的人数，而且要判断多人比赛项目报名参加的人数，是否能正确分组。4输入输出形式：输入 整形输入比赛项目，各项比赛每轮进行所需时间和表示某选手参加某项目的类型。输出 根据报名表输出赛程的安排，其中包括项目的先后顺序，以及项目的参加人数、项目类型、举行场地等。5值的范围设选手m=100个，运动项目7项，其中包括5项单项:跳高,跳远,铅球和2集体项目:4*100米,8*100米.且规定比赛项目依次编号为1、2、3、4、5、6、7。算法的功能：在有限的时间内尽可能短的合理的安排赛程。测试所需的数据和类型：参加人数100人，每个项目所报的人数。二概要设计和数据结构的选择 1设计概要1.1 报名表的定义：数组存储矩阵pep各元素是包含两个成员的结构体类型，两个成员即运动项目和报名信息，报名信息用整形变量1或0，1表示第n个人参加了第m个项目，0表没有参加。表1.报名表项目m选手n1001500铅球跳高跳远4*1008*1001001001121001010311010014001010050001100由表可示，可用矩阵来存储表格中的数据，可设如下：矩阵Amn存储各个结点，各结点包含两个成员：运动项目和报名信息(整形变量1或0)。1.2 选手Pep数组各个元素 表2.选手结构选手Item1TFItem2TFItem3TFItem4TFItem5TFItem6TFItem7TFItem记录参加了什么项目，用1234567依次表示七个项目。TF参加标志符 TF=1报名参加，=0不报名比赛。1.3 数组item每个元素包含两个域:项目域和该项目举行场地结点类型表3.项目结构Ite(项目域)Ch(举行场地)1.4 数组a包含三个域:项目M1域,项目M2域,标志域tag 如表4.项目冲突记录表（a）M1M2tagtag=1时表示M1,M2可以同时进行，tag=0时有冲突不能同时进行在存放可同时进行比赛数组中删除某选手交叉的项目表5.项目冲突记录表（b）1211301411501611702302412502612702数据结构： 2.1 单个比赛项目的结构定义/将每一个项目定义为结构体typedef struct int n;/n=1为单项，n1时为集体项目int data;/项目类型，用1234567依次表示七个项目int TF;/参加标志符，TF=1报名参加，=0不报名比赛node1;n为项目类型，n=1为单项，n1时为集体项目data为项目类型，用1234567依次表示七个项目int TF参加标志符，TF=1报名参加，=0不报名比赛2.2 定义一个结构体存储所有项目typedef struct node1 itemmaxitem;int length1;/单项比赛项目数int length2;/集体比赛项目数int length;/比赛总项目数node2;node1 itemmaxitem;用一个数组存储所有的项目length1 可选的单项比赛项目个数length2 可选的集体比赛项目个数length 可选的比赛总项目数2.3 定义存放每位选手参加项目信息的结构体typedef structnode2 pepMaxman;/存放每位选手参加项目信息int size;/选手个数node3;node2 pepMaxman 用数组存放每位选手参加的项目size记录报名选手的个数2.4 定义存储项目赛事安排相关信息的结构体typedef structint ite;/比赛项目char a;/比赛时间段char ch;/举行场地int time;/比赛需要时间int num;/参加人数node5;ite 与data一致为项目类型，用1234567依次表示七个项目a 比赛时间段=a上午进行，=b下午进行ch 举行场地=A在A场地举行，=b 在B场地举行time 该项目总共所需要的时间num 该项目总共报名参加人数2.5 定义数组存储每个项目比赛需要时间int timemaxitem;/每个项目一组比赛需要时间time 依次存放1-7项比赛每组比赛所需时间/各项目每人或每组需要时间(分钟)time1=2;/跳高time2=2;/跳远time3=2;/铅球time4=4;/跨栏time5=3;/100米time6=10;/ 4*100米time7=18;/8*100米3主程序的流程图: 由跑道规则判断各项目能否同时进行 定义数组并赋值 各项参加的人数 各项目参加的人没有重复 能同时进行的项目 判断每人参加单项是否符合条件排出田径运动会的赛程图1. 流程图三 .详细设计和编码先用结构体存储各个结点的信息，每个选手参加单人项目和多人项目用1表示，不参加用0表示，结构体存储表示项目能同时进行的用TF表示。然后存储各个项目参加的人数和场地的信息，以及每轮比赛的所需时间。再用一个结构体存储每个人的信息包括每人参加的单项和多项以及总的项目数。详情见上面概要设计和数据结构的选择。下面用函数实现个模块功能。模块一 先设一个子函数求出每个人参加各个项目的总数；int countitem(node3 *Link,int i)/第i个人参加单项总个数 int count1=0;for(int j=1;jpepi.length1;j+)/只统计单项if(Link-pepi.itemj.TF=1)/第i个人参加第j个单项count1+;/printf(第%d个人参加单项总个数为%dn,i,count1);return count1;模块二 求出每个项目参加的总人数int countpeople(node3 *Link,int i)/第i个项目参加人数int count=0;for(int j=1;jsize;j+)/第j个选手if(Link-pepj.itemi.TF=1)count+;printf(第%d个项目参加人数为%dn,i,count);return count;模块三 判断每个人所报的项目是否符合标准, 即每人不得参加超过3个单人项目统计所有选手参加的单项比赛int t;/临时变量for(i=1;i3取消参赛资格n,i,t);if(t3)/取消资格通过删除实现dele(p,i);/删除void dele(node3 *Link,int i)/取消第i个选手参赛资格 for(int j=i;jsize;j+)/i以后的选手依次前移Link-pepj=Link-pepj+1; Link-size-;/选手个数减少一个模块四 每人不得参加超过3个单人项目，如过超过则把此人删除即在模块三的条件下,调用此模块void dele(node3 *Link,int i)/取消第i个选手参赛资格 for(int j=i;jsize;j+)/i以后的选手依次前移Link-pepj=Link-pepj+1; Link-size-;/选手个数减少一个模块五 计算各项比赛过程需要时间for(i=1;iitemi.a=a1)/满足条件即第i项比赛a1时间段进行if(Link-itemi.ch=a2)/满足条件即第i项比赛a2场地进行 printf(t 项目%d开始时间 %d:,i,(*m);/i项比赛开始时间(时针)if(*n)itemi.ite=1) printf( 项目类型：跳高 举行场地:运动场A ); if(Link-itemi.ite=2) printf( 项目类型：跳远 举行场地:运动场A);if(Link-itemi.ite=3) printf( 项目类型：铅球 举行场地:运动场A);if(Link-itemi.ite=4) printf( 项目类型：跨栏 举行场地:运动场A);if(Link-itemi.ite=5) printf( 项目类型：100米 举行场地:运动场B);if(Link-itemi.ite=6) printf( 项目类型：4*100米 举行场地:运动场B);if(Link-itemi.ite=7) printf( 项目类型：8*100米 举行场地:运动场B);printf(ntt此项比赛参加人数%d人,Link-itemi.num);/输出此项比赛人数if(Link-itemi.ite=5|Link-itemi.ite=6)/径赛,则须分组int r1=Link-itemi.num%8;/由人数来确定分成的组数if(r1)printf( 分成%d组n,Link-itemi.num/8+1);else printf( 分成%d组n,Link-itemi.num/8);else if(Link-itemi.ite!=7) printf(n);/8*100米 elseprintf( 8*100米总共分成%d队,Link-itemi.num/4);int r2=Link-itemi.num/4%8;/由人数来确定分成的组数if(r2) printf( 8*100米总共分成%d组,Link-itemi.num/4/8+1);elseprintf( 8*100米总共分成%d组,Link-itemi.num/4/8);*n=Link-itemi.time+(*n);/计算第i项下一项比赛开始时间if(*n)=60)*m=*m+*n/60;*n=*n%60;printf(n);模块七 输出田赛void put2(node6 *Link,int *m,int *n,int i,char a1,char a2)if(Link-itemi.a=a1)/a1时间段进行if(Link-itemi.ch!=a2)/不在a2场地进行printf(t 项目%d开始时间 %d:,i,(*m);if(*n)itemi.ite=1) printf( 项目类型：跳高 举行场地:运动场A ); if(Link-itemi.ite=2) printf( 项目类型：跳远 举行场地:运动场A);if(Link-itemi.ite=3) printf( 项目类型：铅球 举行场地:运动场A);if(Link-itemi.ite=4) printf( 项目类型：跨栏 举行场地:运动场A);if(Link-itemi.ite=5) printf( 项目类型：100米 举行场地:运动场B);if(Link-itemi.ite=6) printf( 项目类型：4*100米 举行场地:运动场B);if(Link-itemi.ite=7) printf( 项目类型：8*100米 举行场地:运动场B);printf(ntt此项比赛参加人数%d人,Link-itemi.num);/输出比赛参加人数*n=Link-itemi.time+(*n);/计算第i项下一项比赛开始时间if(*n)=60)*m=*m+*n/60;*n=*n%60;printf(n);四 上机调试1源程序的输入和代码的调试：输入：根据题目的问题分析及解决方法的确定，设计各功能模块，输入源程序。运行时，按任意键进入，即可得到结果。输出：由于程序中的比赛项目和参加的人数已经确定，是否报名是随机产生的所以这个程序输出结果是任意的。2调试过程中遇到的主要问题：2.1 表只有先初始化后才能将其地址赋给一指针变量,否则出现逻辑错误。2.2 子函数中形式参数不能由实参直接传其值，而应该将其地址传给形参，使其内容一致。2.3 结构体定义中包含别的结构体，要仔细分清之间的逻辑关系，否则出现思维混乱。2.4 结构体指针表示其成员必须用-运算符 如* Link2,其成员length应为Link2-size而不是Link2. size,若其成员是另一结构体类型的数组,则数组内成员表示为Link2- pepi.length1。2.5 集体比赛项目时间=组数*每组比赛时间(t), 设每轮8个队.如4*100米参加总人数k其此比赛项目时间: k=k/4;若k%8=0,T=k%8*每组比赛时间,否则T=t* (k%8+1)。3 设计实现的回顾讨论和分析：这个程序设计题完成的比较困难，而且一开始对题目认识不够，走了不少弯路，而且要了解田径运动会所有项目和各个项目举行的场地，需要很多的课外知识。但这个程序设计起来比较困难，由于参加的项目多样化和参加的人数比较多，又要考虑每个人只能参加3个单项。感觉表示起来比较难以下手，要考虑各个方面的逻辑关系，所以需要非常细心，各个方面之间的逻辑关系在心中有数，要有整体思路，如果有半点粗心，就会导致程序得不到正确的结果，甚至编译不能通过。 很难找到一些相关资料和类似的程序，没有正确的提示和参考，由于自己的能力有限，导致这个程序做的不够完善，很多的功能还无法实现，以后要更加努力学习，了解到更多的相关知识，扩大自己的知识面。4改进设想：由于这个程序所需的变量很多，参加的项目和参加的人数都已在主程序中已经赋值，而报名表中的选手信息则有随机函数产生，项目的时间安排和场地安排也是事先安排赋值的，没有冲突，所以这个函数并没有什么实用价值。可以做如下改进：4.1 数中设置一个文件调用此文件中的信息，即文件中存储各个项目的信息和参加的选手信息；然后，根据这个文件排出赛程先后顺序的安排。则会达到更好的效果，若文件中存储更多的信息，则这个程序可以运用到很多方面。4.2考虑到场地冲突的某些比赛项目不能同时进行，考虑某一选手参加的交叉项目不能同时进行。如一选手既参加了100米又参加了200米则为了每个选手都能正常进行100米和200米比赛不能同时进行等时间冲突。五 用户使用说明本程序使用比较简单。出现信息界面时,会停顿,等待用户看完后，输入任意字符，即可进入下面环节。六、 测试结果图2.欢迎界面图3.项目及编排说明图4.场地及时间的确定图5.报名结束,项目人数确定图6.赛程安排表七、参考资料1自编,数据结构与算法实验和课程设计指导书，本系精品课程建设组。2严蔚敏等,数据结构题集（c语言）,北京：清华大学出版社，1999年2月第1版。3李春葆,数据结构习题与解析（c语言）。北京：清华大学出版社，2000年1月第1版。4王立柱,c语言与数据结构,北京：清华大学出版社, 2003年6月第1版。八、源程序#includestdio.h#include #includestdlib.h#includemath.h#define maxitem 50/比赛项目个数最大值/单项：跳高 跳远 铅球 跨栏 100米 /多人参加的集体项目：4*100米 8*100米#define Maxman 300/选手个数最大值/比赛单个项目typedef struct/将每一个项目的报名定义为结构体int n;/n=1为单项，n1时为集体项目int data;/记录参加了什么项目int TF;/参加标志符node1;/所有项目typedef struct node1 itemmaxitem;int length1;/单项比赛项目数int length2;/集体比赛项目数int length;/比赛总项目数node2;typedef structnode2 pepMaxman;/存放每位选手参加项目信息int size;/选手个数node3;node3 Link1;typedef struct int ite;/比赛项目char a;/比赛时间段char ch;/举行场地int time;/比赛需要时间int num;/参加人数node5;typedef structnode5 itemmaxitem;/int leng;node6;node6 Link2;int timemaxitem;/每个项目一组比赛需要时间int countitem(node3 *Link,int i)/第i个人参加单项总个数 int count1=0;for(int j=1;jpepi.length1;j+)/只统计单项if(Link-pepi.itemj.TF=1)/第i个人参加第j个单项count1+;/printf(第%d个人参加单项总个数为%dn,i,count1);return count1;int countpeople(node3 *Link,int i)/第i个项目参加人数int count=0;for(int j=1;jsize;j+)/第j个选手if(Link-pepj.itemi.TF=1)count+;printf(第%d个项目参加人数为%dn,i,count);return count;void dele(node3 *Link,int i)/取消第i个选手参赛资格for(int j=i;jsize;j+)/i以后的选手依次前移Link-pepj=Link-pepj+1; Link-size-;/选手个数减少一个/输出径赛void put1(node6 *Link,int *m,int *n,int i,char a1,char a2)/项目的指针，时间，第几个项目，举行时间，类型if(Link-itemi.a=a1)/满足条件即第i项比赛a1时间段进行if(Link-itemi.ch=a2)/满足条件即第i项比赛a2场地进行 printf(t 项目%d开始时间 %d:,i,(*m);/i项比赛开始时间(时针)if(*n)itemi.ite=1) printf( 项目类型：跳高 举行场地:运动场A ); if(Link-itemi.ite=2) printf( 项目类型：跳远 举行场地:运动场A);if(Link-itemi.ite=3) printf( 项目类型：铅球 举行场地:运动场A);if(Link-itemi.ite=4) printf( 项目类型：跨栏 举行场地:运动场A);if(Link-itemi.ite=5) printf( 项目类型：100米 举行场地:运动场B);if(Link-itemi.ite=6) printf( 项目类型：4*100米 举行场地:运动场B);if(Link-itemi.ite=7) printf( 项目类型：8*100米 举行场地:运动场B);printf(ntt此项比赛参加人数%d人,Link-itemi.num);/输出比赛参加人数if(Link-itemi.ite=5|Link-itemi.ite=6)/满足条件即是径赛,则须分组int r1=Link-itemi.num%8;/由人数来确定分成的组数if(r1)printf( 分成%d组n,Link-itemi.num/8+1);elseprintf( 分成%d组n,Link-itemi.num/8);else if(Link-itemi.ite!=7) printf(n);/8*100米 elseprintf( 8*100米总共分成%d队,Link-itemi.num/4);int r2=Link-itemi.num/4%8;/由人数来确定分成的组数if(r2)printf( 8*100米总共分成%d组,Link-itemi.num/4/8+1);elseprintf( 8*100米总共分成%d组,Link-itemi.num/4/8);*n=Link-itemi.time+(*n);/计算第i项下一项比赛开始时间if(*n)=60)*m=*m+*n/60;*n=*n%60;printf(n);/输出田赛void put2(node6 *Link,int *m,int *n,int i,char a1,char a2)if(Link-itemi.a=a1)/a1时间段进行if(Link-itemi.ch!=a2)/不在a2场地进行printf(t 项目%d开始时间 %d:,i,(*m);if(*n)itemi.ite=1) printf( 项目类型：跳高 举行场地:运动场A ); if(Link-itemi.ite=2) printf( 项目类型：跳远 举行场地:运动场A);if(Link-itemi.ite=3) printf( 项目类型：铅球 举行场地:运动场A);if(Link-itemi.ite=4) printf( 项目类型：跨栏 举行场地:运动场A);if(Link-itemi.ite=5) printf( 项目类型：100米 举行场地:运动场B);if(Link-itemi.ite=6) printf( 项目类型：4*100米 举行场地:运动场B);if(Link-itemi.ite=7) printf( 项目类型：8*100米 举行场地:运动场B);printf(ntt此项比赛参加人数%d人,Link-itemi.num);/输出比赛参加人数*n=Link-itemi.time+(*n);/计算第i项下一项比赛开始时间if(*n)=60)*m=*m+*n/60;*n=*n%60;printf(n);void main()int i,j;node3 *p; node6 *q;/定义指针 printf(n); printf(tt _n); printf(tt| 欢迎进入洪叶的课程设计！ |n); printf(tt|-|n); printf(tt| 学生:洪叶 班级:计算机06专升本 |n); printf(tt|-|n); printf(tt| 学号:0604081019 |n); printf(tt|-|n);printf(tt| 题目: 田径运动会赛程安排 |n); printf(tt|_|n); printf(任意键继续!nn);getch();printf(可以报的体育项目有:n);printf(单项： 项目1:跳高 项目2:跳远 项目3:铅球 项目4:跨栏 项目5:100米n);printf(集体项目： 项目6:4*100米 项目7:8*100米nn);printf(初始化报名表,为方便,采用随机生成!n);printf(nt赛事编排原则:nn);printf(一.先排全能项目,各个单相顺序在田经规则中有严格规定.n);printf(二.先排径赛项目,后排田赛项目.n);printf(三.径赛宜先短距离,后长距离.n);printf(n任意键继续!nn);getch();Link1.size=100;/初始化选手个数/初始化 每个选手可以选报的项目个数for( i=1;i=Link1.size;i+) Link1.pepi.length1=5;/单项 Link1.pepi.length2=2;/集体项目 Link1.pepi.length=7;/总项目for( i=1;i=Link1.size;i+)for( j=1;j1时为集体项目Link1.pepi.item1.data=1;/1代表跳高Link1.pepi.item2.data=2;/2代表跳远Link1.pepi.item3.data=3;/3代表铅球Link1.pepi.item4.data=4;/4代表跨栏Link1.pepi.item5.data=5;/5代表100米 Link1.pepi.item6.n=4;/n1时为集体项目Link1.pepi.item6.data=6;/6代表4*100米Link1.pepi.item7.n=4;/n1时为集体项目Link1.pepi.item7.data=7;/7代表8*100米/举行所在场地的确定/A场地举行田赛(无场地冲突) B场地举行径赛(有场地冲突)Link2.item1.ite=1;/跳高Link2.item1.ch=A;/跳高在A场地举行Link2.item2.ite=2;/跳远Link2.item2.ch=A;/跳远在A场地举行Link2.item3.ite=3;/铅球Link2.item3.ch=A;/铅球在A场地举行Link2.item4.ite=4;/跨栏Link2.item4.ch=A;/跨栏在A场地举行Link2.item5.ite=5;/100米Link2.item5.ch=B;/100米在B场地举行Link2.item6.ite=6;/4*100米Link2.item6.ch=B;/4*100米在B场地举行Link2.item7.ite=7;/8*100Link2.item7.ch=B;/8*100在B场地举行printf(举行所在场地的确定完毕!n);/项目举行时间的确定Link2.item1.a=a;/跳高上午进行Link2.item3.a=a;/铅球上午进行Link2.item5.a=a;/100米上午进行Link2.item6.a=a;/8*100上午进行Link2.item2.a=b;/跳远下午进行Link2.item4.a=b;/跨栏下午进行Link2.item7.a=b;/4*100米下午进行printf(项目举行时间的确定完毕!n);/各项目每人或每组需要时间(分钟)time1=2;/跳高time2=2;/跳远time3=2;/铅球time4=4;/跨栏time5=3;/100米time6=10;/4*100米time7=18;/8*100米printf(各项目每人或每组需要时间确定完毕!n);q=&Link2;/项目int a,k=43;/临时变量/k用来改变随机发生器,初值可任意定for(i=1;i=Link1.size;i+)for(int j=1;j=Link1.pepi.length;j+)/随机产生报名表k+;srand(k);/初始化随机发生器a=rand()%2;/取余数Link1.pepi.itemj.TF=a;/若a=1,则第i个人参加了第j项比赛,反之否/printf(%d,%d,%dn,i,j,a);/体现报名信息p=&Link1;/printf(随机报名成功!n);printf(任意键继续!nn);getch();/统计所有选手参加的单项比赛并将参加单项多余3