学习队列的作用队列的应用--舞伴问题

向右看齐 2022-07-14 13:20 233阅读 0赞

**队列的应用--舞伴问题**    
  
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