(一)问题描述
某班有m个女生，n个男生（m不等于n，男女生人数和不能小于20），现要举办一个舞会，男女生分别编号坐在舞池两边的椅子上等待。每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没有成功配对者坐着等待下一曲找舞伴。一曲结束，舞池中的男女生分别按各自编号又依次回到椅子上等待配对。假设一晚会播放8首曲子（编号分别为1至8），请设计一系统模拟动态地显示出上述过程
（1）输出每曲的学生配对情况
（2）计算出某一个男生（编号为X）和某一个女生（编号为Y）是否互为舞伴，若是，则该晚在哪几首舞曲搭档过
（3）计算出某一个男生（编号为X）该晚曾搭配的女生有哪些，对应的舞曲编号是多少
（4）计算出某一个女生（编号为X）该晚曾搭配的男生有哪些，对应的舞曲编号是多少
(二)流程图
（三）程序详细设计
循环队列的实现
根据问题的描述,发现舞伴搭配问题类似于排队,在前面的就先配对,本曲未配对成功的轮到下一曲优先配对,这种“先进先出”的过程,一下子就会联想到数据结构中的队列,使用队列可以简单且高效的解决这个问题,为了避免“假溢出”的问题，于是定义一个循环队列:（即牺牲一个存储空间用以区分队空和满，这里我规定的是front指向的单位不能存储队列元素起到标志作用）
循环队列个方法所用表达式:
队列为满的条件: (rear+1)%MaxSize ==front
队列为空的条件: front == rear
队列中的元素个数: (rear-front+MaxSize)%MaxSize
入队:rear = (rear+1)%MaxSize
出队:front = (front+1)%MaxSize
class seqQueue //循环队列
{
public:
int* data;//指向存放元素数组的基地址
int maxSize;//队列的大小
int front, rear;//队头和队尾指针
seqQueue(int initSize = 100);
~seqQueue() { delete[] data; }
void clear() { front = rear = 0; }//清空队列
bool empty()const { return front == rear; }//判空
bool full()const { return (rear + 1) % maxSize == front; }//判满
int size()const { return (rear – front + maxSize) % maxSize; }//当前队列长度,元素个数
void inqueue(const int &x);//入队
int dequeue();//出队
};
seqQueue::seqQueue(int initSize)//初始化一个空队列
{
if (initSize <= 0)
{
cout << “队列存储空间异常！” << endl;
exit(0);
}
data = new int[initSize + 1];
maxSize = initSize + 1;
front = rear = 0; //队列为空
}
void seqQueue::inqueue(const int &x)//入队
{
if (full())//如果队满,则抛出异常
{
cout << “队满！” << endl;
exit(0);
}
rear = (rear + 1) % maxSize;//移动队尾指针
data[rear] = x;//x入队
}
int seqQueue::dequeue()//出队
{
if (empty())//如果队空,则抛出异常
{
cout << “队空!” << endl;
exit(0);
}
front = (front + 1) % maxSize;//移动队头指针，队头指针不存元素,起标志作用
return data[front];//返回队首元素
}
输出配对情况的实现
舞会开始之后即输出配对的情况,首先获取用户输入的男生人数man和女生人数woman,并判断得到较少的那一方人数存储在num变量中,用man和woman依次初始化出两个循环队列manQueue和womanQueue,男女全部依次入队,这时两个队列都是满的,因为有8首曲子,最外层循环即为8次,每首曲子配对跳舞时,人数较少的那一方都会有配对者,而人数多的那一方总会剩一些人留到下一首曲子,所以以num作为第二层循环次数,表示每首曲子应该有的舞伴对数，舞会开始后manQueue和womanQueue依次出队,当manQueue为空时，将manQueue入队至满，manQueue和womanQueue依次出队，当womanQueue为空时，将womanQueue入队至满，manQueue和womanQueue依次出队，最终输出可得到舞曲的配对情况
manQueue = new seqQueue(man);
womanQueue = new seqQueue(woman);
for (int i = 1; i <= man; i++)
manQueue->inqueue(i); //男生进入队列
for (int i = 1; i <= woman; i++)
womanQueue->inqueue(i); //女生进入队列
int num = man < woman ? man : woman;
cout << “舞会开始,舞曲配对情况如下:” << endl;
for (int i = 1; i <= 8; i++) //8首曲子
{
cout << “第” << i << “首曲子” << endl;
for (int j = 1; j <= num; j++)
{
int man_id = manQueue->dequeue(); //男女生依次出队
int woman_id = womanQueue->dequeue();
cout << “男” << man_id << “~~” << “女” << woman_id << endl;
vec.push_back(record{ man_id, woman_id, i });
if (manQueue->empty()) //男生队列为空
{
for (int k = 1; k <= man; k++)
manQueue->inqueue(k);
}
if (womanQueue->empty()) //女生队列为空
{
for (int k = 1; k <= woman; k++)
womanQueue->inqueue(k);
}
}
cout << “——————————————–” << endl;
}
查询是否互为舞伴的实现
实现该功能我首先定义了一个记录类,一条记录记录着一对男女及其对应的舞曲编号,使用vector容器存储今晚舞会的所有记录,然后通过读入用户输入的男生编号man_id和女生编号woman_id,对vector容器的循环遍历,判断是否有符合条件的记录,如果有,则表示该男女互为舞伴,并输出这条记录对应的舞曲编号表示该男女在该舞曲进行搭配过
class record //记录类(聚合类)
{
public:
int boy; //男生
int gril; //女生
int number; //曲子编号
};
vector<int> v;
for (auto it = vec.begin(); it != vec.end(); it++)
{
if (it->boy == man_id && it->gril == woman_id)
{
flag = true;
v.push_back(it->number);
}
}
查询男生舞会记录的实现
查询男生的舞会记录就是通过接收用户输入的男生编号,然后对vector容器进行遍历,输出相应的记录
查询女生舞会记录的实现
查询女生的舞会记录就是通过接收用户输入的女生编号,然后对vector容器进行遍历,输出相应的记录
（四）程序演示
程序运行后,进入主界面
此时用户可以输入相应数字选择功能,有以下几点注意:
①若舞会没有开始,除退出外的其他功能是无法使用的
②若输入了不存在的功能数字,则会报错并重新回到主界面
例如:舞会未开始,就使用其他功能,出现提示”舞会还未开始,请先开始舞会”
例如:此时输入了k,会出现提示”输入有误！请输入正确的功能序号”
输入1,开始舞会,系统将会说明舞会规则,随后用户完善相应信息,经系统判定后,不满足舞会规则的数据将无法开始舞会,例如此时男女生都为11人,违反了舞会的第①条规则,被系统要求重新输入
此时重新输入的男女生人数为10和9,，违反了舞会的第②条规则,依旧系统被要求重新输入此时重新输入的男女生人数为10和12,符合舞会规则,舞会开始,并输出各个舞曲男女生的配对情况
编辑
编辑
编辑
输出舞会的配对情况后,就可以选择使用相应的功能了,例如使用2查询是否互为舞伴功能,查询1号男生和4号女生是否互为舞伴,若是,输出相应的舞曲编号
查询结果显示: 1号男生和4号女生今晚并没有搭档过,根据上面输出的配对情况对照，1号男生和4号女生确实没有进行过搭配
接着我们查询1号男生和1号女生今晚是否搭配过
查询结果显示: 1号男生和1号女生今晚互为舞伴,搭档的舞曲编号为1和7,根据上面输出的配对情况对照,可以发现这是正确的
当然,如果输入了不存在的男女生编号,系统将会提示错误！这次舞会男生有10人,女生有12人,如果输入的男女生编号超过10和12,则系统提示错误
使用3查询男生舞会记录功能,查询1号男生的舞会记录,可查询出该男生今晚搭配的女生有哪些，对应的舞曲编号为多少
输入不存在的男生编号也会导致系统报错
使用4查询女生舞会记录功能,查询2号女生的舞会记录,可查询出该女生今晚搭配的男生有哪些,对应的舞曲编号是多少
输入不存在的女生编号也会导致系统报错
舞会结束,功能演示完毕,使用5退出功能退出系统
原文地址：http://www.cnblogs.com/longmunan/p/16838414.html
