【数据结构】第3章栈和队列实验3：循环队列+舞伴问题

蔚落 2022-11-28 03:50 284阅读 0赞

【循环队列的初始化、判空、判满、长度、取队头元素、入队、出队、遍历；舞伴问题】实验报告+完整代码

--------------------

## 一、实验目的和要求 ##

（1）熟悉C++的上机环境，进一步掌握C++的结构特点；  
（2）掌握循环队列——队列的顺序表示和实现。

## 二、实验环境 ##

Windows10, CodeBlocks.

## 三、实验内容及实施 ##

【实验内容】  
1、初始化队列(清空)；  
2、入队；  
3、出队;  
4、求队列长度；  
5、判断队列是否为空；  
6、判断队列是否为满；  
7\*、舞伴问题。  
【源程序】

#include<bits/stdc++.h>
    using namespace std;
    typedef int Status;
    typedef int QElemType;
    #define OVERFLOW -1
    #define ERROR 0
    #define OK 1
    
    //-----队列的顺序存储结构-----
    int MAXQSIZE = 100;		//舞伴问题需要对队列最大值进行限制，为方便修改在此用int定义啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！！！
    typedef struct 
    {
        
        QElemType *base;    //储存空间的基地址
        int front;          //头指针
        int rear;           //尾指针
    }SqQueue;
    
    SqQueue Q, QA, QB;
    
    //1、循环队列初始化
    Status InitQueue(SqQueue &Q)
    {
        
        Q.base = new QElemType[MAXQSIZE];   //为队列分配一个最大容扯为MAXSIZE的数组空间
        if(!Q.base)
            exit(OVERFLOW);                 //存储分配失败
        Q.front = Q.rear = 0;               //头指针和尾指针为0，队列为空
        return OK;
    }
    
    //4、循环队列判空
    Status QueueEmpty(SqQueue Q)
    {
        
        if(Q.front == Q.rear)
            return OK;
        else
            return ERROR;
    }
    
    //5、循环队列长度
    int QueueLength(SqQueue Q)
    {
        //返回Q的元素个数，即队列的长度
        return(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
    //非循环队列Q.rear - Q.front，循环队列可能为负，故先加再模
    }
    
    //6、循环队列取队头元素
    QElemType GetHead(SqQueue Q)
    {
        //返回Q队头元素，不修改队头指针
        if(Q.front != Q.rear)           //队列非空
            return Q.base[Q.front];      //返回队头元素的值，队头指针不变
    }
    
    //7、循环队列入队
    Status EnQueue(SqQueue &Q, QElemType e)
    {
        //插入元素e为Q 的新队尾元素
        if((Q.rear + 1) % MAXQSIZE == Q.front)  //尾指针在循环意义上加1后等于头指针，表明队满
            return ERROR;
        Q.base[Q.rear] = e;                     //新元素插入队尾
        Q.rear = (Q.rear + 1) % MAXQSIZE;       //队尾指针加1
        return OK;
    }
    
    //8、循环队列出队
    Status DeQueue(SqQueue &Q, QElemType &e)
    {
        //删除Q的队头元素，用e返回其值
        if(Q.front == Q.rear)
            return ERROR;                   //队空
        e = Q.base[Q.front];                //保存队头元素
        Q.front = (Q.front + 1) % MAXQSIZE; //队头指针加1
        return OK;
    }
    
    //9、循环链表遍历
    Status QueueTraverse(SqQueue Q)
    {
        
        if(Q.front == Q.rear)
            return ERROR;  
        for(int i = Q.front; i < Q.rear; i++)
            cout<<Q.base[i]<<' ';
        cout<<'\n';
        return ERROR;
    }
    
    //10、循环队列判满
    Status QueueFull(SqQueue Q)
    {
        
        if((Q.rear + 1) % MAXQSIZE == Q.front)
            return OK;
        else
            return ERROR;
    }
    
    //实验3：循环队列+舞伴问题
    int main()
    {
        
        cout<<"------------菜单-----------"<<'\n';
        cout<<" 操作0：退出程序"<<'\n';
        cout<<" 操作1：初始化队列(清空)"<<'\n';
        cout<<" 操作2：入队"<<'\n';
        cout<<" 操作3：出队"<<'\n';
        cout<<" 操作4：求队列长度"<<'\n';
        cout<<" 操作5：判断队列是否为空"<<'\n';
        cout<<" 操作6：判断队列是否为满"<<'\n';
        cout<<" 操作7：舞伴问题"<<'\n';
        cout<<"---------------------------"<<'\n';
        int a, m, flag = 1;
        while(flag)
        {
        
            cout<<'\n'<<"请选择要执行的操作：";
            cin>>a;
            switch(a)
            {
        
            case 0:
            {
        
                flag = 0;
                cout<<"感谢使用本程序，祝您生活愉快！"<<'\n';
                break;
            }
            case 1:
            {
        
                InitQueue(Q);
                cout<<"队列创初始化完毕！" <<'\n';
                break;
            }
            case 2:
            {
        
                QElemType e;
                cout<<"请输入您想要在队尾插入的元素：";
                cin>>e;
                if(EnQueue(Q, e))
                {
        
                    cout<<"元素"<<e<<"已入队：";
                    QueueTraverse(Q);
                }
                if(QueueFull(Q))
                    cout<<"队列为满！"<<'\n';
                break;
            }
            case 3:
            {
        
                QElemType e;
                if(DeQueue(Q, e))
                {
        
                    cout<<"元素"<<e<<"已出队：";
                    QueueTraverse(Q);
                }
                if(QueueEmpty(Q))
                    cout<<"队列为空！"<<'\n';
                break;
            }
            case 4:
            {
        
                cout<<"队列的长度为："<<QueueLength(Q)<<'\n';
                break;
            }
            case 5:
            {
        
                if(QueueEmpty(Q))
                    cout<<"队列为空！"<<'\n';
                else
                    cout<<"队列非空！"<<'\n';
                break;
            }
            case 6:
            {
        
                if(QueueFull(Q))
                    cout<<"队列为满！"<<'\n';
                else
                    cout<<"队列不满！"<<'\n';
                break;
            }
            case 7:
            {
        
                int m, f;
                QElemType mm, ff;
                cout<<"----------------------舞伴问题描述如下------------------------"<<'\n' <<
                "假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。"<<'\n'<<
                "开始跳舞时，依次从男队和女队的队头各出一人配成舞伴。"<<'\n'<<
                "若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。"<<'\n' <<
                "--------------------------------------------------------------"<<'\n';
                cout<<"请输入男队的人数：" ;
                cin>>m;
                MAXQSIZE = m + 1;
                InitQueue(QA);
                for(int i = 1; i <= m; i++)
                    EnQueue(QA, i);
                cout<<"已构建男士队列QA：";
                QueueTraverse(QA);
                cout<<"请输入女队的人数：" ;
                cin>>f;
                MAXQSIZE = f + 1;
                InitQueue(QB);
                for(int i = 1; i <= f; i++)
                    EnQueue(QB, i);
                cout<<"已构建女士队列QB：";
                QueueTraverse(QB);
                cout<<"配对结果如下："<<'\n';
                int tmp = max(m, f);
                while(tmp--)
                {
        
                    MAXQSIZE = m + 1;
                    DeQueue(QA, mm);
                    EnQueue(QA, mm);
                    MAXQSIZE = f + 1;
                    DeQueue(QB, ff);
                    EnQueue(QB, ff);
                    cout<<mm<<" - "<<ff<<'\n';
                }
                cout<<"所有人已分配完毕！" <<'\n';
                break;
            }
            }
        }
        return 0;
    }

## 四、实验结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 1]

## 五、实验讨论 ##

（1）熟悉了C++的上机环境，进一步掌握C++的结构特点；  
（2）掌握了循环队列的表示和实现。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/c7f5948949484f04b971a4120f69b84d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/a3aa4a93e89b4fdebc9bbd23123b264b.png