1. 在一个舞会上，男士们和女士们进入舞厅，各自排成一队。跳舞开始时，依次从男队和女队的队列头上各出一个人配成舞伴。若两队初始人数不同，则较长的那一队中未配对者等待下一轮舞曲。 写一算法模拟上述舞伴配对问题。

2.编写算法每对男女配对成功的话，显示成功配对成舞伴的信息，若有未配对者，则输出第一位没有配对成功的姓名。

3. 使用链式结构完成队列的各种基本操作及其他补充说明。

1.文字描述：

①先入队的男士或女士亦先出队配成舞伴。因此该问题是典型的先进先出，可用队列作为算法的数据结构。

②在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。

③当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出排在队头的等待者的名字，将是下一轮舞曲开始时第一个可获得舞伴的人。

三、实现方法

#include
using namespace std;

#define MAXQSIZE 100
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;
typedef char QElemType;

typedef struct
{
	char name[20];
	char sex;          
}Person;
typedef struct
{
	Person* base;         
	int front;           
	int rear;          
}SqQueue;

SqQueue Mdancers, Fdancers;

Status InitQueue(SqQueue& Q)
{
	Q.base = new Person[MAXQSIZE];
	if (!Q.base) exit(OVERFLOW); 
	Q.front = Q.rear = 0; 
	return OK;
} 

Status EnQueue(SqQueue& Q, Person e)
{
	if ((Q.rear + 1) % MAXQSIZE == Q.front)
		return ERROR; 
	Q.base[Q.rear] = e; 
	Q.rear = (Q.rear + 1) % MAXQSIZE;
	return OK;
} 

Status DeQueue(SqQueue& Q, Person& e)
{
	if (Q.front == Q.rear) return ERROR;
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXQSIZE; 
	return OK;
} 

Person GetHead(SqQueue Q)    
{
	if (Q.front != Q.rear)        
		return Q.base[Q.front]; 
}

Status QueueEmpty(SqQueue& Q)
{
	if (Q.front == Q.rear) return OK;
	else return ERROR;
}

void DancePartner(Person dancer[], int num)
{
	Person p;
	SqQueue Mdancers, Fdancers;
	InitQueue(Mdancers);         
	InitQueue(Fdancers);         
	for (int i = 0; i < num; i++)      
	{
		p = dancer[i];
		if (p.sex == 'F') EnQueue(Fdancers, p); 
		else EnQueue(Mdancers, p);           
	}
	cout << "配对成一对舞伴的男女分别为:n";
	while (!QueueEmpty(Fdancers) && !QueueEmpty(Mdancers))
	{
		DeQueue(Fdancers, p);   
		cout << p.name << "  ";     
		DeQueue(Mdancers, p);     
		cout << p.name << endl;     
	}
	if (!QueueEmpty(Fdancers))   
	{
		p = GetHead(Fdancers);    
		cout << "未配对成功的第一位女子为:" << p.name << endl;
	}
	else if (!QueueEmpty(Mdancers))
	{
		p = GetHead(Mdancers);   
		cout << "未配对成功的第一位男子为:" << p.name << endl;
	}
}

int main()
{
	int n;
	Person dancer[MAXQSIZE];
	cout << "请输入一共跳舞的男女人数：";
	cin >> n;
	while (n <= 0)
	{
		cout << "输入错误，请重新输入跳舞人数：";
		cin >> n;
	}
	for (int i = 1; i <= n; i++)
	{
		cout << "请输入第" << i << "舞者的名字：" << endl;
		cin >> dancer[i - 1].name;
		cout << "请输入第" << i << "个人的性别(F/M)：" << endl;
		cin >> dancer[i - 1].sex;
		while (dancer[i - 1].sex != 'F' && dancer[i - 1].sex != 'M')
		{
			cout << "输入错误，请重新输入：n";
			cout << dancer[i - 1].sex;
			cout << "请输入第" << i << "个人的性别(F/M):" << endl;
			cin >> dancer[i - 1].sex;
			break;
		}
	}
	DancePartner(dancer, n);
	return 0;
}

四、实验结果分析

对本次实验的认知：

1．实验过程中遇到的问题及解决办法

刚开始对队列结构缺乏清楚的认识，对队列的操作不太熟练，导致绕了很多弯路，导致结果总是出错，后来向同学咨询，在同学讲解之后明白了其中缘由，经过改正后程序得以正确运行。

2.对设计及调试过程的心得体会

从这次实验，我明白，要学好数据结构必须得亲自动手去编写算法，经过本次实验我才发现自己是多么的无知，就这次实验的题目，我看了一下觉得没什么难度，算法也挺简单，结果编写过程中还是出了许多问题。以后一定要加强动手编写，不能眼高手低。

3.对程序的一些想法

这个实验相较于其他的，个人认为还是比较简单的，因为个人能力有限，所以能够实现的操作简单易懂。只能实现一些基本的操作，课下我一定会认真钻研，争取能够想到更有创意的程序。另外课本上的其他例题我虽然没有去做，但是也会在课下去认真思考，精益求精。