数据结构—实验05—队列

江西师范大学2022年软件学院软件工程（互联网软件开发方向班）数据结构作业

题目内容：(舞伴问题-队列应用）

假设在周末舞会上，男士和女士们分别进入舞厅，各自排成一队。跳舞开始，依次从男队和女队队头各出一人配成舞伴，若两队初始人数不同，则较长那一队未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。 你需要用循环队列操作实现上述算法。请完成下面3个函数的操作。

类型定义以及函数接口定义：

#define MAXQSIZE 51 //参加舞会的最多人数为50人

typedef struct {

       char name[20]; //姓名

       char sex;  //性别，'F'表示女性，'M'表示男性

} Person;

//- - - - - 队列的顺序存储结构- - - - -

typedef struct {

       Person *Data; 

       int Front; //头指针,指向队首位置

       int Rear; //尾指针，指向队尾元素的下一个位置

       int MaxSize;

} Queue;

bool CreateQueue(Queue &Q, int MaxSize ); //创建初始队列

int QueueLen(Queue &Q);//队列长度

bool AddQ( Queue &Q, Person X );

//如果队列已满，AddQ函数必须输出“Queue Full”并且返回false；

//否则，将X进队，返回true

//提示：采用浪费一个空间的方式判定是否队列满

bool DeleteQ( Queue &Q ,Person &X);

//如果队列是空的，则DeleteQ函数必须输出“Queue Empty”，并且返回false;

//如果队列非空，则队首元素出队，并将值赋给X。

bool QueueEmpty(Queue &Q);//判断队列是否为空

void DancePartner(Person dancers[], int N, Queue &Maledancers, Queue &Femaledancers);

//配对舞伴,舞伴以一个空格分隔；

//若男士人数多于女士人数，则Maledancers用来返回未配对的男士信息，Femaledancers队列为空；

//若女士人数多于男士人数，则Femaledancers用来返回未配对的女士信息，Maledancers队列为空；

//若刚好男女人数相同，则这两个队列都为空。

样例程序代码：

#include 

#include 

using namespace std;

 

#define MAXQSIZE 51 //参加舞会的最多人数为50人

 

typedef struct {

       char name[20]; //姓名

       char sex;  //性别，'F'表示女性，'M'表示男性

} Person;

//- - - - - 队列的顺序存储结构- - - - -

typedef struct {

       Person *Data;  

       int Front; //头指针,指向队首位置

       int Rear; //尾指针，指向队尾元素的下一个位置

       int MaxSize;

} Queue;

 

bool CreateQueue(Queue &Q, int MaxSize ); //创建初始队列

int QueueLen(Queue &Q);//队列长度

bool QueueEmpty(Queue &Q);//判断队列是否为空

 

bool AddQ( Queue &Q, Person X );

//如果队列已满，AddQ函数必须输出“Queue Full”并且返回false；

//否则，将X进队，返回true

//提示：采用浪费一个空间的方式判定是否队列满

 

bool DeleteQ( Queue &Q ,Person &X);

//如果队列是空的，则DeleteQ函数必须输出“Queue Empty”，并且返回false;

//如果队列非空，则队首元素出队，并将值赋给X。

 

void DancePartner(Person dancers[], int N, Queue &Maledancers, Queue &Femaledancers);

//配对舞伴,舞伴以一个空格分隔；

//若男士人数多于女士人数，则Maledancers用来返回未配对的男士信息，Femaledancers队列为空；

//若女士人数多于男士人数，则Femaledancers用来返回未配对的女士信息，Maledancers队列为空；

//若刚好男女人数相同，则这两个队列都为空。

 

int main(){

       int i;

       int N;//实际参加舞会的人数

       Person dancers[MAXQSIZE];

       Queue Maledancers, Femaledancers;

      //定义结构体变量Maledancers, Femaledancers，分别记录男士和女士入队者队列

       cin>>N;  //参加舞会的人数

       for(i=0;i>dancers[i].name>>dancers[i].sex;

    }

 

       CreateQueue(Maledancers,MAXQSIZE); //男士队列初始化

       CreateQueue(Femaledancers,MAXQSIZE); //女士队列初始化

 

       cout<<"The dancing partners are:"< 
补充程序答案：
 
bool AddQ( Queue &Q, Person X ){

 if((Q.Rear+1)%MAXQSIZE == Q.Front){    //尾指针指向最后一个队列空间时，位置为MAXQSIZE-1，尾指针+1再对MAXQSIZE取余便可以判断队列是否已满

 return 0;

 }

 Q.Data[Q.Rear] = X;//基本入队操作

 Q.Rear = (Q.Rear+1)%MAXQSIZE;//尾指针进行加一操作，对MAXQSIZE取余的目的是让队列成为循环队列

 return 1;

} 



bool DeleteQ( Queue &Q ,Person &X){

 if(QueueEmpty(Q)){    //判断队列是否为空

 return 0;

 }

 X = Q.Data[Q.Front];//通过引用的X把队列数据元素值取出

 Q.Front = (Q.Front+1)%MAXQSIZE;//队头指针+1移动到下一个元素的位置，取余的目的是让队列成为循环队列

} 





void DancePartner(Person dancers[], int N, Queue &Maledancers, Queue &Femaledancers){

 int i ;

 for(i = 0 ; i < N; ++i){

 if(dancers[i].sex == 'F')

 AddQ(Femaledancers,dancers[i]);  //女性舞者入队操作

 else

 AddQ(Maledancers,dancers[i]); // 男性舞者入队操作

 

 }

 Person e;

 while((!QueueEmpty(Femaledancers)) && (!QueueEmpty(Maledancers)))

    {    //判断男女舞者队列是否为空，两者均不为空则同时进行出队操作

     

        DeleteQ(Femaledancers,e);

        cout< 
此文章用于记录一位普通的江西师大学子的学习路程，仅供各位参考，理解思路以后自己动手最好，杜绝Ctrl+c。