// 在一次舞会上，来了许多男士和女士。这些男士和女士分别排队进入舞厅。第

[c]代码库

//    在一次舞会上，来了许多男士和女士。这些男士和女士分别排队进入舞厅。第一个
//舞曲开始后，男士和女士按照队列顺序配对并走入舞池。当男士多于女士时，配对
//剩余的男士仍然在队列中。一曲终了，跳完舞的男士排在队尾，女士排成新的队列。
//下一舞曲开始时，男女重新按照队列顺序配对跳舞。当女士多于男士时，配对剩余
//的女士仍然在队列中，等待下一曲配对。现在要求按照队列中的先后顺序打印出第
//十轮配好对的人员名单和剩余人员的名单。


#include<stdio.h>
#include<stdlib.h>
#include"test4.h"
#include<string.h>
#define Maxsize 100

int main()
{
	int i,j,len,len1,len2,count;
	char str[Maxsize],e;
	LinkQueue *Q1,*Q2; //定义俩链式队列Q1，Q2
	Q1=CreateQNode(0);//初始化Q1
	Q2=CreateQNode(0);//初始化Q2

	printf("用字母代表女士!输入女士:\n");
	gets(str);
	len1=strlen(str);//len1表示女士数量
	for(i=0;i<len1;i++)
		EnQNode(Q1,str[i]);//将数据元素插入队列Q1中
	
	printf("从链表队列中输出:\n");
	Display(Q1);//将队列Q1的数据元素输出

	printf("用数字代表男士!输入男士:\n");
	gets(str);
	len2=strlen(str);//len2表示男士数量
	for(i=0;i<len2;i++)
		EnQNode(Q2,str[i]);//将数据元素插入到队列Q2中

	printf("从链表队列中输出:\n");
	Display(Q2);//输出队列Q2的数据元素

	printf("共输出几轮配对:\n");
	scanf("%d",&count);//输入配对次数

	for(i=1;i<=count;i++)
	{
		printf("输出第%d轮配对\n",i);
		printf("输出配对男女:\n");
        if(len1 >= len2)//比较女士Q1和男士Q2的数量，取小值
		     len=len2;
	    else
		     len=len1;

		for(j=0;j<len;j++)
		{
			DeQNode(Q1,&e);//从Q1中取出头元素（出队）
		    printf("%c",e);
		    EnQNode(Q1,e);//将取出的头元素再次插入队列Q1中(入队)

		    DeQNode(Q2,&e);//从Q2中取出头元素（出队）
			printf("%c",e);
			EnQNode(Q2,e);//将取出的头元素再次插入队列Q2中(入队)

			printf(" ");
		}

		printf("\n输出未配对的男（女）:\n");

		if(len1 <= len2)
		{
			len=len2-len1;
			Output(Q2,len);//遍历队列，从Q2中输出前len个数量的数据元素
		}
		else
		{
			len=len1-len2;
			Output(Q1,len);//遍历队列，从Q1中输出前len个数量的数据元素
		}
		printf("\n\n");
	}

	return 0;
}




////////////////////////////////////////
/*         test4.cpp                 */
/*                                   */
/*     filename:test4.cpp            */
/*     description:test4.h的实现文件 */
/*     designer:zhu jian             */
/*     data:12-10-27                 */
///////////////////////////////////////


#include<stdio.h>
#include<stdlib.h>
#include"test4.h"
#include<string.h>
#define Maxsize 100

LinkQueue *CreateQNode(elemtype e)//创建一个空的链表队列
{
	QNode *Q;
	LinkQueue *p;
    Q=(QNode *)malloc(sizeof(QNode));
	p=(LinkQueue *)malloc(sizeof(LinkQueue));
	if(!Q || !p)
		return NULL;

	Q->data=e;
	Q->next=NULL;
	p->front=p->rear=Q;
	return p;
}

unsigned char EnQNode(LinkQueue *Q,elemtype e)//插入数据元素(入队)
{
	LinkQueue *p;
	QNode *q;
	p=Q;
	if(!Q)
		return NULL;

	q=(QNode *)malloc(sizeof(QNode));
	if(!q)
		return ERROR;

	q->data=e;
	q->next=NULL;
	p->rear->next=q;
	p->rear=q;
	return OK;
}

unsigned char DeQNode(LinkQueue *Q,elemtype *e)//读取队列的数据元素,并删除结点(出队)
{
	QNode *p;
	QNode *q;
	p=Q->front;
	if(Q->front == Q->rear)
		return NULL;

	*e=p->next->data;
	q=p->next;
	p->next=q->next;
	if(Q->rear == q)
	      Q->rear=p;
	free(q);
	return OK;
}

unsigned char Display(LinkQueue *Q)//遍历整个队列
{
	LinkQueue *p;
	QNode *q;
	p=Q;
	if(!Q)
		return NULL;

	q=p->front->next;
	while(q != p->rear)
	{
		printf("%c",q->data);
		q=q->next;
	}
	printf("%c\n",q->data);
	return OK;
}

unsigned char Output(LinkQueue *Q,int len)//输出链表队列的前len个元素
{
	int i;
	QNode *p;
	p=Q->front;
	if(!Q)
		return ERROR;

	for(i=0;i<len;i++)
	{
		printf("%c",p->next->data);
		p=p->next;
	}
	printf("\n");

	return OK;
}








///////////////////////////////////
/*         test4.h                */
/*                                */
/*     filename:test4.h           */
/*     description:test4的头文件  */
/*     designer:zhu jian          */
/*     data:12-10-27              */
////////////////////////////////////




#ifndef _DATA_STRUCTURE_TEST4_H_
#define _DATA_STRUCTURE_TEST4_H_

#ifndef ERROR
#define ERROR 0
#endif

#ifndef OK 
#define OK 1
#endif

#ifndef NULL
#define NULL 0
#endif

typedef char elemtype;//用elemtype代替char

typedef struct QNode{//定义队列的链表结构体
	elemtype data;
    struct QNode *next;
}QNode;

typedef struct{//定义队列的头指针和尾指针
	QNode *front;
	QNode *rear;
}LinkQueue;


LinkQueue *CreateQNode(elemtype e);//创建一个链表结构的队列指针

unsigned char EnQNode(LinkQueue *Q,elemtype e);//插入数据元素(入队)

unsigned char DeQNode(LinkQueue *Q,elemtype *e);//读取队列的数据元素(出对)

unsigned char Display(LinkQueue *Q);//遍历整个队列

unsigned char Output(LinkQueue *Q,int len);//输出链表队列的前len个元素


#endif