舞伴配对问题---队列的应用
参考《数据结构》(C语言版)主编 秦锋和http://www.cnblogs.com/xing901022/p/3534937.html博客,这篇博客我认为作者介绍简单明了。
采用空闲一个位置的方式,即N个元素空间的循环队列最多只能存放N-1个有效元素。
1) 循环队列初始化:front=rear=0;
2)入队操作:rear=(rear+1)%size;
3)出队操作:front=(front+1)%size;
4)判断是否为空队列:front==rear;
5)判断队列是否已满:front=(rear+1)%size;
6)遍历队列各元素。
问题描述:循环队列实现模拟舞伴配对问题:
1:在舞会上男女各自排成一队,舞会开始时一次从男队和女队的对头各出一人配成舞伴,如果两队初始人数不等,则较长的那一队中未配对者等待下一轮舞曲。2:假设初始男女人数及性别已经固定舞会的轮数从键盘输入,试模拟解决上述舞伴配对问题,要求从屏幕输出每一轮舞伴配对名单,如果在该轮有没有配上对的,能够从屏幕显示下一轮第一个出场的未配对者的姓名。
a.利用循环队列模拟舞伴配对问题:在舞会上,男、女各自排成一队。舞会开始
时。依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等,则较
长的那一队中未配对者等待下一轮舞曲。
b. 假设初始男、
女人数及性别已经固定,
舞会的轮数从键盘输入。
试模拟解决上
述舞伴配对问题。要求:从屏幕输出每一轮舞伴配对名单,如果在该轮有未配对
的,能够从屏幕显示下一轮第一个出场的未配对者的姓名。
//利用循环队列模拟舞伴配对问题
#include <iostream>#include <string>
#define MAN_SIZE 6
#define WOMAN_SIZE 4
//#define QU_NUM MAN_SIZE<WOMAN_SIZE?MAN_SIZE:WOMAN_SIZE
using namespace std;
typedef struct Queue_1{
string data[MAN_SIZE];
int front;
int rear;
}MAN_Queue; //存储男
typedef struct Queue_2{
string data[WOMAN_SIZE];
int front;
int rear;
}WOMAN_Queue; //存储女
typedef struct Queue{
string data[WOMAN_SIZE][2]; //这里定义配对的男女的名字,wan lin-----da ge @@@@@@我以后看的时候重点关注
int front;
int rear;
}QU_Queue; //存储配对人
void InitQueue_1(MAN_Queue *q,int n,string* BB)
{
int i;
q->front=0;
q->rear =0;
for(i=0;i<n-1;i++)
{
q->data[q->rear]=BB[i];
q->rear++;
}
}
void InitQueue_2(WOMAN_Queue *q,int n,string* BB) ////string *BB 这个地方对我这个菜鸟来说要特别注意,@@@@@@我以后看的时候重点关注
{
int i;
q->front=0;
q->rear =0;
for(i=0;i<n-1;i++)
{
q->data[q->rear]=BB[i];
q->rear++;
}
}
int getLength_1(MAN_Queue *q){
return (q->rear-q->front+MAN_SIZE)%MAN_SIZE;
}
void showQueue_1(MAN_Queue *q){
int i;
int len=getLength_1(q);
cout<<"front";
for(i=0;i<len;i++){
if(q->front+i<MAN_SIZE)
cout<<"->"+q->data[q->front+i];
else
cout<<"->"+q->data[q->front+i-MAN_SIZE];
}
cout<<"->rear"<<endl;
}
int getLength_2(WOMAN_Queue *q){
return (q->rear-q->front+WOMAN_SIZE)%WOMAN_SIZE;
}
void showQueue_2(WOMAN_Queue *q){
int i;
int len=getLength_2(q);
cout<<"front";
for(i=0;i<len;i++){
if(q->front+i<WOMAN_SIZE)
cout<<"->"+q->data[q->front+i];
else
cout<<"->"+q->data[q->front+i-WOMAN_SIZE];
}
cout<<"->rear"<<endl;
}
void main()
{
int Ture_num;
cin>>Ture_num; //舞会的轮数
MAN_Queue *q1 = new MAN_Queue;
WOMAN_Queue *q2 = new WOMAN_Queue;
QU_Queue *q3 = new QU_Queue;
string WAN_names[MAN_SIZE-1]={"wan lin","gao peng","mei wanxin","yu yun","wang peili"};
string WOMAN_names[WOMAN_SIZE-1]={"da ge","li shizen","butiful"};
//初始化
InitQueue_1(q1,MAN_SIZE,WAN_names);
InitQueue_2(q2,WOMAN_SIZE,WOMAN_names);
showQueue_1(q1);
showQueue_2(q2);
//配对
int i=0;
int j=0;
q3->rear=0;
q3->front=0;
string tar_1;
string tar_2;
int rr;
while(i!=Ture_num)
{
if((q3->rear+1)%WOMAN_SIZE != q3->front)
{
if(q1->front != q1->rear)
{
tar_1 = q1->data[q1->front];
q1->front = (q1->front+1)%MAN_SIZE;
}
if(q2->front != q2->rear)
{
tar_2 = q2->data[q2->front];
q2->front = (q2->front+1)%WOMAN_SIZE;
// }
q3->data[q3->rear][0] =tar_1;
//cout<<q3->rear;
q3->data[q3->rear][1] =tar_2;
// cout<<q3->rear;
// cout<<QU_NUM;
q3->rear = (q3->rear+1)%WOMAN_SIZE;
cout<<q3->data[q3->rear][0];
cout<<"------";
cout<<q3->data[q3->rear][1];
cout<<endl;
}
else
{
if(q3->front != q3->rear)
{
tar_1=q3->data[q3->front][0];
tar_2=q3->data[q3->front][1];
q3->front = (q3->front+1)%WOMAN_SIZE;
if((q1->rear+1)%MAN_SIZE != q1->front)
{
q1->data[q1->rear] = tar_1;
q1->rear = (q1->rear+1)%MAN_SIZE;
}
if((q2->rear+1)%WOMAN_SIZE != q2->front)
{
q2->data[q2->rear] = tar_2;
q2->rear = (q2->rear+1)%WOMAN_SIZE;
}
}
i++;
}
}
//cout<<q1->data[q2->front]<<endl;
}
循环队列
循环队列类似栈,但是有两个口,一个专门用来入队,一个专门用来出队。由于入队出队不在一个端口,因此如果不适用循环队列,随着队列的使用,存储空间马上就被耗光了。在循环队列中,一个主要的知识点,就是如何判断队列为空,或者队列满。
这里主要有两个方法:
1 设置一个标记位,初始时,队列为空,我们设置flag=0;随着数据的使用,如果队满,设置flag=1;
2 使用一个空的数据位,这样rear指针永远也不能追上front指针。当front==rear时,队列即为空;当(rear-front)%SIZE==SIZE时,队列为满
数据结构
typedef struct Queue{ int data[MAXSIZE]; int front; int rear; }Queue;
入队操作
int inQueue(Queue *q,int num){ if((q->rear+1)%MAXSIZE == q->front) return 0; q->data[q->rear] = num; q->rear = (q->rear+1)%MAXSIZE; return 1; }
出队操作
int outQueue(Queue *q,int *tar){ if(q->front == q->rear) return 0; *tar = q->data[q->front]; q->front = (q->front+1)%MAXSIZE; return 1; }
示例代码
1 #include <stdio.h> 2 #include <stdlib.h> 3 #define MAXSIZE 10 4 5 typedef struct Queue{ 6 int data[MAXSIZE]; 7 int front; 8 int rear; 9 }Queue; 10 11 void initQueue(Queue *q,int n); 12 void showQueue(Queue *q); 13 int getLength(Queue *q); 14 int inQueue(Queue *q,int num); 15 int outQueue(Queue *q,int *tar); 16 17 int main() 18 { 19 Queue *q = (Queue *)malloc(sizeof(Queue)); 20 initQueue(q,3); 21 showQueue(q); 22 23 if(inQueue(q,9)) 24 showQueue(q); 25 26 int *tar = (int *)malloc(sizeof(int)); 27 if(outQueue(q,tar)) 28 printf("the number %d out Queue\n",*tar); 29 showQueue(q); 30 31 if(outQueue(q,tar)) 32 printf("the number %d out Queue\n",*tar); 33 showQueue(q); 34 35 if(inQueue(q,110)) 36 showQueue(q); 37 38 if(outQueue(q,tar)) 39 printf("the number %d out Queue\n",*tar); 40 showQueue(q); 41 42 if(outQueue(q,tar)) 43 printf("the number %d out Queue\n",*tar); 44 showQueue(q); 45 46 if(outQueue(q,tar)) 47 printf("the number %d out Queue\n",*tar); 48 showQueue(q); 49 50 free(tar); 51 free(q); 52 return 0; 53 } 54 55 void initQueue(Queue *q,int n){ 56 int i; 57 q->front=0; 58 q->rear =0; 59 for(i=0;i<n;i++){ 60 q->data[q->rear]=2*i+1; 61 q->rear++; 62 } 63 } 64 void showQueue(Queue *q){ 65 int i; 66 int len=getLength(q); 67 printf("front-"); 68 for(i=0;i<len;i++){ 69 if(q->front+i<MAXSIZE) 70 printf("%d-",q->data[q->front+i]); 71 else 72 printf("%d-",q->data[q->front+i-MAXSIZE]); 73 } 74 printf("rear\n"); 75 } 76 int getLength(Queue *q){ 77 return (q->rear-q->front+MAXSIZE)%MAXSIZE; 78 } 79 int inQueue(Queue *q,int num){ 80 if((q->rear+1)%MAXSIZE == q->front) 81 return 0; 82 q->data[q->rear] = num; 83 q->rear = (q->rear+1)%MAXSIZE; 84 return 1; 85 } 86 int outQueue(Queue *q,int *tar){ 87 if(q->front == q->rear) 88 return 0; 89 *tar = q->data[q->front]; 90 q->front = (q->front+1)%MAXSIZE; 91 return 1; 92 }
运行结果