数据结构实验四:队列

实验四 队列的实现及应用

一、实验目的

1、掌握队列的类型定义方法。

2、理解和掌握循环队列解决假溢出的方法。

二、实验内容

1、利用循环队列模拟舞伴配对问题：在舞会上，男、女各自排成一队。舞会开始时。依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，则较长的那一队中未配对者等待下一轮舞曲。 2、假设初始男、女人数及性别已经固定，舞会的轮数从键盘输入。试模拟解决上述舞伴配对问题。 3、要求：从屏幕输出每一轮舞伴配对名单，如果在该轮有未配对的，能够从屏幕显示下一轮第一个出场的未配对者的姓名。

报告内容为小组共同完成

一、实验目的
1、掌握队列的类型定义方法
2、理解和掌握循环队列解决假溢出的方法
3、掌握队列的简单应用
4、理解算法与程序的关系，灵活运用队列算法。
二、实验内容
1、利用循环队列模拟舞伴配对问题：在舞会上，男、女各自排成一队。舞会开始时。依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，则较长的那一队中未配对者等待下一轮舞曲。
2、假设初始男、女人数及性别已经固定，舞会的轮数从键盘输入。试模拟解决上述舞伴配对问题。
3、要求：从屏幕输出每一轮舞伴配对名单，如果在该轮有未配对的，能够从屏幕显示下一轮第一个出场的未配对者的姓名。
三、代码实现

#include<iostream>
#include<string>
#define Maxsize 100
using namespace std;
typedef struct QElemType      //舞者
{
  string name;
}QElemType;
typedef struct
{
    QElemType * base;
    int Front;
    int Rear;
}SqQueue;
//构造空队列
void InitQueue(SqQueue& Q)
{
    Q.base = new QElemType[Maxsize];     //分配一个最大容量的数组空间
    Q.Front = Q.Rear = 0;         //头尾指针置为零
}
//入队
void EnQueue(SqQueue& Q, QElemType e)
{
    if ((Q.Rear + 1) % Maxsize == Q.Front)   //队满处理
        return ;
    Q.base[Q.Rear] = e;                  //将元素插入到队尾
    Q.Rear = (Q.Rear + 1) % Maxsize;    //插入结束后尾指针后移
}
//出队，删除队头元素
void DeQueue(SqQueue& Q, QElemType& e)
{
    if (Q.Front == Q.Rear)                 //队空处理
        return;
    e = Q.base[Q.Front];                  //保存队头元素
    Q.Front = (Q.Front + 1) % Maxsize;      //删除队头后头指针后移
}
//取队头元素
void GetHead(SqQueue& Q, QElemType& e)
{
    if (Q.Front == Q.Rear)                  //队空处理
    {
         return;
    }
    e = Q.base[Q.Front];                    //取队头
}
//配对同伴
void PartnerPairing(SqQueue& Qm, SqQueue& Qw, int sessions)
{
int n, m, Min;
    m = (Qm.Rear - Qm.Front + 1 + Maxsize) % Maxsize;     //计算男舞者的人数
    n = (Qw.Rear - Qw.Front + 1 + Maxsize) % Maxsize;     //计算女舞者的人数
    Min = m < n ? m : n;                   //比较男女舞者哪边少
    QElemType man, woman, dancer;
    for (int i = 0; i < sessions; i++)     //舞会轮数
    {
        for (int j = 1; j < Min; j++)       //配对次数
        {
            //先删掉队头元素
            DeQueue(Qm, man);
            DeQueue(Qw, woman);
            cout << man.name << " " << "邀请" << " " << woman.name << " " << "跳一曲" << " " << "乡村爱情小夜曲" << endl;
            //再插入到队尾上
            EnQueue(Qm, man);
            EnQueue(Qw, woman);
        }
        m > n ? GetHead(Qm, dancer) : GetHead(Qw, dancer);    //确定下一轮谁是第一位舞者
        cout << "下一位 : " << dancer.name << endl;
    }
}
int main()
{
    int n, m, sessions;
    int i;
    QElemType  man, woman;
    SqQueue Qm, Qw;
    InitQueue(Qm);
    InitQueue(Qw);
    cout << "象牙山村大型舞会" << endl;
    cout << "分别输入舞会男舞者,女舞者的人数:" << endl;
    cin >> n >> m;
    cout << "请输入" << n << "位男舞者的名字：" << endl;
    for (i = 0; i < n; i++)
    {
        cout << "第" << i + 1 << "位男舞者的姓名：" << endl;
        cin >> man.name;
        EnQueue(Qm, man);
    }
    cout << "请输入" << m << "位女舞者的名字：" << endl;
    for (i = 0; i < m; i++) {
        cout << "第" << i + 1 << "位女舞者的姓名：" << endl;
        cin >> woman.name;
        EnQueue(Qw, woman);
    }
    cout << "请输入需要多少场舞会: " << endl;
    cin >> sessions;
    PartnerPairing(Qm, Qw, sessions);
    return 0;
}

