计科101 冯康 201000814128
题目三：舞伴问题
【实验目的】
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。
2、掌握栈和队列的特点，即后进先出和先进先出的原则。
3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。 【问题描述】
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。
【实验要求】
利用队列实现，存储结构采用顺序或链式均可
【编程思路】
男女配对问题的原则是先入先出进行配对，因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。如果某组有剩余则参与第二轮的配对，并将第一个需要配对学生的信息返回；如果完全配对，则返回信息，不再进行下一轮的配对。
开始时男士和女士的记录存放在一个结构体数组中作为输入，另外需要构建两个队列来保存男队和女队。无论是结构体数组还男女队列的元素或结点都采取结构体类型。 作为输入的结构体数组可以事先创建即初始化时便将数据保存进去，也可以在程序运行时创建。
男女队列的存储类型可以采取顺序或链式结构。二者的原理基本一致，但在操作上却有所不同：
1、顺序存储结构的长度确定，存储容量有限。开辟空间很大的话又浪费存储空间，一种解决方案是采用循环队列，可是本题目是将所用元素都存储完成以后才进行删除，采用循环队列便失去了意义。
2、链式存储结构长度不固定，输入数据可以不固定。相比于顺序存储结构操作简单。 由于，输入数据是放在结构体数组中的，其最大长度已确定，间接限制了队列的最大长度，故采用顺序存储结构。确定好存储的类型之后，将结点的类型定义如下：
结点类型：结构体Node
结构体的数据成员：string型变量Name用来保存姓名
Char型变量Sex用来保存性别
typedef struct
计科101 冯康 201000814128 { Node*base; int Front; int Rear; }LinkQueue;用此结构体创建结构体变量来完成队列的各项操作。接下来进行队列的创建、出队列和判断队列是否为空等，具体操作将在代码解析中介绍。 【代码解析】
男女队列创建函数：void Creat(LinkQueue&p,LinkQueue&q,Node s[])
注：p、q分别是操纵男女队列的结构体，s[]为保存男女学生信息的数组
通过 p.base=new Node[n]和q.base=new Node[n]分别为为男女队列开辟数组空间，空间大小n由主函数中输入。为了程序的健壮性，需要判空。代码如下：
if (!p.base&&!q.base) {
cout
exit(1); } 如果开辟内存空间成功，则将队列中的各个元素进行赋初值：
p.Front=p.Rear=0; q.Front=q.Rear=0; 根据性别信息将n个男女学生对号入座放入上面开辟的空间中: for (int i=0;i
if(s[i].Sex==0)
{
p.base[p.Rear].Name=s[i].Name;
p.base[p.Rear].Sex=s[i].Sex;
p.Rear++;
}
else
{
q.base[q.Rear].Name=s[i].Name;
q.base[q.Rear].Sex=s[i].Sex;
q.Rear++;
} } 进行男女学生配对及确定下一轮要进行跳舞学生信息。其函数为：LinkQueue*Dance(LinkQueue&p,LinkQueue&q) 一直进行循环，将男女生进行配对。最后的结束条件是至少有一个队列为空：
while (p.Front!=p.Rear&&q.Front!=q.Rear)//循环结束条件 {
cout
p.Front++; q.Front++;//进行学生配对 }
if(p.Front!=p.Rear)
return &p; //如果男生队列有剩余则将男生队列返回
计科101 冯康 201000814128
} else if(q.Front!=q.Rear)
return &q; //如果女生队列有剩余则将女生队列返回
else return NULL; //如果男女学生刚好配对则返回空指针
【测试数据】
【实验体会】
对于面向过程编程而言，程序=数据+算法，在编写程序之前首先要对题目要求进行分析和思考。等把问题弄明白后，就要根据事件发展过程，依靠程序来模仿事件，进而形成编程思路，最后确定算法。一般而言，在编程思路路形成以后，根据程序执行过程选择最优算法，当这些都完成以后，编写代码及调试就没有太大麻烦了，所以首先要形成编程思路。刚开始的时候我直接在开发环境下一边看题一边写代码，瞪了半天什么也没写出来，于是我便先开始在纸上画画写写，将事件的整个过程画下来，然后考虑怎么才能运用代码来实现，一边思考一边写一些粗略的代码，最后从上到下执行代码看看是不是符合题目要求。有没有什么漏 3
计科101 冯康 201000814128 洞。等这些完成以后，再在开发环境下将代码完善、编译和调试。虽然说代码还有许多要改进的的地方，有的功能还不够完善，可毕竟是自己亲自写出来的，对于程序的条理有了一个清晰的了解，对编程也有了更加深刻的认识。 【附录代码】
#include #include using namespace std; static int n=0; struct Node { string Name; int Sex; }; typedef struct { Node*base; int Front; int Rear; }LinkQueue; void Creat(LinkQueue&p,LinkQueue&q,Node s[]) { p.base=new Node[n]; q.base=new Node[n]; if (!p.base&&!q.base) {
cout
exit(1); } p.Front=p.Rear=0; q.Front=q.Rear=0; for (int i=0;i
if(s[i].Sex==0)
{
p.base[p.Rear].Name=s[i].Name;
p.base[p.Rear].Sex=s[i].Sex;
p.Rear++;
}
else
{
q.base[q.Rear].Name=s[i].Name;
q.base[q.Rear].Sex=s[i].Sex;
q.Rear++;
计科101 冯康 201000814128
} } } LinkQueue*Dance(LinkQueue&p,LinkQueue&q) { while (p.Front!=p.Rear&&q.Front!=q.Rear) {
cout
p.Front++;
q.Front++; }
if(p.Front!=p.Rear)
return &p;
else if(q.Front!=q.Rear)
return &q;
else
return NULL; } int main() { Node s[100]; cout>n; for (int i=0;i
cout
cin>>s[i].Name;
cout
cin>>s[i].Sex; } LinkQueue p,q; Creat(p,q,s); LinkQueue*t=Dance(p,q); if(t!=NULL)
coutbase[t->Front].Name
cout
return 0; }
