栈和队列 - 栈和队列的应用实例 - 队列的应用实例
队列的应用 舞伴问题
问题叙述
假设在周末舞会上 男士们和女士们进入舞厅时 各自排成一队 跳舞开始时 依次从男队和女队的队头上各出一人配成舞伴
若两队初始人数不相同 则较长的那一队中未配对者等待下一轮舞曲 现要求写一算法模拟上述舞伴配对问题
问题分析
先入队的男士或女士亦先出队配成舞伴 因此该问题具体有典型的先进先出特性 可用队列作为算法的数据结构
在算法中 假设男士和女士的记录存放在一个数组中作为输入 然后依次扫描该数组的各元素 并根据性别来决定是进入男队还
是女队 当这两个队列构造完成之后 依次将两队当前的队头元素出队来配成舞伴 直至某队列变空为止 此时 若某队仍有等待配
对者 算法输出此队列中等待者的人数及排在队头的等待者的名字 他(或她)将是下一轮舞曲开始时第一个可获得舞伴的人
具体算法及相关的类型定义
typedef struct{
char name[ ];
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= ;i <num;i++){ p="" 依次将跳舞者依其性别入队
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
lishixinzhi/Article/program/sjjg/201311/23917
