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

数据结构课 程 设 计 题 目 学生搭配问题 学生姓名 董甜 学 号 20092344033 院 系 滨江学院专 业 软件工程指导教师 宣文霞二一 年 十二 月 十五 日学生搭配问题一、 设计题目一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴。请设计一系统模拟动态地显示出上述过程,要求如下:（1）输出每曲配对情况（2）计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值.二、 运行环境本课题的程序设计和测试等环节都是在Windows7操作系统下完成，软件的编译测试环境为vc6.0 以c语言编写的。软件的硬件运行需求非常低，任何计算机都可运行。三、算法设计的思想基本思路：队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。 循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。（1） 要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列SqQueue和SqQueue2。（2） 将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输出，这是循环队列固有的特性。（3） 利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。（4） 循环队列的长度分别设为男女生的个数即可。（5） 在计算机终端输出的结果是：根据要求输出男生女生搭配情况 关键问题: 循环队列的应用解决方法：数据模型（逻辑结构）: 循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。存储结构: 循环链表核心算法: 循环队列的入队，出队，判队满，判队空。输入数据: 男生人数、女生人数，歌曲数量输出数据: 每一首歌曲播放时，男生和女生搭配情况（只输出编号即可）当要查找的男女搭配时输出歌曲编号，和他们搭配的总次数。通过以上分析，该程序具有可行性。 四、算法的流程图五、算法设计分析调试过程中出现的问题及解决方法：问题：在构造队列时，设队列分配的最大空间为男女生的个数，此时便无法根据Q.front=Q.rear来判别队列空间是“空”还是“满”,因此，在入队操作即插入一个新元素作为新的队尾元素时出现了问题，即最后一位同学无法入队。解决方法：将队列分配的最大空间至少再增加一个六、源代码#include #include#include #include #define MAXSIZE 60#define TRUE 1 #define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1typedef int system;typedef struct QNode int num;struct QNode *next;QNode,* QueuePtr;typedef structQueuePtr 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;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-next;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(nnext;while(F.rear!=p) printf(%d ,p-num);p=p-next;printf(%d n,p-num);void printM(LinkQueue &M,int i) QueuePtr p;int n=1;while(nnext;while(M.rear!=p) printf(%d ,p-num);p=p-next;printf(%d n,p-num);void main() int m,n,k,i,a,b;int count=0,num;QueuePtr p,q;LinkQueue F;LinkQueue M;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;inext;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次n,count);七、运行结果分析测试及运行结果： 测试输入数据：男女生的个数曲子数和要查找的男女生编号输出结果为：每首曲子男女生搭配的情况程序运行界面：八、收获及体会通过一周的学习和实践，解决实际问题（学生搭配问题），让我对循环队列有了更深的了解，对数据结构产生了浓厚的兴趣，同时也让我提高了解决实际问题的能力。我们要不