队列的应用——舞伴配对问题(共5页).doc
精选优质文档-倾情为你奉上实 验 项 目队列的应用舞伴配对问题项 目 类 型综合型完 成 时 间2009-10-20实 验 目 的及 要 求掌握队列的类型定义方法；理解和掌握循环队列解决假溢出的方法，并能灵活运用以上队列知识对现实生活中的实际问题提出解决方案。【实验过程】（实验步骤、绘图、记录、数据、分析、结果）实验内容：a. 利用循环队列模拟舞伴配对问题：在舞会上，男、女各自排成一队。舞会开始时。依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，则较长的那一队中未配对者等待下一轮舞曲。b. 假设初始男、女人数及性别已经固定，舞会的轮数从键盘输入。试模拟解决上述舞伴配对问题。要求：从屏幕输出每一轮舞伴配对名单，如果在该轮有未配对的，能够从屏幕显示下一轮第一个出场的未配对者的姓名。实验步骤：#include<stdio.h>#include<string.h>#include<stdlib.h>typedef 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=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=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();printf("请输入男舞伴的名字:n");for(i=0;i<b;i+)gets(str);EnQueue(Q1,str); printf("请输入女舞伴的人数:n");scanf("%d",&g);ch=getchar();printf("请输入女舞伴的名字:n");for(i=0;i<g;i+)gets(str);EnQueue(Q2,str);printf("请输入舞会的轮数:n");scanf("%d",&ls);if(b<g)k=b;elsek=g;for(i=0;i<ls;i+)printf("第%d轮数配对如下:n",i+1);for(j=0;j<k;j+)DeQueue(Q1,boy); DeQueue(Q2,girl);printf("%s<->%sn",boy,girl);EnQueue(Q1,boy); EnQueue(Q2,girl);if(b<g)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,Q2);实验运行结果教师批阅评语：成绩评定教师签名: 年 月 日优秀良好中等及格不及格专心-专注-专业
