学生搭配问题课程设计

《学生搭配问题课程设计》由会员分享，可在线阅读，更多相关《学生搭配问题课程设计（21页珍藏版）》请在金锄头文库上搜索。

1、课课 程程 设设 计计课程设计名称：课程设计名称： 学生搭配问题 专专 业业 班班 级级 ： 学学 生生 姓姓 名名 ： 学学 号号 ： 指指 导导 教教 师师 ： 课程设计时间：课程设计时间： 2010-6-19-2010-6-23 1专业专业 数据结构数据结构 课程设计任务书课程设计任务书学生姓名学生姓名班级班级学号学号题题 目目学生搭配问题学生搭配问题课题性质课题性质工程设计工程设计课题来源课题来源自拟自拟指导教师指导教师同组姓名同组姓名主要内容主要内容一班有 m 个女生,有 n 个男生(m 不等于 n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,男生和女生依次

2、配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴.请设计一系统模拟动态地显示出上述过程,要求如下:1) 输出每曲配对情况2) 计算出任何一个男生(编号为 X)和任意女生(编号为 Y),在第 K 曲配对跳舞的情况.至少求出 K 的两个值.3) 尽量设计出多种算法及程序,可视情况适当加分提示:用队列来解决比较方便.任务要求任务要求1应用数据结构基础知识进行实际问题求解与分析2作为一个完整的系统，应具有友好的界面和较强的容错能力3上机能正常运行代码4分析算法的运行效率5按要求撰写课程设计报告和设计总结。参考文献参考文献1C 程序设计（第二版），谭浩强，北京，清华大学出版社，1999.2Visual

3、C+实用教程（第一版），张荣梅、梁晓林，冶金工业出版社，2004.3C+实用教程（第一版），杨明军、董亚卓、汪黎，人民邮电出版社，2002.4数据结构（C 语言版），严蔚敏，吴伟民，清华大学出版社，审查意见审查意见指导教师签字：指导教师签字： 2教研室主任签字：教研室主任签字： 年年 月月 日日 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页1 需求分析核心问题：循环队列的应用数据模型（逻辑结构）：循环队列（两个） ，将男生、女生两组人分别存放，以后实现循环配对输出。存储结构：循环链表核心算法：循环队列的入队，出队，判队满，判队空。输入数据：男生人数、女生人

4、数，歌曲数量输出数据：每一首歌曲播放时，男生和女生搭配情况（输出编号）当要查找的男女搭配时输出歌曲编号，和他们搭配的总次数。通过以上分析，该程序具有可行性。2 概要设计算法设计思想队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算限制的线性表。循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元一次存放从队列头到队列尾的元素外，尚需附设两个指针 front 和 rear 分别指示队列头和队列尾元素的位置。循环队列（两个） ，将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。（1）要模拟动态地显示出现题目中所要求的循环，我们要先建立两

5、个循环队列SqQueue 和 SqQueue2.（2）将男生、女生两组人分别存入这两个队列。以实现他们的配对输出，这是循环队列固有的特性。（3）利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。3（4）循环队列的长度分别设为男女生的个数即可。在计算机终端输出的结果是：根据要求输出男生女生搭配情况。3 运行环境硬件开发环境：PC 机 软件开发环境： 操作系统环境：W 4 开发工具和编程语言软件开发工具：Visual C+ 6.0 编程语言：C 语言5 详细设计建立链式循环队列来分别存储男生和女生，然后调用入队出队函数实现循环队列的配对输出。为了充分利用向量空间，克服上述存储

