数据结构课程设计-学生搭配问题

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

2、）先建立两个循环队列 SqQueue和 SqQueue2（2）将男生、女生两组人分别存入这两个队列。（3）将男女生分别进行入队列和出队列操作，且实现搭配输出。（4）循环队列的长度分别设为男女生的个数即可。（5）在计算机终端输出的结果是：根据要求输出男生女生搭配情况。预期结果每一首歌曲播放时，男生和女生搭配情况（只输出编号即可）当 要查找的男女搭配时输出歌曲编号， 和他们搭配的总次数。通过以上 分析，该程序具有可行。计划与进 步的安排1、2012年11月20日之前寻找到解决问题思搭配问题的路2、2012年11月25日之前必须编写出程序3、2012年11月26日之前检查程序的运行并找出错误程序4、

3、2012年11月29日之前找到解决错误的方法5、2012年11月30日写数据结构课程设计报告摘要针对学生搭配问题，循环队列是一种重要的链式结构，其特殊性在于需附设 两个指针 front 和 rear 分别指示对头元素及队尾元素的位置且对头和队尾相邻 接。在程序的设计过程中，运用了各种基本的算法，有判断队空及队满，出队， 入队等. 循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元 依次存放从队列头到队列尾的元素外，尚需附设两个指针 front 和 rear 分别指 示队列头元素和队列尾元素的位置。 学生搭配问题是典型的只有采用循环队列才 能解决的问题，实验表明该算法的空间复杂度优于

4、其他算法。 本文用循环队列会很好的把这个程序设计出来， 会有很好的效果。 得出的程 序运行结果能够很形象的把结果表示出来。关键词：学生配对，数据结构，循环队列。摘要 1 设计题目 目录错误! 未定义书签错误! 未定义书签2 运行环境 13 算法设计的思想 14 算法的流程图 25 算法设计分析 26 源代码 37 运行结果分析 88 收获及体会 8参考文献 9致谢 9学生搭配问题1. 设计题目一班有m个女生,有n个男生（m不等于n）,现要开一个舞会.男女生分别编 号坐在舞池的两边的椅子上 . 每曲开始时 , 依次从男生和女生中各出一人配对跳 舞, 本曲没成功配对者坐着等待下一曲找舞伴。 请设计

5、一系统模拟动态地显示出 上述过程,要求如下:（1）输出每曲配对情况（2）计算出任何一个男生（编号为X）和任意女生（编号为丫），在第K曲配对跳 舞的情况.至少求出K的两个值。2. 运行环境本课题的程序设计和测试等环节都是在 Win dows7操作系统下完成，软件的 编译测试环境为 vc6.0 以 c 语言编写的。软件的硬件运行需求非常低，任何计 算机都可运行。3. 算法设计的思想基本思路：队列（Queue是只允许在一端进行插入，而在另一端进行删除 的运算受限的线性表。循环队列是在队列的顺序存储结构中， 除了用乙组地址连续的存储单元依次 存放从队列头到队列尾的元素外，尚需附设两个指针 front

6、和 rear 分别指示队 列头元素和队列尾元素的位置。循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。 循环队列的入队，出队，判队满，判队空。（1） 要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环 队列 SqQueue和 SqQueue2（2）将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输 出，这是循环队列固有的特性。（3）利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实 现搭配输出。（4）循环队列的长度分别设为男女生的个数即可。（5）在计算机终端输出的结果是：根据要求输出男生女生搭配情况 关键问题 : 循环队列的应用解决方法：数据模型

7、（逻辑结构） : 循环队列（两个），将男生、女生两组 人分别存放，以实现循环配对输出。存储结构 : 循环链表核心算法：循环队列的入队，出队，判队满，判队空。输入数据：男生人数、女生人数，歌曲数量输出数据：每一首歌曲播放时，男生和女生搭配情况（只输出编号即可）当 要查找的男女搭配时输出歌曲编号，和他们搭配的总次数。通过以上分析，该程序具有可行性。4. 算法的流程图5. 算法设计分析调试过程中出现的问题及解决方法：问题：在构造队列时，设队列分配的最大空间为男女生的个数， 此时便无法 根据Q.front=Q.rear来判别队列空间是“空”还是“满”,因此，在入队操作即 插入一个新元素作为新的队尾元素

