舞伴问题.doc

《数据结构》

课 程 设 计 报 告 书

题 目： 舞伴问题
专 业： 计算机科学与技术
学 号：
学生姓名：
指导教师：
完成日期： 2016-06-20

舞伴问题
1. 题目描述
该程序主要实现以下功能：
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队，跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴，若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。
2. 预备知识
① void InitQueue (Queue &Q);
② int EmptyQueue (Queue Q);
③ void EnQueue (Queue &Q, ElemType item);
④ ElemType OutQueue (Queue &Q);
⑤ ElemType PeekQueue (Queue Q);
⑥ void ClearQueue (Queue &Q);
3. 问题分析
a) 由键盘输入数据，每对数据包括姓名和性别；
b) 输出结果包括配成舞伴的女士和男士的姓名，以及未配对者的队伍名称和队头者的姓名；
要求利用主函数中已实现的顺序循环队列的基本操作函数来实现。函数void partner() 在主函数中进行调用测试。
程序流程和设计思想可以用以下流程图来描述：
输入跳舞的总人数

依次输入姓名和姓名

调用队列函数

运行结果并显示

图1.程序运行流程图

4. 数据结构设计
抽象数据类型定义：
typedef struct
{
char sex;//'M代表男、F代表女'
char name[20];//存储姓名
}people;
typedef struct
{
people *queue;
int front; // 队头指针
int rear; // 队尾指针
int count; //数组Q的当前长度
int MaxSize;
}Queue;
队列的基本操作可包括：
① void InitQueue (Queue &Q); //构造一个空队列 Q
② int EmptyQueue (Queue Q);
//判断队列Q是否为空，若空返回1，否则返回0
③ void EnQueue (Queue &Q, ElemType item); //元素 item 进队列Q
④ ElemType OutQueue (Queue &Q); //队头元素出队列Q，并返回其值
⑤ ElemType PeekQueue (Queue Q); //返回队头元素值
⑥ void ClearQueue (Queue &Q); //清空队列

5. 模块设计
① void InitQueue (Queue &Q); //构造一个空队列 Q
{
Q.MaxSize=11;
Q.queue=(people *)malloc(Q.MaxSize*sizeof(people));
Q.rear=Q.front =0;
Q.count=0;
}
② int EmptyQueue (Queue Q);
//判断队列Q是否为空，若空返回1，否则返回0
{
return Q.front==Q.rear;
}
③ void EnQueue (Queue &Q, ElemType item); //元素 item 进队列Q
{
Q.count++;
if ((Q.rear+1)%Q.MaxSize==Q.front )
{ //空间不足，扩大2倍
int k=sizeof(people);
Q.queue=(people *)realloc(Q.queue,2*Q.MaxSize*k);
if(Q.rear!=Q.MaxSize-1) { //移动队列内容，必须要做
for(int i=0;i<=Q.rear;i++)
Q.queue[i+Q.MaxSize]=Q.queue[i];
Q.rear=Q.rear+Q.MaxSize;
}
Q.MaxSize=2*Q.MaxSize; //修改队列最大空间
}
Q.rear=(Q.rear+1)%Q.MaxSize; //元素入队
Q.queue[Q.rear]=p;
}
④ ElemType OutQueue (Queue &Q); //队头元素出队列Q，并返回其值
{
if(Q.front==Q.rear)
{
printf("队列已空无数据元素出队列！\n");
exit(1);
}
//先修改front位置，后取走元素
Q.count--;
Q.front =(Q.front +1) % Q.MaxSize;
return Q.queue[Q.front];
}

⑤ ElemType PeekQueue (Queue Q); //返回队头元素值
{
if(Q.front==Q.rear)
{
printf("队列已空，无法读取！\n");
exit(1);
}
//直接取走元素，不修改front位置，
return Q.queue[Q.front];
}
⑥ void ClearQueue (Queue &Q); //清空队列
{
free(Q.queue);//清空队列
Q.front=Q.rear=Q.MaxSize=Q.count=0;//将数值都赋值为0
}

6. 运行界面及运行结果

图6-1

图6-2
图6-3
附录：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{
char sex;//'M代表男、F代表女'
char name[20];//存储姓名
}people;
typedef struct
{
people *queue;
int front; // 队头指针
int rear; // 队尾指针
int count; //数组Q的当前长度
int MaxSize;
}Queue;

