舞伴问题
(1)问题描述:在一个舞会上,男士们和女士们进入舞厅,各自排成一队。跳舞开始时,依次从男队和女队的队列头上各出一个人进行配对。若两队初始人数不同,则较长的那一队中未配对者等待下一轮舞曲。 编写算法显示成功配对的信息,若有未配对者则输出其所在的队名(男队或女队)及其姓名,在进行下一轮排队时,先对上一轮未配对的人进行配对。
(2)问题分析:首先建立两个队列,一个队列存放男士,一个队列存放女士,配对时,每轮每个队列的对头元素出来配对,未配对的放到下一轮继续配对。
(3)代码:
代码中比较难理解的可能就是对队列中元素的操作,又是指针又是数组的,比较难理解,但没事,我来给大家画两张图,大家看下就会明白了。
我们要访问某个队列的某个元素时,首先找到该队列指针,Male,接着是这个队列的数组,person,然后数组节点的下标,因此就是Male->person[Male->front1]。
1 #include <iostream> 2 using namespace std; 3 4 typedef struct //定义一个人的结构体,用于存放参加舞会的人员的名字和性别 5 { 6 char name[20]; 7 char sex; 8 }Person; 9 10 typedef struct //定义一个队列的结构体,成员变量有结构体数组、头指针、尾指针和队列长度 11 { 12 Person person[20]; 13 int front1=0; 14 int rear=0; 15 int count1=0; 16 }SqQuene; 17 18 //配对函数 19 void Arrange(Person* person,SqQuene* Male,SqQuene* Female,int num) 20 { 21 cout<<"请输入参与舞会的人员的名字和性别:(M/m:男 F/f:女)"<<endl; 22 for(int i = 0;i < num; i++) //根据你输入的人数,进行循环输入成员的信息,同时根据成员的性别分别插入对应的队列 23 { 24 cin>>person[i].name>>person[i].sex; 25 if(person[i].sex == 'M' || person[i].sex == 'm') 26 { 27 Male->person[Male->rear++] = person[i]; 28 Male->count1++; 29 } 30 else if(person[i].sex == 'F' || person[i].sex == 'f') 31 { 32 Female->person[Female->rear++] = person[i]; 33 Female->count1++; 34 } 35 else 36 { 37 cout<<"您的输入有误,请重新输入!"<<endl; //如果输入的性别有误,就重新输入,并保证人数不会出错 38 i--; 39 } 40 } 41 42 cout<<"配对结果:"<<endl; 43 cout<<"男 女"<<endl; 44 while(Male->count1 > 0 && Female->count1 > 0) //当两个队列的个数不为0时,输出两个队列的对头元素 45 { 46 cout<<Male->person[Male->front1].name<<"——"<<Female->person[Female->front1].name<<endl; 47 Male->front1++; 48 Female->front1++; 49 Male->count1--; 50 Female->count1--; 51 } 52 53 if(Male->count1 > 0) //如果男士队有剩余,输出男士队的对头元素 54 { 55 cout<<"下一轮男生队伍的第一个:"<<Male->person[Male->front1].name<<endl; 56 } 57 if(Female->count1 > 0) //如果女士队有剩余,输出女士队的对头元素 58 { 59 cout<<"下一轮女生队伍的第一个:"<<Female->person[Female->front1].name<<endl; 60 } 61 if(Male->count1 == 0 && Female->count1 == 0) 62 { 63 cout<<"该轮无剩余人员!"<<endl; //否则无剩余 64 } 65 } 66 67 int main() 68 { 69 int num,flag = 1; //定义两个变量,一个存放插入的人数,一个是标志变量 70 Person* person = new Person[20]; //定义一个结构体数组 71 SqQuene* female = new SqQuene; //定义一个指向女队列的队列指针 72 SqQuene* male = new SqQuene; //定义一个指向男队列的队列指针 73 while(flag == 1) //判断循环条件 74 { 75 cout<<"请输入本轮跳舞的人数:"<<endl; 76 cin>>num; 77 Arrange(person,male,female,num); //调用配对函数 78 cout<<"是否继续,若继续请输入1,输入其他将退出系统!"<<endl; 79 cin>>flag; //判断变量是否满足循环条件 80 } 81 delete []person; //释放数组所占空间 82 cout<<"感谢您的使用,再见!"<<endl; 83 return 0; 84 }
(4)运行结果