【练习】舞伴配对问题

本文主要是介绍【练习】舞伴配对问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各处一人配成舞伴。若两队初始人数不相同，则较长的那一对中未配对者等待下一轮舞曲。请模拟上述舞伴配对问题。
分析：该问题具有先进先出特性，可通过顺序循环队列存储结构实现。假设男士和女士的记录存放在一个数组中作为输入，然后一次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，一次将两队当前的对头元素出队来配成舞伴，直至某队列变空为止。此时，若某队列仍有等待配对者，则输出次队列中等待着的人数及排在对头的等待者的名字，他（或她）将是下一轮舞曲开始时的第一个可获得舞伴的人。

类型定义

#include<stdio.h>
#define QueueSize 10
typedef struct{char name[20];char sex;  /*性别，'F'表示女性，'M'表示男性*/
}Person;
typedef Person DataType;  /* 将队列中元素的数据类型改为Person */
typedef struct Squeue{  /*顺序队列类型定义*/DataType queue[QueueSize];int front,rear; /*队头指针和队尾指针*/
}SeqQueue;

函数文件

void InitQueue(SeqQueue *SQ)
/*将顺序队列初始化为空队列只需要把队头指针和队尾指针同时置为0*/
{SQ->front=SQ->rear=0;   /*把队头指针和队尾指针同时置为0*/
}
int QueueEmpty(SeqQueue SQ)
/*判断队列是否为空，队列为空返回1，否则返回0*/
{if(SQ.front==SQ.rear)        /*判断队头指针和队尾指针是否相等*/return 1;            /*当队列为空时，返回1；否则返回0*/elsereturn 0;
}
int EnQueue(SeqQueue *SQ,DataType e)
/*将元素x插入到顺序队列SQ中，插入成功返回1，否则返回0*/
{if(SQ->front==(SQ->rear+1)%QueueSize)                      /*在插入新的元素之前，判断队尾指针是否到达数组的最大值，即是否队列已满*/return 0;SQ->queue[SQ->rear]=e;   /*在队尾插入元素x */SQ->rear=(SQ->rear+1)%QueueSize;     /*队尾指针向后移动一个位置*/return 1;
}
int DeQueue(SeqQueue *SQ,DataType *e)
/*删除顺序队列中的队头元素，并将该元素赋值给e，删除成功返回1，否则返回0*/
{if(SQ->front==SQ->rear)  /*在删除元素之前，判断队列是否为空*/return 0;else{*e=SQ->queue[SQ->front];     /*将要删除的元素赋值给e*/SQ->front=(SQ->front+1)%QueueSize;   /*将队头指针向后移动一个位置，指向新的队头*/return 1;}
}
int GetHead (SeqQueue SQ,DataType *e)
/*取队头元素，并将该元素赋值给e，取元素成功返回1，否则返回0*/
{if(SQ.front==SQ.rear)       /*在取队头元素之前，判断顺序循环队列是否为空*/return 0;else{*e=SQ.queue[SQ.front];  /*将队头元素赋值给e，取出队头元素*/return 1;}
}void DancePartner(DataType dancer[],int num)
/*结构数组dancer中存放跳舞的男女，num是跳舞的人数*/
{int i;DataType p;SeqQueue Mdancers,Fdancers;InitQueue(&Mdancers);/*男士队列初始化*/InitQueue(&Fdancers);/*女士队列初始化*/for(i=0;i<num;i++){/*依次将跳舞者依其性别入队*/p=dancer[i];if(p.sex=='F')EnQueue(&Fdancers,p);   /*排入女队*/elseEnQueue(&Mdancers,p);   /*排入男队*/}printf("配对成功的舞伴分别是: \n");while(!QueueEmpty(Fdancers)&&!QueueEmpty(Mdancers)){/*依次输入男女舞伴名*/DeQueue(&Fdancers,&p);     /*女士出队*/printf("%s   ",p.name);/*打印出队女士名*/DeQueue(&Mdancers,&p);     /*男士出队*/printf("%s\n",p.name);    /*打印出队男士名*/}if(!QueueEmpty(Fdancers)){ /*输出女士剩余人数及队头女士的名字*/printf("还有%d名女士等待下一轮舞曲.\n",DancerCount(Fdancers));GetHead(Fdancers,&p);  /*取队头*/printf("%s 将在下一轮中最先得到舞伴. \n",p.name);}else if(!QueueEmpty(Mdancers)){/*输出男队剩余人数及队头者名字*/printf("还有%d名男士等待下一轮舞曲.\n",DancerCount(Mdancers));GetHead(Mdancers,&p);printf("%s 将在下一轮中最先得到舞伴.\n",p.name);}
}
int DancerCount(SeqQueue Q)
/*队列中等待配对的人数*/
{return (Q.rear-Q.front+QueueSize)%QueueSize;
}

主程序

void main()
{int i,n;DataType dancer[30];printf("请输入舞池中排队的人数:");scanf("%d",&n);for(i=0;i<n;i++){printf("姓名:");scanf("%s",dancer[i].name);getchar();printf("性别:");scanf("%c",&dancer[i].sex);}DancePartner(dancer,n);
}