8、时出现了问题，即最后一位同学无法入队。解决方法：将队列分配的最大空间至少再增加一个6. 源代码 #include <string.h> #include<stdio.h> #include <time.h> #include <malloc.h> #define MAXSIZE 60 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 /typedef int system; typedef struct QNode int num; st

9、ruct QNode *next; QNode,* QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue; void sleep( clock_t wait ) clock_t goal; goal = wait + clock(); while( goal > clock() ) ; void InitQ(LinkQueue &Q) QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);Q.front=p;Q.rear=p;Q.front->next=NULL;

10、void EnQueue(LinkQueue &Q,int num)QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode); p->num=num;p->next=NULL;Q.rear->next=p;Q.rear=p;void DeQueue(LinkQueue &Q, int &num)QueuePtr p,q;if(Q.front=Q.rear)printf(" 队列为空 "); p=Q.front->next;num=p->num;Q.front->next=p->n

11、ext;q=p->next;if(Q.rear=q)Q.rear=Q.front;free(p);void printF(LinkQueue &F,int i)QueuePtr p;int n=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);void printM(LinkQueue &M,int i)Que

12、uePtr p;int n=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);int main()int m,n,k,i,a,b;int count=0,num;QueuePtr p,q;LinkQueue F;LinkQueue M;printf(" 请输入女生数量： "); scanf("%d&qu

13、ot;,&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+)EnQue

14、ue(F,i);for(i=1;i<=n;i+)EnQueue(M,i); for(i=1;i<=k;i+)system("CLS");prin tf(" 第4 首曲子 n",i); printF(F,i);printM(M,i);p=F.front->next;q=M.front->next;printf("目前跳舞的是第d号女生和第c号男生n",p->num,q->num);if(p->num=a&&q->num=b)count+;printf("第4曲是要

15、查找的男女生跳舞n",i);sleep(3000);DeQueue(F,num);EnQueue(F,num);DeQueue(M,num);EnQueue(M,num);printf("该对男女生共跳舞d次n",count);system("PAUSE");return 0;7. 运行结果分析测试及运行结果测试输入数据：男女生的个数曲子数和要查找的男女生编号 输出结果为：每首曲子男女生搭配的情况程序运行界面：C; DocuBeBts and Sett ingsX&dBin 1 st ratoiXMQTC-i-rDebugCppI

16、71; exeofrorDECS生生男女 量量k的 菱：養 主主£& -m 了要冇竭男生2 3 4 5 62 3 4 5前ft舞拘是穿1吕女生和第丄号男生245612 自 4 5 13 4 5 6 1 2 4512g黔澎量备;号女生和售4号男生S 6 1 2 45 12 3 4寻摯界勺是寰号女生币诵帝号男生S 1 2 3 4 5L 2 3 4 5屠曙醪是篥6专女生和第丄号男生1 2 3 4 5 A2 3 4 5 1SW舞旳是第i弓女比和第2号男生 该动男女掘共趾舞0次Press &nj keu to continuem 5目胃廻沸旳罡算琦女主和弟3号男生 躬首曲子4 5 6 12 38. 收获及体会通过一周的学习和实践，解决实际问题（学生搭配问题），让我对循环队列 有了更深的了解，对数据结构产生了浓厚的兴趣，同时也让我提高了解决实际问 题的能力。我们要不断的通过上机来提高自己的学习水平， 在上机的同时改正了自己对 某些算法的错误使用，使自己在通过程序解决问题时抓住关键算法， 有了算法设 计思想和流程图，并用C语言描绘出关键算法。参考文献1 数据结构（ C 语言版）严蔚敏 吴伟明 编著，清华大学出版社2 C 语言程序设计（第三版）谭浩强 著，清华大学出版社致谢首先，我要感谢学校给我们提供了此次课程设计的机会， 能让同学们在