void InitQueue(Queue &Q) //构造一个空队列 Q
{
Q.MaxSize=11;
Q.queue=(people *)malloc(Q.MaxSize*sizeof(people));
Q.rear=Q.front =0;
Q.count=0;
}
int EmptyQueue(Queue Q) //判断队列Q是否为空，若空返回1，否则返回0
{
return Q.front==Q.rear;
}

void EnQueue(Queue &Q, people p) //元素 p进队列Q
{
Q.count++;
if ((Q.rear+1)%Q.MaxSize==Q.front )
{ //空间不足，扩大2倍
int k=sizeof(people);
Q.queue=(people *)realloc(Q.queue,2*Q.MaxSize*k);
if(Q.rear!=Q.MaxSize-1) { //移动队列内容，必须要做
for(int i=0;i<=Q.rear;i++)
Q.queue[i+Q.MaxSize]=Q.queue[i];
Q.rear=Q.rear+Q.MaxSize;
}
Q.MaxSize=2*Q.MaxSize; //修改队列最大空间
}
Q.rear=(Q.rear+1)%Q.MaxSize; //元素入队
Q.queue[Q.rear]=p;
}

people OutQueue(Queue &Q) //队头元素出队列Q，并用返回其值
{
if(Q.front==Q.rear)
{
printf("队列已空无数据元素出队列！\n");
exit(1);
}
//先修改front位置，后取走元素
Q.count--;
Q.front =(Q.front +1) % Q.MaxSize;
return Q.queue[Q.front];
}

people PeekQueue(Queue Q) //返回队头元素值
{
if(Q.front==Q.rear)
{
printf("队列已空，无法读取！\n");
exit(1);
}
//直接取走元素，不修改front位置，

return Q.queue[Q.front];
}
void ClearQueue (Queue &Q) //清空队列
{
free(Q.queue);//清空队列
Q.front=Q.rear=Q.MaxSize=Q.count=0;//将数值都赋值为0
}

void partner(people queue[],int count)//舞伴配对函数
{
int i;
people p;
Queue malequeue,femalequeue;//定义两个循环队列
InitQueue(malequeue);//置男空队列
InitQueue(femalequeue);//置女空队列
for(i=0;i<count;i++)
{
p=queue[i];
if(p.sex=='F')
{
EnQueue(femalequeue,p); //女生进女队

}
else
{
EnQueue(malequeue,p); //男生进男队

}
}
printf("D:舞伴配对情况如下:\n");
while(!EmptyQueue(femalequeue)&&!EmptyQueue(malequeue))//当两队都不为空队时候
{
p=OutQueue(malequeue);
printf("%s,",p.name);
p=OutQueue(femalequeue);
printf("%s\n",p.name);
}
//两队中有空的情况：
if(!EmptyQueue(femalequeue))//当女队不为空的时候，输出等待姓名
{
printf("E:女队中还有%d个人在等待！\n",femalequeue.count);
p=OutQueue(femalequeue);
printf("F:%s将是下轮得到舞伴的第一人\n",p.name);
}
else if(!EmptyQueue(malequeue))//当女队为空但男队不为空的时候
{
printf("E:男队中还有%d个人在等待！\n",malequeue.count);
p=OutQueue(malequeue);
printf("F:%s将是下轮得到舞伴的第一人\n",p.name);
}
else
printf("E:所有人都有舞伴,没有人剩余,O(∩_∩)O哈哈~\n");

}
int main(void)
{
people queue[100];

int i,num;

printf("A:输入跳舞人数的总人数:");
scanf("%d",&num);
printf("B:关于性别:F代表女,M代表男\n");
printf("C:输入姓名和性别,如:aa F\n");
for(i=0;i<num;i++)
{

scanf("%s",queue[i].name);

getchar();//作用是空格输入多少都无所谓
scanf("%c",&queue[i].sex);

if(queue[i].sex!='F'&&queue[i].sex!='M'){//判断信息输入是否合法
printf("第%d个人的信息输入错误,请重新输入\n",i+1);
//其实这个步骤有执行,只是因为输入错误,所以重新输入,所以i不变
i--;
}
}
partner(queue,num);
return 0;
}