【练习】舞伴配对问题

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

• 类型定义

#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*/
   else
       return 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);   /*排入女队*/
        else
            EnQueue(&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);
}

• 测试结果