课程名称：数据结构

实验目的：

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

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

实验要求：

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

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

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

实验过程：

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

2、    分别创建男女队列；

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

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

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

 

实验结果：

输入：8人信息（A,B,C,D,E,F,G,H）

输出：The dancepartners:

       A---B

      C---D

      E---F

G is waiting for a partner.

实验分析：

1.队列的操作特点；

2.列举调试运行过程中出现的错误并分析原因。

要求：

(1) 程序要添加适当的注释，程序的书写要采用缩进格式。

(2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。

(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。

(4) 上传源程序到课堂派。顺序表的源程序保存为dancepartner.cpp。

#include<iostream>
using namespace std;

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

typedef int Status;

typedef struct
{
	char name[20];
	char sex;
}person;

typedef person QELemType;

typedef struct
{
	QELemType *base;
	int front;
	int rear;
}SqQueue;

Status InitQueue(SqQueue &Q)
{//构造一个空对列Q
   Q.base=new QELemType[MAXQSIZE];
   if(!Q.base) exit(OVERFLOW);
   Q.front=Q.rear=0;
   return OK; 
}

Status EnQueue(SqQueue &Q,QELemType e)
{//插入元素e为Q的新的队列元素
    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,QELemType &e)
{//删除Q的队头元素，用e返回其值 
   if(Q.front==Q.rear) return ERROR;
   e=Q.base[Q.front];
   Q.front=(Q.front+1)%MAXQSIZE;
   return OK;
}

QELemType GetHead(SqQueue Q)
{//返回Q的队头元素，不修改队头指针
   if(Q.front!=Q.rear) 
     return  Q.base[Q.front];
}

Status QueueEmpty(SqQueue Q)
{//判断队列是否为空 
	if(Q.front==Q.rear)
	   return OK;
	return ERROR; 
}

void DancePartner(person dancer[],int num)
{//结构数组dancer中存放跳舞的男女,num是跳舞的人数
   person p;
   
   SqQueue Mdancers;
   SqQueue 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<<"The dancing partners are:\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<<"The first woman to get a partner is:"<<p.name<<endl;
   }
   else if(!QueueEmpty(Mdancers))
   {
   		p=GetHead(Mdancers);
   		cout<<"The first man to get a partner is:"<<p.name<<endl;
   }
}
int main()
{
	int num,i;
	person dancer[MAXQSIZE];
	puts("请输入舞者总人数:");
	scanf("%d",&num);
	puts("请分别输入舞者姓名和性别:(性别以F及M表示)");
	for(i=0;i<num;i++) 
	{
		scanf("%s",&dancer[i].name);
		getchar();
		scanf("%c",&dancer[i].sex);
	}
	DancePartner(dancer,num);
	return 0;
}