[C++知识库]PTA 6-3 舞伴问题 (20 分) C语言

?

坑点！！！

1.提交时一定要提交完整的函数，不要只提交DancerPartner函数中的代码

2.当男士或者女士多余的时候，只输出没有配对的队头元素的姓名

3.用FrontQueue_link取出队列的元素后，不要忘记用DeQueue_link删除队列的头元素。

4.当输出配对的舞伴之后，要空一行再输出没有配对的

题目要求

假设男士和女士的记录存放在一个数组中，设计算法实现舞伴配对，要求输出配对的舞伴，并输出没有配对的队头元素的姓名。其中 dancer[]是存放男士和女士信息的数组，num是数组大小。

分析代码

对所给的代码加了注释做解析

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

//结构体存放姓名和性别
typedef struct {
    char name[20];
    char sex;
} DataType;
//链表
struct Node {
    DataType      data;
    struct Node*  next;
};
typedef struct Node  *PNode;
//队列
struct Queue
{
    PNode        f;
    PNode        r;
};
typedef struct Queue *LinkQueue;

//创建一个空队列
LinkQueue  SetNullQueue_Link()
{
    LinkQueue lqueue;
    lqueue = (LinkQueue)malloc(sizeof(struct Queue));
    if (lqueue != NULL)
    {
        lqueue->f = NULL;
        lqueue->r = NULL;
    }
    else
        printf("Alloc failure! \n");//创建失败
    return  lqueue;
}

//队列是否为空
int IsNullQueue_link(LinkQueue lqueue)
{
    return (lqueue->f == NULL);
}

//向队列中添加元素
void EnQueue_link(LinkQueue lqueue, DataType x)
{
    PNode  p;
    p = (PNode)malloc(sizeof(struct Node));
    if (p == NULL)
        printf("Alloc failure!");
    else {
        p->data = x;
        p->next = NULL;
        if (lqueue->f == NULL)
        {
            lqueue->f = p;
            lqueue->r = p;
        }
        else
        {
            lqueue->r->next = p;
            lqueue->r = p;
        }
    }
}

//删除队列的头元素
void DeQueue_link(LinkQueue lqueue)
{
    struct Node  * p;
    //判断是否为空
    if (lqueue->f == NULL)
        printf("It is empty queue!\n ");
    else
    {
        p = lqueue->f;
        lqueue->f = lqueue->f->next;
        free(p);
    }
}

//拿到队列的头元素
DataType  FrontQueue_link(LinkQueue lqueue)
{
    //判断队列是否为空
    if (lqueue->f == NULL)
    {
        printf("It is empty queue!\n");
    }
    else
        return (lqueue->f->data);
}

void DancePartner(DataType dancer[], int num)
{
            /* 请在这里填写答案 */
    
}

int main()
{
    DataType dancer[9];
    for (int i = 0; i < 9; i++)
    scanf("%s %c", dancer[i].name, &dancer[i].sex);
    DancePartner(dancer, 9);
    return 0;
}

答案

解析见注释

void DancePartner(DataType dancer[], int num)
{
            /* 请在这里填写答案 */
    //用来存放性别为M的dancer的队列
    LinkQueue Mdancer=SetNullQueue_Link();
    //用来存放性别为F的dancer的队列
    LinkQueue Fdancer=SetNullQueue_Link();
    //遍历所给的dance数据
    for(int i=0;i<num;i++)
    {
        //如果dance的性别为M，存入队列
        if(dancer[i].sex=='M')
            EnQueue_link(Mdancer,dancer[i]);
        else
        //如果dance的性别为F，存入队列
            EnQueue_link(Fdancer,dancer[i]);

    }
    //如果两个队列中都有元素，将舞伴配对输出
    while(!IsNullQueue_link(Mdancer)&&!IsNullQueue_link(Fdancer))
    {
        DataType d0 = FrontQueue_link(Fdancer);
        DeQueue_link(Fdancer);
        DataType d1 = FrontQueue_link(Mdancer);
        DeQueue_link(Mdancer);
        printf("%s %s\n",d0.name,d1.name);
    }
    
    printf("\n");
    //男士的队列还有剩余，输出队列的头元素
    if(!IsNullQueue_link(Mdancer))
    {
        DataType d0 = FrontQueue_link(Mdancer);
        printf("%s",d0.name);
    }
    //女士的队列含有剩余，输出队列的头元素
    if(!IsNullQueue_link(Fdancer))
    {
        DataType d0 = FrontQueue_link(Fdancer);
        printf("%s",d0.name);
    }
}

点点赞吧~