循环队列的应用

客官°小女子只卖身不卖艺 2022-07-16 13:29 207阅读 0赞

2016年7月31日17:47:47
        假设在周末的舞会上,男士们和女士们进入舞厅,各自排成一队,跳舞开始时,依次从男队和女队的队头各出一人配成舞伴.若初始人数不同,
        则较长的那一队中为配对者等待下一轮舞曲,现在要求写一算法模拟上述舞伴配对问题.该问题具有先进先出的特性,可使用队列作为算法的
        数据结构,
        1>首先应该解决的问题是,这些数据如何来存贮?
        我们可以定义一个一维数组来保存所有人的信息,人的信息有两部分;姓名和性别,
        2>需要保存队列中元素人的信息,就需要用户在键盘进行输入,如果是男士就进男队,女士就进女队列,
        需要设置两个队列,男士进男队列,女士进入女队列,因此必须有性别,而最后又一队可能会长一些,那么必定会等待下一个舞曲,那么这些人
        需要被打印出来,因此需要姓名
        3>每次从两个队列中各出队一个人,进行舞伴的匹配,直至某一队为空为止;
        4>当其中某一队为空时,则将另一队中其余元素打印还在等待的人数,以及队头的人的姓名和性别,他将是下一个舞曲中第一个被配舞伴的人;
        算法执行结束;

#include<stdio.h>
    #define MAXSIZE 100
    
    //参与跳舞人
    typedef struct  
    {
        char name[20];//姓名
        char sex;//性别
    }DataType;
    
    //顺序队列的结构体类型
    typedef struct 
    {
        DataType queue[MAXSIZE];//存贮队列元素的一维数组
        int front;//队头指针指示的是队头元素的位置
        int rear;//队尾指针指示的是队尾元素位置的下一个位置
    }SeqQueue;
    
    //函数前置声明
    void initSeqQueue(SeqQueue * Q );
    void traverseSeqQueue(SeqQueue * Q);
    int isEmpty(SeqQueue * Q);
    int isFull(SeqQueue * Q);
    int enSeqQueue(SeqQueue * Q,DataType element);
    int deSeqQueue(SeqQueue * Q,DataType * element);
    int getLength(SeqQueue * Q);
    int getHead(SeqQueue * Q);
    
    
    //初始化顺序队列
    void initSeqQueue(SeqQueue * Q)
    {
        Q->front = 0;
        Q->rear = Q->front;
        return;
    }
    
    //判断队列是否为空
    int isEmpty(SeqQueue * Q)
    {
        if(Q->front == Q->rear)
            return 1;
        else
            return 0;
    }
    
    //判断队列是否为满
    int isFull(SeqQueue * Q)
    {
        if(Q->front == (Q->rear+1) % MAXSIZE)
            return 1;
        else
            return 0;
    }
    
    //循环队列的入队列操作,入队成功返回1,入队失败返回0;
    int enSeqQueue(SeqQueue * Q,DataType element)
    {
        if( isFull(Q) )
        {
            //printf("队列已满,无法继续进队!\n");
            return 0;
        }
        else
        {
            Q->queue[Q->rear] = element;
            Q->rear = (Q->rear+1)%MAXSIZE;
            return 1;
        }
    }
    
    
    //循环队列出队列操作,出队成功返回1,出队失败返回0;
    int deSeqQueue(SeqQueue * Q,DataType * element)
    {
        if( isEmpty(Q) )
        {
            //printf("队列已空,无法继续出队!\n");
            return 0;
        }
        else
        {
            *element = Q->queue[Q->front];
            Q->front = (Q->front+1)%MAXSIZE;
            return 1;
        }   
    }
    
    //获取队列的长度
    int getLength(SeqQueue * Q)
    {
        return (Q->rear-Q->front+MAXSIZE)%MAXSIZE;
    }
    
    //获取队头元素
    int getHead(SeqQueue * Q,DataType * element)
    {
        if( isEmpty(Q) )
        {
            return 0;
        }
        else
        {
            *element = Q->queue[Q->front];
            return 1;
        }
    }
    
    //遍历循环队列
    void traverseSeqQueue(SeqQueue * Q)
    {
        int i;
    
        if(isEmpty(Q))
            return;
        else if(Q->front<Q->rear)
        {
            for(i = Q->front;i<Q->rear;i++)
            {
                printf("%10s%c ",Q->queue[i].name,Q->queue[i].sex); 
            }
        }
        else 
        {
            for( i = Q->front;i<MAXSIZE;i++)
            {
                printf("%10s%c ",Q->queue[i].name,Q->queue[i].sex);         
            }
            for(i = 0;i<Q->rear;i++)
            {
                printf("%10s%c ",Q->queue[i].name,Q->queue[i].sex); 
            }
        }
        return ;
    }
    
    void AssgnSeqQueue(SeqQueue * fQ,SeqQueue * mQ,int len)
    {
        int i;
        DataType e;
    
        for(i = 0;i<len;i++)
        {
            printf("请输入第%d个参加跳舞者信息:\n",i+1);
    
            printf("姓名:");
            scanf("%s",e.name);
            getchar();
            printf("性别F/M:");
            scanf("%c",&e.sex);
            if(e.sex == 'F')
            {
                enSeqQueue(fQ,e);
            }
            else
            {
                enSeqQueue(mQ,e);
            }
        }
        return;
    }
    
    //主函数
    int main(void)
    {
        int len;
        SeqQueue  fQ;
        SeqQueue  mQ;
        DataType  element;
        int i;
    
        //初始化两队列
        initSeqQueue(&fQ);
        initSeqQueue(&mQ);
    
        //将用户输入的参舞者根据性别保存到两队列中
        printf("请输入本次参加的人数:len=");
        scanf("%d",&len);
        AssgnSeqQueue(&fQ,&mQ,len);
    
        //将两队列中参舞者信息输出
        printf("女士队列:\n");
        traverseSeqQueue(&fQ);
        printf("\n");
        printf("男士队列:\n");
        traverseSeqQueue(&mQ);
        printf("\n");
    
        //输出匹配成功的舞伴
        printf("配对成功的舞伴分别是:\n");
        while((!isEmpty(&fQ))&&(!isEmpty(&mQ)))
        {
            deSeqQueue(&fQ,&element);
            printf("%s",element.name);
            printf(" ");
            deSeqQueue(&mQ,&element);
            printf("%s\n",element.name);
            printf(" ");
        }
    
        //当男士数量较多时
        if(!isEmpty(&mQ))
        {
            printf("还有%d名男士等待下一轮舞曲:\n",getLength(&mQ));
            getHead(&mQ,&element);
            printf("%s将在下一轮中最先得到舞伴:\n",element.name);
        }
    
        //当女士数量较多时
        else if(!isEmpty(&fQ))
        {
            printf("还有%d名女士等待下一轮舞曲:\n",getLength(&fQ));
            getHead(&fQ,&element);
            printf("%s将在下一轮中最先得到舞伴:\n",element.name);
        }
        printf("\n");
        return 0;
    }