糖尿病康复,内容丰富有趣,生活中的好帮手!
糖尿病康复 > 舞伴问题(数据结构队列 c语言版)

舞伴问题(数据结构队列 c语言版)

时间:2024-05-19 17:01:56

相关推荐

舞伴问题(数据结构队列 c语言版)

舞伴问题

一、实验题目1.案例分析2.案例实现3.算法步骤4.算法描述二、工具环境三、实验代码四、实验总结

一、实验题目

假设在周末舞会上,男士们和女士们进入舞厅时,各自排成一队。跳舞开始时,依次从男队和女队的队头各出一人配成舞伴。若两队初始人数不相同,则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。

1.案例分析

对千舞伴配对问题,先入队的男士或女士先出队配成舞伴,因此设置两个队列分别存放男士和女士入队者。假设男士和女士的记录存放在一个数组中作为输入,然后依次扫描该数组的各元素,并根据性别来决定是进入男队还是女队。 当这两个队列构造完成之后,依次将两队当前的队头元素出队来配成舞伴,直至某队列变空为止。 此时,若某队仍有等待配对者,则输出此队列中排在队头的等待者的姓名,此人将是下一轮舞曲开始时第一个可获得舞伴的人。

2.案例实现

算法中有关数据结构的定义如下:

//----- 跳舞者个人信息--- -typedef struct {char name [20]; //姓名char sex; //性别,'F'表示女性,'M'表示男性}Person; // ----- 队列的顺序存储结构--- - -#define MAXQSIZE 100 //队列可能达到的最大长度typedef struct { Person *base; //队列中数据元素类型为Personint front; //头指针int rear; //尾指针} SqQueue; SqQueue Mdancers,Fdancers;

3.算法步骤

1.初始化 Mdancers 队列和 Fdancers 队列。

2.反复循环,依次将跳舞者根据其性别插入 Mdancers 队列或 Fdancers 队列。

3.当 Mdancers 队列和 Fdancers 队列均为非空时, 反复循环, 依次输出男女舞伴的姓名。

4.如果 Mdancers 队列为空而 Fdancers 队列非空, 则输出 Fdancers 队列的队头女士的姓名。

5.如果 Fdancers 队列为空而 Mdancers 队列非空, 则输出 Mdancers 队列的队头男士的姓名。

4.算法描述

