数据结构教学规划学生搭配问答

数据结构课程设计学生搭配问题学生姓名学生学号指导教师

如12年12月3日课程设计任务书姓名班级学号设计题目学生搭配问题理论要点队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。循环队列是在队列的1顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。循环队列的入队，出队，判队满，判队空。设计目标（1）输出每曲配对情况。（2）计算出任何一个男生（编号为不和任意女生（编号为丫）,在第K曲配对跳舞的情况.至少求出K的两个值。研究方法步骤（1）先建立两个循环队列SqQueue和SqQueue2。（2）将男生、女生两组人分别存入这两个队列。（3）将男女生分别进行入队列和出队列操作，且实现搭配输出。（4）循环队列的长度分别设为男女生的个数即可。（5）在计算机终端输出的结果是：根据要求输出男生女生搭配情况。

预期名结果每一首歌曲播放时，男生和女生搭配情况（只输出编号即可）当要查找的男女搭配时输出歌曲编号，和他们搭配的总次数。通过以上分析，该程序具有可行。计划与进步的安排1、2012年11月20日之前寻找到解决问题思搭配问题的路2、2012年11月25日之前必须编写出程序3、2012年11月26日之前检查程序的运行并找出错误程序4、2012年11月29日之前找到解决错误的方法5、2012年11月30日写数据结构课程设计报告摘要针对学生搭配问题，循环队列是一种重要的链式结构，其特殊性在于需附设两个指针front和rear分别指示对头元素及队尾元素的位置且对头和队尾相邻接。在程序的设计过程中，运用了各种基本的算法，有判断队空及队满，出队，入队等循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。学生搭配问题是典型的只有采用循环队列才能解决的问题，实验表明该算法的空间复杂度优于其他算法。本文用循环队列会很好的把这个程序设计出来，会有很好的效果。得出的程序运行结果能够很形象的把结果表示出来。关键词：学生配对，数据结构，循环队列。目录摘要 错误!未定义书签。1设计题目 错误!未定义书签。TOC\o"1-5"\h\z\o"CurrentDocument"2运行环境 1\o"CurrentDocument"3算法设计的思想 1\o"CurrentDocument"4算法的流程图 2\o"CurrentDocument"5算法设计分析 26源代码 3\o"CurrentDocument"7运行结果分析 8\o"CurrentDocument"8收获及体会 8\o"CurrentDocument"参考文献 9致谢学生搭配问题一班有m个女生，有n个男生（m不等于叫现要开一个舞会.男女生分别编号坐在舞池的两边的椅子上.每曲开始时，依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴。请设计一系统模拟动态地显示出上述过程,要求如下：（1）输出每曲配对情况（2）计算出任何一个男生（编号为X）和任意女生（编号为Y）,在第K曲配对跳舞的情况.至少求出K的两个值。.运行环境本课题的程序设计和测试等环节都是在Windows7操作系统下完成，软件的编译测试环境为vc6.0以c语言编写的。软件的硬件运行需求非常低，任何计算机都可运行。.算法设计的思想基本思路：队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。（1）要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列I」SqQueue和SqQueue2。（2）将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输出，这是循环队列固有的特性。（3）利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。（4）循环队列的长度分别设为男女生的个数即可。（5）在计算机终端输出的结果是：根据要求输出男生女生搭配情况关键问题：循环队列的应用解决方法：数据模型（逻辑结构）：循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。存储结构：循环链表核心算法：循环队列的入队，出队，判队满，判队空。输入数据：男生人数、女生人数，歌曲数量输出数据：每一首歌曲播放时，男生和女生搭配情况（只输出编号即可）当要查找的男女搭配时输出歌曲编号，和他们搭配的总次数。通过以上分析，该程序具有可行性。.算法的流程DeQueue确孔男女一个数和曲数L犯kDeQueue确孔男女一个数和曲数L犯k和靠我的编号Pmit函数结束IiiitQ.算法设计分析调试过程中出现的问题及解决方法：问题：在构造队列时，设队列分配的最大空间为男女生的个数，此时便无法根据Q.front=Q.rear来判别队列空间是〃空〃还是〃满〃，因此，在入队操作即插入一个新元素作为新的队尾元素时出现了问题，即最后一位同学无法入队。解决方法：将队列分配的最大空间至少再增加一个'(()>p0P<|eo6)a|iq/v\：()>pop+iie/v\=|eo6：|eo6厂>pop)(iie/v\厂>pop)daa|spiOA'anan^)>|U!~|{JeajNuclij}pnjisppadXiLildsnsnb¥即。业^xau¥apoNdprij^s：uunuiui}apoNdpnj^sppadXi'uuaisXsiuippadXi//I-MOldySAO9uipp#0XO决三9uipp#IXO9uipp#0SSlVd9uipp#ISnyl^uipp#093ZISXVIAI9uipp#<q,DO||euj>apnpui#vipuuR〉apnpui#<q,O!pis>apnpu!#<q'6uuis>apnpui#鼠V1T9voidInitQ(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)(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);}voidprintM(LinkQueue&M,inti)(QueuePtrp;intn=1;while(n<i)(printf("_");n++;}p=M.front->next;while(M.rear!=p)(printf("%d",p->num);p=p->next;)printf("%d\n",p->num);)intmain()(intm,n,k,i,a,b;intcount=0,num;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++)(system("CLS");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)(count++;printf("第％d曲是要查找的男女生跳舞\n",i);)sleep(3000);DeQueue(F,num);EnQueue(F,num);DeQueue(M,num);EnQueue(M,num);）printf（"该对男女生共跳舞％d次3”工。口位）;

system("PAUSE");return0;.运行结果分析测试及运行结果测试输入数据：男女生的个数曲子数和要查找的男女生编号输出结果为：每首曲子男女生搭配的情况程序运行界面：:\DocuAentsaridSettings\Ad>iiiistrator\^ffi\VC-M-\Debiig\Cpp1.exe 1234RfiF 22451%懿器靡友生和第:\DocuAentsaridSettings\Ad>iiiistrator\^ffi\VC-M-\Debiig\Cpp1.exe 1234RfiF 22451%懿器靡友生和第2号男生Ipressanykeytocontinue『△玄生数量：6『人舅生痛量।S『曲手号：？『人要查找的男生编号：4必浸至神前女生哧与：3厩嚼鬻］旱第遥在牛和第i岩耳牛F2 451月前跳舞的是第2号M生和第2号月生博宿曲子 345612r_j4112厩曾岸是第3号文生利第3号月生L__4Efcl2345123目褪瞬的是第4号芭生前第4号同生国潜面子 5t1234 51234P前跳用勺是第5弓乂生工□第5弓男生懦清曲子 612345.12345.收获及体会通过一周的学习和实践，解决实际问题（学生搭配问题），让我对循环队列有了更深的了解，对数据结构产生了浓厚的兴趣，同时也让我提高了解决实际问题的能力。我们要不断的通过上机来提高自己的学习水平，在上机的同时改正了自己对某些算法的错误使用，使自己在通过程序解决问题时抓住关键算法，有了算法设计思想和流程图，并用C语言描绘出关键算法。参考文献[1]数据结构（C语言版）严蔚敏吴伟明编著，清华大学出版社[2]C语言程序设计（第三版）谭浩强著，清华大学出版社致谢首先，我要感谢学校给我们提供了此次课程设