队列的应用–舞伴问题

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

2、问题分析
先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性,可用队列作为算法的数据结构。
在算法中,假设男士和女士的记录存放在一个数组中作为输入,然后依次扫描该数组的各元素,并根据性别来决定是进入男队还是女队。当这两个队列构造完成之 后,依次将两队当前的队头元素出队来配成舞伴,直至某队列变空为止。此时,若某队仍有等待配对者,算法输出此队列中等待者的人数及排在队头的等待者的名 字,他(或她)将是下一轮舞曲开始时第一个可获得舞伴的人。

3、具体算法及相关的类型定义
typedef struct{
char name[20];
char sex;  //性别,’F’表示女性,’M’表示男性
}Person;
typedef Person DataType;  //将队列中元素的数据类型改为Person

void DancePartner(Person dancer[],int num)
{//结构数组dancer中存放跳舞的男女,num是跳舞的人数。
int i;
Person p;
CirQueue Mdancers,Fdancers;
InitQueue(&Mdancers);//男士队列初始化
InitQueue(&Fdancers);//女士队列初始化
for(i=0;i<num;i++){//依次将跳舞者依其性别入队
p=dancer[i];
if(p.sex==’F’)
EnQueue(&Fdancers.p);   //排入女队
else
EnQueue(&Mdancers.p);   //排入男队
}
printf(“The dancing partners are: \n \n”);
while(!QueueEmpty(&Fdancers)&&!QueueEmpty(&Mdancers)){
//依次输入男女舞伴名
p=DeQueue(&Fdancers);     //女士出队
printf(“%s        “,p.name);//打印出队女士名
p=DeQueue(&Mdancers);     //男士出队
printf(“%s\n”,p.name);    //打印出队男士名
}
if(!QueueEmpty(&Fdancers)){ //输出女士剩余人数及队头女士的名字
printf(“\n There are %d women waitin for the next  round.\n”,Fdancers.count);
p=QueueFront(&Fdancers);  //取队头
printf(“%s will be the first to get a partner. \n”,p.name);
}else
if(!QueueEmpty(&Mdancers)){//输出男队剩余人数及队头者名字
printf(“\n There are%d men waiting for the next   round.\n”,Mdacers.count);
p=QueueFront(&Mdancers);
printf(“%s will be the first to get a partner.\n”,p.name);
}
}//DancerPartners

Tagged on:

One thought on “队列的应用|一路上

发表评论