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