数据结构实验-男女运动员混合双打组合实验报告

实验报告实验课程：数据结构实验项目：实验二男女运动员混合双打组合专业：计算机科学与技术班级：姓名：学号：指导教师：目录一、问题定义及需求分析（1）问题描述（2）实验任务（3）需求分析二、概要设计：(1)抽象数据类型定义(2)主程序流程(3)模块关系三、详细设计(1)数据类型及存储结构(2)模块设计四、调试分析(1)调试分析(2)算法时空分析(3)经验体会五、使用说明(1)程序使用说明六、测试结果(1)运行测试结果截图七、附录(1)源代码一、问题定义及需求分析(1)问题描述运动员混合双打组合设有M个男羽毛球运动员和N个女羽毛球运动员，现进行男女混合双打组合K轮配对。男女运动员分别编号排队在等候队列，按顺序依次从男女运动员中各出队1人组合配对。本轮没成功配对者等待下一轮次配对。(2)实验任务设计程序模拟完成运动员组合配对过程。(3)需求分析1)采用队列等数据结构。2)输出每轮的配对信息。二、概要设计：(1)抽象数据类型定义：采用链式存储结构构造单链队列，以及队列的基本操作函数，包括：intInitQueue(LinkQueue*Q)//构造一个空队列intEnQueue(LinkQueue*Q,inte)//入队列intDeQueue(LinkQueue*Q,int*e)//出队列(2)主程序流程输入男女两队的人数输入比赛的轮数构造两个队列M和N依次对两队列进行入队操作在循环体中先M出队后N出队输出出队元素信息进行匹配再将出队元素入队尾第二次出对入队实现两次匹配满足需求完成比赛需要的轮数后跳出循环结束程序(3)模块关系开始输入男女队人数m、n输入比赛轮数构造队列MN循环体完成匹配结束三、详细设计数据类型定义及存储结构：typedefstructQNode{QNodeTypedata;structQNode*next;}QNode,*QueuePtr;//节点的结构typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;模块一：intInitQueue(LinkQueue*Q){//构造一个空队列Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode));if(!Q-front)exit(0);Q-front-next=NULL;return1;}模块二：intEnQueue(LinkQueue*Q,inte){//入队列QNode*p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);//存储分配失败p-data=e;p-next=NULL;Q-rear-next=p;//p插到尾指针的下一个位置Q-rear=p;//再将尾指针指向preturn0;}模块三：intDeQueue(LinkQueue*Q,int*e){//出队列QNode*p;p=(QueuePtr)malloc(sizeof(QNode));if(Q-front==Q-rear)return0;//队列为空，出队失败p=Q-front-next;//p指向头指针指向的下一个节点*e=p-data;//获得出队节点的数据信息Q-front-next=p-next;if(Q-rear==p)Q-rear=Q-front;//出队完成后队列为空free(p);//释放Preturn1;}四、调试分析问题解决：for循环的结束条件一开始设定错误，导致输出匹配信息的时候少数出一次；将结束条件改为i=(m*k/2+1)后就解决了；原因是k的奇偶性会影响到i的结束条件；时空分析：由于采用链式存储结构，所以队列的大小可以根据输入条件而变，再存储空间上空间利用率较高；出队和入队操作只涉及到队头和队尾指针的移动，其时间复杂度为O(1);经验体会：链式队列的一个很大的优点就是队列的可变性强，再存储空间分配上比较容易满足，因此，链式队列的实用性更好；五、使用说明第一步：输入男女两队的人数和比赛的轮数第二步：程序根据以上输入的数据可自动输出匹配完成的信息六、测试截屏七、附录#includestdio.htypedefintQNodeType;typedefstructQNode{QNodeTypedata;structQNode*next;}QNode,*QueuePtr;//节点的结构typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;intInitQueue(LinkQueue*Q){//构造一个空队列Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode));if(!Q-front)exit(0);Q-front-next=NULL;return1;}intEnQueue(LinkQueue*Q,inte){//入队列QNode*p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);//存储分配失败p-data=e;//p获得数据信息p-next=NULL;Q-rear-next=p;//p插到尾指针的下一个位置Q-rear=p;//再将尾指针指向preturn0;}intDeQueue(LinkQueue*Q,int*e){//出队列QNode*p;p=(QueuePtr)malloc(sizeof(QNode));if(Q-front==Q-rear)return0;//队列为空，出队失败p=Q-front-next;//p指向头指针指向的下一个节点*e=p-data;//获得出队节点的数据信息Q-front-next=p-next;if(Q-rear==p)Q-rear=Q-front;//出队完成后队列为空free(p);//释放Preturn1;}voidmain(){intm,n,k;printf(请输入队M队员数量：);scanf(%d,&m);printf(请输入队N队员数量：);scanf(%d,&n);printf(请输入需要比赛的轮数K：);scanf(%d,&k);//接受MNKLinkQueue*M,*N;M=(QueuePtr)malloc(sizeof(QNode));N=(QueuePtr)malloc(sizeof(QNode));//给M队输入一个队列InitQueue(M);//初始化队列Minti;for(i=1;i=m;i++){EnQueue(M,i);}//给N队输入一个队列InitQueue(N);for(i=1;i=n;i++){EnQueue(N,i);}int*a,*b,c=1,d=1;a=&d;b=&c;for(i=1;i=(m*k/2+1);i++){DeQueue(M,a);//队列M中元素先出队列DeQueue(N,b);//队列N中元素先出队列printf(m%d&f%dVS,*a,*b);EnQueue(M,*a);//出队后再入队实现多轮循环EnQueue(N,*b);DeQueue(M,a);//实现两次两队元素出队匹配DeQueue(N,b);printf(m%d&f%d,*a,*b);EnQueue(M,*a);EnQueue(N,*b);printf(\n);}getchar();}