四、实验步骤
1、定义循环队列，和舞者信息的数据结构
2、初始化队列，包含男舞者和女舞者队列
3、定义入队、出队、取对头元素等操作
4、定义舞伴配对的方法，其中包含计算和比较男女舞者人数及舞者匹配
五、实验难点
1、对男女舞者配对的分析
需要用到两个队列，一个男队、一个女队，考虑出场(配对次序)，即先入队的男士和女士先配对成舞伴，在对头的男士和女士先出队，然后依次配成舞伴，直到某队列为空。
2、对舞曲循环的分析
若出场人数不变，舞会要进行循环舞曲，那么参与舞会的人需要循环配对。参与舞会的男女人数可能不等，那么在第一次配对结束后，若某队仍有等待配对者，则输出此队列中排在队头的等待者的姓名，这个人就是下一轮舞曲开始时第一个匹配舞伴的人。

3、输出奇怪的汉字：继上次实验中出现了输出“烫烫烫”的问题之后，这个实验中又多了一个“屯屯屯”的问题其实和上次实验非常类似，上次是因为 静态的栈空间（char[]）在未初始化的情况下VC自动填充0xCC的，而这次使用的是动态分配的堆空间（char* = new char[100]）,VC会自动填充0xCD，两个0xCD连起来就是中文汉字屯（此处用的是本组其中一位同学实验课的代码）此时使用的代码是：当把上面的注释去掉在把下面的部分注释掉后问题就解决了：经过测试，无论topElement的实参类型是char[]还是char*使用后一种方法都可以得到正确的值，那么两种写法比较的话，前一种是把直接赋值，而后面一种是一个一个字符赋值。这里的赋值有个小细节，我的i的终止时i<= strlen(cq.base[cq.front].name)这样就可以把‘\0’赋值到topElement的末尾（我说为什么strlen(topElement)有用呢）
发现的问题：
在第二种方法中，实参curBoy 或 curGirl 和 topElement的值是一同修改的，但是如果用第一种方法会出现不同步的情况，把这两个变量设成全局变量一样会出现。

六、实验心得
在本次试验中，在定义队列时使用循环队列解决了顺序存储的假溢出问题，但循环队列的类型定义和顺序队列的类型定义是一样的，二者在存储结构上都是“顺序”的，循环队列是逻辑上的循环，增加了判断队列空或满的一种处理方法。判断队列满的条件(Q.rear+1)%MAXQSZIZE==Q.front，可以看出少用了一个元素空间，而求余的原因是为了消除循环的影响。
通过本次实验，掌握了顺序队列的基本操作和应用，并对课上学习的一些知识进行了加深。也明白了处理问题需要使用最恰当的方法，在舞伴问题匹配中，正符合队列先入先出的特点。这也许就是数据结构的魅力所在，用更加方便高效的算法去解决生活中常见的问题。