学生搭配问题说明书

*******************实践教学*******************兰州理工大学计算机与通信学院2023年春季学期算法与数据结构课程设计题目：学生搭配问题专业班级：计算机四班姓名：赵文基学号：09240412指导教师：张其文成绩：____________目录摘要2序言3正文41.需求分析42.概要设计43.运行环境54.开发工具和编程语言55.详细设计5程序设计过程中的关键算法：56.函数调用关系图67.调试分析78.测试结果8参考文献12总结13致谢14附件I局部程序源代码15摘要1.系统的主要任务学生搭配问题内容是：一班有m个女生,有n个男生(m不等于n),现要开一个舞会.男女生分别编号坐在舞池的两边的椅子上。每曲开始时,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴。应用循环队列来实现此程序。2.设计方法循环队列是一种环状的队列并且对头元素指向队尾元素，学生搭配问题是典型的只有采用循环队列才能解决的问题,实验说明该算法的空间复杂度优于其他算法，通过这次对学生搭配问题的解决可以更好的理解和运用循环队列。关键词：数据结构；C语言；循环队列序言数据结构是一门专业技术根底课，它对学习者的的要求很明确：学会分析、研究计算机加工的数据结构的特性，以便为应用设计所需的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。其次，该课程的学习过程也是复杂程序设计的训练过程，要求学习者编写的程序结构或设计的程序结构体清楚、正确、易读，符合软件工程的标准。循环队列是一种重要的链式结构，其特殊性在于需附设两个指针front和rear分别指示对头元素及队尾元素的位置且对头和队尾相邻接，臆造的环状空间巧妙的解决了插入和删除元素可能出现的假溢出现象。本设计采用目前最通用的程序设计语言之一——C语言作为数据结构和算法的描述语言，循环队列作为数据存储结构。充分考虑了循环队列的特点仅通过对两个循环队列的出、入列操作，就简单的实现了要求，动态的模拟出了舞池两边男女生的搭配情况。该程序通俗易懂且实用性强，其他类似的算法均可借鉴和参考使用。并且该程序清单详细具体、全面、具有很强的可读性。正文1.需求分析核心问题：循环队列的应用数据模型〔逻辑结构〕：循环队列〔两个〕，将男生、女生两组人分别存放，以后实现循环配对输出。存储结构：循环链表核心算法：循环队列的入队，出队，判队满，判队空。输入数据：男生人数、女生人数，歌曲数量输出数据：每一首歌曲播放时，男生和女生搭配情况〔输出编号〕当要查找的男女搭配时输出歌曲编号，和他们搭配的总次数。通过以上分析，该程序具有可行性。2.概要设计算法设计思想队列〔Queue〕是只允许在一端进行插入，而在另一端进行删除的运算限制的线性表。循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元一次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头和队列尾元素的位置。循环队列〔两个〕，将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列SqQueue和SqQueue2.将男生、女生两组人分别存入这两个队列。以实现他们的配对输出，这是循环队列固有的特性。利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。循环队列的长度分别设为男女生的个数即可。在计算机终端输出的结果是：根据要求输出男生女生搭配情况。3.运行环境硬件开发环境：PC机软件开发环境：VisualC++6.0操作系统环境：Windows74.开发工具和编程语言软件开发工具：VisualC++6.0编程语言：C语言5.详细设计建立链式循环队列来分别存储男生和女生，然后调用入队出队函数实现循环队列的配对输出。为了充分利用向量空间，克服上述存储结构上溢现象的方法是将向量空间想象为一个首尾相接的圆环，存储在其中成为循环队列。再循环队列中进行入队、出队操作时，头指针仍要加1，向前移动。只不过当头指针指向上界时其加1操作变为指向下界，这样就可以通过出队再入队来实现男生女生的循环搭配了。程序设计过程中的关键算法：关键算法之一：初始化队列VoidInitQueue(LinkQueue&Q){QueuePtrp;P=(QueuePtr)malloc(sizeof(QNode));Q.front=p;Q.rer=p;Q.front->next=NULL;}关键算法之二：入队函数VoidEnQueue(LinkQueue&Q,intnum){QueuePtrp;P=(QueuePtr)malloc(sizeof(QNode));P->num=num;p->next=NULL;Q.rer->next=p;Q.rer=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){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);}函数调用关系图主函数main主函数main主界面主界面查找配对每曲配对退出系统数据输入查找配对每曲配对退出系统数据输入图6.1函数调用图7.调试分析测试数据：编号12345男生〔5人〕abcde女生〔3人〕aabbccA〔错误分类〕曲子数10测试图如下：图7.1数据测试图测试中出现的问题描述：女生数量设定为3，但实际输入女生数超过3没有错误警告，说明程序还存在一定的漏洞。在输入数据函数voidCreateList_L(LinkList&L1,LinkList&L2,int&m,int&n)中存在不健全，在接收男生或女生数据时没有对数据个数〔m或n〕进行合理性检测。改良方法：在输入数据函数voidCreateList_L(LinkList&L1,LinkList&L2,int&m,int&n)中参加限制语句if(i>m)printf〔“超出限制〞〕;删除刚输入数据；提示重新输入；使得输入男生数〔女生数〕大于预设值时进行提醒，并进行修正。8.测试结果测试输入数据：男女生的个数及姓名、曲子数和要查找的男女生编号编号12345男生abcde女生aabbcc曲子数10输出结果为：每首曲子男女生搭配的情况程序运行界面如下：图8.1输入数据时界面图8.2输出每首曲子配对情况界面图8.3输出某曲子配对情况界面图8.4输出程序结束情况界面参考文献〔1〕严蔚敏等，数据结构〔C语言版〕.北京清华大学出版社,2007年〔2〕严蔚敏等，数据结构题集〔C语言版〕.北京清华大学出版社，2007年〔3〕谭浩强著，C程序设计〔第三版〕.北京清华大学出版社，2005年〔4〕《DATASTRUCTUREWITHC++》.WilliamFord,WilliamTopp.清华大学出版社〔影印版〕.〔5〕数据结构与算法分析〔Java版〕,APracticalIntroductiontoDataStructuresandAlgorithmAnalysisJavaEditionCliffordA.Shaffer,张铭,刘晓丹译电子工业出版社2001年1月总结运用循环队列的根本操作顺利的解决学生舞曲搭配问题，主要利用用循环队列的环状结构，循环地执行出列入列操作并在出队列时进行配对并输出配对情况，而整个过程不需要不需要移动元素使程序在空间复杂度上降到最小，采用指针的移动大大加快了程序的执行效率。并且对输入进行了改良，以防止用户随意输入时出现的各种意想不到的错误。系统整体上比拟完美，无论是输入、输出，还是整个系统的界面，都非常美观、简洁、大方。致谢首先，我们要感谢学校给我们提供了此次课程设计的时机，能让同学们在一起学习与研究，让我们有时机对所学的理论知识进行实践。其次，我们还要特别感谢我们的辅导老师张其文老师，在他的精心辅导和帮助下，我们的设计才得以顺利完成。对他为我们的设计所提出的珍贵意见表示忠心的感谢！最后、在论文的写作过程中，也得到了许多同学的珍贵建议，同时还到许多校友的支持和帮助，在此一并致以诚挚的谢意。附件I局部程序源代码#include<stdio.h>#include<time.h>#include<dos.h>#include<stdlib.h>#include<string.h>#defineMAX200#defineMAXNAME20typedefstructLNode{ intnum;//编号charname[MAXNAME];charsex;//性别，'F'表示女性，'M'表示男性structLNode*next;}LNode,*LinkList;inttime(void)//系统时间函数{time_ttimer;structtm*tblock;/*getstimeofday*/timer=time(NULL);/*convertsdate/timetoastructure*/tblock=localtime(&timer);printf("\t\t\t\t\t当前时刻:%s",asctime(tblock));return0;}voidsleep(clock_twait)//延迟函数{clock_tgoal;goal=wait+clock();while(goal>clock());}voidCreateList_L(LinkList&L1,LinkList&L2,int&m,int&n){printf("\n\n\t\t\t\t^o^参加舞会学生名单^o^\n");printf("\n\n\t\t请输入女生数量：");scanf("%d",&m);while(m<1){printf("\n\n\t\t\t\tERROR\n\n\t\t\t请重新输入女生数量");sleep(1000);//voidsleep(clock_twait)放在前system("CLS");printf("\n\n\t\t\t\t^o^参加舞会学生名单^o^\n");printf("\n\n\t\t请输入女生数量：");scanf("%d",&m);}printf("\t\t请输入男生数量：");scanf("%d",&n);while(n<1){printf("\n\n\t\t\t\tERROR\n\n\t\t\t请重新输入男生数量");sleep(1000);system("CLS");printf("\n\n\t\t\t\t^o^参加舞会学生名单^o^\n");printf("\n\n\t\t请输入女生数量：%d",m);printf("\n\t\t请输入男生数量：");scanf("%d",&n);}inti,choice,numw,numn,b[MAX],j;numw=numn=0;chara[MAX][MAXNAME];LinkListp1,p2,q;//,，不,一，样的p1=p2=L1=L2=NULL;printf("\t\t\t**************");printf("\n\t\t\t*欢送参加舞会*\n");printf("\t\t\t**************\n");printf("\t\t请输入学生的情况\n");for(i=0;i<(m+n)&&i<MAX;i++){if(i>=5){sleep(500);system("CLS");printf("\n\n\t\t\t\t^o^参加舞会学生名单^o^\n");printf("\n\n\t\t请输入女生数量：%d",m);printf("\n\t\t请输入男生数量：%d\n",n);printf("\t\t\t**************");printf("\n\t\t\t*欢送参加舞会*\n");printf("\t\t\t**************\n");printf("\t\t请输入学生的情况\n");for(j=i-4;j<i;j++){printf("\t\t第%d个人姓名:%s\n",j+1,a[j]);printf("\t\t性别<1girl，2boy>:%d\n",b[j]);}}printf("\t\t第%d个人姓名:",i+1);scanf("%s",a[i]);printf("\t\t性别<1girl，2boy>:");scanf("%d",&choice);///////////////scanf("sex:%d",&choice);错错b[i]=choice;q=(LinkList)malloc(sizeof(LNode));if(q==NULL)exit(-1);strcpy(q->name,a[i]);if(choice==1){numw++;q->num=numw;if(L1==NULL){L1=q;p1=q;}//不带头结点else{p1->next=q;p1=q;}p1->next=L1;//循环}else{numn++;q->num=numn;if(L2==NULL){L2=q;p2=q;}//不带头结点else{p2->next=q;p2=q;}p2->next=L2;//循环}}}voidPrint1(LinkListL,intm){LinkListp;inti;p=L;for(i=1;i<=m;i++){printf("%s",p->name);printf("%3c",'');p=p->next;}}voidPrint2(LinkList&p,intm,intn){inti;LinkListq;for(i=1;i<=m;i++){printf("%s",p->name);printf("%3c",'');p=p->next;}q=p;for(;i<=n;i++){printf("%s",q->name);printf("%3c",'');q=q->next;}}voidMatch(LinkListL1,LinkListL2,intm,intn){intk,i,j;LinkListp;printf("\n\n\n\n\t\t\t\t^o^每曲配对情况^o^");printf("\n\n\t\t请输入歌曲的编号：<");scanf("%d",&k);printf(">");while(k<=0){printf("\n\t\t\tERROR!!!\n\t\t请重新输入歌曲的编号");sleep(1000);system("CLS");printf("\n\n\n\n\t\t\t\t^o^每曲配对情况^o^");printf("\n\n\t\t请输入歌曲的编号：<");scanf("%d",&k);printf(">");}if(m<n){p=L2;for(i=1;i<=k;i++){system("CLS");printf("\n\n\n\n\t\t\t\t^o^每曲配对情况^o^");printf("\n\n\t\t请输入曲子编号：<%d>",k);printf("\n\n\n\n\n\t\t\t\t第<%2d>曲配对情况\n\n\n",i);printf("\t\t");Print1(L1,m);printf("\n\t\t");for(j=1;j<=m;j++)printf("|");printf("\n\t\t");Print2(p,m,n);printf("\n\n");sleep(1000);}}else{p=L1;for(i=1;i<=k;i++){system("CLS");printf("\n\n\n\n\t\t\t\t^o^每曲配对情况^o^");printf("\n\n\t\t请输入曲子编号：<%d>",k);printf("\n\n\n\n\n\t\t\t\t第<%2d>曲配对情况\n\n\n",i);printf("\t\t");Print2(p,n,m);printf("\n\t\t");for(j=1;j<=n;j++)printf("|");printf("\n\t\t");Print1(L2,n);sleep(1000);printf("\n\n");}}}voidXXXXXX(LinkListL,intloc,LinkList&p){inti;if(loc==1)p=L;else{p=L;for(i=1;i<loc;i++){p=p->next;}}}voidXHEY(LinkListL1,LinkListL2,intm,intn){intx,y,flag=1,k,loc1,loc2,last;LinkListp1,p2,p11,p22;while(flag!=2){system("CLS");printf("\n\n\n\t\t\t\t^o^查找配对跳舞情况^o^\n\n");printf("\n\t\t请输入你想知道的女生和男生的编号\n\t\t女生的编号:");scanf("%d",&y);while(y>m||y<1){printf("\t\t\tERROR!!!\n\t\t请重新输入女生的编号");sleep(1000);system("CLS");printf("\n\n\n\t\t\t\t^o^查找配对跳舞情况^o^\n");printf("\n\t\t请输入你想知道的女生和男生的编号\n\t\t女生的编号:");scanf("%d",&y);}printf("\t\t男生的编号:");scanf("%d",&x);while(x>n||x<1){printf("\t\t\tERROR!!!\n\t\t请重新输入男生的编号");sleep(1000);system("CLS");printf("\n\n\n\t\t\t\t^o^查找配对跳舞情况^o^\n");printf("\n\t\t请输入你想知道的女生和男生的编号\n\t\t女生的编号:%d\n",y);printf("\t\t男生的编号:");scanf("%d",&x);}printf("\n\t\t歌曲的编号:");scanf("%d",&k);while(k<1){printf("\t\t\tERROR!!!\n\t\t请重新输入歌曲的编号");sleep(1000);system("CLS");printf("\n\n\n\t\t\t\t^o^查找配对跳舞情况^o^\n");printf("\n\t\t请输入你想知道的女生和男生的编号\n\t\t女生的编号:%d\n",y);printf("\t\t男生的编号:%d\n",x);scanf("%d",&k);}printf("\n\n\n");if(m<n){last=((k-1)*m)%n;loc1=(x-last+n)%n;XXXXXX(L2,x,p1);if(loc1>0&&loc1<=m){XXXXXX(L1,loc1,p11);}elseprintf("\t\t在第<%4d>曲编号为<%4d>的男生(%s)没有舞伴\n\n",k,x,p1->name);XXXXXX(L1,y,p2);loc2=(last+y)%m;XXXXXX(L2,loc2,p22);if(loc2==x||loc1==y)printf("\t\t编号为<%4d>的男生(%s)和编号为<%4d>的女生(%s)在第(%4d)首歌配对跳舞\n\n\n",x,p1->name,y,p2->name,k);else{if(loc1>0&&loc1<=m)printf("\t编号为<%4d>的男生(%s)在第(%4d)首歌和编号为<%4d>的女生(%s)配对跳舞\n\n",x,p1->name,k,y,p11->name);printf("\t编号为<%4d>的女生(%s)在第(%4d)首歌和编号为<%4d>的男生(%s)配对跳舞\n\n",x,p2->name,k,y,p22->name);}}else{last=((k-1)*n)%m;loc1=(y-last+m)%m;XXXXXX(L1,y,p1);if(loc1>0&&loc1<=n){XXXXXX(L1,loc1,p11);}elseprintf("\t\t在第<%4d>曲编号为<%4d>的女生(%s)没有舞伴\n\n",k,x,p1->name);XXXXXX(L2,x,p2);loc2=(last+x)%m;XXXXXX(L1,loc2,p22);if(loc2==y||loc1==x)printf("\t\t编号为<%4d>的男生(%s)和编号为<%4d>的女生(%s)在第(%4d)首歌配对跳舞\n\n\n",x,p1->name,y,p2->name,k);else{printf("\t编号为<%4d>的男生(%s)在第(%4d)首歌和编号为<%4d>的女生(%s)配对跳舞\n\n",x,p2->name,k,y,p22->name);if(loc1>0&&loc1<=m)printf("\t编号为<%4d>的女生(%s)在第(%4d)首歌和编号为<%4d>的男生(%s)配对跳舞\n\n",x,p1->name,k,y,p11->name);}}printf("\n\n\t是否继续找配对情况<想1，不想2>：");scanf("%d",&flag);}}intEmptyL(LinkListL){if(L==NULL)return1;elsereturn0;}voidDestroyL(LinkList&L){LinkListp;if(!EmptyL(L)){p=L->next;while(p!=L){L->next=p->next;free(p);p=L->next;}free(L);}}voidJieMian(){for(inti=1;i<=50;i++){//system("colorCF");/*设置背景/字体颜色，1为背景，7为前景，其值可随便设,系统默认为07*/system("CLS"); printf("\n\n\n\n"); printf("\t\t\t^o^学生搭配问题^o^\n\n"); printf("\t\t\t╔*═*═*═*═*═*═*═*═*═*═*╗\n"); printf("\t\t\t║║\n");printf("\t\t\t║1.参加舞会学生名单║\n");printf("\t\t\t║2.输出每曲配对情况║\n");printf("\t\t\t║3.查找配对跳舞情况║\n");printf("\t\t\t║4.退出║\n");printf("\t\t\t║║\n"); printf("\t\t\t║*=*请在1~4选项中选择*=*║\n"); printf("\t\t\t║║\n"); printf("\t\t\t╚*═*═*═*═*═*═*═*═*═*═*╝\n"); printf("\n\n\t\t\t\t\t 赵文基数据结构课程设计\n"); //printf("\t\t\t\t\t\t\ttime()"); time(); printf("\n\n输入选择的工程：");sleep(1);}}voidJiemian2(){inti;system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^欢");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^欢送");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^欢送下");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^欢送下次");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^欢送下次使^");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^欢送下次使用");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^欢送下次使用^o^");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^欢送下次使用^o^\n\n\t\t\t\t");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^欢送下次使用^o^\n\n\t\t\t\tGoodBye!");sleep(200);system("CLS");for(i=1;