6、结构上溢现象的方法是将向量空间想象为一个首尾相接的圆环，存储在其中成为循环队列。再循环队列中进行入队、出队操作时，头指针仍要加 1，向前移动。只不过当头指针指向上界时其加 1 操作变为指向下界，这样就可以通过出队再入队来实现男生女生的循环搭配了。程序设计过程中的关键算法：程序设计过程中的关键算法：（1）关键算法之一：初始化队列Void InitQueue(LinkQueue P=(QueuePtr)malloc(sizeof(QNode); Q.front=p; Q.rer=p; Q.front-next=NULL; （2）关键算法之二：入队函数Void EnQueue(LinkQueue P

7、=(QueuePtr)malloc(sizeof(QNode); P-num=num; p-next=NULL; Q.rer-next=p;4Q.rer=p; （3）关键算法之三：出队函数Void DeQueue(LinkQueue 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); （4）关键算法之四：输出第 i 首曲子时女队的情况Void printf(LinkQueue I

8、nt n=1; While(nnext; While(F.rear!=p) Printf(“%d“,p-num); P=p-next; Printf(“%dn“,p-num); 6 调试分析测试数据：编号12345男生（5 人）abcde5女生（3 人）aabbccA（错误分类）曲子数10测试图如下：图图 6.16.1 数据测试图数据测试图测试中出现的问题描述：女生数量设定为 3，但实际输入女生数超过 3 没有错误警告，说明程序还存在一定的漏洞。在输入数据函数void CreateList_L(LinkList 6删除刚输入数据；提示重新输入；使得输入男生数（女生数）大于预设值时进行提醒，并进

9、行修正。7 测试结果测试输入数据：男女生的个数及姓名、曲子数和要查找的男女生编号编号12345男生abcde女生aabbcc曲子数10输出结果为：每首曲子男女生搭配的情况程序运行界面如下：7图图 7.1 输入数据时界面输入数据时界面8图图 7.2 输出每首曲子配对情况界面输出每首曲子配对情况界面9参考文献1 边肇祺，模式识别（第二版） ，北京：清华大学出版社,1988，25352 李永忠，几种小波变换的图像处理技术，西北民族学院学报（自然科学版） ，2001.6,22（3） ，15183 徐孝凯，数据结构实用教程（C/C+描述） 。北京：清华大学出版社,1999，20254 严蔚敏，数据结构题

10、集（C 语言版） 。北京：清华大学出版社，2006,36405 孙巧萍，数据结构实训教程。北京：科学出版社，2000,132210心得体会心得体会通过一周的学习和实践，解决实际问题（学生搭配问题） ，让我对循环队列有了更深的了解，对数据结构产生了浓厚的兴趣，同时也使我提高了解决问题的能力。以前我对数据结构（C 语言描述）的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对 C 语言中经常出现的错误也不了解，通过实践，是我在这几方面的认识有所提高。让自己有一定的能力去改正一些常见的错误语法，很高兴这一周的学习让我对数据结构有了新的认识，所以在以后的学习过程中，我会更加注重实践操作，

11、是自己更好的学好计算机。在这次课程设计中我们要学会利用时间，在规定的时间内完成我们的任务，要逐渐养成用用 C 语言编写程序的良好习惯。这些对我来说都是一种锻炼，一个知识积累的过程，一种能力的提高。要打好基础，才能用更好的办法，更简洁明了的程序解决问题，只有这样才能进一步的取得更好的成绩。在课程设计中的程序都比较复杂，所以需要我们要更加的细心，认真的完成每一步的操作，修改语法按照老师的指导思想来完成。与此同时也让我们增加了对程序和算法的进一步理解。总之我学到了很对东西，很感谢学校给我们这样一次锻炼的机会，也很感谢老师的指导。11附：附：程序代码#include #include #include

12、 #include #define MAX 200 #define MAXNAME 20typedef struct LNode int num;/编号char nameMAXNAME;char sex; /性别，F表示女性，M表示男性struct LNode *next; LNode, *LinkList;void sleep( clock_t wait ) /延迟函数 clock_t goal; goal = wait + clock(); while( goal clock() ) ; void CreateList_L(LinkList printf(“nntt 请输入女生数量：“);

13、scanf(“%d“,while(m=5)sleep(500);system(“CLS“);printf(“nntttto参加舞会学生名单on“); printf(“nntt 请输入女生数量：%d“,m);printf(“ntt 请输入男生数量：%dn“,n);printf(“ ttt * “);printf(“n ttt *欢迎参加舞会*n“);printf(“t tt * n“);printf(“tt 请输入学生的情况n“);for(j=i-4;j:%dn“,bj);printf(“tt 第%d 个人姓名:“,i+1);scanf(“%s“,ai);printf(“tt 性别:“);sca

14、nf(“%d“,/scanf(“sex:%d“,错错bi=choice;q=(LinkList)malloc(sizeof(LNode);if(q=NULL) exit(-1);13strcpy(q-name,ai);if(choice=1)numw+;q-num=numw;if(L1=NULL)L1=q;p1=q;/不带头结点elsep1-next=q;p1=q;p1-next=L1;/循环elsenumn+;q-num=numn;if(L2=NULL)L2=q;p2=q;/不带头结点 elsep2-next=q;p2=q;p2-next=L2;/循环 void Print1(LinkLis

15、t L,int m) LinkList p;int i;p=L;for(i=1;iname);printf(“%3c“, );p=p-next;14void Print2(LinkList LinkList q;for(i=1;iname);printf(“%3c“, );p=p-next;q=p;for(;iname);printf(“%3c“, );q=q-next;void Match(LinkList L1,LinkList L2,int m,int n) int k,i,j;LinkList p; printf(“nnnntttt o每曲配对情况o“);printf(“nntt 请输入歌曲的编号：“);while(k“);if(m“,k);printf(“nnnnntttt 第曲配对情况nnn“,i);