跳舞对列.cpp

这里面包括数据结构多数的算法

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct
{	char name[20];
	char sex;			/*性别，'F'表示女性，'M'表示男性 */
} Person;
typedef Person DataType;/*将队列中元素的数据类型改为Person */

/*循环队列的类型定义 */
#define QueueSize 100	/*应根据具体情况定义该值 */
typedef struct
{	int front;			/*头指针，队非空时指向队头元素 */
	int rear;			/*尾指针，队非空时指向队尾元素的下一位置 */
	int count;			/*计数器，记录队中元素总数 */
	DataType data[QueueSize];
} CirQueue;



void InitQueue(CirQueue *Q)
{	(*Q).front=(*Q).rear=0;
	(*Q).count=0;					/*计数器置0  */
}

int QueueEmpty(CirQueue *Q)
{
	return (*Q).count==0;			/*队列无元素为空  */
}

int QueueFull(CirQueue *Q)
{
	return (*Q).count==QueueSize;
	/*队中元素个数等于QueueSize时队满  */
}

void EnQueue(CirQueue *Q,DataType x)
{
	if (QueueFull(Q))
	{	printf("Queue overflow");
		exit(0);					/*队满上溢  */
	}
	(*Q).count++;					/*队列元素个数加1  */
	(*Q).data[(*Q).rear]=x;			/*新元素插入队尾  */
	(*Q).rear=((*Q).rear+1)%QueueSize;/*循环意义下将尾指针加1  */
}

DataType DeQueue(CirQueue *Q)
{
	DataType temp;
	if (QueueEmpty(Q))
	{	printf("Queue underflow");
		exit(0);					/*队空下溢 */
	}
	temp=(*Q).data[(*Q).front];
	(*Q).count--;					/*队列元素个数减1  */
	(*Q).front=((*Q).front+1)%QueueSize;/*循环意义下的头指针加1  */
	return temp;
}

DataType QueueFront(CirQueue *Q)
{
	if (QueueEmpty(Q))
	{	printf("Queue is empty");
		exit(0);
	}
	return (*Q).data[(*Q).front];
}

void DancePartners(Person dancer[],int num)
{  /*结构数组dancer中存放跳舞的男女，num是跳舞的人数  */
	int i;	Person p;	CirQueue Mdancers,Fdancers;
	InitQueue(&Mdancers);			/*男士队列初始化  */
	InitQueue(&Fdancers);			/*女士队列初始化  */
	for(i=0;i<num;i++)
	{	p=dancer[i];
		if(p.sex=='F')
			EnQueue(&Fdancers,p);	/*排入女队  */
		else
			EnQueue(&Mdancers,p);	/*排入男队  */
	}
	printf("第一轮舞伴是：\n");
	while(!QueueEmpty(&Fdancers)&&!QueueEmpty(&Mdancers))
	{	p=DeQueue(&Fdancers);		/*女士出队  */
		printf("%-20s",p.name);		/*打印出队女士名  */
		p=DeQueue(&Mdancers);		/*男士出队  */
		printf("%s\n",p.name);		/*打印出队男士名  */
	}
	if(!QueueEmpty(&Fdancers))
	{ /*输出女队剩余人数及队头女士的名字  */
		printf("\n还有%d位女士没有轮到\n",Fdancers.count);
		p=QueueFront(&Fdancers);	/*取队头  */
		printf("%s将第一个得到舞伴\n",p.name);
	}
	else
	if(!QueueEmpty(&Mdancers))
	{ /*输出男队剩余人数及队头男士的名字  */
		printf("\n还有%d位男士没有轮到\n",Mdancers.count);
		p=QueueFront(&Mdancers);	/*取队头  */
		printf("%s将第一个得到舞伴\n",p.name);
	}
void main()
{
	
	DataType dancer[12];
	strcpy(dancer[0].name,"George Thompson");
	dancer[0].sex='M';
	strcpy(dancer[1].name,"Jane Adrews");
	dancer[1].sex='F';
	strcpy(dancer[2].name,"Sandra Williams");
	dancer[2].sex='F';
	strcpy(dancer[3].name,"Bill Brooks");
	dancer[3].sex='M';
	strcpy(dancer[4].name,"Bob Carlson");
	dancer[4].sex='M';
	strcpy(dancer[5].name,"Shirley Granley");
	dancer[5].sex='F';
	strcpy(dancer[6].name,"Louise Sanderson");
	dancer[6].sex='F';
	strcpy(dancer[7].name,"Dave Evans");
	dancer[7].sex='M';
	strcpy(dancer[8].name,"Harold Brown");
	dancer[8].sex='M';
	strcpy(dancer[9].name,"Roberta Edwards");
	dancer[9].sex='F';
	strcpy(dancer[10].name,"Dan Gromley");
	dancer[10].sex='M';
	strcpy(dancer[11].name,"John Gaston");
	dancer[11].sex='M';
	DancePartners(dancer,12);
}
	/*欲看下一轮舞伴配对情况，请将下面的/*和*/删除即可  */
	/*
	for(i=0;i<num;i++)
	{	p=dancer[i];
		if(p.sex=='F')
			EnQueue(&Fdancers,p);	/*排入女队
		else
			EnQueue(&Mdancers,p);	/*排入男队
	}
	printf("第二轮舞伴是：\n");
	while(!QueueEmpty(&Fdancers)&&!QueueEmpty(&Mdancers))
	{	p=DeQueue(&Fdancers);		/*女士出队
		printf("%-20s",p.name);		/*打印出队女士名
		p=DeQueue(&Mdancers);		/*男士出队
		printf("%s\n",p.name);		/*打印出队男士名
	}
	if(!QueueEmpty(&Fdancers))
	{ /*输出女队剩余人数及队头女士的名字
		printf("\n还有%d位女士只跳过一轮\n",Fdancers.count);
		p=QueueFront(&Fdancers);	/*取队头
		printf("%s将第一个得到舞伴\n",p.name);
	}
	else
	if(!QueueEmpty(&Mdancers))
	{ /*输出男队剩余人数及队头男士的名字
		printf("\n还有%d位男士只跳过一轮\n",Mdancers.count);
		p=QueueFront(&Mdancers);	/*取队头
		printf("%s将第一个得到舞伴\n",p.name);
	}
	*/
}