void DancePartner(Person dancer[],int num) {//结构数组dancer中存放跳舞的男女,num是跳舞的人数。InitQueue(Mdancers); //男士队列初始化InitQueue(Fdancers); //女士队列初始化for(i=0;i<num;i++) //依次将跳舞者根据其性别人队{p=dancer[i]; if (p.sex=='F') EnQueue(Fdancers, p); / /插入女队else EnQueue(Mdancers,p); //插人男队}cout<<"The dancing partners are:\n"; while(!QueueEmpty(Fdancers)&&!QueueEmpty(Mdancers)) {//依次输出男女舞伴的姓名DeQueue(Fdancers,p); //女士出队cout<<p. name<<" "; //输出出队女士姓名DeQueue(Mdancers,p); //男士出队cout<<p.name<<endl; //输出出队男士姓名}if (! QueueEmpty (Fdancers)) //女士队列非空,输出队头女士的姓名{p=GetHead(Fdancers); //取女士队头cout<<"The first woman to get a partner is: "<< p.name<<endl; }else if (!QueueEmpty (Mdancers)) //男士队列非空,输出队头男士的姓名{p=GetHead(Mdancers); //取男士队头cout<<"The first man to get a partner is: "<< p.name<<endl; }}

二、工具环境

Window10操作系统,Microsoft Visual C++学习版 集成开发环境,C语言

三、实验代码

#include<stdio.h>#include<stdlib.h>#define MAXSIZE 100 //队列可能达到的最大长度#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef struct{char name [20]; //姓名char sex; //性别,'F'表示女性,'M'表示男性}Person; typedef struct{Person *base; //队列中数据元素类型为Personint front; //头指针int rear; //尾指针}SqQueue; Status InitQueue (SqQueue *Q);//构造一个空队列QStatus EnQueue(SqQueue *Q, Person e);//插入元素e为Q的新的队尾元素Status DeQueue(SqQueue *Q, Person *e);//删除Q的队头元素,用e返回其值Person GetHead(SqQueue Q);//返回Q的队头元素,不修改队头指针Status QueueEmpty(SqQueue Q);//判断队列是否为空,空则返回1void DancePartner(Person dancer[],int num);//舞伴问题匹配算法int main(){Person dancer[MAXSIZE];int i,num;printf("请输入跳舞总人数:");scanf("%d",&num);printf("请输入各个跳舞人的姓名和性别('F'表示女性,'M'表示男性):\n");for(i=0;i<num;i++){printf("请输入第%d个跳舞人的姓名和性别(用空格隔开):",i+1);scanf("%s %c",&dancer[i].name,&dancer[i].sex);}DancePartner(dancer,num);return 0;}Status InitQueue (SqQueue *Q) {//构造一个空队列QQ->base=(Person *)malloc(MAXSIZE*sizeof(Person));//为队列分配一个最大容量为MAXSIZE的数组空间if(!Q->base) exit(OVERFLOW);//存储分配失败Q->front=Q->rear=0;//头指针和尾指针置为零、队列为空return OK;}Status EnQueue(SqQueue *Q, Person e) {//插入元素e为Q的新的队尾元素if ((Q->rear+1)%MAXSIZE==Q->front)//尾指针在循环意义上加1后等于头指针,表明队满return ERROR; Q->base[Q->rear]=e;//新元素插入队尾Q->rear=(Q->rear+1)%MAXSIZE;//队尾指针加1return OK; }Status DeQueue(SqQueue *Q, Person *e) {//删除Q的队头元素,用e返回其值if(Q->front==Q->rear) return ERROR; //队空*e=Q->base[Q->front]; //保存队头元素Q->front=(Q->front+1)%MAXSIZE; //队头指针加1return OK;}Person GetHead(SqQueue Q) {//返回Q的队头元素,不修改队头指针if(Q.front!=Q.rear) //队列非空return Q.base[Q.front]; //返回队头元素的值,队头指针不变}Status QueueEmpty(SqQueue Q){//判断队列是否为空if(Q.front==Q.rear) return OK;//队列空,返回1else return ERROR;//队列不空,返回0}void DancePartner(Person dancer[],int num) {//结构数组dancer中存放跳舞的男女,num是跳舞的人数。SqQueue Mdancers,Fdancers;Person p;int i;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("The dancing partners are:\n"); while(!QueueEmpty(Fdancers)&&!QueueEmpty(Mdancers)) {//依次输出男女舞伴的姓名DeQueue(&Fdancers,&p); //女士出队printf("%s ",p.name);; //输出出队女士姓名DeQueue(&Mdancers,&p); //男士出队printf("%s\n",p.name); //输出出队男士姓名}if (!QueueEmpty(Fdancers)) //女士队列非空,输出队头女士的姓名{p=GetHead(Fdancers); //取女士队头printf("The first woman to get a partner is: %s\n", p.name);}else if (!QueueEmpty (Mdancers)) //男士队列非空,输出队头男士的姓名{p=GetHead(Mdancers); //取男士队头printf("The first man to get a partner is: %s\n", p.name); }}

四、实验总结

栈(stack)和队列(queue)是操作受到限制的线性表:

1.栈是限定仅在表尾进行插入或删除操作的线性表。 因此,对栈来说,表尾端有其特殊含义, 称为栈顶 (top), 相应地, 表头端称为栈底 (bottom)。不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的,因此,栈又称为后进先出(Last In First Out, LIFO) 的线性表。

2.队列和栈相反,队列是一种先进先出(First In First Out, FIFO)的线性表。它只允许在表的一端进行插入,而在另一端删除元素。

如果觉得《舞伴问题(数据结构队列 c语言版)》对你有帮助,请点赞、收藏,并留下你的观点哦!

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。