队列的基本用法 舞者

实验目的：

1．掌握队列的定义及实现；

2．掌握利用队列的基本操作。

实验要求：

1、    使用链式结构完成队列的各种基本操作；

2、    补充完善教材81页的舞伴问题。

实验项目名称：队列的基本操作应用

实验过程：

1、    先建立一个舞者队列，依次往队列中添加人员信息（8个人，5男3女）；

2、    分别创建男女队列；

3、    从舞者队列中依次将队首元素出队并判断其性别并添加至男队（5人）或女队（3人）；

4、    分别从男队和女队出队队首元素并配对输出；（男队女队分别3人）

5、    将未完成的一队队首元素输出（男队的队首成员名称）。

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -1 
#define Status int
#define MAXSIZE 100
using namespace std;

//--------跳舞者个人信息 ------- 
typedef struct
{
	char name[20];
	char sex;
}Person;

//--------队列的链式储存结构 ------- 
typedef struct QNode
{
   Person data; 
   struct QNode *next;
}QNode,*QueuePtr;

typedef struct
{
	QueuePtr front;   //队头指针 
	QueuePtr rear;    //队尾指针 
}LinkQueue;

//---------队列的操作----------- 
//初始化
Status InitQueue(LinkQueue &Q)
{//构造一个空的队列 
	Q.front=Q.rear=new QNode;    //生成新结点作为头结点，队头指针和队尾指针指向此结点 
	Q.front->next=NULL;          //头结点的指针域置空 
	return OK;	
} 
 
 //入队
 Status EnQueue(LinkQueue &Q, Person e)
 {//插入元素e为Q的新的队尾元素 
 	QueuePtr p; 
    p=new QNode;               //为入队元素分配结点空间，用指针p指向 
 	p->data=e;                 //将新结点数据域置为e 
 	p->next=NULL;  Q.rear->next=p;      //将新结点插入到队尾 
 	Q.rear=p;                  //修改队尾指针
 	return OK;
  } 
  
//出队
Status DeQueue(LinkQueue &Q,Person &e)
{//删除Q的队头元素，用e返回其值 
  	QueuePtr  p = new QNode;      
	
  	if(Q.front == Q.rear)       //若队列空，则返回ERROR
  	   return ERROR;
  	   
  	p = Q.front->next;           //p指向队头元素 
  	e = p->data ;                //e保存队头元素的值 
  	Q.front->next = p->next;     //修改头结点的指针域 
  	
  	if(Q.rear==p)                 // 最后一个元素被删，队尾指针指向头结点 
  	   Q.rear=Q.front;
  	delete p;      //释放原队头元素的空间 
  return OK;
} 
 
//取队头元素
Person GetHead(LinkQueue Q)
{
 	if(Q.front!=Q.rear)               //队列非空 
 	 return Q.front->next->data;      //返回队头元素的值，队头指针不变 
} 
  
//判断是否为空
Status QueueEmpty(LinkQueue Q)
{
  	if(Q.front == Q.rear)
  	    return OK;
  	else 
  	    return ERROR;

} 

//----------跳舞者函数----------  
void DancePartner(Person dancer[],int num)
{//结构数组dancer中存放跳舞的男女，num是跳舞的人数 
   	LinkQueue Mdancers,Fdancers;
   	Person p;
   	
   	InitQueue(Mdancers);   //初始化 
   	InitQueue(Fdancers);
   	
   	for(int i=1;i<=num;i++)
   	{
   		p=dancer[i];
   		if(p.sex=='F')
   		   EnQueue(Fdancers,p);   //插入女队 
   		else
   		   EnQueue(Mdancers,p);   //插入男队 
	   }
	   
	   cout<<"\t\t\t*——————————————————————*"<<endl; 
	   cout<<"\t\t\t        The dancing partners are:           "<<endl; 
	   while(!QueueEmpty(Fdancers) && !QueueEmpty(Mdancers))
	   {//依次输出男女舞伴的名字 
	   	DeQueue(Fdancers,p);     //女士出队 
	   	   cout<<"\t\t\t\t\t"<<p.name<<" and ";    //输出女士舞者姓名 
	   	DeQueue(Mdancers,p);     //男士出队 
	   	   cout<<p.name<<endl;   //输出男士舞者姓名  
	   }
	   cout<<"\t\t\t*——————————————————————*"<<endl;
	   
	   if(!QueueEmpty(Fdancers))
	   {//女士队列非空，输出女士队头的姓名 
	   
	   	  p=GetHead(Fdancers);    //取女士队头 
	   	   cout<<"\t\t\t*——————————————————————*"<<endl; 
	   	   cout<<"\t\t\t  The first woman to get a partener is: "<<endl;
		   cout<<"\t\t\t                "<<p.name<<endl;
	   	   cout<<"\t\t\t*——————————————————————*"<<endl; 
	   }
	   else if(!QueueEmpty(Mdancers))
	   {//男士队列非空，输出男士队头的姓名 
	   
	   	  p=GetHead(Mdancers);      //取男士队头 
	   	   cout<<"\t\t\t*——————————————————————*"<<endl; 
	   	   cout<<"\t\t\t   The first man to get a partener is: "<<endl;
	   	   cout<<"\t\t\t                "<<p.name<<endl;
	   	   cout<<"\t\t\t*——————————————————————*"<<endl; 
	   }
	   
}

int main()
{
	int num;
	cout<<"\t\t\t*——————————————————————*"<<endl; 
	cout<<"\t\t\t|    Please inout the number of danceres:    |"<<endl; 
	cout<<"\t\t\t*——————————————————————*"<<endl;
	cout<<"\t\t\t\t\t"; 
	cin>>num;
	cout<<"\t\t\t*——————————————————————*"<<endl; 
	cout<<"\t\t\t|  Please inout the information of danceres: |"<<endl; 
	cout<<"\t\t\t*——————————————————————*"<<endl<<endl; 
	Person dancer[100];
	
	cout<<"\t\tPlease input 'F' or 'M' stand for the sex of danceres:"<<endl; 
    for(int i=1;i<=num;i++)
	{
		cout<<"\t\t\tThe "<<i<<" of the danceres"<<endl;  
		cout<<"\t\t\t\t\tsex:   ";
	      cin>>dancer[i].sex ;
	    cout<<"\t\t\t\t\t  name:   ";
	      cin>>dancer[i].name ;
		 cout<<endl;	
	}
	
     DancePartner(dancer,num);	
	return 0;
}