队列的应用——舞伴配对问题

1、_实验项队列的应用舞伴配对问题目项目类综合型完 成 时2009-10-20型间实 验 目掌握队列的类型定义方法； 理解和掌握循环队列解决假溢出的方法，并能灵活运用以上队列知识对现实生活中的实际问题提出解的及 要决方案。求【实验过程】（实验步骤、绘图、记录、数据、分析、结果）实验内容：a. 利用循环队列模拟舞伴配对问题：在舞会上，男、女各自排成一队。舞会开始时。依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，则较长的那一队中未配对者等待下一轮舞曲。b. 假设初始男、女人数及性别已经固定，舞会的轮数从键盘输入。试模拟解决上述舞伴配对问题。要求：从屏幕输出每一轮舞伴配对名单，如果在该轮

2、有未配对的，能够从屏幕显示下一轮第一个出场的未配对者的姓名。实验步骤：#include#include#includetypedef struct qnodechar name10;struct qnode *next;qnode,*queueptr;typedef structqueueptr front;queueptr rear;linkqueue;void initqueue(linkqueue &q)精品资料_/ 构建一个空队列q.front=q.rear=(queueptr)malloc(sizeof(qnode);if(!q.front)exit(0);q.front-next=

3、q.front;/initqueuevoid enqueue(linkqueue &q,char *str)/ 将字符串入队queueptr p;p=(queueptr)malloc(sizeof(qnode);if(!p)exit(0);strcpy(p-name,str);p-next=null;q.rear-next=p;q.rear=p;void dequeue(linkqueue &q,char *str)/ 将结点删除后连接到队列的后方queueptr p;p=q.front-next;strcpy(str,p-name);q.front-next=p-next;if(q.rear

4、=p)q.rear=q.front;free(p);void gethead(linkqueue q,char *str)/ 若队列非空，取队头元素queueptr p;if(q.front!=q.rear)p=q.front-next;strcpy(str,p-name);void dancer(linkqueue &q1,linkqueue &q2)/ 实现配对，输出配对人名单，打印下一轮等待的人名char str15,boy15,girl15,ch;int b,g,i,k,ls,j;精品资料_printf(请输入男舞伴的人数 :n);scanf(%d,&b);ch=getchar();p

5、rintf(请输入男舞伴的名字 :n);for(i=0;ib;i+)gets(str);enqueue(q1,str);printf(请输入女舞伴的人数 :n);scanf(%d,&g);ch=getchar();printf(请输入女舞伴的名字 :n);for(i=0;ig;i+)gets(str);enqueue(q2,str);printf(请输入舞会的轮数 :n);scanf(%d,&ls);if(bg)k=b;elsek=g;for(i=0;ils;i+)printf(第%d轮数配对如下 :n,i+1);for(j=0;jk;j+)dequeue(q1,boy); dequeue(q2,girl);printf(%s%sn,boy,girl);enqueue(q1,boy); enqueue(q2,girl);if(bg)gethead(q2,str);printf(%s在等待 n,str);elsegethead(q1,str);printf(%s在等待 n,str);精品资料_void main()linkqueue q1,q2;initqueue(q1);initqueue(q2);dancer(q1