1.问题描述

假设在周末舞会上，男士和女士进入舞厅，各自排成一队，跳舞开始时，依次从男队和女队的队头各出一人配成舞伴。若两队初始人数不相同，那么较长的那一对中未配对者等待下一轮舞曲，试写一种算法模拟上面的舞伴问题

2.问题分析

我们可以看出这是一个典型的队列问题，我们只需要把男士队和女士队看成队列，我们可以把男士和女士的信息都存储在一个数组中，再根据不同的性别存储到不同的队列中。然后开始给队列配对，当有一个队列为空的时候，另外一个队列有等待者，则输出队头等待者的姓名，此人将是下一个可以获得舞伴的人

3.代码分析

#include<iostream> using namespace std; #define MAXSIZE 100 #define Status int #define OK 1 #define ERROR 0 #define QElemType Person typedef struct{//跳舞者的个人信息 char name[20];char sex; }Person; typedef struct{Person *base;int font;int rear; }SqQueue; Status InitQueue(SqQueue &Q)//队列初始化 {Q.base=new QElemType[MAXSIZE];if(!Q.base)exit(0);Q.font=Q.rear=0;return 0; } Status EnQueue(SqQueue &Q,QElemType e)//入队 {if((Q.rear+1)%MAXSIZE==Q.font)return ERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;return OK; } Status DeQueue(SqQueue &Q,QElemType &e)//出队 {if(Q.font==Q.rear)return ERROR;e=Q.base[Q.font];Q.font=(Q.font+1)%MAXSIZE;return OK; } QElemType GetHead(SqQueue Q)//得到队列头元素 {if(Q.font!=Q.rear)return Q.base[Q.font]; } Status QueueEmpty(SqQueue Q) {if(Q.font==Q.rear)return OK;return ERROR; } void DancePartner(Person dance[],int num)//dance表示跳舞男女的信息，num表示跳舞的人数 {SqQueue Mdancers,Wdancers;Person p;InitQueue(Mdancers);InitQueue(Wdancers);for(int i=0;i<num;i++){p=dance[i];if(p.sex=='M')EnQueue(Mdancers,p);elseEnQueue(Wdancers,p); }cout<<"The dancing partners are:\n";while(!QueueEmpty(Wdancers)&&!QueueEmpty(Mdancers)){DeQueue(Wdancers,p);cout<<p.name<<" ";DeQueue(Mdancers,p);cout<<p.name<<endl;}if(!QueueEmpty(Wdancers)){p=GetHead(Wdancers);cout<<"在第二轮舞曲才获得舞伴的女士为："<<p.name<<endl; }if(!QueueEmpty(Mdancers)){p=GetHead(Mdancers);cout<<"在第二轮舞曲才获得舞伴的男士为："<<p.name<<endl; }} int main() {int n;cout<<"请输入跳舞人的个数：";cin>>n; Person dance[n];cout<<"请依次输入跳舞人的信息\n";for(int i=0;i<n;i++){getchar(); cout<<"姓名：";cin>>dance[i].name;cout<<"性别：";cin>>dance[i].sex; }DancePartner(dance,n);}

例子：

总结

以上是生活随笔为你收集整理的循环队列之舞伴问题(含源码详解)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。