数据结构课程设计之学生配对问题

##大学数据结构课程设计报告题目： 学生配对问题 院（系）： 计算机工程学院学生姓名: 班级：学号:起迄日期： 2011・6・19——2011・6・30指导教师：

指导教师评语：成绩：签名：年月日2010—2011年度第2学期一、需求分析问题描述：学生搭配问题一班有m个女生，有n个男生（m不等于n）,现要开一个舞会.男女生分别编号坐在舞池的两边的椅子上.每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴.请设计一系统模拟动态地显示出上述过程，要求如下：1） 输出每曲配对情况2） 计算出任何一个男生（编号为X）和任意女生（编号为Y），在第K曲配对跳舞的情况.至少求出K的两个值.基本功能核心问题：循环队列的应用数据模型（逻辑结构）：循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。存储结构：循环链表核心算法：循环队列的入队，出队，判队满，判队空。输入输出输入数据：男生人数、女生人数，歌曲数量，都是整型输出数据：每一首歌曲播放时，男生和女生搭配情况（只输出编号即可）。二、概要设计设计思路：该程序主要运用了循环队列数据结构设计：循环队列：#defineNAXSIZE100//队列长度typedefstruct{QElemType*base；//初始化的动态分配存储空间intfront;//头指针，队列不为空，指向队列头元素intrear；//尾指针，若队列不为空，指向对列尾元素的下一个位置}SqQueue;StatusInitQueue（LinkQueue&Q）〃构造一个空数列StatusEnQueue（LinkQueue&Q,QElemTypee）//插入元素e为Q的新的队尾元素StatusDnQueue（LinkQueue&Q,QElemTypee）//若队列不为空，则删除Q的对头元素，用e返回其指，并返回OK//否则返回ERROR软件结构设计:主程序模块输入模块：通过Get函数输入输出模块：PrintFPrintM函数实现输出数据处理模块：通过循环队列的InitQueue、EnQueue、DnQueue基本操作实现三、详细设计1、课程设计过程中的关键算法如下：关键算法之一：初始化队列voidInitQ(LinkQueue&Q){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));Q.front=p;Q.rear=p;Q.front->next=NULL;}关键算法之二：入队函数voidEnQueue(LinkQueue&Q,intnum)//A队函数{QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));p->num=num;p->next=NULL;Q.rear->next=p;Q.rear=p;}关键算法之三：出队函数voidDeQueue(LinkQueue&Q,int&num)//出队函数{QueuePtrp,q;if(Q.front==Q.rear)printf(-队列为空")；p=Q.front->next;num=p->num;Q.front->next=p->next;q=p->next;if(Q.rear==q)Q.rear=Q.front;free(p);}关键算法之四：输出第i首曲子时女队的情况voidprintF(LinkQueue&F,inti)〃输出第i首曲子时女队的情况{QueuePtrp;intn=1;while(n<i){printf("_");n++;}p=F.front->next;while(F.rear!=p){printf("%d",p->num);p=p->next;}printf("%d\n",p->num);2、主函数：voidmain(){intm,n,k,i,a,b;intcount=0,num;intc[10]={0};int*t=c;inttag=1;QueuePtrp,q;LinkQueueF;〃女生队LinkQueueM;〃男生队printf("请输入女生数量：”)；scanf("%d",&m);printf("请输入男生数量：”)；scanf("%d",&n);printf("请输曲子号：");scanf("%d",&k);printf("请输入要查找的男生编号：”)；scanf("%d",&a);printf("请输入要查找的女生编号：”)；scanf("%d",&b);InitQ(F);InitQ(M);for(i=1;i<=m;i++){EnQueue(F,i);}for(i=1;i<=n;i++){EnQueue(M,i);}for(i=1;i<=k;i++){printf("第％d首曲子\n”,i);printF(F,i);printM(M,i);p=F.front->next;q=M.front->next;printf("目前跳舞的是第％d号女生和第％d号男生\n",p->num,q->num);if(p->num==a&&q->num==b){if(p->num==a&&q->num==b){*t=i;tag++;t++;}count++;DeQueue(F,num);EnQueue(F,num);DeQueue(M,num);EnQueue(M,num);}printf("该对男女生共跳舞％d次\n",count);printf(-要查找的男女生跳舞的曲目是:");for(i=0;i<tag-1;i++)printf("%d\n",c[i]);}3、流程图：图一程序流程图四、｝调试分析实际完成的情况说明本程序支持实现男女生舞蹈时配对问题程序的性能分析，包括时空分析；程序属于循环队列，时间复杂度为0（n）上机过程中出现的问题及其解决方案；在循环队列总是搞错头指针和尾指针，弄错再插入或删除一个元素之后，头指针和尾指针的指向，初始化建空队列，令front=rear=0，每当插入新队列的尾元素时，尾指针增一，每当删除对列头元素时，头指针增一。程序中可以改进的地方说明；加上时间延迟函数也许可能使程序更完美，如果数量较大的话，程序也许会运行较慢程序中可以扩充的功能及设计实现假想。使用循环队列还可以实现更多的功能，只要符合“先进先出”规则，例如：银行业务模拟等等五、测试结果测试输入数据：男女生的个数曲子数和要查找的男女生编号，曲子数，要查找的男女编号输出结果为：每首曲子男女生搭配的情况，要查找的男女有没有跳过舞，哪几曲是要查找的男女在跳舞第一组数据：1男生个数为3,女生个数为5,曲子数为20，要查找的男生编号是3,要查找的女生编号2输出结果生加第。号男生的是第，号女生和第1号男生子是的是第1号女生和第I号男生I子2输出结果生加第。号男生的是第，号女生和第1号男生子是的是第1号女生和第I号男生I子的是难1号女生和票1号男生的是弟w号女生和第砰<里生的是第?号女生和箫?号骂生谶警是龄号女生和软号男生4SL2M歇秘是第<号女生和第1号男生转浦是疑号女生和集'号男生蒐麝堰新号女归哮3号男生睡横前是新号女生和第1号男生、是第4号女生和第2号男生的是第语女生和第，与男生」星第4号女生和第［■男生第二组数据：1男生个数为4,女生个数为3,曲子数为20,要查找的男生编号是2,要查找的女生编号是32输出结果co>nt煎理聂的是新号女生和第5号男生2~~~畚务素的是第3号女生和新号男生”曾甫子332输出结果co>nt煎理聂的是新号女生和第5号男生2~~~畚务素的是第3号女生和新号男生”曾甫子33散暂薛是第】号女生和第，号男生1前跳舞的是第卫号女生和舅之号男生姑首曲子2矗氟是第指女生和第指男生3是新号女生和第4号男生1234前跳秀的是第W号女生和第1号男生姑首曲子2备矗第的是第将女生和第之号男生V首甫子31£舅喜器是第1号女生和第3号男生1H23的是弟1号女生利基」号男生'的是第2号女生和第②号男生'的是第3号女生和弟3号男生'的是第1号女生和第4号男生曲是第W号女生和第］号男生钠是第2号女生和第由号男生劾是第1号女生和第3号用生的是第②号女生和第耳号男生六、用户手册当你运行程序时，自然会弹出要求你输入的数值，如请输入女生的数量：，根据要求输入数值，按回车键就会弹出结果，注意#defineNAXSIZE100按照要求输入男女生数，按回车键会出现按照要求输入男女生数，按回车键会出现按照要求输入曲子数（最好不要超过60）、输入要查找的男女编号，按回车键便会出现结果。昌前为需或是第1号女生和第泻男生弟18RJI：-1-2345是第4号女生和新号男生1234413目晶如晶是第3号女生和第S号男生舅昌前为需或是第1号女生和第泻男生弟18RJI：-1-2345是第4号女生和新号男生1234413目晶如晶是第3号女生和第S号男生舅姑音曲子34S12是第泻女生和勒号男生412i畚如窟鬲是第，号女生和第4号男生嚣:留首曲子句号女生和第二1次要苴理院女生跳舞的曲目是』七、体会与自我评价通过两周的学习和实践，解决实际问题（学生搭配问题），让我对循环队列有了更深的了解，对数据结构产生了浓厚的兴趣，同时也让我提高了解决实际问题的能力。我们要不断的通过上机来提高自己的学习水平，在上机的同时改正了自己对某些算法的错误使用，使自己在通过程序解决问题时抓住关键算法，有了算法设计思想和流程图，并用C语言描绘出关键算法。以前我对数据结构（C语言描述）的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对C语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。让自己有一定的能力去改正一些常见的错误语法，很高兴这一周的学习让我对数据结构（C语言描述）有了新的认识，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。在这次课程设计的实验中，我收获了许多知识，通过查找大量资料，请教老师，以及不懈的努力，也培养了独立思考、动手操作的能力。我也学会了许多学习和解决实际问题的方法，让我受益匪浅。时间的紧缺成为一个很大的问题。也希望老师可以为我们知道一下以后的发展方向。如果可以让每个人都有动手焊接以及参与其他的各个流程，有专门的知道就更好了。课程设计对我来说，趣味性强，不仅锻炼能力，而且可以学到很多东西，在与老师和同学的交流过程中，互动学习，将知识融会贯通，也增强了我和同学之间的团队合作的能力。让我们知道只要努力，集中精力解决问题，一定会有收获的，过程也是很重要的。在这次课程设计中我们要学会利用时间，在规定的时间内完成我们的任务，要逐渐养成用C语言编写程序的良好习惯。这些对我来说都是一种锻炼，一个知识积累的过程，一种能力的提高。要打好基础，才能用更好的办法，更简洁明了的程序解决实际问题，只有这样才能进一步的取得更好的成绩。我们会更加努力，努力的去弥补自己的缺点，发展自己的优点，去充实自己，只有在了解了自己的长短之后，我们会更加珍惜拥有的，更加努力的去完善它，增进它。虽然我现在的水平还很差，但我还会继续努力的，在解决实际问题时如果遇到了难题，我们要学会去查找大量的有关这方面的资料，还要借助于网络不断扩大自己的知识面和阅读量。这样也可以锻炼我们的自主学习能力和解决问题的能力，学到了许多以前没学到的东西。在课程设计中的程序都比较复杂，所以需要我们要更加地细心，认真的完成每一步的操作，修改语法，按照老师的指导思想来完成。与此同时也让我们增加了对程序和算法进一步理解。总之，我学到了很多东西，很感谢学校给我们这样一次锻炼自我的机会，也很感谢老师的指导。源程序:#include<string.h>#include<stdio.h>#include<malloc.h>#defineMAXSIZE100#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1typedefstructQNode{intnum;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;voidInitQ(LinkQueue&Q)//建立空队列{QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));Q.front=p;Q.rear=p;Q.front->next=NULL;}voidEnQueue(LinkQueue&Q,intnum){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));p->num=num;p->next=NULL;Q.rear->next=p;Q.rear=p;}voidDeQueue(LinkQueue&Q,int&num){QueuePtrp,q;if(Q.front==Q.rear)printf(-队列为空")；p=Q.front->next;num=p->num;Q.front->next=p->next;q=p->next;if(Q.rear==q)Q.rear=Q.front;free(p);}voidprintF(LinkQueue&F,inti)//打印第i首曲子时女队的情况{QueuePtrp;intn=1;p=F.front->next;while(F.rear!=p){printf("%d",p->num);p=p->next;}printf("%d\n",p->num);}voidprintM(LinkQueue&M,inti)〃打印第i首曲子时男队的情况{QueuePtrp;intn=1;p=M.front->next;while(M.rear!=p){printf("%d",p->num);p=p->next;}printf("%d\n",p->num);}voidmain(){intm,n,k,i,a,b;intcount=0,num;intc[10]={0};int*t=c;inttag=1;QueuePtrp,q;